00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_GRAPH_EXTENDER_H
00020 #define LEMON_GRAPH_EXTENDER_H
00021
00022 #include <lemon/invalid.h>
00023 #include <lemon/error.h>
00024
00025 namespace lemon {
00026
00027 template <typename _Base>
00028 class GraphExtender : public _Base {
00029 public:
00030
00031 typedef _Base Parent;
00032 typedef GraphExtender Graph;
00033
00034 typedef typename Parent::Node Node;
00035 typedef typename Parent::Edge Edge;
00036
00037 int maxId(Node) const {
00038 return Parent::maxNodeId();
00039 }
00040
00041 int maxId(Edge) const {
00042 return Parent::maxEdgeId();
00043 }
00044
00045 Node fromId(int id, Node) const {
00046 return Parent::nodeFromId(id);
00047 }
00048
00049 Edge fromId(int id, Edge) const {
00050 return Parent::edgeFromId(id);
00051 }
00052
00053 Node oppositeNode(const Node &n, const Edge &e) const {
00054 if (n == Parent::source(e))
00055 return Parent::target(e);
00056 else if(n==Parent::target(e))
00057 return Parent::source(e);
00058 else
00059 return INVALID;
00060 }
00061
00062 };
00063
00064 template <typename _Base>
00065 class UGraphExtender : public _Base {
00066 typedef _Base Parent;
00067 typedef UGraphExtender Graph;
00068
00069 public:
00070
00071 typedef typename Parent::Edge UEdge;
00072 typedef typename Parent::Node Node;
00073
00074 class Edge : public UEdge {
00075 friend class UGraphExtender;
00076
00077 protected:
00078
00079
00080 bool forward;
00081
00082 Edge(const UEdge &ue, bool _forward) :
00083 UEdge(ue), forward(_forward) {}
00084
00085 public:
00086 Edge() {}
00087
00089 Edge(Invalid i) : UEdge(i), forward(true) {}
00090
00091 bool operator==(const Edge &that) const {
00092 return forward==that.forward && UEdge(*this)==UEdge(that);
00093 }
00094 bool operator!=(const Edge &that) const {
00095 return forward!=that.forward || UEdge(*this)!=UEdge(that);
00096 }
00097 bool operator<(const Edge &that) const {
00098 return forward<that.forward ||
00099 (!(that.forward<forward) && UEdge(*this)<UEdge(that));
00100 }
00101 };
00102
00103
00107 Edge oppositeEdge(const Edge &e) const {
00108 return Edge(e,!e.forward);
00109 }
00110
00111 public:
00114 using Parent::source;
00115
00117 Node source(const Edge &e) const {
00118 return e.forward ? Parent::source(e) : Parent::target(e);
00119 }
00120
00123 using Parent::target;
00124
00126 Node target(const Edge &e) const {
00127 return e.forward ? Parent::target(e) : Parent::source(e);
00128 }
00129
00130 Node oppositeNode(const Node &n, const UEdge &e) const {
00131 if( n == Parent::source(e))
00132 return Parent::target(e);
00133 else if( n == Parent::target(e))
00134 return Parent::source(e);
00135 else
00136 return INVALID;
00137 }
00138
00144 Edge direct(const UEdge &ue, const Node &s) const {
00145 return Edge(ue, s == source(ue));
00146 }
00147
00153 Edge direct(const UEdge &ue, bool d) const {
00154 return Edge(ue, d);
00155 }
00156
00162 bool direction(const Edge &e) const { return e.forward; }
00163
00164
00165 using Parent::first;
00166 void first(Edge &e) const {
00167 Parent::first(e);
00168 e.forward=true;
00169 }
00170
00171 using Parent::next;
00172 void next(Edge &e) const {
00173 if( e.forward ) {
00174 e.forward = false;
00175 }
00176 else {
00177 Parent::next(e);
00178 e.forward = true;
00179 }
00180 }
00181
00182 public:
00183
00184 void firstOut(Edge &e, const Node &n) const {
00185 Parent::firstIn(e,n);
00186 if( UEdge(e) != INVALID ) {
00187 e.forward = false;
00188 }
00189 else {
00190 Parent::firstOut(e,n);
00191 e.forward = true;
00192 }
00193 }
00194 void nextOut(Edge &e) const {
00195 if( ! e.forward ) {
00196 Node n = Parent::target(e);
00197 Parent::nextIn(e);
00198 if( UEdge(e) == INVALID ) {
00199 Parent::firstOut(e, n);
00200 e.forward = true;
00201 }
00202 }
00203 else {
00204 Parent::nextOut(e);
00205 }
00206 }
00207
00208 void firstIn(Edge &e, const Node &n) const {
00209 Parent::firstOut(e,n);
00210 if( UEdge(e) != INVALID ) {
00211 e.forward = false;
00212 }
00213 else {
00214 Parent::firstIn(e,n);
00215 e.forward = true;
00216 }
00217 }
00218 void nextIn(Edge &e) const {
00219 if( ! e.forward ) {
00220 Node n = Parent::source(e);
00221 Parent::nextOut(e);
00222 if( UEdge(e) == INVALID ) {
00223 Parent::firstIn(e, n);
00224 e.forward = true;
00225 }
00226 }
00227 else {
00228 Parent::nextIn(e);
00229 }
00230 }
00231
00232 void firstInc(UEdge &e, const Node &n) const {
00233 Parent::firstOut(e, n);
00234 if (e != INVALID) return;
00235 Parent::firstIn(e, n);
00236 }
00237 void nextInc(UEdge &e, const Node &n) const {
00238 if (Parent::source(e) == n) {
00239 Parent::nextOut(e);
00240 if (e != INVALID) return;
00241 Parent::firstIn(e, n);
00242 } else {
00243 Parent::nextIn(e);
00244 }
00245 }
00246
00247 void firstInc(UEdge &e, bool &d, const Node &n) const {
00248 d = true;
00249 Parent::firstOut(e, n);
00250 if (e != INVALID) return;
00251 d = false;
00252 Parent::firstIn(e, n);
00253 }
00254 void nextInc(UEdge &e, bool &d) const {
00255 if (d) {
00256 Node s = Parent::source(e);
00257 Parent::nextOut(e);
00258 if (e != INVALID) return;
00259 d = false;
00260 Parent::firstIn(e, s);
00261 } else {
00262 Parent::nextIn(e);
00263 }
00264 }
00265
00266
00267
00270
00271
00272
00273
00274
00275 int id(const Node &n) const {
00276 return Parent::id(n);
00277 }
00278
00279 int id(const UEdge &e) const {
00280 return Parent::id(e);
00281 }
00282
00283 int id(const Edge &e) const {
00284 return 2 * Parent::id(e) + int(e.forward);
00285 }
00286
00287 int maxNodeId() const {
00288 return Parent::maxNodeId();
00289 }
00290
00291 int maxEdgeId() const {
00292 return 2 * Parent::maxEdgeId() + 1;
00293 }
00294
00295 int maxUEdgeId() const {
00296 return Parent::maxEdgeId();
00297 }
00298
00299 int maxId(Node) const {
00300 return maxNodeId();
00301 }
00302
00303 int maxId(Edge) const {
00304 return maxEdgeId();
00305 }
00306 int maxId(UEdge) const {
00307 return maxUEdgeId();
00308 }
00309
00310 int edgeNum() const {
00311 return 2 * Parent::edgeNum();
00312 }
00313
00314 int uEdgeNum() const {
00315 return Parent::edgeNum();
00316 }
00317
00318 Node nodeFromId(int id) const {
00319 return Parent::nodeFromId(id);
00320 }
00321
00322 Edge edgeFromId(int id) const {
00323 return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
00324 }
00325
00326 UEdge uEdgeFromId(int id) const {
00327 return Parent::edgeFromId(id >> 1);
00328 }
00329
00330 Node fromId(int id, Node) const {
00331 return nodeFromId(id);
00332 }
00333
00334 Edge fromId(int id, Edge) const {
00335 return edgeFromId(id);
00336 }
00337
00338 UEdge fromId(int id, UEdge) const {
00339 return uEdgeFromId(id);
00340 }
00341
00342
00343 Edge findEdge(Node source, Node target, Edge prev) const {
00344 if (prev == INVALID) {
00345 UEdge edge = Parent::findEdge(source, target);
00346 if (edge != INVALID) return direct(edge, true);
00347 edge = Parent::findEdge(target, source);
00348 if (edge != INVALID) return direct(edge, false);
00349 } else if (direction(prev)) {
00350 UEdge edge = Parent::findEdge(source, target, prev);
00351 if (edge != INVALID) return direct(edge, true);
00352 edge = Parent::findEdge(target, source);
00353 if (edge != INVALID) return direct(edge, false);
00354 } else {
00355 UEdge edge = Parent::findEdge(target, source, prev);
00356 if (edge != INVALID) return direct(edge, false);
00357 }
00358 return INVALID;
00359 }
00360
00361 UEdge findUEdge(Node source, Node target, UEdge prev) const {
00362 if (prev == INVALID) {
00363 UEdge edge = Parent::findEdge(source, target);
00364 if (edge != INVALID) return edge;
00365 edge = Parent::findEdge(target, source);
00366 if (edge != INVALID) return edge;
00367 } else if (Parent::source(prev) == source) {
00368 UEdge edge = Parent::findEdge(source, target, prev);
00369 if (edge != INVALID) return edge;
00370 edge = Parent::findEdge(target, source);
00371 if (edge != INVALID) return edge;
00372 } else {
00373 UEdge edge = Parent::findEdge(target, source, prev);
00374 if (edge != INVALID) return edge;
00375 }
00376 return INVALID;
00377 }
00378
00379 };
00380
00381
00382 template <typename _Base>
00383 class BpUGraphExtender : public _Base {
00384 public:
00385 typedef _Base Parent;
00386 typedef BpUGraphExtender Graph;
00387
00388 typedef typename Parent::Node Node;
00389 typedef typename Parent::Edge UEdge;
00390
00391 using Parent::first;
00392 using Parent::next;
00393
00394 using Parent::id;
00395
00396 Node source(const UEdge& edge) const {
00397 return aNode(edge);
00398 }
00399 Node target(const UEdge& edge) const {
00400 return bNode(edge);
00401 }
00402
00403 void firstInc(UEdge& edge, bool& direction, const Node& node) const {
00404 if (Parent::aNode(node)) {
00405 Parent::firstOut(edge, node);
00406 direction = true;
00407 } else {
00408 Parent::firstIn(edge, node);
00409 direction = static_cast<UEdge&>(edge) == INVALID;
00410 }
00411 }
00412 void nextInc(UEdge& edge, bool& direction) const {
00413 if (direction) {
00414 Parent::nextOut(edge);
00415 } else {
00416 Parent::nextIn(edge);
00417 if (edge == INVALID) direction = true;
00418 }
00419 }
00420
00421 int maxUEdgeId() const {
00422 return Parent::maxEdgeId();
00423 }
00424
00425 UEdge uEdgeFromId(int id) const {
00426 return Parent::edgeFromId(id);
00427 }
00428
00429 class Edge : public UEdge {
00430 friend class BpUGraphExtender;
00431 protected:
00432 bool forward;
00433
00434 Edge(const UEdge& edge, bool _forward)
00435 : UEdge(edge), forward(_forward) {}
00436
00437 public:
00438 Edge() {}
00439 Edge (Invalid) : UEdge(INVALID), forward(true) {}
00440 bool operator==(const Edge& i) const {
00441 return UEdge::operator==(i) && forward == i.forward;
00442 }
00443 bool operator!=(const Edge& i) const {
00444 return UEdge::operator!=(i) || forward != i.forward;
00445 }
00446 bool operator<(const Edge& i) const {
00447 return UEdge::operator<(i) ||
00448 (!(i.forward<forward) && UEdge(*this)<UEdge(i));
00449 }
00450 };
00451
00452 void first(Edge& edge) const {
00453 Parent::first(static_cast<UEdge&>(edge));
00454 edge.forward = true;
00455 }
00456
00457 void next(Edge& edge) const {
00458 if (!edge.forward) {
00459 Parent::next(static_cast<UEdge&>(edge));
00460 }
00461 edge.forward = !edge.forward;
00462 }
00463
00464 void firstOut(Edge& edge, const Node& node) const {
00465 if (Parent::aNode(node)) {
00466 Parent::firstOut(edge, node);
00467 edge.forward = true;
00468 } else {
00469 Parent::firstIn(edge, node);
00470 edge.forward = static_cast<UEdge&>(edge) == INVALID;
00471 }
00472 }
00473 void nextOut(Edge& edge) const {
00474 if (edge.forward) {
00475 Parent::nextOut(edge);
00476 } else {
00477 Parent::nextIn(edge);
00478 edge.forward = static_cast<UEdge&>(edge) == INVALID;
00479 }
00480 }
00481
00482 void firstIn(Edge& edge, const Node& node) const {
00483 if (Parent::bNode(node)) {
00484 Parent::firstIn(edge, node);
00485 edge.forward = true;
00486 } else {
00487 Parent::firstOut(edge, node);
00488 edge.forward = static_cast<UEdge&>(edge) == INVALID;
00489 }
00490 }
00491 void nextIn(Edge& edge) const {
00492 if (edge.forward) {
00493 Parent::nextIn(edge);
00494 } else {
00495 Parent::nextOut(edge);
00496 edge.forward = static_cast<UEdge&>(edge) == INVALID;
00497 }
00498 }
00499
00500 Node source(const Edge& edge) const {
00501 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
00502 }
00503 Node target(const Edge& edge) const {
00504 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
00505 }
00506
00507 bool direction(const Edge& edge) const {
00508 return edge.forward;
00509 }
00510
00511 Edge direct(const UEdge& edge, const Node& node) const {
00512 return Edge(edge, node == Parent::source(edge));
00513 }
00514
00515 Edge direct(const UEdge& edge, bool direction) const {
00516 return Edge(edge, direction);
00517 }
00518
00519 Node oppositeNode(const UEdge& edge, const Node& node) const {
00520 return source(edge) == node ?
00521 target(edge) : source(edge);
00522 }
00523
00524 Edge oppositeEdge(const Edge& edge) const {
00525 return Edge(edge, !edge.forward);
00526 }
00527
00528 int id(const Edge& edge) const {
00529 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
00530 }
00531 Edge edgeFromId(int id) const {
00532 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
00533 }
00534 int maxEdgeId() const {
00535 return (Parent::maxId(UEdge()) << 1) + 1;
00536 }
00537
00538 class ANode : public Node {
00539 friend class BpUGraphExtender;
00540 public:
00541 ANode() {}
00542 ANode(const Node& node) : Node(node) {
00543 LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
00544 typename Parent::NodeSetError());
00545 }
00546 ANode(Invalid) : Node(INVALID) {}
00547 };
00548
00549 void first(ANode& node) const {
00550 Parent::firstANode(static_cast<Node&>(node));
00551 }
00552 void next(ANode& node) const {
00553 Parent::nextANode(static_cast<Node&>(node));
00554 }
00555
00556 int id(const ANode& node) const {
00557 return Parent::aNodeId(node);
00558 }
00559
00560 class BNode : public Node {
00561 friend class BpUGraphExtender;
00562 public:
00563 BNode() {}
00564 BNode(const Node& node) : Node(node) {
00565 LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
00566 typename Parent::NodeSetError());
00567 }
00568 BNode(Invalid) : Node(INVALID) {}
00569 };
00570
00571 void first(BNode& node) const {
00572 Parent::firstBNode(static_cast<Node&>(node));
00573 }
00574 void next(BNode& node) const {
00575 Parent::nextBNode(static_cast<Node&>(node));
00576 }
00577
00578 int id(const BNode& node) const {
00579 return Parent::aNodeId(node);
00580 }
00581
00582
00583
00584 int maxId(Node) const {
00585 return Parent::maxNodeId();
00586 }
00587 int maxId(BNode) const {
00588 return Parent::maxBNodeId();
00589 }
00590 int maxId(ANode) const {
00591 return Parent::maxANodeId();
00592 }
00593 int maxId(Edge) const {
00594 return maxEdgeId();
00595 }
00596 int maxId(UEdge) const {
00597 return maxUEdgeId();
00598 }
00599
00600
00601 Node fromId(int id, Node) const {
00602 return Parent::nodeFromId(id);
00603 }
00604 ANode fromId(int id, ANode) const {
00605 return Parent::fromANodeId(id);
00606 }
00607 BNode fromId(int id, BNode) const {
00608 return Parent::fromBNodeId(id);
00609 }
00610 Edge fromId(int id, Edge) const {
00611 return edgeFromId(id);
00612 }
00613 UEdge fromId(int id, UEdge) const {
00614 return uEdgeFromId(id);
00615 }
00616
00617 };
00618
00619 }
00620
00621 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H