COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2335:27aa03cd3121 in lemon-0.x for lemon/path.h


Ignore:
Timestamp:
01/08/07 11:39:59 (17 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3123
Message:

New path concept and path structures

TODO: BellmanFord::negativeCycle()

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/path.h

    r2247 r2335  
    2929#include <algorithm>
    3030
     31#include <lemon/path_utils.h>
    3132#include <lemon/error.h>
    3233#include <lemon/bits/invalid.h>
    … …  
    3839
    3940
    40   //! \brief A structure for representing directed paths in a graph.
    41   //!
    42   //! A structure for representing directed path in a graph.
    43   //! \param Graph The graph type in which the path is.
    44   //!
    45   //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    46   //! and \c EdgeIt with the same usage. These types converts to the \c Node
    47   //! and \c Edge of the original graph.
    48   //!
    49   //! \todo Thoroughfully check all the range and consistency tests.
    50   template<typename Graph>
     41  /// \brief A structure for representing directed paths in a graph.
     42  ///
     43  /// A structure for representing directed path in a graph.
     44  /// \param Graph The graph type in which the path is.
     45  ///
     46  /// In a sense, the path can be treated as a list of edges. The
     47  /// lemon path type stores just this list. As a consequence it
     48  /// cannot enumerate the nodes in the path and the zero length paths
     49  /// cannot store the source.
     50  ///
     51  /// This implementation is a back and front insertable and erasable
     52  /// path type. It can be indexed in O(1) time. The front and back
     53  /// insertion and erasure is amortized O(1) time. The
     54  /// impelementation is based on two opposite organized vectors.
     55  template <typename _Graph>
    5156  class Path {
    5257  public:
    53     /// Edge type of the underlying graph.
     58
     59    typedef _Graph Graph;
    5460    typedef typename Graph::Edge Edge;
    55     /// Node type of the underlying graph.
    56     typedef typename Graph::Node Node;
    57 
    58     class NodeIt;
    59     class EdgeIt;
    60 
    61     struct PathError : public LogicError {
    62       virtual const char* what() const throw() {
    63         return "lemon::PathError";
    64       }     
    65     };
    66 
    67   public:
    68 
    69     /// \brief Constructor
    70     ///
    71     /// Constructor
    72     /// \param _G The graph in which the path is.
    73     Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
    74    
    75     /// \brief Subpath constructor.
    76     ///
    77     /// Subpath defined by two nodes.
    78     /// \warning It is an error if the two edges are not in order!
    79     Path(const Path &other, const NodeIt &a, const NodeIt &b) {
    80       graph = other.graph;
    81       start = a;
    82       edges.insert(edges.end(),
    83                    other.edges.begin() + a.id, other.edges.begin() + b.id);
    84     }
    85 
    86     /// \brief Subpath constructor.
    87     ///
    88     /// Subpath defined by two edges. Contains edges in [a,b)
    89     /// \warning It is an error if the two edges are not in order!
    90     Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
    91       graph = other.graph;
    92       start = graph->source(a);
    93       edges.insert(edges.end(),
    94                    other.edges.begin() + a.id, other.edges.begin() + b.id);
    95     }
    96 
    97     /// \brief Length of the path.
    98     ///
    99     /// The number of the edges in the path. It can be zero if the
    100     /// path has only one node or it is empty.
    101     int length() const { return edges.size(); }
    102 
    103     /// \brief Returns whether the path is empty.
    104     ///
    105     /// Returns true when the path does not contain neither edge nor
    106     /// node.
    107     bool empty() const { return start == INVALID; }
    108 
    109     /// \brief Resets the path to an empty path.
    110     ///
    111     /// Resets the path to an empty path.
    112     void clear() { edges.clear(); start = INVALID; }
    113 
    114     /// \brief Starting point of the path.
    115     ///
    116     /// Starting point of the path.
    117     /// Returns INVALID if the path is empty.
    118     Node source() const {
    119       return start;
    120     }
    121     /// \brief End point of the path.
    122     ///
    123     /// End point of the path.
    124     /// Returns INVALID if the path is empty.
    125     Node target() const {
    126       return length() == 0 ? start : graph->target(edges[length()-1]);
    127     }
    128 
    129     /// \brief Gives back a node iterator to point to the node of a
    130     /// given index.
    131     ///
    132     /// Gives back a node iterator to point to the node of a given
    133     /// index.
    134     /// \pre n should less or equal to \c length()
    135     NodeIt nthNode(int n) const {
    136       return NodeIt(*this, n);
    137     }
    138 
    139     /// \brief Gives back an edge iterator to point to the edge of a
    140     /// given index.
    141     ///
    142     /// Gives back an edge iterator to point to the node of a given
    143     /// index. 
    144     /// \pre n should less than \c length()
    145     EdgeIt nthEdge(int n) const {
    146       return EdgeIt(*this, n);
    147     }
    148 
    149     /// \brief Returns node iterator pointing to the source node of the
    150     /// given edge iterator.
    151     ///
    152     /// Returns node iterator pointing to the source node of the given
    153     /// edge iterator.
    154     NodeIt source(const EdgeIt& e) const {
    155       return NodeIt(*this, e.id);
    156     }
    157 
    158     /// \brief Returns node iterator pointing to the target node of the
    159     /// given edge iterator.
    160     ///
    161     /// Returns node iterator pointing to the target node of the given
    162     /// edge iterator.
    163     NodeIt target(const EdgeIt& e) const {
    164       return NodeIt(*this, e.id + 1);
    165     }
    166 
    167 
    168     /// \brief Iterator class to iterate on the nodes of the paths
    169     ///
    170     /// This class is used to iterate on the nodes of the paths
    171     ///
    172     /// Of course it converts to Graph::Node
    173     class NodeIt {
    174       friend class Path;
    175     public:
    176 
    177       /// \brief Default constructor
    178       ///
    179       /// Default constructor
    180       NodeIt() {}
    181 
    182       /// \brief Invalid constructor
    183       ///
    184       /// Invalid constructor
    185       NodeIt(Invalid) : id(-1), path(0) {}
    186 
    187       /// \brief Constructor with starting point
    188       ///
    189       /// Constructor with starting point
    190       NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
    191         if (id > path->length()) id = -1;
    192       }
    193 
    194       /// \brief Conversion to Graph::Node
    195       ///
    196       /// Conversion to Graph::Node
    197       operator Node() const {
    198         if (id > 0) {
    199           return path->graph->target(path->edges[id - 1]);
    200         } else if (id == 0) {
    201           return path->start;
    202         } else {
    203           return INVALID;
    204         }
    205       }
    206 
    207       /// \brief Steps to the next node
    208       ///
    209       /// Steps to the next node
    210       NodeIt& operator++() {
    211         ++id;
    212         if (id > path->length()) id = -1;
    213         return *this;
    214       }
    215 
    216       /// \brief Comparison operator
    217       ///
    218       /// Comparison operator
    219       bool operator==(const NodeIt& n) const { return id == n.id; }
    220 
    221       /// \brief Comparison operator
    222       ///
    223       /// Comparison operator
    224       bool operator!=(const NodeIt& n) const { return id != n.id; }
    225 
    226       /// \brief Comparison operator
    227       ///
    228       /// Comparison operator
    229       bool operator<(const NodeIt& n) const { return id < n.id; }
    230 
    231     private:
    232       int id;
    233       const Path *path;
    234     };
    235 
    236     /// \brief Iterator class to iterate on the edges of the paths
    237     ///
    238     /// This class is used to iterate on the edges of the paths
    239     /// Of course it converts to Graph::Edge
     61
     62    /// \brief Default constructor
     63    ///
     64    /// Default constructor
     65    Path() {}
     66
     67    /// \brief Template copy constructor
     68    ///
     69    /// This path can be initialized with any other path type. It just
     70    /// makes a copy of the given path.
     71    template <typename CPath>
     72    Path(const CPath& cpath) {
     73      copyPath(*this, cpath);
     74    }
     75
     76    /// \brief Template copy assignment
     77    ///
     78    /// This path can be initialized with any other path type. It just
     79    /// makes a copy of the given path.
     80    template <typename CPath>
     81    Path& operator=(const CPath& cpath) {
     82      copyPath(*this, cpath);
     83      return *this;
     84    }
     85
     86    /// \brief Lemon style iterator for path edges
     87    ///
     88    /// This class is used to iterate on the edges of the paths.
    24089    class EdgeIt {
    24190      friend class Path;
    24291    public:
    243 
    24492      /// \brief Default constructor
    245       ///
     93      EdgeIt() {}
     94      /// \brief Invalid constructor
     95      EdgeIt(Invalid) : path(0), idx(-1) {}
     96      /// \brief Initializate the constructor to the first edge of path
     97      EdgeIt(const Path &_path)
     98        : path(&_path), idx(_path.empty() ? -1 : 0) {}
     99
     100    private:
     101
     102      EdgeIt(const Path &_path, int _idx)
     103        : idx(_idx), path(&_path) {}
     104
     105    public:
     106
     107      /// \brief Conversion to Edge
     108      operator const Edge&() const {
     109        return path->nth(idx);
     110      }
     111
     112      /// \brief Next edge
     113      EdgeIt& operator++() {
     114        ++idx;
     115        if (idx >= path->length()) idx = -1;
     116        return *this;
     117      }
     118
     119      /// \brief Comparison operator
     120      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
     121      /// \brief Comparison operator
     122      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
     123      /// \brief Comparison operator
     124      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
     125
     126    private:
     127      const Path *path;
     128      int idx;
     129    };
     130
     131    /// \brief Length of the path.
     132    int length() const { return head.size() + tail.size(); }
     133    /// \brief Returns whether the path is empty.
     134    bool empty() const { return head.empty() && tail.empty(); }
     135
     136    /// \brief Resets the path to an empty path.
     137    void clear() { head.clear(); tail.clear(); }
     138
     139    /// \brief Gives back the nth edge.
     140    ///
     141    /// \pre n is in the [0..length() - 1] range
     142    const Edge& nth(int n) const {
     143      return n < (int)head.size() ? *(head.rbegin() + n) :
     144        *(tail.begin() + (n - head.size()));
     145    }
     146
     147    /// \brief Initializes edge iterator to point to the nth edge
     148    ///
     149    /// \pre n is in the [0..length() - 1] range
     150    EdgeIt nthIt(int n) const {
     151      return EdgeIt(*this, n);
     152    }
     153
     154    /// \brief Gives back the first edge of the path
     155    const Edge& front() const {
     156      return head.empty() ? tail.front() : head.back();
     157    }
     158
     159    /// \brief Add a new edge before the current path
     160    void addFront(const Edge& edge) {
     161      head.push_back(edge);
     162    }
     163
     164    /// \brief Erase the first edge of the path
     165    void eraseFront() {
     166      if (!head.empty()) {
     167        head.pop_back();
     168      } else {
     169        head.clear();
     170        int halfsize = tail.size() / 2;
     171        head.resize(halfsize);
     172        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
     173                  head.rbegin());
     174        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
     175        tail.resize(tail.size() - halfsize - 1);
     176      }
     177    }
     178
     179    /// \brief Gives back the last edge of the path
     180    const Edge& back() const {
     181      return tail.empty() ? head.front() : tail.back();
     182    }
     183
     184    /// \brief Add a new edge behind the current path
     185    void addBack(const Edge& edge) {
     186      tail.push_back(edge);
     187    }
     188
     189    /// \brief Erase the last edge of the path
     190    void eraseBack() {
     191      if (!tail.empty()) {
     192        tail.pop_back();
     193      } else {
     194        int halfsize = head.size() / 2;
     195        tail.resize(halfsize);
     196        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
     197                  tail.rbegin());
     198        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
     199        head.resize(head.size() - halfsize - 1);
     200      }
     201    }
     202
     203
     204
     205    typedef True BuildTag;
     206
     207    template <typename CPath>
     208    void build(const CPath& path) {
     209      int len = path.length();
     210      tail.reserve(len);
     211      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     212        tail.push_back(it);
     213      }
     214    }
     215
     216    template <typename CPath>
     217    void buildRev(const CPath& path) {
     218      int len = path.length();
     219      head.reserve(len);
     220      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     221        head.push_back(it);
     222      }
     223    }
     224
     225  protected:
     226    typedef std::vector<Edge> Container;
     227    Container head, tail;
     228
     229  };
     230
     231  /// \brief A structure for representing directed paths in a graph.
     232  ///
     233  /// A structure for representing directed path in a graph.
     234  /// \param Graph The graph type in which the path is.
     235  ///
     236  /// In a sense, the path can be treated as a list of edges. The
     237  /// lemon path type stores just this list. As a consequence it
     238  /// cannot enumerate the nodes in the path and the zero length paths
     239  /// cannot store the source.
     240  ///
     241  /// This implementation is a just back insertable and erasable path
     242  /// type. It can be indexed in O(1) time. The back insertion and
     243  /// erasure is amortized O(1) time. This implementation is faster
     244  /// then the \c Path type because it use just one vector for the
     245  /// edges.
     246  template <typename _Graph>
     247  class SimplePath {
     248  public:
     249
     250    typedef _Graph Graph;
     251    typedef typename Graph::Edge Edge;
     252
     253    /// \brief Default constructor
     254    ///
     255    /// Default constructor
     256    SimplePath() {}
     257
     258    /// \brief Template copy constructor
     259    ///
     260    /// This path can be initialized with any other path type. It just
     261    /// makes a copy of the given path.
     262    template <typename CPath>
     263    SimplePath(const CPath& cpath) {
     264      copyPath(*this, cpath);
     265    }
     266
     267    /// \brief Template copy assignment
     268    ///
     269    /// This path can be initialized with any other path type. It just
     270    /// makes a copy of the given path.
     271    template <typename CPath>
     272    SimplePath& operator=(const CPath& cpath) {
     273      copyPath(*this, cpath);
     274      return *this;
     275    }
     276
     277    /// \brief Iterator class to iterate on the edges of the paths
     278    ///
     279    /// This class is used to iterate on the edges of the paths
     280    ///
     281    /// Of course it converts to Graph::Edge
     282    class EdgeIt {
     283      friend class SimplePath;
     284    public:
    246285      /// Default constructor
    247286      EdgeIt() {}
    248 
    249       /// \brief Invalid constructor
    250       ///
    251287      /// Invalid constructor
    252       EdgeIt(Invalid) : id(-1), path(0) {}
    253 
    254       /// \brief Constructor with starting point
    255       ///
     288      EdgeIt(Invalid) : path(0), idx(-1) {}
     289      /// \brief Initializate the constructor to the first edge of path
     290      EdgeIt(const SimplePath &_path)
     291        : path(&_path), idx(_path.empty() ? -1 : 0) {}
     292
     293    private:
     294
    256295      /// Constructor with starting point
    257       EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
    258         if (id >= path->length()) id = -1;
    259       }
    260 
    261       /// \brief Conversion to Graph::Edge
    262       ///
    263       /// Conversion to Graph::Edge
    264       operator Edge() const {
    265         return id != -1 ? path->edges[id] : INVALID;
    266       }
    267 
    268       /// \brief Steps to the next edge
    269       ///
    270       /// Steps to the next edge
     296      EdgeIt(const SimplePath &_path, int _idx)
     297        : idx(_idx), path(&_path) {}
     298
     299    public:
     300
     301      ///Conversion to Graph::Edge
     302      operator const Edge&() const {
     303        return path->nth(idx);
     304      }
     305
     306      /// Next edge
    271307      EdgeIt& operator++() {
    272         ++id;
    273         if (id >= path->length()) id = -1;
     308        ++idx;
     309        if (idx >= path->length()) idx = -1;
    274310        return *this;
    275311      }
    276312
    277       /// \brief Comparison operator
    278       ///
    279313      /// Comparison operator
    280       bool operator==(const EdgeIt& e) const { return id == e.id; }
    281 
    282       /// \brief Comparison operator
    283       ///
     314      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
    284315      /// Comparison operator
    285       bool operator!=(const EdgeIt& e) const { return id != e.id; }
    286 
    287       /// \brief Comparison operator
    288       ///
     316      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
    289317      /// Comparison operator
    290       bool operator<(const EdgeIt& e) const { return id < e.id; }
     318      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
    291319
    292320    private:
    293 
    294       int id;
    295       const Path *path;
     321      const SimplePath *path;
     322      int idx;
    296323    };
    297324
     325    /// \brief Length of the path.
     326    int length() const { return data.size(); }
     327    /// \brief Returns whether the path is empty.
     328    bool empty() const { return data.empty(); }
     329
     330    /// \brief Resets the path to an empty path.
     331    void clear() { data.clear(); }
     332
     333    /// \brief Gives back the nth edge.
     334    ///
     335    /// \pre n is in the [0..length() - 1] range
     336    const Edge& nth(int n) const {
     337      return data[n];
     338    }
     339
     340    /// \brief  Initializes edge iterator to point to the nth edge.
     341    EdgeIt nthIt(int n) const {
     342      return EdgeIt(*this, n);
     343    }
     344
     345    /// \brief Gives back the last edge of the path.
     346    const Edge& back() const {
     347      return data.back();
     348    }
     349
     350    /// \brief Add a new edge behind the current path.
     351    void addBack(const Edge& edge) {
     352      data.push_back(edge);
     353    }
     354
     355    /// \brief Erase the last edge of the path
     356    void eraseBack() {
     357      data.pop_back();
     358    }
     359
     360    typedef True BuildTag;
     361
     362    template <typename CPath>
     363    void build(const CPath& path) {
     364      int len = path.length();
     365      data.resize(len);
     366      int index = 0;
     367      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     368        data[index] = it;;
     369        ++index;
     370      }
     371    }
     372
     373    template <typename CPath>
     374    void buildRev(const CPath& path) {
     375      int len = path.length();
     376      data.resize(len);
     377      int index = len;
     378      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     379        --index;
     380        data[index] = it;;
     381      }
     382    }
     383
    298384  protected:
    299 
    300     const Graph *graph;
    301 
    302385    typedef std::vector<Edge> Container;
    303     Container edges;
    304     Node start;
    305 
     386    Container data;
     387
     388  };
     389
     390  /// \brief A structure for representing directed paths in a graph.
     391  ///
     392  /// A structure for representing directed path in a graph.
     393  /// \param Graph The graph type in which the path is.
     394  ///
     395  /// In a sense, the path can be treated as a list of edges. The
     396  /// lemon path type stores just this list. As a consequence it
     397  /// cannot enumerate the nodes in the path and the zero length paths
     398  /// cannot store the source.
     399  ///
     400  /// This implementation is a back and front insertable and erasable
     401  /// path type. It can be indexed in O(k) time, where k is the rank
     402  /// of the edge in the path. The length can be computed in O(n)
     403  /// time. The front and back insertion and erasure is O(1) time
     404  /// and it can be splited and spliced in O(1) time.
     405  template <typename _Graph>
     406  class ListPath {
    306407  public:
    307408
    308     friend class Builder;
    309 
    310     /// \brief Class to build paths
    311     ///
    312     /// This class is used to fill a path with edges.
    313     ///
    314     /// You can push new edges to the front and to the back of the
    315     /// path in arbitrary order then you should commit these changes
    316     /// to the graph.
    317     ///
    318     /// Fundamentally, for most "Paths" (classes fulfilling the
    319     /// PathConcept) while the builder is active (after the first
    320     /// modifying operation and until the commit()) the original Path
    321     /// is in a "transitional" state (operations on it have undefined
    322     /// result). But in the case of Path the original path remains
    323     /// unchanged until the commit. However we don't recomend that you
    324     /// use this feature.
    325     class Builder {
     409    typedef _Graph Graph;
     410    typedef typename Graph::Edge Edge;
     411
     412  protected:
     413
     414    // the std::list<> is incompatible
     415    // hard to create invalid iterator
     416    struct Node {
     417      Edge edge;
     418      Node *next, *prev;
     419    };
     420
     421    Node *first, *last;
     422
     423    std::allocator<Node> alloc;
     424
     425  public:
     426 
     427    /// \brief Default constructor
     428    ///
     429    /// Default constructor
     430    ListPath() : first(0), last(0) {}
     431
     432    /// \brief Template copy constructor
     433    ///
     434    /// This path can be initialized with any other path type. It just
     435    /// makes a copy of the given path.
     436    template <typename CPath>
     437    ListPath(const CPath& cpath) : first(0), last(0) {
     438      copyPath(*this, cpath);
     439    }
     440
     441    /// \brief Destructor of the path
     442    ///
     443    /// Destructor of the path
     444    ~ListPath() {
     445      clear();
     446    }
     447
     448    /// \brief Template copy assignment
     449    ///
     450    /// This path can be initialized with any other path type. It just
     451    /// makes a copy of the given path.
     452    template <typename CPath>
     453    ListPath& operator=(const CPath& cpath) {
     454      copyPath(*this, cpath);
     455      return *this;
     456    }
     457
     458    /// \brief Iterator class to iterate on the edges of the paths
     459    ///
     460    /// This class is used to iterate on the edges of the paths
     461    ///
     462    /// Of course it converts to Graph::Edge
     463    class EdgeIt {
     464      friend class ListPath;
    326465    public:
    327       /// \brief Constructor
    328       ///
    329       /// Constructor
    330       /// \param _path the path you want to fill in.
    331       Builder(Path &_path) : path(_path), start(INVALID) {}
    332 
    333       /// \brief Destructor
    334       ///
    335       /// Destructor
    336       ~Builder() {
    337         LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
    338                      PathError());
    339       }
    340 
    341       /// \brief Sets the starting node of the path.
    342       ///
    343       /// Sets the starting node of the path. Edge added to the path
    344       /// afterwards have to be incident to this node.  It should be
    345       /// called if and only if the path is empty and before any call
    346       /// to \ref pushFront() or \ref pushBack()
    347       void setStartNode(const Node &_start) {
    348         LEMON_ASSERT(path.empty() && start == INVALID, PathError());
    349         start = _start;
    350       }
    351 
    352       /// \brief Push a new edge to the front of the path
    353       ///
    354       /// Push a new edge to the front of the path. 
    355       /// \sa setStartNode
    356       void pushFront(const Edge& e) {
    357         LEMON_ASSERT(front.empty() ||
    358                      (path.graph->source(front.back()) ==
    359                       path.graph->target(e)), PathError());
    360         LEMON_ASSERT(path.empty() ||
    361                      (path.source() == path.graph->target(e)), PathError());
    362         LEMON_ASSERT(!path.empty() || !front.empty() ||
    363                      (start == path.graph->target(e)), PathError());
    364         front.push_back(e);
    365       }
    366 
    367       /// \brief Push a new edge to the back of the path
    368       ///
    369       /// Push a new edge to the back of the path.
    370       /// \sa setStartNode
    371       void pushBack(const Edge& e) {
    372         LEMON_ASSERT(back.empty() ||
    373                      (path.graph->target(back.back()) ==
    374                       path.graph->source(e)), PathError());
    375         LEMON_ASSERT(path.empty() ||
    376                      (path.target() == path.graph->source(e)), PathError());
    377         LEMON_ASSERT(!path.empty() || !back.empty() ||
    378                      (start == path.graph->source(e)), PathError());
    379         back.push_back(e);
    380       }
    381 
    382       /// \brief Commit the changes to the path.
    383       ///
    384       /// Commit the changes to the path.
    385       void commit() {
    386         if( !front.empty() || !back.empty() || start != INVALID) {
    387           Container tmp;
    388           tmp.reserve(front.size() + back.size() + path.length());
    389           tmp.insert(tmp.end(), front.rbegin(), front.rend());
    390           tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
    391           tmp.insert(tmp.end(), back.begin(), back.end());
    392           path.edges.swap(tmp);
    393           if (!front.empty()) {
    394             path.start = path.graph->source(front.back());
     466      /// Default constructor
     467      EdgeIt() {}
     468      /// Invalid constructor
     469      EdgeIt(Invalid) : path(0), node(0) {}
     470      /// \brief Initializate the constructor to the first edge of path
     471      EdgeIt(const ListPath &_path)
     472        : path(&_path), node(_path.first) {}
     473
     474    protected:
     475
     476      EdgeIt(const ListPath &_path, Node *_node)
     477        : path(&_path), node(_node) {}
     478
     479
     480    public:
     481
     482      ///Conversion to Graph::Edge
     483      operator const Edge&() const {
     484        return node->edge;
     485      }
     486
     487      /// Next edge
     488      EdgeIt& operator++() {
     489        node = node->next;
     490        return *this;
     491      }
     492
     493      /// Comparison operator
     494      bool operator==(const EdgeIt& e) const { return node==e.node; }
     495      /// Comparison operator
     496      bool operator!=(const EdgeIt& e) const { return node!=e.node; }
     497      /// Comparison operator
     498      bool operator<(const EdgeIt& e) const { return node<e.node; }
     499
     500    private:
     501      const ListPath *path;
     502      Node *node;
     503    };
     504
     505    /// \brief Gives back the nth edge.
     506    ///
     507    /// Gives back the nth edge in O(n) time.
     508    /// \pre n is in the [0..length() - 1] range
     509    const Edge& nth(int n) const {
     510      Node *node = first;
     511      for (int i = 0; i < n; ++i) {
     512        node = node->next;
     513      }
     514      return node->edge;
     515    }
     516
     517    /// \brief Initializes edge iterator to point to the nth edge.
     518    EdgeIt nthIt(int n) const {
     519      Node *node = first;
     520      for (int i = 0; i < n; ++i) {
     521        node = node->next;
     522      }
     523      return EdgeIt(*this, node);
     524    }
     525
     526    /// \brief Length of the path.
     527    int length() const {
     528      int len = 0;
     529      Node *node = first;
     530      while (node != 0) {
     531        node = node->next;
     532        ++len;
     533      }
     534      return len;
     535    }
     536
     537    /// \brief Returns whether the path is empty.
     538    bool empty() const { return first == 0; }
     539
     540    /// \brief Resets the path to an empty path.
     541    void clear() {
     542      while (first != 0) {
     543        last = first->next;
     544        alloc.destroy(first);
     545        alloc.deallocate(first, 1);
     546        first = last;
     547      }
     548    }
     549
     550    /// \brief Gives back the first edge of the path
     551    const Edge& front() const {
     552      return first->edge;
     553    }
     554
     555    /// \brief Add a new edge before the current path
     556    void addFront(const Edge& edge) {
     557      Node *node = alloc.allocate(1);
     558      alloc.construct(node, Node());
     559      node->prev = 0;
     560      node->next = first;
     561      node->edge = edge;
     562      if (first) {
     563        first->prev = node;
     564        first = node;
     565      } else {
     566        first = last = node;
     567      }
     568    }
     569
     570    /// \brief Erase the first edge of the path
     571    void eraseFront() {
     572      Node *node = first;
     573      first = first->next;
     574      if (first) {
     575        first->prev = 0;
     576      } else {
     577        last = 0;
     578      }
     579      alloc.destroy(node);
     580      alloc.deallocate(node, 1);
     581    }
     582
     583    /// \brief Gives back the last edge of the path.
     584    const Edge& back() const {
     585      return last->edge;
     586    }
     587
     588    /// \brief Add a new edge behind the current path.
     589    void addBack(const Edge& edge) {
     590      Node *node = alloc.allocate(1);
     591      alloc.construct(node, Node());
     592      node->next = 0;
     593      node->prev = last;
     594      node->edge = edge;
     595      if (last) {
     596        last->next = node;
     597        last = node;
     598      } else {
     599        last = first = node;
     600      }
     601    }
     602
     603    /// \brief Erase the last edge of the path
     604    void eraseBack() {
     605      Node *node = last;
     606      last = last->prev;
     607      if (last) {
     608        last->next = 0;
     609      } else {
     610        first = 0;
     611      }
     612      alloc.destroy(node);
     613      alloc.deallocate(node, 1);
     614    }
     615
     616    /// \brief Splicing the given path to the current path.
     617    ///
     618    /// It splices the \c tpath to the back of the current path and \c
     619    /// tpath becomes empty. The time complexity of this function is
     620    /// O(1).
     621    void spliceBack(ListPath& tpath) {
     622      if (first) {
     623        if (tpath.first) {
     624          last->next = tpath.first;
     625          tpath.first->prev = last;
     626          last = tpath.last;
     627        }
     628      } else {
     629        first = tpath.first;
     630        last = tpath.last;
     631      }
     632      tpath.first = tpath.last = 0;
     633    }
     634
     635    /// \brief Splicing the given path to the current path.
     636    ///
     637    /// It splices the \c tpath before the current path and \c tpath
     638    /// becomes empty. The time complexity of this function
     639    /// is O(1).
     640    void spliceFront(ListPath& tpath) {
     641      if (first) {
     642        if (tpath.first) {
     643          first->prev = tpath.last;
     644          tpath.last->next = first;
     645          first = tpath.first;
     646        }
     647      } else {
     648        first = tpath.first;
     649        last = tpath.last;
     650      }
     651      tpath.first = tpath.last = 0;
     652    }
     653
     654    /// \brief Splicing the given path into the current path.
     655    ///
     656    /// It splices the \c tpath into the current path before the
     657    /// position of \c it iterator and \c tpath becomes empty. The
     658    /// time complexity of this function is O(1). If the \c it is \c
     659    /// INVALID then it will splice behind the current path.
     660    void splice(EdgeIt it, ListPath& tpath) {
     661      if (it.node) {
     662        if (tpath.first) {
     663          tpath.first->prev = it.node->prev;
     664          if (it.node->prev) {
     665            it.node->prev->next = tpath.first;
    395666          } else {
    396             path.start = start;
     667            first = tpath.first;
    397668          }
    398           start = INVALID;
    399           front.clear();
    400           back.clear();
    401         }
    402       }
    403 
    404       /// \brief Reserve storage for the builder in advance.
    405       ///
    406       /// If you know a reasonable upper bound of the number of the
    407       /// edges to add to the front, using this function you can speed
    408       /// up the building.
    409       void reserveFront(size_t r) {front.reserve(r);}
    410 
    411       /// \brief Reserve storage for the builder in advance.
    412       ///
    413       /// If you know a reasonable upper bound of the number of the
    414       /// edges to add to the back, using this function you can speed
    415       /// up the building.
    416       void reserveBack(size_t r) {back.reserve(r);}
     669          it.node->prev = tpath.last;
     670          tpath.last->next = it.node;
     671        }
     672      } else {
     673        if (first) {
     674          if (tpath.first) {
     675            last->next = tpath.first;
     676            tpath.first->prev = last;
     677            last = tpath.last;
     678          }
     679        } else {
     680          first = tpath.first;
     681          last = tpath.last;
     682        }
     683      }
     684      tpath.first = tpath.last = 0;
     685    }
     686
     687    /// \brief Spliting the current path.
     688    ///
     689    /// It splits the current path into two parts. The part before \c
     690    /// it iterator will remain in the current path and the part from
     691    /// the it will put into the \c tpath. If the \c tpath had edges
     692    /// before the operation they will be removed first.  The time
     693    /// complexity of this function is O(1) plus the clearing of \c
     694    /// tpath. If the \c it is \c INVALID then it just clears \c
     695    /// tpath.
     696    void split(EdgeIt it, ListPath& tpath) {
     697      tpath.clear();
     698      if (it.node) {
     699        tpath.first = it.node;
     700        tpath.last = last;
     701        if (it.node->prev) {
     702          last = it.node->prev;
     703          last->next = 0;
     704        } else {
     705          first = last = 0;
     706        }
     707        it.node->prev = 0;
     708      }
     709    }
     710
     711
     712    typedef True BuildTag;
     713
     714    template <typename CPath>
     715    void build(const CPath& path) {
     716      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     717        addBack(it);
     718      }
     719    }
     720
     721    template <typename CPath>
     722    void buildRev(const CPath& path) {
     723      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     724        addFront(it);
     725      }
     726    }
     727
     728  };
     729
     730  /// \brief A structure for representing directed paths in a graph.
     731  ///
     732  /// A structure for representing directed path in a graph.
     733  /// \param Graph The graph type in which the path is.
     734  ///
     735  /// In a sense, the path can be treated as a list of edges. The
     736  /// lemon path type stores just this list. As a consequence it
     737  /// cannot enumerate the nodes in the path and the zero length paths
     738  /// cannot store the source.
     739  ///
     740  /// This implementation is completly static, so it cannot be
     741  /// modified exclude the assign an other path. It is intented to be
     742  /// used when you want to store a large amount paths because it is
     743  /// the most memory efficient path type in the lemon.
     744  template <typename _Graph>
     745  class StaticPath {
     746  public:
     747
     748    typedef _Graph Graph;
     749    typedef typename Graph::Edge Edge;
     750
     751    /// \brief Default constructor
     752    ///
     753    /// Default constructor
     754    StaticPath() : len(0), edges(0) {}
     755   
     756    /// \brief Template copy constructor
     757    ///
     758    /// This path can be initialized with any other path type. It just
     759    /// makes a copy of the given path.
     760    template <typename CPath>
     761    StaticPath(const CPath& cpath) : edges(0) {
     762      copyPath(*this, cpath);
     763    }
     764
     765    /// \brief Destructor of the path
     766    ///
     767    /// Destructor of the path
     768    ~StaticPath() {
     769      if (edges) delete[] edges;
     770    }
     771
     772    /// \brief Template copy assignment
     773    ///
     774    /// This path can be initialized with any other path type. It just
     775    /// makes a copy of the given path.
     776    template <typename CPath>
     777    StaticPath& operator=(const CPath& cpath) {
     778      copyPath(*this, cpath);
     779      return *this;
     780    }
     781
     782    /// \brief Iterator class to iterate on the edges of the paths
     783    ///
     784    /// This class is used to iterate on the edges of the paths
     785    ///
     786    /// Of course it converts to Graph::Edge
     787    class EdgeIt {
     788      friend class StaticPath;
     789    public:
     790      /// Default constructor
     791      EdgeIt() {}
     792      /// Invalid constructor
     793      EdgeIt(Invalid) : path(0), idx(-1) {}
     794      /// Initializate the constructor to the first edge of path
     795      EdgeIt(const StaticPath &_path)
     796        : path(&_path), idx(_path.empty() ? -1 : 0) {}
    417797
    418798    private:
    419799
    420       Path &path;
    421       Container front, back;
    422       Node start;
    423 
     800      /// Constructor with starting point
     801      EdgeIt(const StaticPath &_path, int _idx)
     802        : idx(_idx), path(&_path) {}
     803
     804    public:
     805
     806      ///Conversion to Graph::Edge
     807      operator const Edge&() const {
     808        return path->nth(idx);
     809      }
     810
     811      /// Next edge
     812      EdgeIt& operator++() {
     813        ++idx;
     814        if (idx >= path->length()) idx = -1;
     815        return *this;
     816      }
     817
     818      /// Comparison operator
     819      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
     820      /// Comparison operator
     821      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
     822      /// Comparison operator
     823      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
     824
     825    private:
     826      const StaticPath *path;
     827      int idx;
    424828    };
    425829
     830    /// \brief Gives back the nth edge.
     831    ///
     832    /// \pre n is in the [0..length() - 1] range
     833    const Edge& nth(int n) const {
     834      return edges[n];
     835    }
     836
     837    /// \brief Initializes edge iterator to point to the nth edge.
     838    EdgeIt nthIt(int n) const {
     839      return EdgeIt(*this, n);
     840    }
     841
     842    /// \brief Gives back the length of the path.
     843    int length() const { return len; }
     844
     845    /// \brief Returns true when the path is empty.
     846    int empty() const { return len == 0; }
     847
     848    /// \break Erase all edge in the graph.
     849    void clear() {
     850      len = 0;
     851      if (edges) delete[] edges;
     852      edges = 0;
     853    }
     854
     855    /// \brief Gives back the first edge of the path.
     856    const Edge& front() const {
     857      return edges[0];
     858    }
     859
     860    /// \brief Gives back the last edge of the path.
     861    const Edge& back() const {
     862      return edges[len - 1];
     863    }
     864
     865
     866    typedef True BuildTag;
     867
     868    template <typename CPath>
     869    void build(const CPath& path) {
     870      len = path.length();
     871      edges = new Edge[len];
     872      int index = 0;
     873      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     874        edges[index] = it;
     875        ++index;
     876      }
     877    }
     878
     879    template <typename CPath>
     880    void buildRev(const CPath& path) {
     881      len = path.length();
     882      edges = new Edge[len];
     883      int index = len;
     884      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     885        --index;
     886        edges[index] = it;
     887      }
     888    }
     889
     890  private:
     891    int len;
     892    Edge* edges;
    426893  };
    427894
Note: See TracChangeset for help on using the changeset viewer.