1.1 --- a/lemon/full_graph.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/full_graph.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -24,14 +24,14 @@
1.4
1.5 ///\ingroup graphs
1.6 ///\file
1.7 -///\brief FullGraph and FullDigraph classes.
1.8 +///\brief FullDigraph and FullGraph classes.
1.9
1.10 namespace lemon {
1.11
1.12 class FullDigraphBase {
1.13 public:
1.14
1.15 - typedef FullDigraphBase Graph;
1.16 + typedef FullDigraphBase Digraph;
1.17
1.18 class Node;
1.19 class Arc;
1.20 @@ -51,7 +51,7 @@
1.21 typedef True ArcNumTag;
1.22
1.23 Node operator()(int ix) const { return Node(ix); }
1.24 - int index(const Node& node) const { return node._id; }
1.25 + static int index(const Node& node) { return node._id; }
1.26
1.27 Arc arc(const Node& s, const Node& t) const {
1.28 return Arc(s._id * _node_num + t._id);
1.29 @@ -148,33 +148,36 @@
1.30
1.31 /// \ingroup graphs
1.32 ///
1.33 - /// \brief A full digraph class.
1.34 + /// \brief A directed full graph class.
1.35 ///
1.36 - /// This is a simple and fast directed full graph implementation.
1.37 - /// From each node go arcs to each node (including the source node),
1.38 - /// therefore the number of the arcs in the digraph is the square of
1.39 - /// the node number. This digraph type is completely static, so you
1.40 - /// can neither add nor delete either arcs or nodes, and it needs
1.41 - /// constant space in memory.
1.42 + /// FullDigraph is a simple and fast implmenetation of directed full
1.43 + /// (complete) graphs. It contains an arc from each node to each node
1.44 + /// (including a loop for each node), therefore the number of arcs
1.45 + /// is the square of the number of nodes.
1.46 + /// This class is completely static and it needs constant memory space.
1.47 + /// Thus you can neither add nor delete nodes or arcs, however
1.48 + /// the structure can be resized using resize().
1.49 ///
1.50 - /// This class conforms to the \ref concepts::Digraph "Digraph" concept
1.51 - /// and it also has an important extra feature that its maps are
1.52 - /// real \ref concepts::ReferenceMap "reference map"s.
1.53 + /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
1.54 + /// Most of its member functions and nested classes are documented
1.55 + /// only in the concept class.
1.56 ///
1.57 - /// The \c FullDigraph and \c FullGraph classes are very similar,
1.58 + /// \note FullDigraph and FullGraph classes are very similar,
1.59 /// but there are two differences. While this class conforms only
1.60 - /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
1.61 - /// class conforms to the \ref concepts::Graph "Graph" concept,
1.62 - /// moreover \c FullGraph does not contain a loop arc for each
1.63 - /// node as \c FullDigraph does.
1.64 + /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
1.65 + /// conforms to the \ref concepts::Graph "Graph" concept,
1.66 + /// moreover FullGraph does not contain a loop for each
1.67 + /// node as this class does.
1.68 ///
1.69 /// \sa FullGraph
1.70 class FullDigraph : public ExtendedFullDigraphBase {
1.71 + typedef ExtendedFullDigraphBase Parent;
1.72 +
1.73 public:
1.74
1.75 - typedef ExtendedFullDigraphBase Parent;
1.76 -
1.77 - /// \brief Constructor
1.78 + /// \brief Default constructor.
1.79 + ///
1.80 + /// Default constructor. The number of nodes and arcs will be zero.
1.81 FullDigraph() { construct(0); }
1.82
1.83 /// \brief Constructor
1.84 @@ -185,8 +188,8 @@
1.85
1.86 /// \brief Resizes the digraph
1.87 ///
1.88 - /// Resizes the digraph. The function will fully destroy and
1.89 - /// rebuild the digraph. This cause that the maps of the digraph will
1.90 + /// This function resizes the digraph. It fully destroys and
1.91 + /// rebuilds the structure, therefore the maps of the digraph will be
1.92 /// reallocated automatically and the previous values will be lost.
1.93 void resize(int n) {
1.94 Parent::notifier(Arc()).clear();
1.95 @@ -198,24 +201,24 @@
1.96
1.97 /// \brief Returns the node with the given index.
1.98 ///
1.99 - /// Returns the node with the given index. Since it is a static
1.100 - /// digraph its nodes can be indexed with integers from the range
1.101 - /// <tt>[0..nodeNum()-1]</tt>.
1.102 + /// Returns the node with the given index. Since this structure is
1.103 + /// completely static, the nodes can be indexed with integers from
1.104 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.105 /// \sa index()
1.106 Node operator()(int ix) const { return Parent::operator()(ix); }
1.107
1.108 /// \brief Returns the index of the given node.
1.109 ///
1.110 - /// Returns the index of the given node. Since it is a static
1.111 - /// digraph its nodes can be indexed with integers from the range
1.112 - /// <tt>[0..nodeNum()-1]</tt>.
1.113 - /// \sa operator()
1.114 - int index(const Node& node) const { return Parent::index(node); }
1.115 + /// Returns the index of the given node. Since this structure is
1.116 + /// completely static, the nodes can be indexed with integers from
1.117 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.118 + /// \sa operator()()
1.119 + static int index(const Node& node) { return Parent::index(node); }
1.120
1.121 /// \brief Returns the arc connecting the given nodes.
1.122 ///
1.123 /// Returns the arc connecting the given nodes.
1.124 - Arc arc(const Node& u, const Node& v) const {
1.125 + Arc arc(Node u, Node v) const {
1.126 return Parent::arc(u, v);
1.127 }
1.128
1.129 @@ -227,8 +230,6 @@
1.130
1.131
1.132 class FullGraphBase {
1.133 - int _node_num;
1.134 - int _edge_num;
1.135 public:
1.136
1.137 typedef FullGraphBase Graph;
1.138 @@ -239,6 +240,9 @@
1.139
1.140 protected:
1.141
1.142 + int _node_num;
1.143 + int _edge_num;
1.144 +
1.145 FullGraphBase() {}
1.146
1.147 void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
1.148 @@ -283,7 +287,7 @@
1.149 public:
1.150
1.151 Node operator()(int ix) const { return Node(ix); }
1.152 - int index(const Node& node) const { return node._id; }
1.153 + static int index(const Node& node) { return node._id; }
1.154
1.155 Edge edge(const Node& u, const Node& v) const {
1.156 if (u._id < v._id) {
1.157 @@ -520,31 +524,33 @@
1.158 ///
1.159 /// \brief An undirected full graph class.
1.160 ///
1.161 - /// This is a simple and fast undirected full graph
1.162 - /// implementation. From each node go edge to each other node,
1.163 - /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
1.164 - /// This graph type is completely static, so you can neither
1.165 - /// add nor delete either edges or nodes, and it needs constant
1.166 - /// space in memory.
1.167 + /// FullGraph is a simple and fast implmenetation of undirected full
1.168 + /// (complete) graphs. It contains an edge between every distinct pair
1.169 + /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
1.170 + /// This class is completely static and it needs constant memory space.
1.171 + /// Thus you can neither add nor delete nodes or edges, however
1.172 + /// the structure can be resized using resize().
1.173 ///
1.174 - /// This class conforms to the \ref concepts::Graph "Graph" concept
1.175 - /// and it also has an important extra feature that its maps are
1.176 - /// real \ref concepts::ReferenceMap "reference map"s.
1.177 + /// This type fully conforms to the \ref concepts::Graph "Graph concept".
1.178 + /// Most of its member functions and nested classes are documented
1.179 + /// only in the concept class.
1.180 ///
1.181 - /// The \c FullGraph and \c FullDigraph classes are very similar,
1.182 - /// but there are two differences. While the \c FullDigraph class
1.183 + /// \note FullDigraph and FullGraph classes are very similar,
1.184 + /// but there are two differences. While FullDigraph
1.185 /// conforms only to the \ref concepts::Digraph "Digraph" concept,
1.186 /// this class conforms to the \ref concepts::Graph "Graph" concept,
1.187 - /// moreover \c FullGraph does not contain a loop arc for each
1.188 - /// node as \c FullDigraph does.
1.189 + /// moreover this class does not contain a loop for each
1.190 + /// node as FullDigraph does.
1.191 ///
1.192 /// \sa FullDigraph
1.193 class FullGraph : public ExtendedFullGraphBase {
1.194 + typedef ExtendedFullGraphBase Parent;
1.195 +
1.196 public:
1.197
1.198 - typedef ExtendedFullGraphBase Parent;
1.199 -
1.200 - /// \brief Constructor
1.201 + /// \brief Default constructor.
1.202 + ///
1.203 + /// Default constructor. The number of nodes and edges will be zero.
1.204 FullGraph() { construct(0); }
1.205
1.206 /// \brief Constructor
1.207 @@ -555,8 +561,8 @@
1.208
1.209 /// \brief Resizes the graph
1.210 ///
1.211 - /// Resizes the graph. The function will fully destroy and
1.212 - /// rebuild the graph. This cause that the maps of the graph will
1.213 + /// This function resizes the graph. It fully destroys and
1.214 + /// rebuilds the structure, therefore the maps of the graph will be
1.215 /// reallocated automatically and the previous values will be lost.
1.216 void resize(int n) {
1.217 Parent::notifier(Arc()).clear();
1.218 @@ -570,31 +576,31 @@
1.219
1.220 /// \brief Returns the node with the given index.
1.221 ///
1.222 - /// Returns the node with the given index. Since it is a static
1.223 - /// graph its nodes can be indexed with integers from the range
1.224 - /// <tt>[0..nodeNum()-1]</tt>.
1.225 + /// Returns the node with the given index. Since this structure is
1.226 + /// completely static, the nodes can be indexed with integers from
1.227 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.228 /// \sa index()
1.229 Node operator()(int ix) const { return Parent::operator()(ix); }
1.230
1.231 /// \brief Returns the index of the given node.
1.232 ///
1.233 - /// Returns the index of the given node. Since it is a static
1.234 - /// graph its nodes can be indexed with integers from the range
1.235 - /// <tt>[0..nodeNum()-1]</tt>.
1.236 - /// \sa operator()
1.237 - int index(const Node& node) const { return Parent::index(node); }
1.238 + /// Returns the index of the given node. Since this structure is
1.239 + /// completely static, the nodes can be indexed with integers from
1.240 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.241 + /// \sa operator()()
1.242 + static int index(const Node& node) { return Parent::index(node); }
1.243
1.244 /// \brief Returns the arc connecting the given nodes.
1.245 ///
1.246 /// Returns the arc connecting the given nodes.
1.247 - Arc arc(const Node& s, const Node& t) const {
1.248 + Arc arc(Node s, Node t) const {
1.249 return Parent::arc(s, t);
1.250 }
1.251
1.252 - /// \brief Returns the edge connects the given nodes.
1.253 + /// \brief Returns the edge connecting the given nodes.
1.254 ///
1.255 - /// Returns the edge connects the given nodes.
1.256 - Edge edge(const Node& u, const Node& v) const {
1.257 + /// Returns the edge connecting the given nodes.
1.258 + Edge edge(Node u, Node v) const {
1.259 return Parent::edge(u, v);
1.260 }
1.261