path.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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     /* Iterator classes */
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       // FIXME: comparison between signed and unsigned...
00537       // Jo ez igy? Vagy esetleg legyen a length() int?
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 } // namespace lemon
00705 
00706 #endif // LEMON_PATH_H

Generated on Fri Feb 3 18:39:34 2006 for LEMON by  doxygen 1.4.6