1.1 --- a/lemon/full_graph.h Mon Jul 18 15:07:28 2005 +0000
1.2 +++ b/lemon/full_graph.h Mon Jul 18 15:08:18 2005 +0000
1.3 @@ -24,6 +24,8 @@
1.4 #include <lemon/bits/alteration_notifier.h>
1.5 #include <lemon/bits/default_map.h>
1.6
1.7 +#include <lemon/bits/undir_graph_extender.h>
1.8 +
1.9 #include <lemon/invalid.h>
1.10 #include <lemon/utility.h>
1.11
1.12 @@ -36,8 +38,8 @@
1.13 namespace lemon {
1.14
1.15 class FullGraphBase {
1.16 - int NodeNum;
1.17 - int EdgeNum;
1.18 + int _nodeNum;
1.19 + int _edgeNum;
1.20 public:
1.21
1.22 typedef FullGraphBase Graph;
1.23 @@ -51,32 +53,32 @@
1.24
1.25
1.26 ///Creates a full graph with \c n nodes.
1.27 - void construct(int n) { NodeNum = n; EdgeNum = n * n; }
1.28 + void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
1.29 ///
1.30 // FullGraphBase(const FullGraphBase &_g)
1.31 - // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
1.32 + // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
1.33
1.34 typedef True NodeNumTag;
1.35 typedef True EdgeNumTag;
1.36
1.37 ///Number of nodes.
1.38 - int nodeNum() const { return NodeNum; }
1.39 + int nodeNum() const { return _nodeNum; }
1.40 ///Number of edges.
1.41 - int edgeNum() const { return EdgeNum; }
1.42 + int edgeNum() const { return _edgeNum; }
1.43
1.44 /// Maximum node ID.
1.45
1.46 /// Maximum node ID.
1.47 ///\sa id(Node)
1.48 - int maxId(Node = INVALID) const { return NodeNum-1; }
1.49 + int maxId(Node = INVALID) const { return _nodeNum-1; }
1.50 /// Maximum edge ID.
1.51
1.52 /// Maximum edge ID.
1.53 ///\sa id(Edge)
1.54 - int maxId(Edge = INVALID) const { return EdgeNum-1; }
1.55 + int maxId(Edge = INVALID) const { return _edgeNum-1; }
1.56
1.57 - Node source(Edge e) const { return e.id % NodeNum; }
1.58 - Node target(Edge e) const { return e.id / NodeNum; }
1.59 + Node source(Edge e) const { return e.id % _nodeNum; }
1.60 + Node target(Edge e) const { return e.id / _nodeNum; }
1.61
1.62
1.63 /// Node ID.
1.64 @@ -103,6 +105,8 @@
1.65
1.66 static Edge fromId(int id, Edge) { return Edge(id);}
1.67
1.68 + typedef True FindEdgeTag;
1.69 +
1.70 /// Finds an edge between two nodes.
1.71
1.72 /// Finds an edge from node \c u to node \c v.
1.73 @@ -111,8 +115,7 @@
1.74 /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.75 /// the next edge from \c u to \c v after \c prev.
1.76 /// \return The found edge or INVALID if there is no such an edge.
1.77 - Edge findEdge(Node u,Node v, Edge prev = INVALID)
1.78 - {
1.79 + Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
1.80 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
1.81 }
1.82
1.83 @@ -137,12 +140,12 @@
1.84 friend class FullGraphBase;
1.85
1.86 protected:
1.87 - int id; // NodeNum * target + source;
1.88 + int id; // _nodeNum * target + source;
1.89
1.90 Edge(int _id) : id(_id) {}
1.91
1.92 Edge(const FullGraphBase& _graph, int source, int target)
1.93 - : id(_graph.NodeNum * target+source) {}
1.94 + : id(_graph._nodeNum * target+source) {}
1.95 public:
1.96 Edge() { }
1.97 Edge (Invalid) { id = -1; }
1.98 @@ -152,7 +155,7 @@
1.99 };
1.100
1.101 void first(Node& node) const {
1.102 - node.id = NodeNum-1;
1.103 + node.id = _nodeNum-1;
1.104 }
1.105
1.106 static void next(Node& node) {
1.107 @@ -160,7 +163,7 @@
1.108 }
1.109
1.110 void first(Edge& edge) const {
1.111 - edge.id = EdgeNum-1;
1.112 + edge.id = _edgeNum-1;
1.113 }
1.114
1.115 static void next(Edge& edge) {
1.116 @@ -168,43 +171,45 @@
1.117 }
1.118
1.119 void firstOut(Edge& edge, const Node& node) const {
1.120 - edge.id = EdgeNum + node.id - NodeNum;
1.121 + edge.id = _edgeNum + node.id - _nodeNum;
1.122 }
1.123
1.124 void nextOut(Edge& edge) const {
1.125 - edge.id -= NodeNum;
1.126 + edge.id -= _nodeNum;
1.127 if (edge.id < 0) edge.id = -1;
1.128 }
1.129
1.130 void firstIn(Edge& edge, const Node& node) const {
1.131 - edge.id = node.id * NodeNum;
1.132 + edge.id = node.id * _nodeNum;
1.133 }
1.134
1.135 void nextIn(Edge& edge) const {
1.136 ++edge.id;
1.137 - if (edge.id % NodeNum == 0) edge.id = -1;
1.138 + if (edge.id % _nodeNum == 0) edge.id = -1;
1.139 }
1.140
1.141 };
1.142
1.143
1.144 - typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
1.145 - typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
1.146 - typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;
1.147 + typedef AlterableGraphExtender<FullGraphBase>
1.148 + AlterableFullGraphBase;
1.149 + typedef IterableGraphExtender<AlterableFullGraphBase>
1.150 + IterableFullGraphBase;
1.151 + typedef DefaultMappableGraphExtender<IterableFullGraphBase>
1.152 + MappableFullGraphBase;
1.153
1.154 - /// \addtogroup graphs
1.155 - /// @{
1.156 -
1.157 - ///A full graph class.
1.158 -
1.159 - ///This is a simple and fast directed full graph implementation.
1.160 - ///It is completely static, so you can neither add nor delete either
1.161 - ///edges or nodes.
1.162 - ///Thus it conforms to
1.163 - ///the \ref concept::StaticGraph "StaticGraph" concept
1.164 - ///\sa concept::StaticGraph.
1.165 + /// \ingroup graphs
1.166 ///
1.167 - ///\author Alpar Juttner
1.168 + /// \brief A full graph class.
1.169 + ///
1.170 + /// This is a simple and fast directed full graph implementation.
1.171 + /// It is completely static, so you can neither add nor delete either
1.172 + /// edges or nodes.
1.173 + /// Thus it conforms to
1.174 + /// the \ref concept::StaticGraph "StaticGraph" concept
1.175 + /// \sa concept::StaticGraph.
1.176 + ///
1.177 + /// \author Alpar Juttner
1.178 class FullGraph : public MappableFullGraphBase {
1.179 public:
1.180
1.181 @@ -213,10 +218,9 @@
1.182
1.183 ///@}
1.184
1.185 - // Base graph class for UndirFullGraph.
1.186 class UndirFullGraphBase {
1.187 - int NodeNum;
1.188 - int EdgeNum;
1.189 + int _nodeNum;
1.190 + int _edgeNum;
1.191 public:
1.192
1.193 typedef UndirFullGraphBase Graph;
1.194 @@ -230,29 +234,29 @@
1.195
1.196
1.197 ///Creates a full graph with \c n nodes.
1.198 - void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }
1.199 + void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
1.200 ///
1.201 // FullGraphBase(const FullGraphBase &_g)
1.202 - // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
1.203 + // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
1.204
1.205 typedef True NodeNumTag;
1.206 typedef True EdgeNumTag;
1.207
1.208 ///Number of nodes.
1.209 - int nodeNum() const { return NodeNum; }
1.210 + int nodeNum() const { return _nodeNum; }
1.211 ///Number of edges.
1.212 - int edgeNum() const { return EdgeNum; }
1.213 + int edgeNum() const { return _edgeNum; }
1.214
1.215 /// Maximum node ID.
1.216
1.217 /// Maximum node ID.
1.218 ///\sa id(Node)
1.219 - int maxId(Node = INVALID) const { return NodeNum-1; }
1.220 + int maxId(Node = INVALID) const { return _nodeNum-1; }
1.221 /// Maximum edge ID.
1.222
1.223 /// Maximum edge ID.
1.224 ///\sa id(Edge)
1.225 - int maxId(Edge = INVALID) const { return EdgeNum-1; }
1.226 + int maxId(Edge = INVALID) const { return _edgeNum-1; }
1.227
1.228 Node source(Edge e) const {
1.229 /// \todo we may do it faster
1.230 @@ -319,12 +323,12 @@
1.231 friend class UndirFullGraphBase;
1.232
1.233 protected:
1.234 - int id; // NodeNum * target + source;
1.235 + int id; // _nodeNum * target + source;
1.236
1.237 Edge(int _id) : id(_id) {}
1.238
1.239 Edge(const UndirFullGraphBase& _graph, int source, int target)
1.240 - : id(_graph.NodeNum * target+source) {}
1.241 + : id(_graph._nodeNum * target+source) {}
1.242 public:
1.243 Edge() { }
1.244 Edge (Invalid) { id = -1; }
1.245 @@ -334,7 +338,7 @@
1.246 };
1.247
1.248 void first(Node& node) const {
1.249 - node.id = NodeNum-1;
1.250 + node.id = _nodeNum-1;
1.251 }
1.252
1.253 static void next(Node& node) {
1.254 @@ -342,7 +346,7 @@
1.255 }
1.256
1.257 void first(Edge& edge) const {
1.258 - edge.id = EdgeNum-1;
1.259 + edge.id = _edgeNum-1;
1.260 }
1.261
1.262 static void next(Edge& edge) {
1.263 @@ -369,19 +373,39 @@
1.264 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
1.265 int target = e.id - (source) * (source - 1) / 2; ++target;
1.266 ++source;
1.267 - e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;
1.268 + e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
1.269 }
1.270
1.271 };
1.272
1.273 - /// \addtogroup graphs
1.274 - /// @{
1.275 + typedef UndirGraphExtender<UndirFullGraphBase>
1.276 + UndirUndirFullGraphBase;
1.277 + typedef AlterableUndirGraphExtender<UndirUndirFullGraphBase>
1.278 + AlterableUndirFullGraphBase;
1.279 + typedef IterableUndirGraphExtender<AlterableUndirFullGraphBase>
1.280 + IterableUndirFullGraphBase;
1.281 + typedef MappableUndirGraphExtender<IterableUndirFullGraphBase>
1.282 + MappableUndirFullGraphBase;
1.283
1.284 -
1.285 - /// \todo UndirFullGraph from the UndirFullGraphBase
1.286 -
1.287 -
1.288 - /// @}
1.289 + /// \ingroup graphs
1.290 + ///
1.291 + /// \brief An undirected full graph class.
1.292 + ///
1.293 + /// This is a simple and fast directed full graph implementation.
1.294 + /// It is completely static, so you can neither add nor delete either
1.295 + /// edges or nodes.
1.296 + ///
1.297 + /// The main difference beetween the \e FullGraph and \e UndirFullGraph class
1.298 + /// is that this class conforms to the undirected graph concept and
1.299 + /// it does not contain the hook edges.
1.300 + ///
1.301 + /// \sa FullGraph
1.302 + ///
1.303 + /// \author Balazs Dezso
1.304 + class UndirFullGraph : public MappableUndirFullGraphBase {
1.305 + public:
1.306 + UndirFullGraph(int n) { construct(n); }
1.307 + };
1.308
1.309 } //namespace lemon
1.310