1.1 --- a/lemon/full_graph.h Thu Aug 14 21:49:39 2008 +0200
1.2 +++ b/lemon/full_graph.h Sat Nov 01 19:22:18 2008 +0100
1.3 @@ -19,14 +19,13 @@
1.4 #ifndef LEMON_FULL_GRAPH_H
1.5 #define LEMON_FULL_GRAPH_H
1.6
1.7 -#include <lemon/math.h>
1.8 -
1.9 #include <lemon/core.h>
1.10 #include <lemon/bits/graph_extender.h>
1.11
1.12 ///\ingroup graphs
1.13 ///\file
1.14 -///\brief FullDigraph and FullGraph classes.
1.15 +///\brief FullGraph and FullDigraph classes.
1.16 +
1.17 namespace lemon {
1.18
1.19 class FullDigraphBase {
1.20 @@ -67,12 +66,10 @@
1.21 Node source(Arc arc) const { return arc._id / _node_num; }
1.22 Node target(Arc arc) const { return arc._id % _node_num; }
1.23
1.24 -
1.25 static int id(Node node) { return node._id; }
1.26 static int id(Arc arc) { return arc._id; }
1.27
1.28 static Node nodeFromId(int id) { return Node(id);}
1.29 -
1.30 static Arc arcFromId(int id) { return Arc(id);}
1.31
1.32 typedef True FindArcTag;
1.33 @@ -81,7 +78,6 @@
1.34 return prev != INVALID ? arc(s, t) : INVALID;
1.35 }
1.36
1.37 -
1.38 class Node {
1.39 friend class FullDigraphBase;
1.40
1.41 @@ -157,14 +153,20 @@
1.42 /// This is a simple and fast directed full graph implementation.
1.43 /// From each node go arcs to each node (including the source node),
1.44 /// therefore the number of the arcs in the digraph is the square of
1.45 - /// the node number. The digraph is completely static, so you can
1.46 - /// neither add nor delete either arcs or nodes, and it needs just
1.47 + /// the node number. This digraph type is completely static, so you
1.48 + /// can neither add nor delete either arcs or nodes, and it needs
1.49 /// constant space in memory.
1.50 ///
1.51 - /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept
1.52 + /// This class conforms to the \ref concepts::Digraph "Digraph" concept
1.53 /// and it also has an important extra feature that its maps are
1.54 /// real \ref concepts::ReferenceMap "reference map"s.
1.55 - /// \sa concepts::Digraph.
1.56 + ///
1.57 + /// The \c FullDigraph and \c FullGraph classes are very similar,
1.58 + /// but there are two differences. While this class conforms only
1.59 + /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
1.60 + /// class conforms to the \ref concepts::Graph "Graph" concept,
1.61 + /// moreover \c FullGraph does not contain a loop arc for each
1.62 + /// node as \c FullDigraph does.
1.63 ///
1.64 /// \sa FullGraph
1.65 class FullDigraph : public ExtendedFullDigraphBase {
1.66 @@ -177,15 +179,15 @@
1.67
1.68 /// \brief Constructor
1.69 ///
1.70 + /// Constructor.
1.71 /// \param n The number of the nodes.
1.72 FullDigraph(int n) { construct(n); }
1.73
1.74 - /// \brief Resize the digraph
1.75 + /// \brief Resizes the digraph
1.76 ///
1.77 - /// Resize the digraph. The function will fully destroy and
1.78 - /// rebuild the digraph. This cause that the maps of the digraph
1.79 - /// will reallocated automatically and the previous values will be
1.80 - /// lost.
1.81 + /// Resizes the digraph. The function will fully destroy and
1.82 + /// rebuild the digraph. This cause that the maps of the digraph will
1.83 + /// reallocated automatically and the previous values will be lost.
1.84 void resize(int n) {
1.85 Parent::notifier(Arc()).clear();
1.86 Parent::notifier(Node()).clear();
1.87 @@ -196,23 +198,23 @@
1.88
1.89 /// \brief Returns the node with the given index.
1.90 ///
1.91 - /// Returns the node with the given index. Because it is a
1.92 - /// static size digraph the node's of the digraph can be indexed
1.93 - /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
1.94 - /// the node can accessed by the \e index() member.
1.95 + /// Returns the node with the given index. Since it is a static
1.96 + /// digraph its nodes can be indexed with integers from the range
1.97 + /// <tt>[0..nodeNum()-1]</tt>.
1.98 + /// \sa index()
1.99 Node operator()(int ix) const { return Parent::operator()(ix); }
1.100
1.101 - /// \brief Returns the index of the node.
1.102 + /// \brief Returns the index of the given node.
1.103 ///
1.104 - /// Returns the index of the node. Because it is a
1.105 - /// static size digraph the node's of the digraph can be indexed
1.106 - /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
1.107 - /// the node can accessed by the \e index() member.
1.108 + /// Returns the index of the given node. Since it is a static
1.109 + /// digraph its nodes can be indexed with integers from the range
1.110 + /// <tt>[0..nodeNum()-1]</tt>.
1.111 + /// \sa operator()
1.112 int index(const Node& node) const { return Parent::index(node); }
1.113
1.114 - /// \brief Returns the arc connects the given nodes.
1.115 + /// \brief Returns the arc connecting the given nodes.
1.116 ///
1.117 - /// Returns the arc connects the given nodes.
1.118 + /// Returns the arc connecting the given nodes.
1.119 Arc arc(const Node& u, const Node& v) const {
1.120 return Parent::arc(u, v);
1.121 }
1.122 @@ -280,7 +282,6 @@
1.123
1.124 public:
1.125
1.126 -
1.127 Node operator()(int ix) const { return Node(ix); }
1.128 int index(const Node& node) const { return node._id; }
1.129
1.130 @@ -367,6 +368,7 @@
1.131
1.132 class Edge {
1.133 friend class FullGraphBase;
1.134 + friend class Arc;
1.135
1.136 protected:
1.137 int _id;
1.138 @@ -518,20 +520,21 @@
1.139 ///
1.140 /// This is a simple and fast undirected full graph
1.141 /// implementation. From each node go edge to each other node,
1.142 - /// therefore the number of edges in the graph is
1.143 - /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither
1.144 - /// add nor delete either edges or nodes, and it needs just constant
1.145 + /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
1.146 + /// This graph type is completely static, so you can neither
1.147 + /// add nor delete either edges or nodes, and it needs constant
1.148 /// space in memory.
1.149 ///
1.150 - /// The \e FullDigraph and \e FullGraph classes are very similar,
1.151 - /// but there are two differences. While the \e FullDigraph class is
1.152 - /// conform just to the \ref concepts::Digraph "Digraph" concept,
1.153 - /// this class is conform to the \ref concepts::Graph "Graph"
1.154 - /// concept. In addition, the \e FullGraph class does not contain a
1.155 - /// loop arc from each node as the \e FullDigraph does.
1.156 + /// This class conforms to the \ref concepts::Graph "Graph" concept
1.157 + /// and it also has an important extra feature that its maps are
1.158 + /// real \ref concepts::ReferenceMap "reference map"s.
1.159 ///
1.160 - /// It also has an important extra feature that its maps are real
1.161 - /// \ref concepts::ReferenceMap "reference map"s.
1.162 + /// The \c FullGraph and \c FullDigraph classes are very similar,
1.163 + /// but there are two differences. While the \c FullDigraph class
1.164 + /// conforms only to the \ref concepts::Digraph "Digraph" concept,
1.165 + /// this class conforms to the \ref concepts::Graph "Graph" concept,
1.166 + /// moreover \c FullGraph does not contain a loop arc for each
1.167 + /// node as \c FullDigraph does.
1.168 ///
1.169 /// \sa FullDigraph
1.170 class FullGraph : public ExtendedFullGraphBase {
1.171 @@ -544,15 +547,15 @@
1.172
1.173 /// \brief Constructor
1.174 ///
1.175 + /// Constructor.
1.176 /// \param n The number of the nodes.
1.177 FullGraph(int n) { construct(n); }
1.178
1.179 - /// \brief Resize the graph
1.180 + /// \brief Resizes the graph
1.181 ///
1.182 - /// Resize the graph. The function will fully destroy and rebuild
1.183 - /// the graph. This cause that the maps of the graph will
1.184 - /// reallocated automatically and the previous values will be
1.185 - /// lost.
1.186 + /// Resizes the graph. The function will fully destroy and
1.187 + /// rebuild the graph. This cause that the maps of the graph will
1.188 + /// reallocated automatically and the previous values will be lost.
1.189 void resize(int n) {
1.190 Parent::notifier(Arc()).clear();
1.191 Parent::notifier(Edge()).clear();
1.192 @@ -565,30 +568,23 @@
1.193
1.194 /// \brief Returns the node with the given index.
1.195 ///
1.196 - /// Returns the node with the given index. Because it is a static
1.197 - /// size graph the node's of the graph can be indexed in the range
1.198 - /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
1.199 - /// accessed by the \e index() member.
1.200 + /// Returns the node with the given index. Since it is a static
1.201 + /// graph its nodes can be indexed with integers from the range
1.202 + /// <tt>[0..nodeNum()-1]</tt>.
1.203 + /// \sa index()
1.204 Node operator()(int ix) const { return Parent::operator()(ix); }
1.205
1.206 - /// \brief Returns the index of the node.
1.207 + /// \brief Returns the index of the given node.
1.208 ///
1.209 - /// Returns the index of the node. Because it is a static size
1.210 - /// graph the node's of the graph can be indexed in the range
1.211 - /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
1.212 - /// accessed by the \e index() member.
1.213 + /// Returns the index of the given node. Since it is a static
1.214 + /// graph its nodes can be indexed with integers from the range
1.215 + /// <tt>[0..nodeNum()-1]</tt>.
1.216 + /// \sa operator()
1.217 int index(const Node& node) const { return Parent::index(node); }
1.218
1.219 - /// \brief Number of nodes.
1.220 - int nodeNum() const { return Parent::nodeNum(); }
1.221 - /// \brief Number of arcs.
1.222 - int arcNum() const { return Parent::arcNum(); }
1.223 - /// \brief Number of edges.
1.224 - int edgeNum() const { return Parent::edgeNum(); }
1.225 -
1.226 - /// \brief Returns the arc connects the given nodes.
1.227 + /// \brief Returns the arc connecting the given nodes.
1.228 ///
1.229 - /// Returns the arc connects the given nodes.
1.230 + /// Returns the arc connecting the given nodes.
1.231 Arc arc(const Node& s, const Node& t) const {
1.232 return Parent::arc(s, t);
1.233 }
1.234 @@ -599,6 +595,14 @@
1.235 Edge edge(const Node& u, const Node& v) const {
1.236 return Parent::edge(u, v);
1.237 }
1.238 +
1.239 + /// \brief Number of nodes.
1.240 + int nodeNum() const { return Parent::nodeNum(); }
1.241 + /// \brief Number of arcs.
1.242 + int arcNum() const { return Parent::arcNum(); }
1.243 + /// \brief Number of edges.
1.244 + int edgeNum() const { return Parent::edgeNum(); }
1.245 +
1.246 };
1.247
1.248