summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
raw | bz2 | zip | gz |
help

author | Peter Kovacs <kpeter@inf.elte.hu> |

Sun, 23 Aug 2009 11:09:22 +0200 | |

changeset 782 | 853fcddcf282 |

parent 781 | bd72f8d20f33 |

child 783 | 2e20aad15754 |

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

doc/groups.dox | file | annotate | diff | comparison | revisions | |

lemon/full_graph.h | file | annotate | diff | comparison | revisions | |

lemon/grid_graph.h | file | annotate | diff | comparison | revisions | |

lemon/hypercube_graph.h | file | annotate | diff | comparison | revisions | |

lemon/list_graph.h | file | annotate | diff | comparison | revisions | |

lemon/smart_graph.h | file | annotate | diff | comparison | revisions |

1.1 --- a/doc/groups.dox Sun Aug 23 11:07:50 2009 +0200 1.2 +++ b/doc/groups.dox Sun Aug 23 11:09:22 2009 +0200 1.3 @@ -636,8 +636,8 @@ 1.4 @ingroup concept 1.5 \brief Skeleton and concept checking classes for graph structures 1.6 1.7 -This group contains the skeletons and concept checking classes of LEMON's 1.8 -graph structures and helper classes used to implement these. 1.9 +This group contains the skeletons and concept checking classes of 1.10 +graph structures. 1.11 */ 1.12 1.13 /**

2.1 --- a/lemon/full_graph.h Sun Aug 23 11:07:50 2009 +0200 2.2 +++ b/lemon/full_graph.h Sun Aug 23 11:09:22 2009 +0200 2.3 @@ -24,7 +24,7 @@ 2.4 2.5 ///\ingroup graphs 2.6 ///\file 2.7 -///\brief FullGraph and FullDigraph classes. 2.8 +///\brief FullDigraph and FullGraph classes. 2.9 2.10 namespace lemon { 2.11 2.12 @@ -148,24 +148,26 @@ 2.13 2.14 /// \ingroup graphs 2.15 /// 2.16 - /// \brief A full digraph class. 2.17 + /// \brief A directed full graph class. 2.18 /// 2.19 - /// This is a simple and fast directed full graph implementation. 2.20 - /// From each node go arcs to each node (including the source node), 2.21 - /// therefore the number of the arcs in the digraph is the square of 2.22 - /// the node number. This digraph type is completely static, so you 2.23 - /// can neither add nor delete either arcs or nodes, and it needs 2.24 - /// constant space in memory. 2.25 + /// FullDigraph is a simple and fast implmenetation of directed full 2.26 + /// (complete) graphs. It contains an arc from each node to each node 2.27 + /// (including a loop for each node), therefore the number of arcs 2.28 + /// is the square of the number of nodes. 2.29 + /// This class is completely static and it needs constant memory space. 2.30 + /// Thus you can neither add nor delete nodes or arcs, however 2.31 + /// the structure can be resized using resize(). 2.32 /// 2.33 - /// This class fully conforms to the \ref concepts::Digraph 2.34 - /// "Digraph concept". 2.35 + /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". 2.36 + /// Most of its member functions and nested classes are documented 2.37 + /// only in the concept class. 2.38 /// 2.39 - /// The \c FullDigraph and \c FullGraph classes are very similar, 2.40 + /// \note FullDigraph and FullGraph classes are very similar, 2.41 /// but there are two differences. While this class conforms only 2.42 - /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph 2.43 - /// class conforms to the \ref concepts::Graph "Graph" concept, 2.44 - /// moreover \c FullGraph does not contain a loop arc for each 2.45 - /// node as \c FullDigraph does. 2.46 + /// to the \ref concepts::Digraph "Digraph" concept, FullGraph 2.47 + /// conforms to the \ref concepts::Graph "Graph" concept, 2.48 + /// moreover FullGraph does not contain a loop for each 2.49 + /// node as this class does. 2.50 /// 2.51 /// \sa FullGraph 2.52 class FullDigraph : public ExtendedFullDigraphBase { 2.53 @@ -173,7 +175,9 @@ 2.54 2.55 public: 2.56 2.57 - /// \brief Constructor 2.58 + /// \brief Default constructor. 2.59 + /// 2.60 + /// Default constructor. The number of nodes and arcs will be zero. 2.61 FullDigraph() { construct(0); } 2.62 2.63 /// \brief Constructor 2.64 @@ -184,8 +188,8 @@ 2.65 2.66 /// \brief Resizes the digraph 2.67 /// 2.68 - /// Resizes the digraph. The function will fully destroy and 2.69 - /// rebuild the digraph. This cause that the maps of the digraph will 2.70 + /// This function resizes the digraph. It fully destroys and 2.71 + /// rebuilds the structure, therefore the maps of the digraph will be 2.72 /// reallocated automatically and the previous values will be lost. 2.73 void resize(int n) { 2.74 Parent::notifier(Arc()).clear(); 2.75 @@ -197,24 +201,24 @@ 2.76 2.77 /// \brief Returns the node with the given index. 2.78 /// 2.79 - /// Returns the node with the given index. Since it is a static 2.80 - /// digraph its nodes can be indexed with integers from the range 2.81 - /// <tt>[0..nodeNum()-1]</tt>. 2.82 + /// Returns the node with the given index. Since this structure is 2.83 + /// completely static, the nodes can be indexed with integers from 2.84 + /// the range <tt>[0..nodeNum()-1]</tt>. 2.85 /// \sa index() 2.86 Node operator()(int ix) const { return Parent::operator()(ix); } 2.87 2.88 /// \brief Returns the index of the given node. 2.89 /// 2.90 - /// Returns the index of the given node. Since it is a static 2.91 - /// digraph its nodes can be indexed with integers from the range 2.92 - /// <tt>[0..nodeNum()-1]</tt>. 2.93 - /// \sa operator() 2.94 - int index(const Node& node) const { return Parent::index(node); } 2.95 + /// Returns the index of the given node. Since this structure is 2.96 + /// completely static, the nodes can be indexed with integers from 2.97 + /// the range <tt>[0..nodeNum()-1]</tt>. 2.98 + /// \sa operator()() 2.99 + int index(Node node) const { return Parent::index(node); } 2.100 2.101 /// \brief Returns the arc connecting the given nodes. 2.102 /// 2.103 /// Returns the arc connecting the given nodes. 2.104 - Arc arc(const Node& u, const Node& v) const { 2.105 + Arc arc(Node u, Node v) const { 2.106 return Parent::arc(u, v); 2.107 } 2.108 2.109 @@ -520,21 +524,23 @@ 2.110 /// 2.111 /// \brief An undirected full graph class. 2.112 /// 2.113 - /// This is a simple and fast undirected full graph 2.114 - /// implementation. From each node go edge to each other node, 2.115 - /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. 2.116 - /// This graph type is completely static, so you can neither 2.117 - /// add nor delete either edges or nodes, and it needs constant 2.118 - /// space in memory. 2.119 + /// FullGraph is a simple and fast implmenetation of undirected full 2.120 + /// (complete) graphs. It contains an edge between every distinct pair 2.121 + /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>. 2.122 + /// This class is completely static and it needs constant memory space. 2.123 + /// Thus you can neither add nor delete nodes or edges, however 2.124 + /// the structure can be resized using resize(). 2.125 /// 2.126 - /// This class fully conforms to the \ref concepts::Graph "Graph concept". 2.127 + /// This type fully conforms to the \ref concepts::Graph "Graph concept". 2.128 + /// Most of its member functions and nested classes are documented 2.129 + /// only in the concept class. 2.130 /// 2.131 - /// The \c FullGraph and \c FullDigraph classes are very similar, 2.132 - /// but there are two differences. While the \c FullDigraph class 2.133 + /// \note FullDigraph and FullGraph classes are very similar, 2.134 + /// but there are two differences. While FullDigraph 2.135 /// conforms only to the \ref concepts::Digraph "Digraph" concept, 2.136 /// this class conforms to the \ref concepts::Graph "Graph" concept, 2.137 - /// moreover \c FullGraph does not contain a loop arc for each 2.138 - /// node as \c FullDigraph does. 2.139 + /// moreover this class does not contain a loop for each 2.140 + /// node as FullDigraph does. 2.141 /// 2.142 /// \sa FullDigraph 2.143 class FullGraph : public ExtendedFullGraphBase { 2.144 @@ -542,7 +548,9 @@ 2.145 2.146 public: 2.147 2.148 - /// \brief Constructor 2.149 + /// \brief Default constructor. 2.150 + /// 2.151 + /// Default constructor. The number of nodes and edges will be zero. 2.152 FullGraph() { construct(0); } 2.153 2.154 /// \brief Constructor 2.155 @@ -553,8 +561,8 @@ 2.156 2.157 /// \brief Resizes the graph 2.158 /// 2.159 - /// Resizes the graph. The function will fully destroy and 2.160 - /// rebuild the graph. This cause that the maps of the graph will 2.161 + /// This function resizes the graph. It fully destroys and 2.162 + /// rebuilds the structure, therefore the maps of the graph will be 2.163 /// reallocated automatically and the previous values will be lost. 2.164 void resize(int n) { 2.165 Parent::notifier(Arc()).clear(); 2.166 @@ -568,31 +576,31 @@ 2.167 2.168 /// \brief Returns the node with the given index. 2.169 /// 2.170 - /// Returns the node with the given index. Since it is a static 2.171 - /// graph its nodes can be indexed with integers from the range 2.172 - /// <tt>[0..nodeNum()-1]</tt>. 2.173 + /// Returns the node with the given index. Since this structure is 2.174 + /// completely static, the nodes can be indexed with integers from 2.175 + /// the range <tt>[0..nodeNum()-1]</tt>. 2.176 /// \sa index() 2.177 Node operator()(int ix) const { return Parent::operator()(ix); } 2.178 2.179 /// \brief Returns the index of the given node. 2.180 /// 2.181 - /// Returns the index of the given node. Since it is a static 2.182 - /// graph its nodes can be indexed with integers from the range 2.183 - /// <tt>[0..nodeNum()-1]</tt>. 2.184 - /// \sa operator() 2.185 - int index(const Node& node) const { return Parent::index(node); } 2.186 + /// Returns the index of the given node. Since this structure is 2.187 + /// completely static, the nodes can be indexed with integers from 2.188 + /// the range <tt>[0..nodeNum()-1]</tt>. 2.189 + /// \sa operator()() 2.190 + int index(Node node) const { return Parent::index(node); } 2.191 2.192 /// \brief Returns the arc connecting the given nodes. 2.193 /// 2.194 /// Returns the arc connecting the given nodes. 2.195 - Arc arc(const Node& s, const Node& t) const { 2.196 + Arc arc(Node s, Node t) const { 2.197 return Parent::arc(s, t); 2.198 } 2.199 2.200 - /// \brief Returns the edge connects the given nodes. 2.201 + /// \brief Returns the edge connecting the given nodes. 2.202 /// 2.203 - /// Returns the edge connects the given nodes. 2.204 - Edge edge(const Node& u, const Node& v) const { 2.205 + /// Returns the edge connecting the given nodes. 2.206 + Edge edge(Node u, Node v) const { 2.207 return Parent::edge(u, v); 2.208 } 2.209

