lemon/path.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 20 Feb 2010 18:39:03 +0100
changeset 839 f3bc4e9b5f3a
parent 784 1a7fe3bef514
parent 802 994c7df296c9
child 877 141f9c0db4a3
permissions -rw-r--r--
New heuristics for MCF algorithms (#340)
and some implementation improvements.

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