00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00035
00036
00037
00038
00039
00040
00041 #ifndef LEMON_PATH_H
00042 #define LEMON_PATH_H
00043
00044 #include <deque>
00045 #include <vector>
00046 #include <algorithm>
00047
00048 #include <lemon/invalid.h>
00049
00050 namespace lemon {
00051
00054
00055
00067 template<typename Graph>
00068 class DirPath {
00069 public:
00071 typedef typename Graph::Edge GraphEdge;
00073 typedef typename Graph::Node GraphNode;
00074 class NodeIt;
00075 class EdgeIt;
00076
00077 protected:
00078 const Graph *gr;
00079 typedef std::vector<GraphEdge> Container;
00080 Container edges;
00081
00082 public:
00083
00086 DirPath(const Graph &_G) : gr(&_G) {}
00087
00092 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
00093 gr = P.gr;
00094 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00095 }
00096
00101 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
00102 gr = P.gr;
00103 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00104 }
00105
00107 int length() const { return edges.size(); }
00109 bool empty() const { return edges.empty(); }
00110
00112 void clear() { edges.clear(); }
00113
00118 GraphNode source() const {
00119 return empty() ? INVALID : gr->source(edges[0]);
00120 }
00125 GraphNode target() const {
00126 return empty() ? INVALID : gr->target(edges[length()-1]);
00127 }
00128
00133 template<typename It>
00134 It& first(It &i) const { return i=It(*this); }
00135
00137 NodeIt& nth(NodeIt &i, int n) const {
00138 return i=NodeIt(*this, n);
00139 }
00140
00142 EdgeIt& nth(EdgeIt &i, int n) const {
00143 return i=EdgeIt(*this, n);
00144 }
00145
00148 NodeIt target(const EdgeIt& e) const {
00149 return NodeIt(*this, e.idx+1);
00150 }
00151
00154 NodeIt source(const EdgeIt& e) const {
00155 return NodeIt(*this, e.idx);
00156 }
00157
00158
00159
00160
00169 class EdgeIt {
00170 friend class DirPath;
00171
00172 int idx;
00173 const DirPath *p;
00174 public:
00176 EdgeIt() {}
00178 EdgeIt(Invalid) : idx(-1), p(0) {}
00180 EdgeIt(const DirPath &_p, int _idx = 0) :
00181 idx(_idx), p(&_p) { validate(); }
00182
00184 bool valid() const { return idx!=-1; }
00185
00187 operator GraphEdge () const {
00188 return valid() ? p->edges[idx] : INVALID;
00189 }
00190
00192 EdgeIt& operator++() { ++idx; validate(); return *this; }
00193
00195 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
00197 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
00199 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
00200
00201 private:
00202 void validate() { if(idx >= p->length() ) idx=-1; }
00203 };
00204
00213 class NodeIt {
00214 friend class DirPath;
00215
00216 int idx;
00217 const DirPath *p;
00218 public:
00220 NodeIt() {}
00222 NodeIt(Invalid) : idx(-1), p(0) {}
00224 NodeIt(const DirPath &_p, int _idx = 0) :
00225 idx(_idx), p(&_p) { validate(); }
00226
00228 bool valid() const { return idx!=-1; }
00229
00231 operator const GraphNode& () const {
00232 if(idx >= p->length())
00233 return p->target();
00234 else if(idx >= 0)
00235 return p->gr->source(p->edges[idx]);
00236 else
00237 return INVALID;
00238 }
00240 NodeIt& operator++() { ++idx; validate(); return *this; }
00241
00243 bool operator==(const NodeIt& e) const { return idx==e.idx; }
00245 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
00247 bool operator<(const NodeIt& e) const { return idx<e.idx; }
00248
00249 private:
00250 void validate() { if(idx > p->length() ) idx=-1; }
00251 };
00252
00253 friend class Builder;
00254
00270 class Builder {
00271 DirPath &P;
00272 Container front, back;
00273
00274 public:
00277 Builder(DirPath &_p) : P(_p) {}
00278
00280
00286 void setStartNode(const GraphNode &) {}
00287
00289
00292 void pushFront(const GraphEdge& e) {
00293 front.push_back(e);
00294 }
00295
00297
00300 void pushBack(const GraphEdge& e) {
00301 back.push_back(e);
00302 }
00303
00305 void commit() {
00306 if( !front.empty() || !back.empty() ) {
00307 Container tmp;
00308 tmp.reserve(front.size()+back.size()+P.length());
00309 tmp.insert(tmp.end(), front.rbegin(), front.rend());
00310 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
00311 tmp.insert(tmp.end(), back.begin(), back.end());
00312 P.edges.swap(tmp);
00313 front.clear();
00314 back.clear();
00315 }
00316 }
00317
00319
00322
00323 void reserveFront(size_t r) {front.reserve(r);}
00324
00326
00329
00330 void reserveBack(size_t r) {back.reserve(r);}
00331
00332 private:
00333 bool empty() {
00334 return front.empty() && back.empty() && P.empty();
00335 }
00336
00337 GraphNode source() const {
00338 if( ! front.empty() )
00339 return P.gr->source(front[front.size()-1]);
00340 else if( ! P.empty() )
00341 return P.gr->source(P.edges[0]);
00342 else if( ! back.empty() )
00343 return P.gr->source(back[0]);
00344 else
00345 return INVALID;
00346 }
00347 GraphNode target() const {
00348 if( ! back.empty() )
00349 return P.gr->target(back[back.size()-1]);
00350 else if( ! P.empty() )
00351 return P.gr->target(P.edges[P.length()-1]);
00352 else if( ! front.empty() )
00353 return P.gr->target(front[0]);
00354 else
00355 return INVALID;
00356 }
00357
00358 };
00359
00360 };
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00389 template<typename Graph>
00390 class UPath {
00391 public:
00393 typedef typename Graph::Edge GraphEdge;
00395 typedef typename Graph::Node GraphNode;
00396 class NodeIt;
00397 class EdgeIt;
00398
00399 protected:
00400 const Graph *gr;
00401 typedef std::vector<GraphEdge> Container;
00402 Container edges;
00403
00404 public:
00405
00408 UPath(const Graph &_G) : gr(&_G) {}
00409
00414 UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
00415 gr = P.gr;
00416 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00417 }
00418
00423 UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
00424 gr = P.gr;
00425 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00426 }
00427
00429 size_t length() const { return edges.size(); }
00431 bool empty() const { return edges.empty(); }
00432
00434 void clear() { edges.clear(); }
00435
00440 GraphNode source() const {
00441 return empty() ? INVALID : gr->source(edges[0]);
00442 }
00447 GraphNode target() const {
00448 return empty() ? INVALID : gr->target(edges[length()-1]);
00449 }
00450
00455 template<typename It>
00456 It& first(It &i) const { return i=It(*this); }
00457
00459 NodeIt& nth(NodeIt &i, int n) const {
00460 return i=NodeIt(*this, n);
00461 }
00462
00464 EdgeIt& nth(EdgeIt &i, int n) const {
00465 return i=EdgeIt(*this, n);
00466 }
00467
00469 template<typename It>
00470 static
00471 bool valid(const It &i) { return i.valid(); }
00472
00474 template<typename It>
00475 static
00476 It& next(It &e) {
00477 return ++e;
00478 }
00479
00482 NodeIt target(const EdgeIt& e) const {
00483 return NodeIt(*this, e.idx+1);
00484 }
00485
00488 NodeIt source(const EdgeIt& e) const {
00489 return NodeIt(*this, e.idx);
00490 }
00491
00492
00493
00504 class EdgeIt {
00505 friend class UPath;
00506
00507 int idx;
00508 const UPath *p;
00509 public:
00511 EdgeIt() {}
00513 EdgeIt(Invalid) : idx(-1), p(0) {}
00515 EdgeIt(const UPath &_p, int _idx = 0) :
00516 idx(_idx), p(&_p) { validate(); }
00517
00519 bool valid() const { return idx!=-1; }
00520
00522 operator GraphEdge () const {
00523 return valid() ? p->edges[idx] : INVALID;
00524 }
00526 EdgeIt& operator++() { ++idx; validate(); return *this; }
00527
00529 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
00531 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
00533 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
00534
00535 private:
00536
00537
00538 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
00539 };
00540
00551 class NodeIt {
00552 friend class UPath;
00553
00554 int idx;
00555 const UPath *p;
00556 public:
00558 NodeIt() {}
00560 NodeIt(Invalid) : idx(-1), p(0) {}
00562 NodeIt(const UPath &_p, int _idx = 0) :
00563 idx(_idx), p(&_p) { validate(); }
00564
00566 bool valid() const { return idx!=-1; }
00567
00569 operator const GraphNode& () const {
00570 if(idx >= p->length())
00571 return p->target();
00572 else if(idx >= 0)
00573 return p->gr->source(p->edges[idx]);
00574 else
00575 return INVALID;
00576 }
00578 NodeIt& operator++() { ++idx; validate(); return *this; }
00579
00581 bool operator==(const NodeIt& e) const { return idx==e.idx; }
00583 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
00585 bool operator<(const NodeIt& e) const { return idx<e.idx; }
00586
00587 private:
00588 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
00589 };
00590
00591 friend class Builder;
00592
00608 class Builder {
00609 UPath &P;
00610 Container front, back;
00611
00612 public:
00615 Builder(UPath &_p) : P(_p) {}
00616
00618
00624 void setStartNode(const GraphNode &) {}
00625
00627
00630 void pushFront(const GraphEdge& e) {
00631 front.push_back(e);
00632 }
00633
00635
00638 void pushBack(const GraphEdge& e) {
00639 back.push_back(e);
00640 }
00641
00643 void commit() {
00644 if( !(front.empty() && back.empty()) ) {
00645 Container tmp;
00646 tmp.reserve(front.size()+back.size()+P.length());
00647 tmp.insert(tmp.end(), front.rbegin(), front.rend());
00648 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
00649 tmp.insert(tmp.end(), back.begin(), back.end());
00650 P.edges.swap(tmp);
00651 front.clear();
00652 back.clear();
00653 }
00654 }
00655
00656
00658
00661
00662 void reserveFront(size_t r) {front.reserve(r);}
00663
00665
00668
00669 void reserveBack(size_t r) {back.reserve(r);}
00670
00671 private:
00672 bool empty() {
00673 return front.empty() && back.empty() && P.empty();
00674 }
00675
00676 GraphNode source() const {
00677 if( ! front.empty() )
00678 return P.gr->source(front[front.size()-1]);
00679 else if( ! P.empty() )
00680 return P.gr->source(P.edges[0]);
00681 else if( ! back.empty() )
00682 return P.gr->source(back[0]);
00683 else
00684 return INVALID;
00685 }
00686 GraphNode target() const {
00687 if( ! back.empty() )
00688 return P.gr->target(back[back.size()-1]);
00689 else if( ! P.empty() )
00690 return P.gr->target(P.edges[P.length()-1]);
00691 else if( ! front.empty() )
00692 return P.gr->target(front[0]);
00693 else
00694 return INVALID;
00695 }
00696
00697 };
00698
00699 };
00700
00701
00703
00704 }
00705
00706 #endif // LEMON_PATH_H