3.1 --- a/lemon/grid_graph.h Sun Aug 23 11:07:50 2009 +0200 3.2 +++ b/lemon/grid_graph.h Sun Aug 23 11:09:22 2009 +0200 3.3 @@ -470,18 +470,22 @@ 3.4 /// 3.5 /// \brief Grid graph class 3.6 /// 3.7 - /// This class implements a special graph type. The nodes of the 3.8 - /// graph can be indexed by two integer \c (i,j) value where \c i is 3.9 - /// in the \c [0..width()-1] range and j is in the \c 3.10 - /// [0..height()-1] range. Two nodes are connected in the graph if 3.11 - /// the indexes differ exactly on one position and exactly one is 3.12 - /// the difference. The nodes of the graph can be indexed by position 3.13 - /// with the \c operator()() function. The positions of the nodes can be 3.14 - /// get with \c pos(), \c col() and \c row() members. The outgoing 3.15 + /// GridGraph implements a special graph type. The nodes of the 3.16 + /// graph can be indexed by two integer values \c (i,j) where \c i is 3.17 + /// in the range <tt>[0..width()-1]</tt> and j is in the range 3.18 + /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if 3.19 + /// the indices differ exactly on one position and the difference is 3.20 + /// also exactly one. The nodes of the graph can be obtained by position 3.21 + /// using the \c operator()() function and the indices of the nodes can 3.22 + /// be obtained using \c pos(), \c col() and \c row() members. The outgoing 3.23 /// arcs can be retrieved with the \c right(), \c up(), \c left() 3.24 /// and \c down() functions, where the bottom-left corner is the 3.25 /// origin. 3.26 /// 3.27 + /// This class is completely static and it needs constant memory space. 3.28 + /// Thus you can neither add nor delete nodes or edges, however 3.29 + /// the structure can be resized using resize(). 3.30 + /// 3.31 /// \image html grid_graph.png 3.32 /// \image latex grid_graph.eps "Grid graph" width=\textwidth 3.33 /// 3.34 @@ -496,16 +500,19 @@ 3.35 /// } 3.36 ///\endcode 3.37 /// 3.38 - /// This graph type fully conforms to the \ref concepts::Graph 3.39 - /// "Graph concept". 3.40 + /// This type fully conforms to the \ref concepts::Graph "Graph concept". 3.41 + /// Most of its member functions and nested classes are documented 3.42 + /// only in the concept class. 3.43 class GridGraph : public ExtendedGridGraphBase { 3.44 typedef ExtendedGridGraphBase Parent; 3.45 3.46 public: 3.47 3.48 - /// \brief Map to get the indices of the nodes as dim2::Point<int>. 3.49 + /// \brief Map to get the indices of the nodes as \ref dim2::Point 3.50 + /// "dim2::Point<int>". 3.51 /// 3.52 - /// Map to get the indices of the nodes as dim2::Point<int>. 3.53 + /// Map to get the indices of the nodes as \ref dim2::Point 3.54 + /// "dim2::Point<int>". 3.55 class IndexMap { 3.56 public: 3.57 /// \brief The key type of the map 3.58 @@ -514,13 +521,9 @@ 3.59 typedef dim2::Point<int> Value; 3.60 3.61 /// \brief Constructor 3.62 - /// 3.63 - /// Constructor 3.64 IndexMap(const GridGraph& graph) : _graph(graph) {} 3.65 3.66 /// \brief The subscript operator 3.67 - /// 3.68 - /// The subscript operator. 3.69 Value operator[](Key key) const { 3.70 return _graph.pos(key); 3.71 } 3.72 @@ -540,13 +543,9 @@ 3.73 typedef int Value; 3.74 3.75 /// \brief Constructor 3.76 - /// 3.77 - /// Constructor 3.78 ColMap(const GridGraph& graph) : _graph(graph) {} 3.79 3.80 /// \brief The subscript operator 3.81 - /// 3.82 - /// The subscript operator. 3.83 Value operator[](Key key) const { 3.84 return _graph.col(key); 3.85 } 3.86 @@ -566,13 +565,9 @@ 3.87 typedef int Value; 3.88 3.89 /// \brief Constructor 3.90 - /// 3.91 - /// Constructor 3.92 RowMap(const GridGraph& graph) : _graph(graph) {} 3.93 3.94 /// \brief The subscript operator 3.95 - /// 3.96 - /// The subscript operator. 3.97 Value operator[](Key key) const { 3.98 return _graph.row(key); 3.99 } 3.100 @@ -583,15 +578,14 @@ 3.101 3.102 /// \brief Constructor 3.103 /// 3.104 - /// Construct a grid graph with given size. 3.105 + /// Construct a grid graph with the given size. 3.106 GridGraph(int width, int height) { construct(width, height); } 3.107 3.108 - /// \brief Resize the graph 3.109 + /// \brief Resizes the graph 3.110 /// 3.111 - /// Resize the graph. The function will fully destroy and rebuild 3.112 - /// the graph. This cause that the maps of the graph will 3.113 - /// reallocated automatically and the previous values will be 3.114 - /// lost. 3.115 + /// This function resizes the graph. It fully destroys and 3.116 + /// rebuilds the structure, therefore the maps of the graph will be 3.117 + /// reallocated automatically and the previous values will be lost. 3.118 void resize(int width, int height) { 3.119 Parent::notifier(Arc()).clear(); 3.120 Parent::notifier(Edge()).clear(); 3.121 @@ -609,42 +603,42 @@ 3.122 return Parent::operator()(i, j); 3.123 } 3.124 3.125 - /// \brief Gives back the column index of the node. 3.126 + /// \brief The column index of the node. 3.127 /// 3.128 /// Gives back the column index of the node. 3.129 int col(Node n) const { 3.130 return Parent::col(n); 3.131 } 3.132 3.133 - /// \brief Gives back the row index of the node. 3.134 + /// \brief The row index of the node. 3.135 /// 3.136 /// Gives back the row index of the node. 3.137 int row(Node n) const { 3.138 return Parent::row(n); 3.139 } 3.140 3.141 - /// \brief Gives back the position of the node. 3.142 + /// \brief The position of the node. 3.143 /// 3.144 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. 3.145 dim2::Point<int> pos(Node n) const { 3.146 return Parent::pos(n); 3.147 } 3.148 3.149 - /// \brief Gives back the number of the columns. 3.150 + /// \brief The number of the columns. 3.151 /// 3.152 /// Gives back the number of the columns. 3.153 int width() const { 3.154 return Parent::width(); 3.155 } 3.156 3.157 - /// \brief Gives back the number of the rows. 3.158 + /// \brief The number of the rows. 3.159 /// 3.160 /// Gives back the number of the rows. 3.161 int height() const { 3.162 return Parent::height(); 3.163 } 3.164 3.165 - /// \brief Gives back the arc goes right from the node. 3.166 + /// \brief The arc goes right from the node. 3.167 /// 3.168 /// Gives back the arc goes right from the node. If there is not 3.169 /// outgoing arc then it gives back INVALID. 3.170 @@ -652,7 +646,7 @@ 3.171 return Parent::right(n); 3.172 } 3.173 3.174 - /// \brief Gives back the arc goes left from the node. 3.175 + /// \brief The arc goes left from the node. 3.176 /// 3.177 /// Gives back the arc goes left from the node. If there is not 3.178 /// outgoing arc then it gives back INVALID. 3.179 @@ -660,7 +654,7 @@ 3.180 return Parent::left(n); 3.181 } 3.182 3.183 - /// \brief Gives back the arc goes up from the node. 3.184 + /// \brief The arc goes up from the node. 3.185 /// 3.186 /// Gives back the arc goes up from the node. If there is not 3.187 /// outgoing arc then it gives back INVALID. 3.188 @@ -668,7 +662,7 @@ 3.189 return Parent::up(n); 3.190 } 3.191 3.192 - /// \brief Gives back the arc goes down from the node. 3.193 + /// \brief The arc goes down from the node. 3.194 /// 3.195 /// Gives back the arc goes down from the node. If there is not 3.196 /// outgoing arc then it gives back INVALID.

