1.1 --- a/src/lemon/full_graph.h Mon Oct 25 13:29:46 2004 +0000
1.2 +++ b/src/lemon/full_graph.h Wed Oct 27 22:38:50 2004 +0000
1.3 @@ -17,20 +17,21 @@
1.4 #ifndef LEMON_FULL_GRAPH_H
1.5 #define LEMON_FULL_GRAPH_H
1.6
1.7 +
1.8 +#include <lemon/idmappable_graph_extender.h>
1.9 +
1.10 +#include <lemon/iterable_graph_extender.h>
1.11 +
1.12 +#include <lemon/alteration_observer_registry.h>
1.13 +#include <lemon/default_map.h>
1.14 +
1.15 ///\ingroup graphs
1.16 ///\file
1.17 ///\brief FullGraph and SymFullGraph classes.
1.18
1.19 -#include <vector>
1.20 -#include <climits>
1.21
1.22 #include <lemon/invalid.h>
1.23
1.24 -#include <lemon/map_registry.h>
1.25 -#include <lemon/array_map.h>
1.26 -
1.27 -#include <lemon/map_defines.h>
1.28 -
1.29 namespace lemon {
1.30
1.31 /// \addtogroup graphs
1.32 @@ -48,34 +49,26 @@
1.33 ///\todo Don't we need SymEdgeMap?
1.34 ///
1.35 ///\author Alpar Juttner
1.36 - class FullGraph {
1.37 + class FullGraphBase {
1.38 int NodeNum;
1.39 int EdgeNum;
1.40 public:
1.41
1.42 - typedef FullGraph Graph;
1.43 + typedef FullGraphBase Graph;
1.44
1.45 class Node;
1.46 class Edge;
1.47
1.48 - class NodeIt;
1.49 - class EdgeIt;
1.50 - class OutEdgeIt;
1.51 - class InEdgeIt;
1.52 -
1.53 -
1.54 - // Create map registries.
1.55 - CREATE_MAP_REGISTRIES;
1.56 - // Create node and edge maps.
1.57 - CREATE_MAPS(ArrayMap);
1.58 -
1.59 public:
1.60
1.61 + FullGraphBase() {}
1.62 +
1.63 +
1.64 ///Creates a full graph with \c n nodes.
1.65 - FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
1.66 + void construct(int n) { NodeNum = n; EdgeNum = n * n; }
1.67 ///
1.68 - FullGraph(const FullGraph &_g)
1.69 - : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
1.70 + // FullGraphBase(const FullGraphBase &_g)
1.71 + // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
1.72
1.73 ///Number of nodes.
1.74 int nodeNum() const { return NodeNum; }
1.75 @@ -93,17 +86,9 @@
1.76 ///\sa id(Edge)
1.77 int maxEdgeId() const { return EdgeNum-1; }
1.78
1.79 - Node tail(Edge e) const { return e.n%NodeNum; }
1.80 - Node head(Edge e) const { return e.n/NodeNum; }
1.81 + Node tail(Edge e) const { return e.id % NodeNum; }
1.82 + Node head(Edge e) const { return e.id / NodeNum; }
1.83
1.84 - NodeIt& first(NodeIt& v) const {
1.85 - v=NodeIt(*this); return v; }
1.86 - EdgeIt& first(EdgeIt& e) const {
1.87 - e=EdgeIt(*this); return e; }
1.88 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.89 - e=OutEdgeIt(*this,v); return e; }
1.90 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.91 - e=InEdgeIt(*this,v); return e; }
1.92
1.93 /// Node ID.
1.94
1.95 @@ -113,7 +98,8 @@
1.96 ///
1.97 /// The ID of the \ref INVALID node is -1.
1.98 ///\return The ID of the node \c v.
1.99 - static int id(Node v) { return v.n; }
1.100 +
1.101 + static int id(Node v) { return v.id; }
1.102 /// Edge ID.
1.103
1.104 /// The ID of a valid Edge is a nonnegative integer not greater than
1.105 @@ -122,7 +108,7 @@
1.106 ///
1.107 /// The ID of the \ref INVALID edge is -1.
1.108 ///\return The ID of the edge \c e.
1.109 - static int id(Edge e) { return e.n; }
1.110 + static int id(Edge e) { return e.id; }
1.111
1.112 /// Finds an edge between two nodes.
1.113
1.114 @@ -134,110 +120,102 @@
1.115 /// \return The found edge or INVALID if there is no such an edge.
1.116 Edge findEdge(Node u,Node v, Edge prev = INVALID)
1.117 {
1.118 - return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
1.119 + return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
1.120 }
1.121
1.122
1.123 class Node {
1.124 - friend class FullGraph;
1.125 - template <typename T> friend class NodeMap;
1.126 -
1.127 - friend class Edge;
1.128 - friend class OutEdgeIt;
1.129 - friend class InEdgeIt;
1.130 - friend class SymEdge;
1.131 + friend class FullGraphBase;
1.132
1.133 protected:
1.134 - int n;
1.135 - friend int FullGraph::id(Node v);
1.136 - Node(int nn) {n=nn;}
1.137 + int id;
1.138 + Node(int _id) { id = _id;}
1.139 public:
1.140 Node() {}
1.141 - Node (Invalid) { n=-1; }
1.142 - bool operator==(const Node i) const {return n==i.n;}
1.143 - bool operator!=(const Node i) const {return n!=i.n;}
1.144 - bool operator<(const Node i) const {return n<i.n;}
1.145 + Node (Invalid) { id = -1; }
1.146 + bool operator==(const Node node) const {return id == node.id;}
1.147 + bool operator!=(const Node node) const {return id != node.id;}
1.148 + bool operator<(const Node node) const {return id < node.id;}
1.149 };
1.150
1.151 - class NodeIt : public Node {
1.152 - const FullGraph *G;
1.153 - friend class FullGraph;
1.154 +
1.155 +
1.156 + class Edge {
1.157 + friend class FullGraphBase;
1.158 +
1.159 + protected:
1.160 + int id; // NodeNum * head + tail;
1.161 +
1.162 + Edge(int _id) : id(_id) {}
1.163 +
1.164 + Edge(const FullGraphBase& _graph, int tail, int head)
1.165 + : id(_graph.NodeNum * head+tail) {}
1.166 public:
1.167 - NodeIt() : Node() { }
1.168 - NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
1.169 - NodeIt(Invalid i) : Node(i) { }
1.170 - NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
1.171 - ///\todo Undocumented conversion Node -\> NodeIt.
1.172 - NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
1.173 + Edge() { }
1.174 + Edge (Invalid) { id = -1; }
1.175 + bool operator==(const Edge edge) const {return id == edge.id;}
1.176 + bool operator!=(const Edge edge) const {return id != edge.id;}
1.177 + bool operator<(const Edge edge) const {return id < edge.id;}
1.178 };
1.179
1.180 - class Edge {
1.181 - friend class FullGraph;
1.182 - template <typename T> friend class EdgeMap;
1.183 -
1.184 - friend class Node;
1.185 - friend class NodeIt;
1.186 - protected:
1.187 - int n; //NodeNum*head+tail;
1.188 - friend int FullGraph::id(Edge e);
1.189 + void first(Node& node) const {
1.190 + node.id = NodeNum-1;
1.191 + }
1.192
1.193 - Edge(int nn) : n(nn) {}
1.194 - Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
1.195 - public:
1.196 - Edge() { }
1.197 - Edge (Invalid) { n=-1; }
1.198 - bool operator==(const Edge i) const {return n==i.n;}
1.199 - bool operator!=(const Edge i) const {return n!=i.n;}
1.200 - bool operator<(const Edge i) const {return n<i.n;}
1.201 - ///\bug This is a workaround until somebody tells me how to
1.202 - ///make class \c SymFullGraph::SymEdgeMap friend of Edge
1.203 - int &idref() {return n;}
1.204 - const int &idref() const {return n;}
1.205 - };
1.206 + static void next(Node& node) {
1.207 + --node.id;
1.208 + }
1.209 +
1.210 + void first(Edge& edge) const {
1.211 + edge.id = EdgeNum-1;
1.212 + }
1.213 +
1.214 + static void next(Edge& edge) {
1.215 + --edge.id;
1.216 + }
1.217 +
1.218 + void firstOut(Edge& edge, const Node& node) const {
1.219 + edge.id = EdgeNum + node.id - NodeNum;
1.220 + }
1.221 +
1.222 + void nextOut(Edge& edge) const {
1.223 + edge.id -= NodeNum;
1.224 + if (edge.id < 0) edge.id = -1;
1.225 + }
1.226 +
1.227 + void firstIn(Edge& edge, const Node& node) const {
1.228 + edge.id = node.id * NodeNum;
1.229 + }
1.230
1.231 - class EdgeIt : public Edge {
1.232 - friend class FullGraph;
1.233 - public:
1.234 - EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
1.235 - EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
1.236 - EdgeIt (Invalid i) : Edge(i) { }
1.237 - EdgeIt() : Edge() { }
1.238 - EdgeIt& operator++() { --n; return *this; }
1.239 -
1.240 - ///\bug This is a workaround until somebody tells me how to
1.241 - ///make class \c SymFullGraph::SymEdgeMap friend of Edge
1.242 - int &idref() {return n;}
1.243 - };
1.244 -
1.245 - class OutEdgeIt : public Edge {
1.246 - const FullGraph *G;
1.247 - friend class FullGraph;
1.248 - public:
1.249 - OutEdgeIt() : Edge() { }
1.250 - OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
1.251 - OutEdgeIt (Invalid i) : Edge(i) { }
1.252 -
1.253 - OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
1.254 -
1.255 - OutEdgeIt& operator++()
1.256 - { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
1.257 -
1.258 - };
1.259 -
1.260 - class InEdgeIt : public Edge {
1.261 - const FullGraph *G;
1.262 - friend class FullGraph;
1.263 - public:
1.264 - InEdgeIt() : Edge() { }
1.265 - InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
1.266 - InEdgeIt (Invalid i) : Edge(i) { }
1.267 - InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
1.268 - InEdgeIt& operator++()
1.269 - { if(!((++n)%G->NodeNum)) n=-1; return *this; }
1.270 - };
1.271 + void nextIn(Edge& edge) const {
1.272 + ++edge.id;
1.273 + if (edge.id % NodeNum == 0) edge.id = -1;
1.274 + }
1.275
1.276 };
1.277
1.278 +
1.279 + typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
1.280 + typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
1.281 + typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase;
1.282 + typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase;
1.283 +
1.284 + class FullGraph : public MappableFullGraphBase {
1.285 + public:
1.286 +
1.287 + FullGraph(int n) { construct(n); }
1.288 + };
1.289 +
1.290 + template <>
1.291 + int countNodes<FullGraph>(const FullGraph& graph) {
1.292 + return graph.nodeNum();
1.293 + }
1.294 +
1.295 + template <>
1.296 + int countEdges<FullGraph>(const FullGraph& graph) {
1.297 + return graph.edgeNum();
1.298 + }
1.299 +
1.300 /// @}
1.301
1.302 } //namespace lemon