00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_FULL_GRAPH_H
00020 #define LEMON_FULL_GRAPH_H
00021
00022 #include <cmath>
00023
00024
00025 #include <lemon/bits/iterable_graph_extender.h>
00026 #include <lemon/bits/alteration_notifier.h>
00027 #include <lemon/bits/static_map.h>
00028 #include <lemon/bits/graph_extender.h>
00029
00030 #include <lemon/invalid.h>
00031 #include <lemon/utility.h>
00032
00033
00037
00038
00039 namespace lemon {
00040
00041 class FullGraphBase {
00042 int _nodeNum;
00043 int _edgeNum;
00044 public:
00045
00046 typedef FullGraphBase Graph;
00047
00048 class Node;
00049 class Edge;
00050
00051 public:
00052
00053 FullGraphBase() {}
00054
00055
00057 void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
00059
00060
00061
00062 typedef True NodeNumTag;
00063 typedef True EdgeNumTag;
00064
00066 int nodeNum() const { return _nodeNum; }
00068 int edgeNum() const { return _edgeNum; }
00069
00071
00074 int maxNodeId() const { return _nodeNum-1; }
00076
00079 int maxEdgeId() const { return _edgeNum-1; }
00080
00081 Node source(Edge e) const { return e.id % _nodeNum; }
00082 Node target(Edge e) const { return e.id / _nodeNum; }
00083
00084
00086
00093
00094 static int id(Node v) { return v.id; }
00096
00103 static int id(Edge e) { return e.id; }
00104
00105 static Node nodeFromId(int id) { return Node(id);}
00106
00107 static Edge edgeFromId(int id) { return Edge(id);}
00108
00109 typedef True FindEdgeTag;
00110
00112
00119 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
00120 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
00121 }
00122
00123
00124 class Node {
00125 friend class FullGraphBase;
00126
00127 protected:
00128 int id;
00129 Node(int _id) : id(_id) {}
00130 public:
00131 Node() {}
00132 Node (Invalid) : id(-1) {}
00133 bool operator==(const Node node) const {return id == node.id;}
00134 bool operator!=(const Node node) const {return id != node.id;}
00135 bool operator<(const Node node) const {return id < node.id;}
00136 };
00137
00138
00139
00140 class Edge {
00141 friend class FullGraphBase;
00142
00143 protected:
00144 int id;
00145
00146 Edge(int _id) : id(_id) {}
00147
00148 Edge(const FullGraphBase& _graph, int source, int target)
00149 : id(_graph._nodeNum * target+source) {}
00150 public:
00151 Edge() { }
00152 Edge (Invalid) { id = -1; }
00153 bool operator==(const Edge edge) const {return id == edge.id;}
00154 bool operator!=(const Edge edge) const {return id != edge.id;}
00155 bool operator<(const Edge edge) const {return id < edge.id;}
00156 };
00157
00158 void first(Node& node) const {
00159 node.id = _nodeNum-1;
00160 }
00161
00162 static void next(Node& node) {
00163 --node.id;
00164 }
00165
00166 void first(Edge& edge) const {
00167 edge.id = _edgeNum-1;
00168 }
00169
00170 static void next(Edge& edge) {
00171 --edge.id;
00172 }
00173
00174 void firstOut(Edge& edge, const Node& node) const {
00175 edge.id = _edgeNum + node.id - _nodeNum;
00176 }
00177
00178 void nextOut(Edge& edge) const {
00179 edge.id -= _nodeNum;
00180 if (edge.id < 0) edge.id = -1;
00181 }
00182
00183 void firstIn(Edge& edge, const Node& node) const {
00184 edge.id = node.id * _nodeNum;
00185 }
00186
00187 void nextIn(Edge& edge) const {
00188 ++edge.id;
00189 if (edge.id % _nodeNum == 0) edge.id = -1;
00190 }
00191
00192 };
00193
00194 typedef StaticMappableGraphExtender<
00195 IterableGraphExtender<
00196 AlterableGraphExtender<
00197 GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase;
00198
00211 class FullGraph : public ExtendedFullGraphBase {
00212 public:
00213
00214 FullGraph(int n) { construct(n); }
00215 };
00216
00217
00218 class FullUGraphBase {
00219 int _nodeNum;
00220 int _edgeNum;
00221 public:
00222
00223 typedef FullUGraphBase Graph;
00224
00225 class Node;
00226 class Edge;
00227
00228 public:
00229
00230 FullUGraphBase() {}
00231
00232
00234 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
00236
00237
00238
00239 typedef True NodeNumTag;
00240 typedef True EdgeNumTag;
00241
00243 int nodeNum() const { return _nodeNum; }
00245 int edgeNum() const { return _edgeNum; }
00246
00248
00251 int maxNodeId() const { return _nodeNum-1; }
00253
00256 int maxEdgeId() const { return _edgeNum-1; }
00257
00258 Node source(Edge e) const {
00260 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
00261 }
00262
00263 Node target(Edge e) const {
00264 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00265 return Node(e.id - (source) * (source - 1) / 2);
00266 }
00267
00268
00270
00277
00278 static int id(Node v) { return v.id; }
00280
00287 static int id(Edge e) { return e.id; }
00288
00290
00297 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
00298 if (prev.id != -1 || u.id <= v.id) return -1;
00299 return Edge(u.id * (u.id - 1) / 2 + v.id);
00300 }
00301
00302 typedef True FindEdgeTag;
00303
00304
00305 class Node {
00306 friend class FullUGraphBase;
00307
00308 protected:
00309 int id;
00310 Node(int _id) { id = _id;}
00311 public:
00312 Node() {}
00313 Node (Invalid) { id = -1; }
00314 bool operator==(const Node node) const {return id == node.id;}
00315 bool operator!=(const Node node) const {return id != node.id;}
00316 bool operator<(const Node node) const {return id < node.id;}
00317 };
00318
00319
00320
00321 class Edge {
00322 friend class FullUGraphBase;
00323
00324 protected:
00325 int id;
00326
00327 Edge(int _id) : id(_id) {}
00328
00329 public:
00330 Edge() { }
00331 Edge (Invalid) { id = -1; }
00332 bool operator==(const Edge edge) const {return id == edge.id;}
00333 bool operator!=(const Edge edge) const {return id != edge.id;}
00334 bool operator<(const Edge edge) const {return id < edge.id;}
00335 };
00336
00337 void first(Node& node) const {
00338 node.id = _nodeNum - 1;
00339 }
00340
00341 static void next(Node& node) {
00342 --node.id;
00343 }
00344
00345 void first(Edge& edge) const {
00346 edge.id = _edgeNum - 1;
00347 }
00348
00349 static void next(Edge& edge) {
00350 --edge.id;
00351 }
00352
00353 void firstOut(Edge& edge, const Node& node) const {
00354 int src = node.id;
00355 int trg = 0;
00356 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
00357 }
00358
00360 void nextOut(Edge& edge) const {
00361 int src = source(edge).id;
00362 int trg = target(edge).id;
00363 ++trg;
00364 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
00365 }
00366
00367 void firstIn(Edge& edge, const Node& node) const {
00368 int src = node.id + 1;
00369 int trg = node.id;
00370 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
00371 }
00372
00373 void nextIn(Edge& edge) const {
00374 int src = source(edge).id;
00375 int trg = target(edge).id;
00376 ++src;
00377 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
00378 }
00379
00380 };
00381
00382 typedef StaticMappableUGraphExtender<
00383 IterableUGraphExtender<
00384 AlterableUGraphExtender<
00385 UGraphExtender<FullUGraphBase> > > > ExtendedFullUGraphBase;
00386
00402 class FullUGraph : public ExtendedFullUGraphBase {
00403 public:
00404 FullUGraph(int n) { construct(n); }
00405 };
00406
00407
00408 class FullBpUGraphBase {
00409 protected:
00410
00411 int _aNodeNum;
00412 int _bNodeNum;
00413
00414 int _edgeNum;
00415
00416 public:
00417
00418 class NodeSetError : public LogicError {
00419 virtual const char* exceptionName() const {
00420 return "lemon::FullBpUGraph::NodeSetError";
00421 }
00422 };
00423
00424 class Node {
00425 friend class FullBpUGraphBase;
00426 protected:
00427 int id;
00428
00429 Node(int _id) : id(_id) {}
00430 public:
00431 Node() {}
00432 Node(Invalid) { id = -1; }
00433 bool operator==(const Node i) const {return id==i.id;}
00434 bool operator!=(const Node i) const {return id!=i.id;}
00435 bool operator<(const Node i) const {return id<i.id;}
00436 };
00437
00438 class Edge {
00439 friend class FullBpUGraphBase;
00440 protected:
00441 int id;
00442
00443 Edge(int _id) { id = _id;}
00444 public:
00445 Edge() {}
00446 Edge (Invalid) { id = -1; }
00447 bool operator==(const Edge i) const {return id==i.id;}
00448 bool operator!=(const Edge i) const {return id!=i.id;}
00449 bool operator<(const Edge i) const {return id<i.id;}
00450 };
00451
00452 void construct(int aNodeNum, int bNodeNum) {
00453 _aNodeNum = aNodeNum;
00454 _bNodeNum = bNodeNum;
00455 _edgeNum = aNodeNum * bNodeNum;
00456 }
00457
00458 void firstANode(Node& node) const {
00459 node.id = 2 * _aNodeNum - 2;
00460 if (node.id < 0) node.id = -1;
00461 }
00462 void nextANode(Node& node) const {
00463 node.id -= 2;
00464 if (node.id < 0) node.id = -1;
00465 }
00466
00467 void firstBNode(Node& node) const {
00468 node.id = 2 * _bNodeNum - 1;
00469 }
00470 void nextBNode(Node& node) const {
00471 node.id -= 2;
00472 }
00473
00474 void first(Node& node) const {
00475 if (_aNodeNum > 0) {
00476 node.id = 2 * _aNodeNum - 2;
00477 } else {
00478 node.id = 2 * _bNodeNum - 1;
00479 }
00480 }
00481 void next(Node& node) const {
00482 node.id -= 2;
00483 if (node.id == -2) {
00484 node.id = 2 * _bNodeNum - 1;
00485 }
00486 }
00487
00488 void first(Edge& edge) const {
00489 edge.id = _edgeNum - 1;
00490 }
00491 void next(Edge& edge) const {
00492 --edge.id;
00493 }
00494
00495 void firstOut(Edge& edge, const Node& node) const {
00496 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
00497 edge.id = (node.id >> 1) * _bNodeNum;
00498 }
00499 void nextOut(Edge& edge) const {
00500 ++(edge.id);
00501 if (edge.id % _bNodeNum == 0) edge.id = -1;
00502 }
00503
00504 void firstIn(Edge& edge, const Node& node) const {
00505 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
00506 edge.id = (node.id >> 1);
00507 }
00508 void nextIn(Edge& edge) const {
00509 edge.id += _bNodeNum;
00510 if (edge.id >= _edgeNum) edge.id = -1;
00511 }
00512
00513 static int id(const Node& node) {
00514 return node.id;
00515 }
00516 static Node nodeFromId(int id) {
00517 return Node(id);
00518 }
00519 int maxNodeId() const {
00520 return _aNodeNum > _bNodeNum ?
00521 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
00522 }
00523
00524 static int id(const Edge& edge) {
00525 return edge.id;
00526 }
00527 static Edge edgeFromId(int id) {
00528 return Edge(id);
00529 }
00530 int maxEdgeId() const {
00531 return _edgeNum - 1;
00532 }
00533
00534 static int aNodeId(const Node& node) {
00535 return node.id >> 1;
00536 }
00537 static Node fromANodeId(int id, Node) {
00538 return Node(id << 1);
00539 }
00540 int maxANodeId() const {
00541 return _aNodeNum;
00542 }
00543
00544 static int bNodeId(const Node& node) {
00545 return node.id >> 1;
00546 }
00547 static Node fromBNodeId(int id) {
00548 return Node((id << 1) + 1);
00549 }
00550 int maxBNodeId() const {
00551 return _bNodeNum;
00552 }
00553
00554 Node aNode(const Edge& edge) const {
00555 return Node((edge.id / _bNodeNum) << 1);
00556 }
00557 Node bNode(const Edge& edge) const {
00558 return Node(((edge.id % _bNodeNum) << 1) + 1);
00559 }
00560
00561 static bool aNode(const Node& node) {
00562 return (node.id & 1) == 0;
00563 }
00564
00565 static bool bNode(const Node& node) {
00566 return (node.id & 1) == 1;
00567 }
00568
00569 static Node aNode(int index) {
00570 return Node(index << 1);
00571 }
00572
00573 static Node bNode(int index) {
00574 return Node((index << 1) + 1);
00575 }
00576
00577 };
00578
00579
00580 typedef StaticMappableBpUGraphExtender<
00581 IterableBpUGraphExtender<
00582 AlterableBpUGraphExtender<
00583 BpUGraphExtender <
00584 FullBpUGraphBase> > > >
00585 ExtendedFullBpUGraphBase;
00586
00587
00599 class FullBpUGraph :
00600 public ExtendedFullBpUGraphBase {
00601 public:
00602 typedef ExtendedFullBpUGraphBase Parent;
00603 FullBpUGraph(int aNodeNum, int bNodeNum) {
00604 Parent::construct(aNodeNum, bNodeNum);
00605 }
00606 };
00607
00608 }
00609
00610
00611 #endif //LEMON_FULL_GRAPH_H