4.1 --- a/lemon/hypercube_graph.h Sun Aug 23 11:07:50 2009 +0200 4.2 +++ b/lemon/hypercube_graph.h Sun Aug 23 11:09:22 2009 +0200 4.3 @@ -282,17 +282,20 @@ 4.4 /// 4.5 /// \brief Hypercube graph class 4.6 /// 4.7 - /// This class implements a special graph type. The nodes of the graph 4.8 - /// are indiced with integers with at most \c dim binary digits. 4.9 + /// HypercubeGraph implements a special graph type. The nodes of the 4.10 + /// graph are indexed with integers having at most \c dim binary digits. 4.11 /// Two nodes are connected in the graph if and only if their indices 4.12 /// differ only on one position in the binary form. 4.13 + /// This class is completely static and it needs constant memory space. 4.14 + /// Thus you can neither add nor delete nodes or edges. 4.15 + /// 4.16 + /// This type fully conforms to the \ref concepts::Graph "Graph concept". 4.17 + /// Most of its member functions and nested classes are documented 4.18 + /// only in the concept class. 4.19 /// 4.20 /// \note The type of the indices is chosen to \c int for efficiency 4.21 /// reasons. Thus the maximum dimension of this implementation is 26 4.22 /// (assuming that the size of \c int is 32 bit). 4.23 - /// 4.24 - /// This graph type fully conforms to the \ref concepts::Graph 4.25 - /// "Graph concept". 4.26 class HypercubeGraph : public ExtendedHypercubeGraphBase { 4.27 typedef ExtendedHypercubeGraphBase Parent; 4.28 4.29 @@ -320,7 +323,7 @@ 4.30 /// \brief The dimension id of an edge. 4.31 /// 4.32 /// Gives back the dimension id of the given edge. 4.33 - /// It is in the [0..dim-1] range. 4.34 + /// It is in the range <tt>[0..dim-1]</tt>. 4.35 int dimension(Edge edge) const { 4.36 return Parent::dimension(edge); 4.37 } 4.38 @@ -328,7 +331,7 @@ 4.39 /// \brief The dimension id of an arc. 4.40 /// 4.41 /// Gives back the dimension id of the given arc. 4.42 - /// It is in the [0..dim-1] range. 4.43 + /// It is in the range <tt>[0..dim-1]</tt>. 4.44 int dimension(Arc arc) const { 4.45 return Parent::dimension(arc); 4.46 }

