00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00033
00034
00035
00036
00037
00038
00039 #ifndef LEMON_PATH_H
00040 #define LEMON_PATH_H
00041
00042 #include <deque>
00043 #include <vector>
00044 #include <algorithm>
00045
00046 #include <lemon/invalid.h>
00047
00048 namespace lemon {
00049
00052
00053
00065 template<typename Graph>
00066 class DirPath {
00067 public:
00069 typedef typename Graph::Edge GraphEdge;
00071 typedef typename Graph::Node GraphNode;
00072 class NodeIt;
00073 class EdgeIt;
00074
00075 protected:
00076 const Graph *gr;
00077 typedef std::vector<GraphEdge> Container;
00078 Container edges;
00079
00080 public:
00081
00084 DirPath(const Graph &_G) : gr(&_G) {}
00085
00090 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
00091 gr = P.gr;
00092 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00093 }
00094
00099 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
00100 gr = P.gr;
00101 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00102 }
00103
00105 size_t length() const { return edges.size(); }
00107 bool empty() const { return edges.empty(); }
00108
00110 void clear() { edges.clear(); }
00111
00116 GraphNode source() const {
00117 return empty() ? INVALID : gr->source(edges[0]);
00118 }
00123 GraphNode target() const {
00124 return empty() ? INVALID : gr->target(edges[length()-1]);
00125 }
00126
00131 template<typename It>
00132 It& first(It &i) const { return i=It(*this); }
00133
00135 NodeIt& nth(NodeIt &i, int n) const {
00136 return i=NodeIt(*this, n);
00137 }
00138
00140 EdgeIt& nth(EdgeIt &i, int n) const {
00141 return i=EdgeIt(*this, n);
00142 }
00143
00146 NodeIt target(const EdgeIt& e) const {
00147 return NodeIt(*this, e.idx+1);
00148 }
00149
00152 NodeIt source(const EdgeIt& e) const {
00153 return NodeIt(*this, e.idx);
00154 }
00155
00156
00157
00158
00167 class EdgeIt {
00168 friend class DirPath;
00169
00170 int idx;
00171 const DirPath *p;
00172 public:
00174 EdgeIt() {}
00176 EdgeIt(Invalid) : idx(-1), p(0) {}
00178 EdgeIt(const DirPath &_p, int _idx = 0) :
00179 idx(_idx), p(&_p) { validate(); }
00180
00182 bool valid() const { return idx!=-1; }
00183
00185 operator GraphEdge () const {
00186 return valid() ? p->edges[idx] : INVALID;
00187 }
00188
00190 EdgeIt& operator++() { ++idx; validate(); return *this; }
00191
00193 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
00195 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
00197 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
00198
00199 private:
00200
00201
00202 void validate() { if( size_t(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( size_t(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
00388 template<typename Graph>
00389 class UndirPath {
00390 public:
00392 typedef typename Graph::Edge GraphEdge;
00394 typedef typename Graph::Node GraphNode;
00395 class NodeIt;
00396 class EdgeIt;
00397
00398 protected:
00399 const Graph *gr;
00400 typedef std::vector<GraphEdge> Container;
00401 Container edges;
00402
00403 public:
00404
00407 UndirPath(const Graph &_G) : gr(&_G) {}
00408
00413 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
00414 gr = P.gr;
00415 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00416 }
00417
00422 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
00423 gr = P.gr;
00424 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
00425 }
00426
00428 size_t length() const { return edges.size(); }
00430 bool empty() const { return edges.empty(); }
00431
00433 void clear() { edges.clear(); }
00434
00439 GraphNode source() const {
00440 return empty() ? INVALID : gr->source(edges[0]);
00441 }
00446 GraphNode target() const {
00447 return empty() ? INVALID : gr->target(edges[length()-1]);
00448 }
00449
00454 template<typename It>
00455 It& first(It &i) const { return i=It(*this); }
00456
00458 NodeIt& nth(NodeIt &i, int n) const {
00459 return i=NodeIt(*this, n);
00460 }
00461
00463 EdgeIt& nth(EdgeIt &i, int n) const {
00464 return i=EdgeIt(*this, n);
00465 }
00466
00468 template<typename It>
00469 static
00470 bool valid(const It &i) { return i.valid(); }
00471
00473 template<typename It>
00474 static
00475 It& next(It &e) {
00476 return ++e;
00477 }
00478
00481 NodeIt target(const EdgeIt& e) const {
00482 return NodeIt(*this, e.idx+1);
00483 }
00484
00487 NodeIt source(const EdgeIt& e) const {
00488 return NodeIt(*this, e.idx);
00489 }
00490
00491
00492
00503 class EdgeIt {
00504 friend class UndirPath;
00505
00506 int idx;
00507 const UndirPath *p;
00508 public:
00510 EdgeIt() {}
00512 EdgeIt(Invalid) : idx(-1), p(0) {}
00514 EdgeIt(const UndirPath &_p, int _idx = 0) :
00515 idx(_idx), p(&_p) { validate(); }
00516
00518 bool valid() const { return idx!=-1; }
00519
00521 operator GraphEdge () const {
00522 return valid() ? p->edges[idx] : INVALID;
00523 }
00525 EdgeIt& operator++() { ++idx; validate(); return *this; }
00526
00528 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
00530 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
00532 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
00533
00534 private:
00535
00536
00537 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
00538 };
00539
00550 class NodeIt {
00551 friend class UndirPath;
00552
00553 int idx;
00554 const UndirPath *p;
00555 public:
00557 NodeIt() {}
00559 NodeIt(Invalid) : idx(-1), p(0) {}
00561 NodeIt(const UndirPath &_p, int _idx = 0) :
00562 idx(_idx), p(&_p) { validate(); }
00563
00565 bool valid() const { return idx!=-1; }
00566
00568 operator const GraphNode& () const {
00569 if(idx >= p->length())
00570 return p->target();
00571 else if(idx >= 0)
00572 return p->gr->source(p->edges[idx]);
00573 else
00574 return INVALID;
00575 }
00577 NodeIt& operator++() { ++idx; validate(); return *this; }
00578
00580 bool operator==(const NodeIt& e) const { return idx==e.idx; }
00582 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
00584 bool operator<(const NodeIt& e) const { return idx<e.idx; }
00585
00586 private:
00587 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
00588 };
00589
00590 friend class Builder;
00591
00607 class Builder {
00608 UndirPath &P;
00609 Container front, back;
00610
00611 public:
00614 Builder(UndirPath &_P) : P(_P) {}
00615
00617
00623 void setStartNode(const GraphNode &) {}
00624
00626
00629 void pushFront(const GraphEdge& e) {
00630 front.push_back(e);
00631 }
00632
00634
00637 void pushBack(const GraphEdge& e) {
00638 back.push_back(e);
00639 }
00640
00642 void commit() {
00643 if( !(front.empty() && back.empty()) ) {
00644 Container tmp;
00645 tmp.reserve(front.size()+back.size()+P.length());
00646 tmp.insert(tmp.end(), front.rbegin(), front.rend());
00647 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
00648 tmp.insert(tmp.end(), back.begin(), back.end());
00649 P.edges.swap(tmp);
00650 front.clear();
00651 back.clear();
00652 }
00653 }
00654
00655
00657
00660
00661 void reserveFront(size_t r) {front.reserve(r);}
00662
00664
00667
00668 void reserveBack(size_t r) {back.reserve(r);}
00669
00670 private:
00671 bool empty() {
00672 return front.empty() && back.empty() && P.empty();
00673 }
00674
00675 GraphNode source() const {
00676 if( ! front.empty() )
00677 return P.gr->source(front[front.size()-1]);
00678 else if( ! P.empty() )
00679 return P.gr->source(P.edges[0]);
00680 else if( ! back.empty() )
00681 return P.gr->source(back[0]);
00682 else
00683 return INVALID;
00684 }
00685 GraphNode target() const {
00686 if( ! back.empty() )
00687 return P.gr->target(back[back.size()-1]);
00688 else if( ! P.empty() )
00689 return P.gr->target(P.edges[P.length()-1]);
00690 else if( ! front.empty() )
00691 return P.gr->target(front[0]);
00692 else
00693 return INVALID;
00694 }
00695
00696 };
00697
00698 };
00699
00700
00702
00703 }
00704
00705 #endif // LEMON_PATH_H