Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

path.h

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

Generated on Sat Mar 19 10:58:40 2005 for LEMON by  doxygen 1.4.1