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);