COIN-OR::LEMON - Graph Library

Changeset 369:dc9c19f4ca9a in lemon-0.x for src/work/klao/path.h


Ignore:
Timestamp:
04/22/04 01:47:01 (17 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@497
Message:

Directed path structure.
Proposal for a path building interface.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/klao/path.h

    r227 r369  
    1111
    1212#include <deque>
     13#include <vector>
    1314#include <algorithm>
    1415
     
    1617
    1718namespace hugo {
     19
     20  template<typename Graph>
     21  class DirPath {
     22  public:
     23    typedef typename Graph::Edge GraphEdge;
     24    typedef typename Graph::Node GraphNode;
     25    class NodeIt;
     26    class EdgeIt;
     27
     28  protected:
     29    const Graph *gr;
     30    typedef std::vector<GraphEdge> Container;
     31    Container edges;
     32
     33  public:
     34
     35    DirPath(const Graph &_G) : gr(&_G) {}
     36
     37    /// Subpath defined by two nodes.
     38    /// It is an error if the two edges are not in order!
     39    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
     40    /// Subpath defined by two edges. Contains edges in [a,b)
     41    /// It is an error if the two edges are not in order!
     42    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
     43
     44    size_t length() const { return edges.size(); }
     45    bool empty() const { return edges.empty(); }
     46    GraphNode from() const {
     47      return empty() ? INVALID : gr->tail(edges[0]);
     48    }
     49    GraphNode to() const {
     50      return empty() ? INVALID : gr->head(edges[length()-1]);
     51    }
     52
     53    template<typename It>
     54    It& first(It &i) const { return i=It(*this); }
     55
     56    template<typename It>
     57    It& nth(It &i, int n) const { return i=It(*this, n); }
     58
     59    template<typename It>
     60    bool valid(const It &i) const { return i.valid(); }
     61
     62    template<typename It>
     63    It& next(It &e) const { return ++e; }
     64
     65    /// \todo !
     66    NodeIt head(const EdgeIt& e) const;
     67    NodeIt tail(const EdgeIt& e) const;
     68
     69
     70    /*** Iterator classes ***/
     71    class EdgeIt {
     72      friend class DirPath;
     73
     74      int idx;
     75      const DirPath *p;
     76    public:
     77      EdgeIt() {}
     78      EdgeIt(Invalid) : idx(-1), p(0) {}
     79      EdgeIt(const DirPath &_p, int _idx = 0) :
     80        idx(_idx), p(&_p) { validate(); }
     81
     82      bool valid() const { return idx!=-1; }
     83
     84      operator GraphEdge () const {
     85        return valid() ? p->edges[idx] : INVALID;
     86      }
     87      EdgeIt& operator++() { ++idx; validate(); return *this; }
     88
     89      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
     90      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
     91      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
     92
     93    private:
     94      // FIXME: comparison between signed and unsigned...
     95      // Jo ez igy? Vagy esetleg legyen a length() int?
     96      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
     97    };
     98
     99    class NodeIt {
     100      friend class DirPath;
     101
     102      int idx;
     103      const DirPath *p;
     104    public:
     105      NodeIt() {}
     106      NodeIt(Invalid) : idx(-1), p(0) {}
     107      NodeIt(const DirPath &_p, int _idx = 0) :
     108        idx(_idx), p(&_p) { validate(); }
     109
     110      bool valid() const { return idx!=-1; }
     111
     112      operator const GraphEdge& () const {
     113        if(idx >= p->length())
     114          return p->to();
     115        else if(idx >= 0)
     116          return p->gr->tail(p->edges[idx]);
     117        else
     118          return INVALID;
     119      }
     120      NodeIt& operator++() { ++idx; validate(); return *this; }
     121
     122      bool operator==(const NodeIt& e) const { return idx==e.idx; }
     123      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
     124      bool operator<(const NodeIt& e) const { return idx<e.idx; }
     125
     126    private:
     127      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
     128    };
     129
     130    friend class Builder;   
     131    class Builder {
     132      DirPath &P;
     133      Container d;
     134
     135    public:
     136      Builder(DirPath &_P) : P(_P) {}
     137
     138      bool pushFront(const GraphEdge& e) {
     139        if( empty() || P.gr->head(e)==from() ) {
     140          d.push_back(e);
     141          return true;
     142        }
     143        return false;
     144      }
     145      bool pushBack(const GraphEdge& e) {
     146        if( empty() || P.gr->tail(e)==to() ) {
     147          P.edges.push_back(e);
     148          return true;
     149        }
     150        return false;
     151      }
     152
     153      void commit() {
     154        if( !d.empty() ) {
     155          P.edges.insert(P.edges.begin(), d.rbegin(), d.rend());
     156          d.clear();
     157        }
     158      }
     159
     160      ~Builder() { commit(); }
     161
     162      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
     163      // Hogy kenyelmes egy ilyet hasznalni?
     164      void reserve(size_t r) {
     165        d.reserve(r);
     166        P.edges.reserve(P.length()+r);
     167      }
     168
     169    private:
     170      bool empty() { return d.empty() && P.empty(); }
     171
     172      GraphNode from() const {
     173        if( ! d.empty() )
     174          return P.gr->tail(d[d.size()-1]);
     175        else if( ! P.empty() )
     176          return P.gr->tail(P.edges[0]);
     177        else
     178          return INVALID;
     179      }
     180      GraphNode to() const {
     181        if( ! P.empty() )
     182          return P.gr->head(P.edges[P.length()-1]);
     183        else if( ! d.empty() )
     184          return P.gr->head(d[0]);
     185        else
     186          return INVALID;
     187      }
     188
     189    };
     190
     191  };
     192
     193
     194
     195
     196
     197
     198
     199
     200
     201
     202
     203  /**********************************************************************/
     204
    18205
    19206  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
     
    21208
    22209  template<typename Graph>
    23   class Path {
     210  class DynamicPath {
    24211
    25212  public:
     
    39226  public:
    40227
    41     Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
     228    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
    42229
    43230    /// Subpath defined by two nodes.
    44231    /// Nodes may be in reversed order, then
    45232    /// we contstruct the reversed path.
    46     Path(const Path &P, const NodeIt &a, const NodeIt &b);
     233    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
    47234    /// Subpath defined by two edges. Contains edges in [a,b)
    48235    /// It is an error if the two edges are not in order!
    49     Path(const Path &P, const EdgeIt &a, const EdgeIt &b);
     236    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
    50237   
    51238    size_t length() const { return edges.size(); }
     
    113300    /*** Iterator classes ***/
    114301    class EdgeIt {
    115       friend class Path;
     302      friend class DynamicPath;
    116303
    117304      typename Container::const_iterator it;
     
    129316
    130317    class NodeIt {
    131       friend class Path;
    132       friend class EdgeIt;
     318      friend class DynamicPath;
    133319
    134320      size_t idx;
     
    151337
    152338  template<typename Gr>
    153   typename Path<Gr>::EdgeIt&
    154   Path<Gr>::next(Path::EdgeIt &e) const {
     339  typename DynamicPath<Gr>::EdgeIt&
     340  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
    155341    if( e.it == edges.end() )
    156342      return e;
     
    170356
    171357  template<typename Gr>
    172   typename Path<Gr>::NodeIt& Path<Gr>::next(NodeIt &n) const {
     358  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
    173359    if( n.idx >= length() ) {
    174360      // FIXME: invalid
     
    192378
    193379  template<typename Gr>
    194   bool Path<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
     380  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
    195381                          GraphNode &b) {
    196382    if( G.tail(e) == a ) {
     
    206392
    207393  template<typename Gr>
    208   bool Path<Gr>::connectTwoEdges(const GraphEdge &e,
     394  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
    209395                             const GraphEdge &f) {
    210396    if( edgeIncident(f, G.tail(e), _last) ) {
     
    220406
    221407  template<typename Gr>
    222   bool Path<Gr>::pushFront(const GraphEdge &e) {
     408  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
    223409    if( G.valid(_first) ) {
    224410        if( edgeIncident(e, _first, _first) ) {
     
    238424
    239425  template<typename Gr>
    240   bool Path<Gr>::pushBack(const GraphEdge &e) {
     426  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
    241427    if( G.valid(_last) ) {
    242428        if( edgeIncident(e, _last, _last) ) {
     
    257443
    258444  template<typename Gr>
    259   bool Path<Gr>::setFrom(const GraphNode &n) {
     445  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
    260446    if( G.valid(_first) ) {
    261447      return _first == n;
     
    277463
    278464  template<typename Gr>
    279   bool Path<Gr>::setTo(const GraphNode &n) {
     465  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
    280466    if( G.valid(_last) ) {
    281467      return _last == n;
     
    298484
    299485  template<typename Gr>
    300   typename Path<Gr>::NodeIt
    301   Path<Gr>::tail(const EdgeIt& e) const {
     486  typename DynamicPath<Gr>::NodeIt
     487  DynamicPath<Gr>::tail(const EdgeIt& e) const {
    302488    NodeIt n;
    303489
     
    315501
    316502  template<typename Gr>
    317   typename Path<Gr>::NodeIt
    318   Path<Gr>::head(const EdgeIt& e) const {
     503  typename DynamicPath<Gr>::NodeIt
     504  DynamicPath<Gr>::head(const EdgeIt& e) const {
    319505    if( e.it == edges.end()-1 ) {
    320506      return _last;
     
    327513     
    328514  template<typename Gr>
    329   typename Path<Gr>::GraphEdge
    330   Path<Gr>::graphEdge(const EdgeIt& e) const {
     515  typename DynamicPath<Gr>::GraphEdge
     516  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
    331517    if( e.it != edges.end() ) {
    332518      return *e.it;
     
    338524 
    339525  template<typename Gr>
    340   typename Path<Gr>::GraphNode
    341   Path<Gr>::graphNode(const NodeIt& n) const {
     526  typename DynamicPath<Gr>::GraphNode
     527  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
    342528    if( n.idx < length() ) {
    343529      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
     
    352538
    353539  template<typename Gr>
    354   typename Path<Gr>::EdgeIt& Path<Gr>::nth(EdgeIt &e, size_t k) const {
     540  typename DynamicPath<Gr>::EdgeIt&
     541  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
    355542    if( k<0 || k>=length() ) {
    356543      // FIXME: invalid EdgeIt
     
    372559   
    373560  template<typename Gr>
    374   typename Path<Gr>::NodeIt& Path<Gr>::nth(NodeIt &n, size_t k) const {
     561  typename DynamicPath<Gr>::NodeIt&
     562  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
    375563    if( k<0 || k>length() ) {
    376564      // FIXME: invalid NodeIt
     
    392580
    393581  template<typename Gr>
    394   Path<Gr>::Path(const Path &P, const EdgeIt &a, const EdgeIt &b) :
     582  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
     583                               const EdgeIt &b) :
    395584    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up!
    396585  {
     
    407596
    408597  template<typename Gr>
    409   Path<Gr>::Path(const Path &P, const NodeIt &a, const NodeIt &b) :
    410     G(P.G)
     598  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
     599                               const NodeIt &b) : G(P.G)
    411600  {
    412601    if( !P.valid(a) || !P.valid(b) )
Note: See TracChangeset for help on using the changeset viewer.