5.1 --- a/lemon/list_graph.h Sun Aug 23 11:07:50 2009 +0200 5.2 +++ b/lemon/list_graph.h Sun Aug 23 11:09:22 2009 +0200 5.3 @@ -21,7 +21,7 @@ 5.4 5.5 ///\ingroup graphs 5.6 ///\file 5.7 -///\brief ListDigraph, ListGraph classes. 5.8 +///\brief ListDigraph and ListGraph classes. 5.9 5.10 #include <lemon/core.h> 5.11 #include <lemon/error.h> 5.12 @@ -311,31 +311,25 @@ 5.13 5.14 ///A general directed graph structure. 5.15 5.16 - ///\ref ListDigraph is a simple and fast <em>directed graph</em> 5.17 - ///implementation based on static linked lists that are stored in 5.18 + ///\ref ListDigraph is a versatile and fast directed graph 5.19 + ///implementation based on linked lists that are stored in 5.20 ///\c std::vector structures. 5.21 /// 5.22 - ///It conforms to the \ref concepts::Digraph "Digraph concept" and it 5.23 - ///also provides several useful additional functionalities. 5.24 - ///Most of the member functions and nested classes are documented 5.25 + ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 5.26 + ///and it also provides several useful additional functionalities. 5.27 + ///Most of its member functions and nested classes are documented 5.28 ///only in the concept class. 5.29 /// 5.30 ///\sa concepts::Digraph 5.31 - 5.32 + ///\sa ListGraph 5.33 class ListDigraph : public ExtendedListDigraphBase { 5.34 typedef ExtendedListDigraphBase Parent; 5.35 5.36 private: 5.37 - ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 5.38 - 5.39 - ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 5.40 - /// 5.41 + /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 5.42 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; 5.43 - ///\brief Assignment of ListDigraph to another one is \e not allowed. 5.44 - ///Use copyDigraph() instead. 5.45 - 5.46 - ///Assignment of ListDigraph to another one is \e not allowed. 5.47 - ///Use copyDigraph() instead. 5.48 + /// \brief Assignment of a digraph to another one is \e not allowed. 5.49 + /// Use DigraphCopy instead. 5.50 void operator=(const ListDigraph &) {} 5.51 public: 5.52 5.53 @@ -347,71 +341,65 @@ 5.54 5.55 ///Add a new node to the digraph. 5.56 5.57 - ///Add a new node to the digraph. 5.58 + ///This function adds a new node to the digraph. 5.59 ///\return The new node. 5.60 Node addNode() { return Parent::addNode(); } 5.61 5.62 ///Add a new arc to the digraph. 5.63 5.64 - ///Add a new arc to the digraph with source node \c s 5.65 + ///This function adds a new arc to the digraph with source node \c s 5.66 ///and target node \c t. 5.67 ///\return The new arc. 5.68 - Arc addArc(const Node& s, const Node& t) { 5.69 + Arc addArc(Node s, Node t) { 5.70 return Parent::addArc(s, t); 5.71 } 5.72 5.73 ///\brief Erase a node from the digraph. 5.74 /// 5.75 - ///Erase a node from the digraph. 5.76 - /// 5.77 - void erase(const Node& n) { Parent::erase(n); } 5.78 + ///This function erases the given node from the digraph. 5.79 + void erase(Node n) { Parent::erase(n); } 5.80 5.81 ///\brief Erase an arc from the digraph. 5.82 /// 5.83 - ///Erase an arc from the digraph. 5.84 - /// 5.85 - void erase(const Arc& a) { Parent::erase(a); } 5.86 + ///This function erases the given arc from the digraph. 5.87 + void erase(Arc a) { Parent::erase(a); } 5.88 5.89 /// Node validity check 5.90 5.91 - /// This function gives back true if the given node is valid, 5.92 - /// ie. it is a real node of the graph. 5.93 + /// This function gives back \c true if the given node is valid, 5.94 + /// i.e. it is a real node of the digraph. 5.95 /// 5.96 - /// \warning A Node pointing to a removed item 5.97 - /// could become valid again later if new nodes are 5.98 - /// added to the graph. 5.99 + /// \warning A removed node could become valid again if new nodes are 5.100 + /// added to the digraph. 5.101 bool valid(Node n) const { return Parent::valid(n); } 5.102 5.103 /// Arc validity check 5.104 5.105 - /// This function gives back true if the given arc is valid, 5.106 - /// ie. it is a real arc of the graph. 5.107 + /// This function gives back \c true if the given arc is valid, 5.108 + /// i.e. it is a real arc of the digraph. 5.109 /// 5.110 - /// \warning An Arc pointing to a removed item 5.111 - /// could become valid again later if new nodes are 5.112 - /// added to the graph. 5.113 + /// \warning A removed arc could become valid again if new arcs are 5.114 + /// added to the digraph. 5.115 bool valid(Arc a) const { return Parent::valid(a); } 5.116 5.117 - /// Change the target of \c a to \c n 5.118 + /// Change the target node of an arc 5.119 5.120 - /// Change the target of \c a to \c n 5.121 + /// This function changes the target node of the given arc \c a to \c n. 5.122 /// 5.123 - ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing 5.124 - ///the changed arc remain valid. However <tt>InArcIt</tt>s are 5.125 - ///invalidated. 5.126 + ///\note \c ArcIt and \c OutArcIt iterators referencing the changed 5.127 + ///arc remain valid, however \c InArcIt iterators are invalidated. 5.128 /// 5.129 ///\warning This functionality cannot be used together with the Snapshot 5.130 ///feature. 5.131 void changeTarget(Arc a, Node n) { 5.132 Parent::changeTarget(a,n); 5.133 } 5.134 - /// Change the source of \c a to \c n 5.135 + /// Change the source node of an arc 5.136 5.137 - /// Change the source of \c a to \c n 5.138 + /// This function changes the source node of the given arc \c a to \c n. 5.139 /// 5.140 - ///\note The <tt>InArcIt</tt>s referencing the changed arc remain 5.141 - ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are 5.142 - ///invalidated. 5.143 + ///\note \c InArcIt iterators referencing the changed arc remain 5.144 + ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated. 5.145 /// 5.146 ///\warning This functionality cannot be used together with the Snapshot 5.147 ///feature. 5.148 @@ -419,86 +407,70 @@ 5.149 Parent::changeSource(a,n); 5.150 } 5.151 5.152 - /// Invert the direction of an arc. 5.153 + /// Reverse the direction of an arc. 5.154 5.155 - ///\note The <tt>ArcIt</tt>s referencing the changed arc remain 5.156 - ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are 5.157 - ///invalidated. 5.158 + /// This function reverses the direction of the given arc. 5.159 + ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing 5.160 + ///the changed arc are invalidated. 5.161 /// 5.162 ///\warning This functionality cannot be used together with the Snapshot 5.163 ///feature. 5.164 - void reverseArc(Arc e) { 5.165 - Node t=target(e); 5.166 - changeTarget(e,source(e)); 5.167 - changeSource(e,t); 5.168 + void reverseArc(Arc a) { 5.169 + Node t=target(a); 5.170 + changeTarget(a,source(a)); 5.171 + changeSource(a,t); 5.172 } 5.173 5.174 - /// Reserve memory for nodes. 5.175 - 5.176 - /// Using this function it is possible to avoid the superfluous memory 5.177 - /// allocation: if you know that the digraph you want to build will 5.178 - /// be very large (e.g. it will contain millions of nodes and/or arcs) 5.179 - /// then it is worth reserving space for this amount before starting 5.180 - /// to build the digraph. 5.181 - /// \sa reserveArc 5.182 - void reserveNode(int n) { nodes.reserve(n); }; 5.183 - 5.184 - /// Reserve memory for arcs. 5.185 - 5.186 - /// Using this function it is possible to avoid the superfluous memory 5.187 - /// allocation: if you know that the digraph you want to build will 5.188 - /// be very large (e.g. it will contain millions of nodes and/or arcs) 5.189 - /// then it is worth reserving space for this amount before starting 5.190 - /// to build the digraph. 5.191 - /// \sa reserveNode 5.192 - void reserveArc(int m) { arcs.reserve(m); }; 5.193 - 5.194 ///Contract two nodes. 5.195 5.196 - ///This function contracts two nodes. 5.197 - ///Node \p b will be removed but instead of deleting 5.198 - ///incident arcs, they will be joined to \p a. 5.199 - ///The last parameter \p r controls whether to remove loops. \c true 5.200 - ///means that loops will be removed. 5.201 + ///This function contracts the given two nodes. 5.202 + ///Node \c v is removed, but instead of deleting its 5.203 + ///incident arcs, they are joined to node \c u. 5.204 + ///If the last parameter \c r is \c true (this is the default value), 5.205 + ///then the newly created loops are removed. 5.206 /// 5.207 - ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 5.208 - ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s 5.209 - ///may be invalidated. 5.210 + ///\note The moved arcs are joined to node \c u using changeSource() 5.211 + ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are 5.212 + ///invalidated for the outgoing arcs of node \c v and \c InArcIt 5.213 + ///iterators are invalidated for the incomming arcs of \c v. 5.214 + ///Moreover all iterators referencing node \c v or the removed 5.215 + ///loops are also invalidated. Other iterators remain valid. 5.216 /// 5.217 ///\warning This functionality cannot be used together with the Snapshot 5.218 ///feature. 5.219 - void contract(Node a, Node b, bool r = true) 5.220 + void contract(Node u, Node v, bool r = true) 5.221 { 5.222 - for(OutArcIt e(*this,b);e!=INVALID;) { 5.223 + for(OutArcIt e(*this,v);e!=INVALID;) { 5.224 OutArcIt f=e; 5.225 ++f; 5.226 - if(r && target(e)==a) erase(e); 5.227 - else changeSource(e,a); 5.228 + if(r && target(e)==u) erase(e); 5.229 + else changeSource(e,u); 5.230 e=f; 5.231 } 5.232 - for(InArcIt e(*this,b);e!=INVALID;) { 5.233 + for(InArcIt e(*this,v);e!=INVALID;) { 5.234 InArcIt f=e; 5.235 ++f; 5.236 - if(r && source(e)==a) erase(e); 5.237 - else changeTarget(e,a); 5.238 + if(r && source(e)==u) erase(e); 5.239 + else changeTarget(e,u); 5.240 e=f; 5.241 } 5.242 - erase(b); 5.243 + erase(v); 5.244 } 5.245 5.246 ///Split a node. 5.247 5.248 - ///This function splits a node. First a new node is added to the digraph, 5.249 - ///then the source of each outgoing arc of \c n is moved to this new node. 5.250 - ///If \c connect is \c true (this is the default value), then a new arc 5.251 - ///from \c n to the newly created node is also added. 5.252 + ///This function splits the given node. First, a new node is added 5.253 + ///to the digraph, then the source of each outgoing arc of node \c n 5.254 + ///is moved to this new node. 5.255 + ///If the second parameter \c connect is \c true (this is the default 5.256 + ///value), then a new arc from node \c n to the newly created node 5.257 + ///is also added. 5.258 ///\return The newly created node. 5.259 /// 5.260 - ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 5.261 - ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may 5.262 - ///be invalidated. 5.263 + ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing 5.264 + ///arcs of node \c n are invalidated. Other iterators remain valid. 5.265 /// 5.266 - ///\warning This functionality cannot be used in conjunction with the 5.267 + ///\warning This functionality cannot be used together with the 5.268 ///Snapshot feature. 5.269 Node split(Node n, bool connect = true) { 5.270 Node b = addNode(); 5.271 @@ -514,21 +486,52 @@ 5.272 5.273 ///Split an arc. 5.274 5.275 - ///This function splits an arc. First a new node \c b is added to 5.276 - ///the digraph, then the original arc is re-targeted to \c 5.277 - ///b. Finally an arc from \c b to the original target is added. 5.278 + ///This function splits the given arc. First, a new node \c v is 5.279 + ///added to the digraph, then the target node of the original arc 5.280 + ///is set to \c v. Finally, an arc from \c v to the original target 5.281 + ///is added. 5.282 + ///\return The newly created node. 5.283 /// 5.284 - ///\return The newly created node. 5.285 + ///\note \c InArcIt iterators referencing the original arc are 5.286 + ///invalidated. Other iterators remain valid. 5.287 /// 5.288 ///\warning This functionality cannot be used together with the 5.289 ///Snapshot feature. 5.290 - Node split(Arc e) { 5.291 - Node b = addNode(); 5.292 - addArc(b,target(e)); 5.293 - changeTarget(e,b); 5.294 - return b; 5.295 + Node split(Arc a) { 5.296 + Node v = addNode(); 5.297 + addArc(v,target(a)); 5.298 + changeTarget(a,v); 5.299 + return v; 5.300 } 5.301 5.302 + ///Clear the digraph. 5.303 + 5.304 + ///This function erases all nodes and arcs from the digraph. 5.305 + /// 5.306 + void clear() { 5.307 + Parent::clear(); 5.308 + } 5.309 + 5.310 + /// Reserve memory for nodes. 5.311 + 5.312 + /// Using this function, it is possible to avoid superfluous memory 5.313 + /// allocation: if you know that the digraph you want to build will 5.314 + /// be large (e.g. it will contain millions of nodes and/or arcs), 5.315 + /// then it is worth reserving space for this amount before starting 5.316 + /// to build the digraph. 5.317 + /// \sa reserveArc() 5.318 + void reserveNode(int n) { nodes.reserve(n); }; 5.319 + 5.320 + /// Reserve memory for arcs. 5.321 + 5.322 + /// Using this function, it is possible to avoid superfluous memory 5.323 + /// allocation: if you know that the digraph you want to build will 5.324 + /// be large (e.g. it will contain millions of nodes and/or arcs), 5.325 + /// then it is worth reserving space for this amount before starting 5.326 + /// to build the digraph. 5.327 + /// \sa reserveNode() 5.328 + void reserveArc(int m) { arcs.reserve(m); }; 5.329 + 5.330 /// \brief Class to make a snapshot of the digraph and restore 5.331 /// it later. 5.332 /// 5.333 @@ -537,9 +540,15 @@ 5.334 /// The newly added nodes and arcs can be removed using the 5.335 /// restore() function. 5.336 /// 5.337 - /// \warning Arc and node deletions and other modifications (e.g. 5.338 - /// contracting, splitting, reversing arcs or nodes) cannot be 5.339 + /// \note After a state is restored, you cannot restore a later state, 5.340 + /// i.e. you cannot add the removed nodes and arcs again using 5.341 + /// another Snapshot instance. 5.342 + /// 5.343 + /// \warning Node and arc deletions and other modifications (e.g. 5.344 + /// reversing, contracting, splitting arcs or nodes) cannot be 5.345 /// restored. These events invalidate the snapshot. 5.346 + /// However the arcs and nodes that were added to the digraph after 5.347 + /// making the current snapshot can be removed without invalidating it. 5.348 class Snapshot { 5.349 protected: 5.350 5.351 @@ -709,39 +718,37 @@ 5.352 /// \brief Default constructor. 5.353 /// 5.354 /// Default constructor. 5.355 - /// To actually make a snapshot you must call save(). 5.356 + /// You have to call save() to actually make a snapshot. 5.357 Snapshot() 5.358 : digraph(0), node_observer_proxy(*this), 5.359 arc_observer_proxy(*this) {} 5.360 5.361 /// \brief Constructor that immediately makes a snapshot. 5.362 /// 5.363 - /// This constructor immediately makes a snapshot of the digraph. 5.364 - /// \param _digraph The digraph we make a snapshot of. 5.365 - Snapshot(ListDigraph &_digraph) 5.366 + /// This constructor immediately makes a snapshot of the given digraph. 5.367 + Snapshot(ListDigraph &gr) 5.368 : node_observer_proxy(*this), 5.369 arc_observer_proxy(*this) { 5.370 - attach(_digraph); 5.371 + attach(gr); 5.372 } 5.373 5.374 /// \brief Make a snapshot. 5.375 /// 5.376 - /// Make a snapshot of the digraph. 5.377 - /// 5.378 - /// This function can be called more than once. In case of a repeated 5.379 + /// This function makes a snapshot of the given digraph. 5.380 + /// It can be called more than once. In case of a repeated 5.381 /// call, the previous snapshot gets lost. 5.382 - /// \param _digraph The digraph we make the snapshot of. 5.383 - void save(ListDigraph &_digraph) { 5.384 + void save(ListDigraph &gr) { 5.385 if (attached()) { 5.386 detach(); 5.387 clear(); 5.388 } 5.389 - attach(_digraph); 5.390 + attach(gr); 5.391 } 5.392 5.393 /// \brief Undo the changes until the last snapshot. 5.394 - // 5.395 - /// Undo the changes until the last snapshot created by save(). 5.396 + /// 5.397 + /// This function undos the changes until the last snapshot 5.398 + /// created by save() or Snapshot(ListDigraph&). 5.399 void restore() { 5.400 detach(); 5.401 for(std::list<Arc>::iterator it = added_arcs.begin(); 5.402 @@ -755,9 +762,9 @@ 5.403 clear(); 5.404 } 5.405 5.406 - /// \brief Gives back true when the snapshot is valid. 5.407 + /// \brief Returns \c true if the snapshot is valid. 5.408 /// 5.409 - /// Gives back true when the snapshot is valid. 5.410 + /// This function returns \c true if the snapshot is valid. 5.411 bool valid() const { 5.412 return attached(); 5.413 } 5.414 @@ -795,10 +802,6 @@ 5.415 5.416 typedef ListGraphBase Graph; 5.417 5.418 - class Node; 5.419 - class Arc; 5.420 - class Edge; 5.421 - 5.422 class Node { 5.423 friend class ListGraphBase; 5.424 protected: 5.425 @@ -848,8 +851,6 @@ 5.426 bool operator<(const Arc& arc) const {return id < arc.id;} 5.427 }; 5.428 5.429 - 5.430 - 5.431 ListGraphBase() 5.432 : nodes(), first_node(-1), 5.433 first_free_node(-1), arcs(), first_free_arc(-1) {} 5.434 @@ -1164,31 +1165,25 @@ 5.435 5.436 ///A general undirected graph structure. 5.437 5.438 - ///\ref ListGraph is a simple and fast <em>undirected graph</em> 5.439 - ///implementation based on static linked lists that are stored in 5.440 + ///\ref ListGraph is a versatile and fast undirected graph 5.441 + ///implementation based on linked lists that are stored in 5.442 ///\c std::vector structures. 5.443 /// 5.444 - ///It conforms to the \ref concepts::Graph "Graph concept" and it 5.445 - ///also provides several useful additional functionalities. 5.446 - ///Most of the member functions and nested classes are documented 5.447 + ///This type fully conforms to the \ref concepts::Graph "Graph concept" 5.448 + ///and it also provides several useful additional functionalities. 5.449 + ///Most of its member functions and nested classes are documented 5.450 ///only in the concept class. 5.451 /// 5.452 ///\sa concepts::Graph 5.453 - 5.454 + ///\sa ListDigraph 5.455 class ListGraph : public ExtendedListGraphBase { 5.456 typedef ExtendedListGraphBase Parent; 5.457 5.458 private: 5.459 - ///ListGraph is \e not copy constructible. Use copyGraph() instead. 5.460 - 5.461 - ///ListGraph is \e not copy constructible. Use copyGraph() instead. 5.462 - /// 5.463 + /// Graphs are \e not copy constructible. Use GraphCopy instead. 5.464 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; 5.465 - ///\brief Assignment of ListGraph to another one is \e not allowed. 5.466 - ///Use copyGraph() instead. 5.467 - 5.468 - ///Assignment of ListGraph to another one is \e not allowed. 5.469 - ///Use copyGraph() instead. 5.470 + /// \brief Assignment of a graph to another one is \e not allowed. 5.471 + /// Use GraphCopy instead. 5.472 void operator=(const ListGraph &) {} 5.473 public: 5.474 /// Constructor 5.475 @@ -1201,94 +1196,95 @@ 5.476 5.477 /// \brief Add a new node to the graph. 5.478 /// 5.479 - /// Add a new node to the graph. 5.480 + /// This function adds a new node to the graph. 5.481 /// \return The new node. 5.482 Node addNode() { return Parent::addNode(); } 5.483 5.484 /// \brief Add a new edge to the graph. 5.485 /// 5.486 - /// Add a new edge to the graph with source node \c s 5.487 - /// and target node \c t. 5.488 + /// This function adds a new edge to the graph between nodes 5.489 + /// \c u and \c v with inherent orientation from node \c u to 5.490 + /// node \c v. 5.491 /// \return The new edge. 5.492 - Edge addEdge(const Node& s, const Node& t) { 5.493 - return Parent::addEdge(s, t); 5.494 + Edge addEdge(Node u, Node v) { 5.495 + return Parent::addEdge(u, v); 5.496 } 5.497 5.498 - /// \brief Erase a node from the graph. 5.499 + ///\brief Erase a node from the graph. 5.500 /// 5.501 - /// Erase a node from the graph. 5.502 + /// This function erases the given node from the graph. 5.503 + void erase(Node n) { Parent::erase(n); } 5.504 + 5.505 + ///\brief Erase an edge from the graph. 5.506 /// 5.507 - void erase(const Node& n) { Parent::erase(n); } 5.508 - 5.509 - /// \brief Erase an edge from the graph. 5.510 - /// 5.511 - /// Erase an edge from the graph. 5.512 - /// 5.513 - void erase(const Edge& e) { Parent::erase(e); } 5.514 + /// This function erases the given edge from the graph. 5.515 + void erase(Edge e) { Parent::erase(e); } 5.516 /// Node validity check 5.517 5.518 - /// This function gives back true if the given node is valid, 5.519 - /// ie. it is a real node of the graph. 5.520 + /// This function gives back \c true if the given node is valid, 5.521 + /// i.e. it is a real node of the graph. 5.522 /// 5.523 - /// \warning A Node pointing to a removed item 5.524 - /// could become valid again later if new nodes are 5.525 + /// \warning A removed node could become valid again if new nodes are 5.526 /// added to the graph. 5.527 bool valid(Node n) const { return Parent::valid(n); } 5.528 + /// Edge validity check 5.529 + 5.530 + /// This function gives back \c true if the given edge is valid, 5.531 + /// i.e. it is a real edge of the graph. 5.532 + /// 5.533 + /// \warning A removed edge could become valid again if new edges are 5.534 + /// added to the graph. 5.535 + bool valid(Edge e) const { return Parent::valid(e); } 5.536 /// Arc validity check 5.537 5.538 - /// This function gives back true if the given arc is valid, 5.539 - /// ie. it is a real arc of the graph. 5.540 + /// This function gives back \c true if the given arc is valid, 5.541 + /// i.e. it is a real arc of the graph. 5.542 /// 5.543 - /// \warning An Arc pointing to a removed item 5.544 - /// could become valid again later if new edges are 5.545 + /// \warning A removed arc could become valid again if new edges are 5.546 /// added to the graph. 5.547 bool valid(Arc a) const { return Parent::valid(a); } 5.548 - /// Edge validity check 5.549 5.550 - /// This function gives back true if the given edge is valid, 5.551 - /// ie. it is a real arc of the graph. 5.552 + /// \brief Change the first node of an edge. 5.553 /// 5.554 - /// \warning A Edge pointing to a removed item 5.555 - /// could become valid again later if new edges are 5.556 - /// added to the graph. 5.557 - bool valid(Edge e) const { return Parent::valid(e); } 5.558 - /// \brief Change the end \c u of \c e to \c n 5.559 + /// This function changes the first node of the given edge \c e to \c n. 5.560 /// 5.561 - /// This function changes the end \c u of \c e to node \c n. 5.562 - /// 5.563 - ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the 5.564 - ///changed edge are invalidated and if the changed node is the 5.565 - ///base node of an iterator then this iterator is also 5.566 - ///invalidated. 5.567 + ///\note \c EdgeIt and \c ArcIt iterators referencing the 5.568 + ///changed edge are invalidated and all other iterators whose 5.569 + ///base node is the changed node are also invalidated. 5.570 /// 5.571 ///\warning This functionality cannot be used together with the 5.572 ///Snapshot feature. 5.573 void changeU(Edge e, Node n) { 5.574 Parent::changeU(e,n); 5.575 } 5.576 - /// \brief Change the end \c v of \c e to \c n 5.577 + /// \brief Change the second node of an edge. 5.578 /// 5.579 - /// This function changes the end \c v of \c e to \c n. 5.580 + /// This function changes the second node of the given edge \c e to \c n. 5.581 /// 5.582 - ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain 5.583 - ///valid, however <tt>ArcIt</tt>s and if the changed node is the 5.584 - ///base node of an iterator then this iterator is invalidated. 5.585 + ///\note \c EdgeIt iterators referencing the changed edge remain 5.586 + ///valid, however \c ArcIt iterators referencing the changed edge and 5.587 + ///all other iterators whose base node is the changed node are also 5.588 + ///invalidated. 5.589 /// 5.590 ///\warning This functionality cannot be used together with the 5.591 ///Snapshot feature. 5.592 void changeV(Edge e, Node n) { 5.593 Parent::changeV(e,n); 5.594 } 5.595 + 5.596 /// \brief Contract two nodes. 5.597 /// 5.598 - /// This function contracts two nodes. 5.599 - /// Node \p b will be removed but instead of deleting 5.600 - /// its neighboring arcs, they will be joined to \p a. 5.601 - /// The last parameter \p r controls whether to remove loops. \c true 5.602 - /// means that loops will be removed. 5.603 + /// This function contracts the given two nodes. 5.604 + /// Node \c b is removed, but instead of deleting 5.605 + /// its incident edges, they are joined to node \c a. 5.606 + /// If the last parameter \c r is \c true (this is the default value), 5.607 + /// then the newly created loops are removed. 5.608 /// 5.609 - /// \note The <tt>ArcIt</tt>s referencing a moved arc remain 5.610 - /// valid. 5.611 + /// \note The moved edges are joined to node \c a using changeU() 5.612 + /// or changeV(), thus all edge and arc iterators whose base node is 5.613 + /// \c b are invalidated. 5.614 + /// Moreover all iterators referencing node \c b or the removed 5.615 + /// loops are also invalidated. Other iterators remain valid. 5.616 /// 5.617 ///\warning This functionality cannot be used together with the 5.618 ///Snapshot feature. 5.619 @@ -1307,6 +1303,13 @@ 5.620 erase(b); 5.621 } 5.622 5.623 + ///Clear the graph. 5.624 + 5.625 + ///This function erases all nodes and arcs from the graph. 5.626 + /// 5.627 + void clear() { 5.628 + Parent::clear(); 5.629 + } 5.630 5.631 /// \brief Class to make a snapshot of the graph and restore 5.632 /// it later. 5.633 @@ -1316,9 +1319,15 @@ 5.634 /// The newly added nodes and edges can be removed 5.635 /// using the restore() function. 5.636 /// 5.637 - /// \warning Edge and node deletions and other modifications 5.638 - /// (e.g. changing nodes of edges, contracting nodes) cannot be 5.639 - /// restored. These events invalidate the snapshot. 5.640 + /// \note After a state is restored, you cannot restore a later state, 5.641 + /// i.e. you cannot add the removed nodes and edges again using 5.642 + /// another Snapshot instance. 5.643 + /// 5.644 + /// \warning Node and edge deletions and other modifications 5.645 + /// (e.g. changing the end-nodes of edges or contracting nodes) 5.646 + /// cannot be restored. These events invalidate the snapshot. 5.647 + /// However the edges and nodes that were added to the graph after 5.648 + /// making the current snapshot can be removed without invalidating it. 5.649 class Snapshot { 5.650 protected: 5.651 5.652 @@ -1488,39 +1497,37 @@ 5.653 /// \brief Default constructor. 5.654 /// 5.655 /// Default constructor. 5.656 - /// To actually make a snapshot you must call save(). 5.657 + /// You have to call save() to actually make a snapshot. 5.658 Snapshot() 5.659 : graph(0), node_observer_proxy(*this), 5.660 edge_observer_proxy(*this) {} 5.661 5.662 /// \brief Constructor that immediately makes a snapshot. 5.663 /// 5.664 - /// This constructor immediately makes a snapshot of the graph. 5.665 - /// \param _graph The graph we make a snapshot of. 5.666 - Snapshot(ListGraph &_graph) 5.667 + /// This constructor immediately makes a snapshot of the given graph. 5.668 + Snapshot(ListGraph &gr) 5.669 : node_observer_proxy(*this), 5.670 edge_observer_proxy(*this) { 5.671 - attach(_graph); 5.672 + attach(gr); 5.673 } 5.674 5.675 /// \brief Make a snapshot. 5.676 /// 5.677 - /// Make a snapshot of the graph. 5.678 - /// 5.679 - /// This function can be called more than once. In case of a repeated 5.680 + /// This function makes a snapshot of the given graph. 5.681 + /// It can be called more than once. In case of a repeated 5.682 /// call, the previous snapshot gets lost. 5.683 - /// \param _graph The graph we make the snapshot of. 5.684 - void save(ListGraph &_graph) { 5.685 + void save(ListGraph &gr) { 5.686 if (attached()) { 5.687 detach(); 5.688 clear(); 5.689 } 5.690 - attach(_graph); 5.691 + attach(gr); 5.692 } 5.693 5.694 /// \brief Undo the changes until the last snapshot. 5.695 - // 5.696 - /// Undo the changes until the last snapshot created by save(). 5.697 + /// 5.698 + /// This function undos the changes until the last snapshot 5.699 + /// created by save() or Snapshot(ListGraph&). 5.700 void restore() { 5.701 detach(); 5.702 for(std::list<Edge>::iterator it = added_edges.begin(); 5.703 @@ -1534,9 +1541,9 @@ 5.704 clear(); 5.705 } 5.706 5.707 - /// \brief Gives back true when the snapshot is valid. 5.708 + /// \brief Returns \c true if the snapshot is valid. 5.709 /// 5.710 - /// Gives back true when the snapshot is valid. 5.711 + /// This function returns \c true if the snapshot is valid. 5.712 bool valid() const { 5.713 return attached(); 5.714 }

