COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/path.h

1.2
Last change on this file was 958:a5810903ed28, checked in by Alpar Juttner <alpar@…>, 7 years ago

Merge bugfix #444 to branch 1.2

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