lemon/path.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 07 Feb 2008 21:28:39 +0000
changeset 99 dbaa96cc1013
parent 97 ee1324c91288
child 100 4f754b4cf82b
permissions -rw-r--r--
Merge
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup paths
    20 ///\file
    21 ///\brief Classes for representing paths in digraphs.
    22 ///
    23 
    24 #ifndef LEMON_PATH_H
    25 #define LEMON_PATH_H
    26 
    27 #include <vector>
    28 #include <algorithm>
    29 
    30 #include <lemon/error.h>
    31 #include <lemon/bits/invalid.h>
    32 
    33 namespace lemon {
    34 
    35   /// \addtogroup paths
    36   /// @{
    37 
    38 
    39   /// \brief A structure for representing directed paths in a digraph.
    40   ///
    41   /// A structure for representing directed path in a digraph.
    42   /// \param Digraph The digraph type in which the path is.
    43   ///
    44   /// In a sense, the path can be treated as a list of arcs. The
    45   /// lemon path type stores just this list. As a consequence, it
    46   /// cannot enumerate the nodes of the path and the source node of
    47   /// a zero length path is undefined.
    48   ///
    49   /// This implementation is a back and front insertable and erasable
    50   /// path type. It can be indexed in O(1) time. The front and back
    51   /// insertion and erase is done in O(1) (amortized) time. The
    52   /// implementation uses two vectors for storing the front and back
    53   /// insertions.
    54   template <typename _Digraph>
    55   class Path {
    56   public:
    57 
    58     typedef _Digraph Digraph;
    59     typedef typename Digraph::Arc Arc;
    60 
    61     /// \brief Default constructor
    62     ///
    63     /// Default constructor
    64     Path() {}
    65 
    66     /// \brief Template copy constructor
    67     ///
    68     /// This constuctor initializes the path from any other path type.
    69     /// It simply makes a copy of the given path.
    70     template <typename CPath>
    71     Path(const CPath& cpath) {
    72       copyPath(*this, cpath);
    73     }
    74 
    75     /// \brief Template copy assignment
    76     ///
    77     /// This operator makes a copy of a path of any other type.
    78     template <typename CPath>
    79     Path& operator=(const CPath& cpath) {
    80       copyPath(*this, cpath);
    81       return *this;
    82     }
    83 
    84     /// \brief Lemon style iterator for path arcs
    85     ///
    86     /// This class is used to iterate on the arcs of the paths.
    87     class ArcIt {
    88       friend class Path;
    89     public:
    90       /// \brief Default constructor
    91       ArcIt() {}
    92       /// \brief Invalid constructor
    93       ArcIt(Invalid) : path(0), idx(-1) {}
    94       /// \brief Initializate the iterator to the first arc of path
    95       ArcIt(const Path &_path) 
    96         : path(&_path), idx(_path.empty() ? -1 : 0) {}
    97 
    98     private:
    99 
   100       ArcIt(const Path &_path, int _idx) 
   101         : path(&_path), idx(_idx) {}
   102 
   103     public:
   104 
   105       /// \brief Conversion to Arc
   106       operator const Arc&() const {
   107         return path->nth(idx);
   108       }
   109 
   110       /// \brief Next arc
   111       ArcIt& operator++() { 
   112         ++idx;
   113         if (idx >= path->length()) idx = -1; 
   114         return *this; 
   115       }
   116 
   117       /// \brief Comparison operator
   118       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   119       /// \brief Comparison operator
   120       bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
   121       /// \brief Comparison operator
   122       bool operator<(const ArcIt& e) const { return idx<e.idx; }
   123 
   124     private:
   125       const Path *path;
   126       int idx;
   127     };
   128 
   129     /// \brief Length of the path.
   130     int length() const { return head.size() + tail.size(); }
   131     /// \brief Return whether the path is empty.
   132     bool empty() const { return head.empty() && tail.empty(); }
   133 
   134     /// \brief Reset the path to an empty one.
   135     void clear() { head.clear(); tail.clear(); }
   136 
   137     /// \brief The nth arc.
   138     ///
   139     /// \pre n is in the [0..length() - 1] range
   140     const Arc& nth(int n) const {
   141       return n < int(head.size()) ? *(head.rbegin() + n) :
   142         *(tail.begin() + (n - head.size()));
   143     }
   144 
   145     /// \brief Initialize arc iterator to point to the nth arc
   146     ///
   147     /// \pre n is in the [0..length() - 1] range
   148     ArcIt nthIt(int n) const {
   149       return ArcIt(*this, n);
   150     }
   151 
   152     /// \brief The first arc of the path
   153     const Arc& front() const {
   154       return head.empty() ? tail.front() : head.back();
   155     }
   156 
   157     /// \brief Add a new arc before the current path
   158     void addFront(const Arc& arc) {
   159       head.push_back(arc);
   160     }
   161 
   162     /// \brief Erase the first arc of the path
   163     void eraseFront() {
   164       if (!head.empty()) {
   165         head.pop_back();
   166       } else {
   167         head.clear();
   168         int halfsize = tail.size() / 2;
   169         head.resize(halfsize);
   170         std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
   171                   head.rbegin());
   172         std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
   173         tail.resize(tail.size() - halfsize - 1);
   174       }
   175     }
   176 
   177     /// \brief The last arc of the path
   178     const Arc& back() const {
   179       return tail.empty() ? head.front() : tail.back();
   180     }
   181 
   182     /// \brief Add a new arc behind the current path
   183     void addBack(const Arc& arc) {
   184       tail.push_back(arc);
   185     }
   186 
   187     /// \brief Erase the last arc of the path
   188     void eraseBack() {
   189       if (!tail.empty()) {
   190         tail.pop_back();
   191       } else {
   192         int halfsize = head.size() / 2;
   193         tail.resize(halfsize);
   194         std::copy(head.begin() + 1, head.begin() + halfsize + 1,
   195                   tail.rbegin());
   196         std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
   197         head.resize(head.size() - halfsize - 1);
   198       }
   199     }
   200 
   201     typedef True BuildTag;
   202 
   203     template <typename CPath>
   204     void build(const CPath& path) {
   205       int len = path.length();
   206       tail.reserve(len);
   207       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
   208         tail.push_back(it);
   209       }
   210     }
   211 
   212     template <typename CPath>
   213     void buildRev(const CPath& path) {
   214       int len = path.length();
   215       head.reserve(len);
   216       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
   217         head.push_back(it);
   218       }
   219     }
   220 
   221   protected:
   222     typedef std::vector<Arc> Container;
   223     Container head, tail;
   224 
   225   };
   226 
   227   /// \brief A structure for representing directed paths in a digraph.
   228   ///
   229   /// A structure for representing directed path in a digraph.
   230   /// \param Digraph The digraph type in which the path is.
   231   ///
   232   /// In a sense, the path can be treated as a list of arcs. The
   233   /// lemon path type stores just this list. As a consequence it
   234   /// cannot enumerate the nodes in the path and the zero length paths
   235   /// cannot store the source.
   236   ///
   237   /// This implementation is a just back insertable and erasable path
   238   /// type. It can be indexed in O(1) time. The back insertion and
   239   /// erasure is amortized O(1) time. This implementation is faster
   240   /// then the \c Path type because it use just one vector for the
   241   /// arcs.
   242   template <typename _Digraph>
   243   class SimplePath {
   244   public:
   245 
   246     typedef _Digraph Digraph;
   247     typedef typename Digraph::Arc Arc;
   248 
   249     /// \brief Default constructor
   250     ///
   251     /// Default constructor
   252     SimplePath() {}
   253 
   254     /// \brief Template copy constructor
   255     ///
   256     /// This path can be initialized with any other path type. It just
   257     /// makes a copy of the given path.
   258     template <typename CPath>
   259     SimplePath(const CPath& cpath) {
   260       copyPath(*this, cpath);
   261     }
   262 
   263     /// \brief Template copy assignment
   264     ///
   265     /// This path can be initialized with any other path type. It just
   266     /// makes a copy of the given path.
   267     template <typename CPath>
   268     SimplePath& operator=(const CPath& cpath) {
   269       copyPath(*this, cpath);
   270       return *this;
   271     }
   272 
   273     /// \brief Iterator class to iterate on the arcs of the paths
   274     ///
   275     /// This class is used to iterate on the arcs of the paths
   276     ///
   277     /// Of course it converts to Digraph::Arc
   278     class ArcIt {
   279       friend class SimplePath;
   280     public:
   281       /// Default constructor
   282       ArcIt() {}
   283       /// Invalid constructor
   284       ArcIt(Invalid) : path(0), idx(-1) {}
   285       /// \brief Initializate the constructor to the first arc of path
   286       ArcIt(const SimplePath &_path) 
   287         : path(&_path), idx(_path.empty() ? -1 : 0) {}
   288 
   289     private:
   290 
   291       /// Constructor with starting point
   292       ArcIt(const SimplePath &_path, int _idx) 
   293         : idx(_idx), path(&_path) {}
   294 
   295     public:
   296 
   297       ///Conversion to Digraph::Arc
   298       operator const Arc&() const {
   299         return path->nth(idx);
   300       }
   301 
   302       /// Next arc
   303       ArcIt& operator++() { 
   304         ++idx;
   305         if (idx >= path->length()) idx = -1; 
   306         return *this; 
   307       }
   308 
   309       /// Comparison operator
   310       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   311       /// Comparison operator
   312       bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
   313       /// Comparison operator
   314       bool operator<(const ArcIt& e) const { return idx<e.idx; }
   315 
   316     private:
   317       const SimplePath *path;
   318       int idx;
   319     };
   320 
   321     /// \brief Length of the path.
   322     int length() const { return data.size(); }
   323     /// \brief Return true if the path is empty.
   324     bool empty() const { return data.empty(); }
   325 
   326     /// \brief Reset the path to an empty one.
   327     void clear() { data.clear(); }
   328 
   329     /// \brief The nth arc.
   330     ///
   331     /// \pre n is in the [0..length() - 1] range
   332     const Arc& nth(int n) const {
   333       return data[n];
   334     }
   335 
   336     /// \brief  Initializes arc iterator to point to the nth arc.
   337     ArcIt nthIt(int n) const {
   338       return ArcIt(*this, n);
   339     }
   340 
   341     /// \brief The first arc of the path.
   342     const Arc& front() const {
   343       return data.front();
   344     }
   345 
   346     /// \brief The last arc of the path.
   347     const Arc& back() const {
   348       return data.back();
   349     }
   350 
   351     /// \brief Add a new arc behind the current path.
   352     void addBack(const Arc& arc) {
   353       data.push_back(arc);
   354     }
   355 
   356     /// \brief Erase the last arc of the path
   357     void eraseBack() {
   358       data.pop_back();
   359     }
   360 
   361     typedef True BuildTag;
   362 
   363     template <typename CPath>
   364     void build(const CPath& path) {
   365       int len = path.length();
   366       data.resize(len);
   367       int index = 0;
   368       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
   369         data[index] = it;;
   370         ++index;
   371       }
   372     }
   373 
   374     template <typename CPath>
   375     void buildRev(const CPath& path) {
   376       int len = path.length();
   377       data.resize(len);
   378       int index = len;
   379       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
   380         --index;
   381         data[index] = it;;
   382       }
   383     }
   384 
   385   protected:
   386     typedef std::vector<Arc> Container;
   387     Container data;
   388 
   389   };
   390 
   391   /// \brief A structure for representing directed paths in a digraph.
   392   ///
   393   /// A structure for representing directed path in a digraph.
   394   /// \param Digraph The digraph type in which the path is.
   395   ///
   396   /// In a sense, the path can be treated as a list of arcs. The
   397   /// lemon path type stores just this list. As a consequence it
   398   /// cannot enumerate the nodes in the path and the zero length paths
   399   /// cannot store the source.
   400   ///
   401   /// This implementation is a back and front insertable and erasable
   402   /// path type. It can be indexed in O(k) time, where k is the rank
   403   /// of the arc in the path. The length can be computed in O(n)
   404   /// time. The front and back insertion and erasure is O(1) time
   405   /// and it can be splited and spliced in O(1) time.
   406   template <typename _Digraph>
   407   class ListPath {
   408   public:
   409 
   410     typedef _Digraph Digraph;
   411     typedef typename Digraph::Arc Arc;
   412 
   413   protected:
   414 
   415     // the std::list<> is incompatible 
   416     // hard to create invalid iterator
   417     struct Node {
   418       Arc arc;
   419       Node *next, *prev;
   420     };
   421 
   422     Node *first, *last;
   423 
   424     std::allocator<Node> alloc;
   425 
   426   public:
   427  
   428     /// \brief Default constructor
   429     ///
   430     /// Default constructor
   431     ListPath() : first(0), last(0) {}
   432 
   433     /// \brief Template copy constructor
   434     ///
   435     /// This path can be initialized with any other path type. It just
   436     /// makes a copy of the given path.
   437     template <typename CPath>
   438     ListPath(const CPath& cpath) : first(0), last(0) {
   439       copyPath(*this, cpath);
   440     }
   441 
   442     /// \brief Destructor of the path
   443     ///
   444     /// Destructor of the path
   445     ~ListPath() {
   446       clear();
   447     }
   448 
   449     /// \brief Template copy assignment
   450     ///
   451     /// This path can be initialized with any other path type. It just
   452     /// makes a copy of the given path.
   453     template <typename CPath>
   454     ListPath& operator=(const CPath& cpath) {
   455       copyPath(*this, cpath);
   456       return *this;
   457     }
   458 
   459     /// \brief Iterator class to iterate on the arcs of the paths
   460     ///
   461     /// This class is used to iterate on the arcs of the paths
   462     ///
   463     /// Of course it converts to Digraph::Arc
   464     class ArcIt {
   465       friend class ListPath;
   466     public:
   467       /// Default constructor
   468       ArcIt() {}
   469       /// Invalid constructor
   470       ArcIt(Invalid) : path(0), node(0) {}
   471       /// \brief Initializate the constructor to the first arc of path
   472       ArcIt(const ListPath &_path) 
   473         : path(&_path), node(_path.first) {}
   474 
   475     protected:
   476 
   477       ArcIt(const ListPath &_path, Node *_node) 
   478         : path(&_path), node(_node) {}
   479 
   480 
   481     public:
   482 
   483       ///Conversion to Digraph::Arc
   484       operator const Arc&() const {
   485         return node->arc;
   486       }
   487 
   488       /// Next arc
   489       ArcIt& operator++() { 
   490         node = node->next;
   491         return *this; 
   492       }
   493 
   494       /// Comparison operator
   495       bool operator==(const ArcIt& e) const { return node==e.node; }
   496       /// Comparison operator
   497       bool operator!=(const ArcIt& e) const { return node!=e.node; }
   498       /// Comparison operator
   499       bool operator<(const ArcIt& e) const { return node<e.node; }
   500 
   501     private:
   502       const ListPath *path;
   503       Node *node;
   504     };
   505 
   506     /// \brief The nth arc.
   507     ///
   508     /// This function looks for the nth arc in O(n) time.
   509     /// \pre n is in the [0..length() - 1] range
   510     const Arc& nth(int n) const {
   511       Node *node = first;
   512       for (int i = 0; i < n; ++i) {
   513         node = node->next;
   514       }
   515       return node->arc;
   516     }
   517 
   518     /// \brief Initializes arc iterator to point to the nth arc.
   519     ArcIt nthIt(int n) const {
   520       Node *node = first;
   521       for (int i = 0; i < n; ++i) {
   522         node = node->next;
   523       }
   524       return ArcIt(*this, node);
   525     }
   526 
   527     /// \brief Length of the path.
   528     int length() const {
   529       int len = 0;
   530       Node *node = first;
   531       while (node != 0) {
   532         node = node->next;
   533         ++len;
   534       }
   535       return len;
   536     }
   537 
   538     /// \brief Return true if the path is empty.
   539     bool empty() const { return first == 0; }
   540 
   541     /// \brief Reset the path to an empty one.
   542     void clear() {
   543       while (first != 0) {
   544         last = first->next;
   545         alloc.destroy(first);
   546         alloc.deallocate(first, 1);
   547         first = last;
   548       }
   549     }
   550 
   551     /// \brief The first arc of the path
   552     const Arc& front() const {
   553       return first->arc;
   554     }
   555 
   556     /// \brief Add a new arc before the current path
   557     void addFront(const Arc& arc) {
   558       Node *node = alloc.allocate(1);
   559       alloc.construct(node, Node());
   560       node->prev = 0;
   561       node->next = first;
   562       node->arc = arc;
   563       if (first) {
   564         first->prev = node;
   565         first = node;
   566       } else {
   567         first = last = node;
   568       }
   569     }
   570 
   571     /// \brief Erase the first arc of the path
   572     void eraseFront() {
   573       Node *node = first;
   574       first = first->next;
   575       if (first) {
   576         first->prev = 0;
   577       } else {
   578         last = 0;
   579       }
   580       alloc.destroy(node);
   581       alloc.deallocate(node, 1);
   582     }
   583 
   584     /// \brief The last arc of the path.
   585     const Arc& back() const {
   586       return last->arc;
   587     }
   588 
   589     /// \brief Add a new arc behind the current path.
   590     void addBack(const Arc& arc) {
   591       Node *node = alloc.allocate(1);
   592       alloc.construct(node, Node());
   593       node->next = 0;
   594       node->prev = last;
   595       node->arc = arc;
   596       if (last) {
   597         last->next = node;
   598         last = node;
   599       } else {
   600         last = first = node;
   601       }
   602     }
   603 
   604     /// \brief Erase the last arc of the path
   605     void eraseBack() {
   606       Node *node = last;
   607       last = last->prev;
   608       if (last) {
   609         last->next = 0;
   610       } else {
   611         first = 0;
   612       }
   613       alloc.destroy(node);
   614       alloc.deallocate(node, 1);
   615     }
   616 
   617     /// \brief Splice a path to the back of the current path.
   618     ///
   619     /// It splices \c tpath to the back of the current path and \c
   620     /// tpath becomes empty. The time complexity of this function is
   621     /// O(1).
   622     void spliceBack(ListPath& tpath) {
   623       if (first) {
   624         if (tpath.first) {
   625           last->next = tpath.first;
   626           tpath.first->prev = last;
   627           last = tpath.last;
   628         }
   629       } else {
   630         first = tpath.first;
   631         last = tpath.last;
   632       }
   633       tpath.first = tpath.last = 0;
   634     }
   635 
   636     /// \brief Splice a path to the front of the current path.
   637     ///
   638     /// It splices \c tpath before the current path and \c tpath
   639     /// becomes empty. The time complexity of this function
   640     /// is O(1).
   641     void spliceFront(ListPath& tpath) {
   642       if (first) {
   643         if (tpath.first) {
   644           first->prev = tpath.last;
   645           tpath.last->next = first;
   646           first = tpath.first;
   647         }
   648       } else {
   649         first = tpath.first;
   650         last = tpath.last;
   651       }
   652       tpath.first = tpath.last = 0;
   653     }
   654 
   655     /// \brief Splice a path into the current path.
   656     ///
   657     /// It splices the \c tpath into the current path before the
   658     /// position of \c it iterator and \c tpath becomes empty. The
   659     /// time complexity of this function is O(1). If the \c it is
   660     /// \c INVALID then it will splice behind the current path.
   661     void splice(ArcIt it, ListPath& tpath) {
   662       if (it.node) {
   663         if (tpath.first) {
   664           tpath.first->prev = it.node->prev;
   665           if (it.node->prev) {
   666             it.node->prev->next = tpath.first;
   667           } else {
   668             first = tpath.first;
   669           }
   670           it.node->prev = tpath.last;
   671           tpath.last->next = it.node;
   672         }
   673       } else {
   674         if (first) {
   675           if (tpath.first) {
   676             last->next = tpath.first;
   677             tpath.first->prev = last;
   678             last = tpath.last;
   679           }
   680         } else {
   681           first = tpath.first;
   682           last = tpath.last;
   683         }
   684       }
   685       tpath.first = tpath.last = 0;
   686     }
   687 
   688     /// \brief Split the current path.
   689     ///
   690     /// It splits the current path into two parts. The part before
   691     /// the iterator \c it will remain in the current path and the part
   692     /// starting with
   693     /// \c it will put into \c tpath. If \c tpath have arcs
   694     /// before the operation they are removed first.  The time
   695     /// complexity of this function is O(1) plus the the time of emtying
   696     /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
   697     void split(ArcIt it, ListPath& tpath) {
   698       tpath.clear();
   699       if (it.node) {
   700         tpath.first = it.node;
   701         tpath.last = last;
   702         if (it.node->prev) {
   703           last = it.node->prev;
   704           last->next = 0;
   705         } else {
   706           first = last = 0;
   707         }
   708         it.node->prev = 0;
   709       }
   710     }
   711 
   712 
   713     typedef True BuildTag;
   714 
   715     template <typename CPath>
   716     void build(const CPath& path) {
   717       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
   718         addBack(it);
   719       }
   720     }
   721 
   722     template <typename CPath>
   723     void buildRev(const CPath& path) {
   724       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
   725         addFront(it);
   726       }
   727     }
   728 
   729   };
   730 
   731   /// \brief A structure for representing directed paths in a digraph.
   732   ///
   733   /// A structure for representing directed path in a digraph.
   734   /// \param Digraph The digraph type in which the path is.
   735   ///
   736   /// In a sense, the path can be treated as a list of arcs. The
   737   /// lemon path type stores just this list. As a consequence it
   738   /// cannot enumerate the nodes in the path and the source node of
   739   /// a zero length path is undefined.
   740   ///
   741   /// This implementation is completly static, i.e. it can be copy constucted
   742   /// or copy assigned from another path, but otherwise it cannot be
   743   /// modified.
   744   ///
   745   /// Being the the most memory efficient path type in LEMON,
   746   /// it is intented to be
   747   /// used when you want to store a large number of paths.
   748   template <typename _Digraph>
   749   class StaticPath {
   750   public:
   751 
   752     typedef _Digraph Digraph;
   753     typedef typename Digraph::Arc Arc;
   754 
   755     /// \brief Default constructor
   756     ///
   757     /// Default constructor
   758     StaticPath() : len(0), arcs(0) {}
   759     
   760     /// \brief Template copy constructor
   761     ///
   762     /// This path can be initialized from any other path type.
   763     template <typename CPath>
   764     StaticPath(const CPath& cpath) : arcs(0) {
   765       copyPath(*this, cpath);
   766     }
   767 
   768     /// \brief Destructor of the path
   769     ///
   770     /// Destructor of the path
   771     ~StaticPath() {
   772       if (arcs) delete[] arcs;
   773     }
   774 
   775     /// \brief Template copy assignment
   776     ///
   777     /// This path can be made equal to any other path type. It simply
   778     /// makes a copy of the given path.
   779     template <typename CPath>
   780     StaticPath& operator=(const CPath& cpath) {
   781       copyPath(*this, cpath);
   782       return *this;
   783     }
   784 
   785     /// \brief Iterator class to iterate on the arcs of the paths
   786     ///
   787     /// This class is used to iterate on the arcs of the paths
   788     ///
   789     /// Of course it converts to Digraph::Arc
   790     class ArcIt {
   791       friend class StaticPath;
   792     public:
   793       /// Default constructor
   794       ArcIt() {}
   795       /// Invalid constructor
   796       ArcIt(Invalid) : path(0), idx(-1) {}
   797       /// Initializate the constructor to the first arc of path
   798       ArcIt(const StaticPath &_path) 
   799         : path(&_path), idx(_path.empty() ? -1 : 0) {}
   800 
   801     private:
   802 
   803       /// Constructor with starting point
   804       ArcIt(const StaticPath &_path, int _idx) 
   805         : idx(_idx), path(&_path) {}
   806 
   807     public:
   808 
   809       ///Conversion to Digraph::Arc
   810       operator const Arc&() const {
   811         return path->nth(idx);
   812       }
   813 
   814       /// Next arc
   815       ArcIt& operator++() { 
   816         ++idx;
   817         if (idx >= path->length()) idx = -1; 
   818         return *this; 
   819       }
   820 
   821       /// Comparison operator
   822       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   823       /// Comparison operator
   824       bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
   825       /// Comparison operator
   826       bool operator<(const ArcIt& e) const { return idx<e.idx; }
   827 
   828     private:
   829       const StaticPath *path;
   830       int idx;
   831     };
   832 
   833     /// \brief The nth arc.
   834     ///
   835     /// \pre n is in the [0..length() - 1] range
   836     const Arc& nth(int n) const {
   837       return arcs[n];
   838     }
   839 
   840     /// \brief The arc iterator pointing to the nth arc.
   841     ArcIt nthIt(int n) const {
   842       return ArcIt(*this, n);
   843     }
   844 
   845     /// \brief The length of the path.
   846     int length() const { return len; }
   847 
   848     /// \brief Return true when the path is empty.
   849     int empty() const { return len == 0; }
   850 
   851     /// \break Erase all arcs in the digraph.
   852     void clear() {
   853       len = 0;
   854       if (arcs) delete[] arcs;
   855       arcs = 0;
   856     }
   857 
   858     /// \brief The first arc of the path.
   859     const Arc& front() const {
   860       return arcs[0];
   861     }
   862 
   863     /// \brief The last arc of the path.
   864     const Arc& back() const {
   865       return arcs[len - 1];
   866     }
   867 
   868 
   869     typedef True BuildTag;
   870 
   871     template <typename CPath>
   872     void build(const CPath& path) {
   873       len = path.length();
   874       arcs = new Arc[len];
   875       int index = 0;
   876       for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
   877         arcs[index] = it;
   878         ++index;
   879       }
   880     }
   881 
   882     template <typename CPath>
   883     void buildRev(const CPath& path) {
   884       len = path.length();
   885       arcs = new Arc[len];
   886       int index = len;
   887       for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
   888         --index;
   889         arcs[index] = it;
   890       }
   891     }
   892 
   893   private:
   894     int len;
   895     Arc* arcs;
   896   };
   897 
   898   ///////////////////////////////////////////////////////////////////////
   899   // Additional utilities
   900   ///////////////////////////////////////////////////////////////////////
   901 
   902   namespace _path_bits {
   903 
   904     template <typename Path, typename Enable = void>
   905     struct RevTagIndicator {
   906       static const bool value = false;
   907     };
   908 
   909     template <typename Digraph>
   910     struct RevTagIndicator<
   911       Digraph, 
   912       typename enable_if<typename Digraph::RevTag, void>::type
   913     > {
   914       static const bool value = true;
   915     };
   916 
   917     template <typename Target, typename Source,
   918               typename BuildEnable = void, typename RevEnable = void>
   919     struct PathCopySelector {
   920       static void copy(Target& target, const Source& source) {
   921         target.clear();
   922         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
   923           target.addBack(it);
   924         }
   925       }
   926     };
   927 
   928     template <typename Target, typename Source, typename BuildEnable>
   929     struct PathCopySelector<
   930       Target, Source, BuildEnable, 
   931       typename enable_if<typename Source::RevPathTag, void>::type> {
   932       static void copy(Target& target, const Source& source) {
   933         target.clear();
   934         for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
   935           target.addFront(it);
   936         }
   937       }
   938     };
   939 
   940     template <typename Target, typename Source, typename RevEnable>
   941     struct PathCopySelector<
   942       Target, Source, 
   943       typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
   944       static void copy(Target& target, const Source& source) {
   945         target.clear();
   946         target.build(source);
   947       }
   948     };
   949 
   950     template <typename Target, typename Source>
   951     struct PathCopySelector<
   952       Target, Source, 
   953       typename enable_if<typename Target::BuildTag, void>::type,
   954       typename enable_if<typename Source::RevPathTag, void>::type> {
   955       static void copy(Target& target, const Source& source) {
   956         target.clear();
   957         target.buildRev(source);
   958       }
   959     };
   960 
   961   }
   962 
   963 
   964   /// \brief Make a copy of a path.
   965   ///
   966   ///  This function makes a copy of a path.
   967   template <typename Target, typename Source>
   968   void copyPath(Target& target, const Source& source) {
   969     checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
   970     _path_bits::PathCopySelector<Target, Source>::copy(target, source);
   971   }
   972 
   973   /// \brief Check the consistency of a path.
   974   ///
   975   /// This function checks that the target of each arc is the same
   976   /// as the source of the next one. 
   977   /// 
   978   template <typename Digraph, typename Path>
   979   bool checkPath(const Digraph& digraph, const Path& path) {
   980     typename Path::ArcIt it(path);
   981     if (it == INVALID) return true;
   982     typename Digraph::Node node = digraph.target(it);
   983     ++it;
   984     while (it != INVALID) {
   985       if (digraph.source(it) != node) return false;
   986       node = digraph.target(it);
   987       ++it;
   988     }
   989     return true;
   990   }
   991 
   992   /// \brief The source of a path
   993   ///
   994   /// This function returns the source of the given path.
   995   template <typename Digraph, typename Path>
   996   typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
   997     return digraph.source(path.front());
   998   }
   999 
  1000   /// \brief The target of a path
  1001   ///
  1002   /// This function returns the target of the given path.
  1003   template <typename Digraph, typename Path>
  1004   typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
  1005     return digraph.target(path.back());
  1006   }
  1007 
  1008   /// \brief Class which helps to iterate through the nodes of a path
  1009   ///
  1010   /// In a sense, the path can be treated as a list of arcs. The
  1011   /// lemon path type stores only this list. As a consequence, it
  1012   /// cannot enumerate the nodes in the path and the zero length paths
  1013   /// cannot have a source node.
  1014   ///
  1015   /// This class implements the node iterator of a path structure. To
  1016   /// provide this feature, the underlying digraph should be passed to
  1017   /// the constructor of the iterator.
  1018   template <typename Path>
  1019   class PathNodeIt {
  1020   private:
  1021     const typename Path::Digraph *_digraph;
  1022     typename Path::ArcIt _it;
  1023     typename Path::Digraph::Node _nd;
  1024 
  1025   public:
  1026 
  1027     typedef typename Path::Digraph Digraph;
  1028     typedef typename Digraph::Node Node;
  1029     
  1030     /// Default constructor
  1031     PathNodeIt() {}
  1032     /// Invalid constructor
  1033     PathNodeIt(Invalid) 
  1034       : _digraph(0), _it(INVALID), _nd(INVALID) {}
  1035     /// Constructor
  1036     PathNodeIt(const Digraph& digraph, const Path& path) 
  1037       : _digraph(&digraph), _it(path) {
  1038       _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
  1039     }
  1040     /// Constructor
  1041     PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) 
  1042       : _digraph(&digraph), _it(path), _nd(src) {}
  1043 
  1044     ///Conversion to Digraph::Node
  1045     operator Node() const {
  1046       return _nd;
  1047     }
  1048 
  1049     /// Next node
  1050     PathNodeIt& operator++() {
  1051       if (_it == INVALID) _nd = INVALID;
  1052       else {
  1053 	_nd = _digraph->target(_it);
  1054 	++_it;
  1055       }
  1056       return *this;
  1057     }
  1058 
  1059     /// Comparison operator
  1060     bool operator==(const PathNodeIt& n) const { 
  1061       return _it == n._it && _nd == n._nd; 
  1062     }
  1063     /// Comparison operator
  1064     bool operator!=(const PathNodeIt& n) const { 
  1065       return _it != n._it || _nd != n._nd; 
  1066     }
  1067     /// Comparison operator
  1068     bool operator<(const PathNodeIt& n) const { 
  1069       return (_it < n._it && _nd != INVALID);
  1070     }
  1071     
  1072   };
  1073   
  1074   ///@}
  1075 
  1076 } // namespace lemon
  1077 
  1078 #endif // LEMON_PATH_H