6.1 --- a/lemon/smart_graph.h Sun Aug 23 11:07:50 2009 +0200 6.2 +++ b/lemon/smart_graph.h Sun Aug 23 11:09:22 2009 +0200 6.3 @@ -32,10 +32,7 @@ 6.4 namespace lemon { 6.5 6.6 class SmartDigraph; 6.7 - ///Base of SmartDigraph 6.8 6.9 - ///Base of SmartDigraph 6.10 - /// 6.11 class SmartDigraphBase { 6.12 protected: 6.13 6.14 @@ -187,28 +184,26 @@ 6.15 /// 6.16 ///\brief A smart directed graph class. 6.17 /// 6.18 - ///This is a simple and fast digraph implementation. 6.19 - ///It is also quite memory efficient, but at the price 6.20 - ///that <b> it does support only limited (only stack-like) 6.21 - ///node and arc deletions</b>. 6.22 - ///It fully conforms to the \ref concepts::Digraph "Digraph concept". 6.23 + ///\ref SmartDigraph is a simple and fast digraph implementation. 6.24 + ///It is also quite memory efficient but at the price 6.25 + ///that it does not support node and arc deletion 6.26 + ///(except for the Snapshot feature). 6.27 /// 6.28 - ///\sa concepts::Digraph. 6.29 + ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 6.30 + ///and it also provides some additional functionalities. 6.31 + ///Most of its member functions and nested classes are documented 6.32 + ///only in the concept class. 6.33 + /// 6.34 + ///\sa concepts::Digraph 6.35 + ///\sa SmartGraph 6.36 class SmartDigraph : public ExtendedSmartDigraphBase { 6.37 typedef ExtendedSmartDigraphBase Parent; 6.38 6.39 private: 6.40 - 6.41 - ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 6.42 - 6.43 - ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 6.44 - /// 6.45 + /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 6.46 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; 6.47 - ///\brief Assignment of SmartDigraph to another one is \e not allowed. 6.48 - ///Use DigraphCopy() instead. 6.49 - 6.50 - ///Assignment of SmartDigraph to another one is \e not allowed. 6.51 - ///Use DigraphCopy() instead. 6.52 + /// \brief Assignment of a digraph to another one is \e not allowed. 6.53 + /// Use DigraphCopy instead. 6.54 void operator=(const SmartDigraph &) {} 6.55 6.56 public: 6.57 @@ -221,79 +216,49 @@ 6.58 6.59 ///Add a new node to the digraph. 6.60 6.61 - /// Add a new node to the digraph. 6.62 - /// \return The new node. 6.63 + ///This function adds a new node to the digraph. 6.64 + ///\return The new node. 6.65 Node addNode() { return Parent::addNode(); } 6.66 6.67 ///Add a new arc to the digraph. 6.68 6.69 - ///Add a new arc to the digraph with source node \c s 6.70 + ///This function adds a new arc to the digraph with source node \c s 6.71 ///and target node \c t. 6.72 ///\return The new arc. 6.73 - Arc addArc(const Node& s, const Node& t) { 6.74 + Arc addArc(Node s, Node t) { 6.75 return Parent::addArc(s, t); 6.76 } 6.77 6.78 - /// \brief Using this it is possible to avoid the superfluous memory 6.79 - /// allocation. 6.80 - 6.81 - /// Using this it is possible to avoid the superfluous memory 6.82 - /// allocation: if you know that the digraph you want to build will 6.83 - /// be very large (e.g. it will contain millions of nodes and/or arcs) 6.84 - /// then it is worth reserving space for this amount before starting 6.85 - /// to build the digraph. 6.86 - /// \sa reserveArc 6.87 - void reserveNode(int n) { nodes.reserve(n); }; 6.88 - 6.89 - /// \brief Using this it is possible to avoid the superfluous memory 6.90 - /// allocation. 6.91 - 6.92 - /// Using this it is possible to avoid the superfluous memory 6.93 - /// allocation: if you know that the digraph you want to build will 6.94 - /// be very large (e.g. it will contain millions of nodes and/or arcs) 6.95 - /// then it is worth reserving space for this amount before starting 6.96 - /// to build the digraph. 6.97 - /// \sa reserveNode 6.98 - void reserveArc(int m) { arcs.reserve(m); }; 6.99 - 6.100 /// \brief Node validity check 6.101 /// 6.102 - /// This function gives back true if the given node is valid, 6.103 - /// ie. it is a real node of the graph. 6.104 + /// This function gives back \c true if the given node is valid, 6.105 + /// i.e. it is a real node of the digraph. 6.106 /// 6.107 /// \warning A removed node (using Snapshot) could become valid again 6.108 - /// when new nodes are added to the graph. 6.109 + /// if new nodes are added to the digraph. 6.110 bool valid(Node n) const { return Parent::valid(n); } 6.111 6.112 /// \brief Arc validity check 6.113 /// 6.114 - /// This function gives back true if the given arc is valid, 6.115 - /// ie. it is a real arc of the graph. 6.116 + /// This function gives back \c true if the given arc is valid, 6.117 + /// i.e. it is a real arc of the digraph. 6.118 /// 6.119 /// \warning A removed arc (using Snapshot) could become valid again 6.120 - /// when new arcs are added to the graph. 6.121 + /// if new arcs are added to the graph. 6.122 bool valid(Arc a) const { return Parent::valid(a); } 6.123 6.124 - ///Clear the digraph. 6.125 - 6.126 - ///Erase all the nodes and arcs from the digraph. 6.127 - /// 6.128 - void clear() { 6.129 - Parent::clear(); 6.130 - } 6.131 - 6.132 ///Split a node. 6.133 6.134 - ///This function splits a node. First a new node is added to the digraph, 6.135 - ///then the source of each outgoing arc of \c n is moved to this new node. 6.136 - ///If \c connect is \c true (this is the default value), then a new arc 6.137 - ///from \c n to the newly created node is also added. 6.138 + ///This function splits the given node. First, a new node is added 6.139 + ///to the digraph, then the source of each outgoing arc of node \c n 6.140 + ///is moved to this new node. 6.141 + ///If the second parameter \c connect is \c true (this is the default 6.142 + ///value), then a new arc from node \c n to the newly created node 6.143 + ///is also added. 6.144 ///\return The newly created node. 6.145 /// 6.146 - ///\note The <tt>Arc</tt>s 6.147 - ///referencing a moved arc remain 6.148 - ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s 6.149 - ///may be invalidated. 6.150 + ///\note All iterators remain valid. 6.151 + /// 6.152 ///\warning This functionality cannot be used together with the Snapshot 6.153 ///feature. 6.154 Node split(Node n, bool connect = true) 6.155 @@ -308,6 +273,34 @@ 6.156 return b; 6.157 } 6.158 6.159 + ///Clear the digraph. 6.160 + 6.161 + ///This function erases all nodes and arcs from the digraph. 6.162 + /// 6.163 + void clear() { 6.164 + Parent::clear(); 6.165 + } 6.166 + 6.167 + /// Reserve memory for nodes. 6.168 + 6.169 + /// Using this function, it is possible to avoid superfluous memory 6.170 + /// allocation: if you know that the digraph you want to build will 6.171 + /// be large (e.g. it will contain millions of nodes and/or arcs), 6.172 + /// then it is worth reserving space for this amount before starting 6.173 + /// to build the digraph. 6.174 + /// \sa reserveArc() 6.175 + void reserveNode(int n) { nodes.reserve(n); }; 6.176 + 6.177 + /// Reserve memory for arcs. 6.178 + 6.179 + /// Using this function, it is possible to avoid superfluous memory 6.180 + /// allocation: if you know that the digraph you want to build will 6.181 + /// be large (e.g. it will contain millions of nodes and/or arcs), 6.182 + /// then it is worth reserving space for this amount before starting 6.183 + /// to build the digraph. 6.184 + /// \sa reserveNode() 6.185 + void reserveArc(int m) { arcs.reserve(m); }; 6.186 + 6.187 public: 6.188 6.189 class Snapshot; 6.190 @@ -332,20 +325,23 @@ 6.191 6.192 public: 6.193 6.194 - ///Class to make a snapshot of the digraph and to restrore to it later. 6.195 + ///Class to make a snapshot of the digraph and to restore it later. 6.196 6.197 - ///Class to make a snapshot of the digraph and to restrore to it later. 6.198 + ///Class to make a snapshot of the digraph and to restore it later. 6.199 /// 6.200 ///The newly added nodes and arcs can be removed using the 6.201 - ///restore() function. 6.202 - ///\note After you restore a state, you cannot restore 6.203 - ///a later state, in other word you cannot add again the arcs deleted 6.204 - ///by restore() using another one Snapshot instance. 6.205 + ///restore() function. This is the only way for deleting nodes and/or 6.206 + ///arcs from a SmartDigraph structure. 6.207 /// 6.208 - ///\warning If you do not use correctly the snapshot that can cause 6.209 - ///either broken program, invalid state of the digraph, valid but 6.210 - ///not the restored digraph or no change. Because the runtime performance 6.211 - ///the validity of the snapshot is not stored. 6.212 + ///\note After a state is restored, you cannot restore a later state, 6.213 + ///i.e. you cannot add the removed nodes and arcs again using 6.214 + ///another Snapshot instance. 6.215 + /// 6.216 + ///\warning Node splitting cannot be restored. 6.217 + ///\warning The validity of the snapshot is not stored due to 6.218 + ///performance reasons. If you do not use the snapshot correctly, 6.219 + ///it can cause broken program, invalid or not restored state of 6.220 + ///the digraph or no change. 6.221 class Snapshot 6.222 { 6.223 SmartDigraph *_graph; 6.224 @@ -357,39 +353,32 @@ 6.225 ///Default constructor. 6.226 6.227 ///Default constructor. 6.228 - ///To actually make a snapshot you must call save(). 6.229 - /// 6.230 + ///You have to call save() to actually make a snapshot. 6.231 Snapshot() : _graph(0) {} 6.232 ///Constructor that immediately makes a snapshot 6.233 6.234 - ///This constructor immediately makes a snapshot of the digraph. 6.235 - ///\param graph The digraph we make a snapshot of. 6.236 - Snapshot(SmartDigraph &graph) : _graph(&graph) { 6.237 + ///This constructor immediately makes a snapshot of the given digraph. 6.238 + /// 6.239 + Snapshot(SmartDigraph &gr) : _graph(&gr) { 6.240 node_num=_graph->nodes.size(); 6.241 arc_num=_graph->arcs.size(); 6.242 } 6.243 6.244 ///Make a snapshot. 6.245 6.246 - ///Make a snapshot of the digraph. 6.247 - /// 6.248 - ///This function can be called more than once. In case of a repeated 6.249 + ///This function makes a snapshot of the given digraph. 6.250 + ///It can be called more than once. In case of a repeated 6.251 ///call, the previous snapshot gets lost. 6.252 - ///\param graph The digraph we make the snapshot of. 6.253 - void save(SmartDigraph &graph) 6.254 - { 6.255 - _graph=&graph; 6.256 + void save(SmartDigraph &gr) { 6.257 + _graph=&gr; 6.258 node_num=_graph->nodes.size(); 6.259 arc_num=_graph->arcs.size(); 6.260 } 6.261 6.262 ///Undo the changes until a snapshot. 6.263 6.264 - ///Undo the changes until a snapshot created by save(). 6.265 - /// 6.266 - ///\note After you restored a state, you cannot restore 6.267 - ///a later state, in other word you cannot add again the arcs deleted 6.268 - ///by restore(). 6.269 + ///This function undos the changes until the last snapshot 6.270 + ///created by save() or Snapshot(SmartDigraph&). 6.271 void restore() 6.272 { 6.273 _graph->restoreSnapshot(*this); 6.274 @@ -621,29 +610,26 @@ 6.275 /// 6.276 /// \brief A smart undirected graph class. 6.277 /// 6.278 - /// This is a simple and fast graph implementation. 6.279 - /// It is also quite memory efficient, but at the price 6.280 - /// that <b> it does support only limited (only stack-like) 6.281 - /// node and arc deletions</b>. 6.282 - /// It fully conforms to the \ref concepts::Graph "Graph concept". 6.283 + /// \ref SmartGraph is a simple and fast graph implementation. 6.284 + /// It is also quite memory efficient but at the price 6.285 + /// that it does not support node and edge deletion 6.286 + /// (except for the Snapshot feature). 6.287 /// 6.288 - /// \sa concepts::Graph. 6.289 + /// This type fully conforms to the \ref concepts::Graph "Graph concept" 6.290 + /// and it also provides some additional functionalities. 6.291 + /// Most of its member functions and nested classes are documented 6.292 + /// only in the concept class. 6.293 + /// 6.294 + /// \sa concepts::Graph 6.295 + /// \sa SmartDigraph 6.296 class SmartGraph : public ExtendedSmartGraphBase { 6.297 typedef ExtendedSmartGraphBase Parent; 6.298 6.299 private: 6.300 - 6.301 - ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 6.302 - 6.303 - ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 6.304 - /// 6.305 + /// Graphs are \e not copy constructible. Use GraphCopy instead. 6.306 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; 6.307 - 6.308 - ///\brief Assignment of SmartGraph to another one is \e not allowed. 6.309 - ///Use GraphCopy() instead. 6.310 - 6.311 - ///Assignment of SmartGraph to another one is \e not allowed. 6.312 - ///Use GraphCopy() instead. 6.313 + /// \brief Assignment of a graph to another one is \e not allowed. 6.314 + /// Use GraphCopy instead. 6.315 void operator=(const SmartGraph &) {} 6.316 6.317 public: 6.318 @@ -654,51 +640,52 @@ 6.319 /// 6.320 SmartGraph() {} 6.321 6.322 - ///Add a new node to the graph. 6.323 - 6.324 - /// Add a new node to the graph. 6.325 + /// \brief Add a new node to the graph. 6.326 + /// 6.327 + /// This function adds a new node to the graph. 6.328 /// \return The new node. 6.329 Node addNode() { return Parent::addNode(); } 6.330 6.331 - ///Add a new edge to the graph. 6.332 - 6.333 - ///Add a new edge to the graph with node \c s 6.334 - ///and \c t. 6.335 - ///\return The new edge. 6.336 - Edge addEdge(const Node& s, const Node& t) { 6.337 - return Parent::addEdge(s, t); 6.338 + /// \brief Add a new edge to the graph. 6.339 + /// 6.340 + /// This function adds a new edge to the graph between nodes 6.341 + /// \c u and \c v with inherent orientation from node \c u to 6.342 + /// node \c v. 6.343 + /// \return The new edge. 6.344 + Edge addEdge(Node u, Node v) { 6.345 + return Parent::addEdge(u, v); 6.346 } 6.347 6.348 /// \brief Node validity check 6.349 /// 6.350 - /// This function gives back true if the given node is valid, 6.351 - /// ie. it is a real node of the graph. 6.352 + /// This function gives back \c true if the given node is valid, 6.353 + /// i.e. it is a real node of the graph. 6.354 /// 6.355 /// \warning A removed node (using Snapshot) could become valid again 6.356 - /// when new nodes are added to the graph. 6.357 + /// if new nodes are added to the graph. 6.358 bool valid(Node n) const { return Parent::valid(n); } 6.359 6.360 + /// \brief Edge validity check 6.361 + /// 6.362 + /// This function gives back \c true if the given edge is valid, 6.363 + /// i.e. it is a real edge of the graph. 6.364 + /// 6.365 + /// \warning A removed edge (using Snapshot) could become valid again 6.366 + /// if new edges are added to the graph. 6.367 + bool valid(Edge e) const { return Parent::valid(e); } 6.368 + 6.369 /// \brief Arc validity check 6.370 /// 6.371 - /// This function gives back true if the given arc is valid, 6.372 - /// ie. it is a real arc of the graph. 6.373 + /// This function gives back \c true if the given arc is valid, 6.374 + /// i.e. it is a real arc of the graph. 6.375 /// 6.376 /// \warning A removed arc (using Snapshot) could become valid again 6.377 - /// when new edges are added to the graph. 6.378 + /// if new edges are added to the graph. 6.379 bool valid(Arc a) const { return Parent::valid(a); } 6.380 6.381 - /// \brief Edge validity check 6.382 - /// 6.383 - /// This function gives back true if the given edge is valid, 6.384 - /// ie. it is a real edge of the graph. 6.385 - /// 6.386 - /// \warning A removed edge (using Snapshot) could become valid again 6.387 - /// when new edges are added to the graph. 6.388 - bool valid(Edge e) const { return Parent::valid(e); } 6.389 - 6.390 ///Clear the graph. 6.391 6.392 - ///Erase all the nodes and edges from the graph. 6.393 + ///This function erases all nodes and arcs from the graph. 6.394 /// 6.395 void clear() { 6.396 Parent::clear(); 6.397 @@ -742,21 +729,22 @@ 6.398 6.399 public: 6.400 6.401 - ///Class to make a snapshot of the digraph and to restrore to it later. 6.402 + ///Class to make a snapshot of the graph and to restore it later. 6.403 6.404 - ///Class to make a snapshot of the digraph and to restrore to it later. 6.405 + ///Class to make a snapshot of the graph and to restore it later. 6.406 /// 6.407 - ///The newly added nodes and arcs can be removed using the 6.408 - ///restore() function. 6.409 + ///The newly added nodes and edges can be removed using the 6.410 + ///restore() function. This is the only way for deleting nodes and/or 6.411 + ///edges from a SmartGraph structure. 6.412 /// 6.413 - ///\note After you restore a state, you cannot restore 6.414 - ///a later state, in other word you cannot add again the arcs deleted 6.415 - ///by restore() using another one Snapshot instance. 6.416 + ///\note After a state is restored, you cannot restore a later state, 6.417 + ///i.e. you cannot add the removed nodes and edges again using 6.418 + ///another Snapshot instance. 6.419 /// 6.420 - ///\warning If you do not use correctly the snapshot that can cause 6.421 - ///either broken program, invalid state of the digraph, valid but 6.422 - ///not the restored digraph or no change. Because the runtime performance 6.423 - ///the validity of the snapshot is not stored. 6.424 + ///\warning The validity of the snapshot is not stored due to 6.425 + ///performance reasons. If you do not use the snapshot correctly, 6.426 + ///it can cause broken program, invalid or not restored state of 6.427 + ///the graph or no change. 6.428 class Snapshot 6.429 { 6.430 SmartGraph *_graph; 6.431 @@ -768,36 +756,30 @@ 6.432 ///Default constructor. 6.433 6.434 ///Default constructor. 6.435 - ///To actually make a snapshot you must call save(). 6.436 - /// 6.437 + ///You have to call save() to actually make a snapshot. 6.438 Snapshot() : _graph(0) {} 6.439 ///Constructor that immediately makes a snapshot 6.440 6.441 - ///This constructor immediately makes a snapshot of the digraph. 6.442 - ///\param graph The digraph we make a snapshot of. 6.443 - Snapshot(SmartGraph &graph) { 6.444 - graph.saveSnapshot(*this); 6.445 + /// This constructor immediately makes a snapshot of the given graph. 6.446 + /// 6.447 + Snapshot(SmartGraph &gr) { 6.448 + gr.saveSnapshot(*this); 6.449 } 6.450 6.451 ///Make a snapshot. 6.452 6.453 - ///Make a snapshot of the graph. 6.454 - /// 6.455 - ///This function can be called more than once. In case of a repeated 6.456 + ///This function makes a snapshot of the given graph. 6.457 + ///It can be called more than once. In case of a repeated 6.458 ///call, the previous snapshot gets lost. 6.459 - ///\param graph The digraph we make the snapshot of. 6.460 - void save(SmartGraph &graph) 6.461 + void save(SmartGraph &gr) 6.462 { 6.463 - graph.saveSnapshot(*this); 6.464 + gr.saveSnapshot(*this); 6.465 } 6.466 6.467 - ///Undo the changes until a snapshot. 6.468 + ///Undo the changes until the last snapshot. 6.469 6.470 - ///Undo the changes until a snapshot created by save(). 6.471 - /// 6.472 - ///\note After you restored a state, you cannot restore 6.473 - ///a later state, in other word you cannot add again the arcs deleted 6.474 - ///by restore(). 6.475 + ///This function undos the changes until the last snapshot 6.476 + ///created by save() or Snapshot(SmartGraph&). 6.477 void restore() 6.478 { 6.479 _graph->restoreSnapshot(*this);