COIN-OR::LEMON - Graph Library

source: lemon/lemon/path.h @ 548:41bdb4d6c8c3

Last change on this file since 548:41bdb4d6c8c3 was 548:41bdb4d6c8c3, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Fix in pathSource() and pathTarget() (#250)
and extend the doc.

File size: 29.6 KB
Line 
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-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/core.h>
32#include <lemon/concepts/path.h>
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.
43  /// \tparam _Digraph 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 _Digraph>
56  class Path {
57  public:
58
59    typedef _Digraph 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      copyPath(*this, cpath);
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      copyPath(*this, cpath);
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 n is in the [0..length() - 1] 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 n is in the [0..length() - 1] 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 _Digraph 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 _Digraph>
244  class SimplePath {
245  public:
246
247    typedef _Digraph 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      copyPath(*this, cpath);
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      copyPath(*this, cpath);
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 n is in the [0..length() - 1] 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 _Digraph 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 _Digraph>
408  class ListPath {
409  public:
410
411    typedef _Digraph 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      copyPath(*this, cpath);
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      copyPath(*this, cpath);
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 n is in the [0..length() - 1] 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 _Digraph 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 _Digraph>
750  class StaticPath {
751  public:
752
753    typedef _Digraph 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      copyPath(*this, cpath);
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      copyPath(*this, cpath);
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 n is in the [0..length() - 1] 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 Target, typename Source,
932              bool buildEnable = BuildTagIndicator<Target>::value>
933    struct PathCopySelectorForward {
934      static void copy(Target& target, const Source& source) {
935        target.clear();
936        for (typename Source::ArcIt it(source); it != INVALID; ++it) {
937          target.addBack(it);
938        }
939      }
940    };
941
942    template <typename Target, typename Source>
943    struct PathCopySelectorForward<Target, Source, true> {
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              bool buildEnable = BuildTagIndicator<Target>::value>
952    struct PathCopySelectorBackward {
953      static void copy(Target& target, const Source& source) {
954        target.clear();
955        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
956          target.addFront(it);
957        }
958      }
959    };
960
961    template <typename Target, typename Source>
962    struct PathCopySelectorBackward<Target, Source, true> {
963      static void copy(Target& target, const Source& source) {
964        target.clear();
965        target.buildRev(source);
966      }
967    };
968
969   
970    template <typename Target, typename Source,
971              bool revEnable = RevPathTagIndicator<Source>::value>
972    struct PathCopySelector {
973      static void copy(Target& target, const Source& source) {
974        PathCopySelectorForward<Target, Source>::copy(target, source);
975      }     
976    };
977
978    template <typename Target, typename Source>
979    struct PathCopySelector<Target, Source, true> {
980      static void copy(Target& target, const Source& source) {
981        PathCopySelectorBackward<Target, Source>::copy(target, source);
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 Target, typename Source>
992  void copyPath(Target& target, const Source& source) {
993    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
994    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
995  }
996
997  /// \brief Check the consistency of a path.
998  ///
999  /// This function checks that the target of each arc is the same
1000  /// as the source of the next one.
1001  ///
1002  template <typename Digraph, typename Path>
1003  bool checkPath(const Digraph& digraph, const Path& path) {
1004    typename Path::ArcIt it(path);
1005    if (it == INVALID) return true;
1006    typename Digraph::Node node = digraph.target(it);
1007    ++it;
1008    while (it != INVALID) {
1009      if (digraph.source(it) != node) return false;
1010      node = digraph.target(it);
1011      ++it;
1012    }
1013    return true;
1014  }
1015
1016  /// \brief The source of a path
1017  ///
1018  /// This function returns the source node of the given path.
1019  /// If the path is empty, then it returns \c INVALID.
1020  template <typename Digraph, typename Path>
1021  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1022    return path.empty() ? INVALID : digraph.source(path.front());
1023  }
1024
1025  /// \brief The target of a path
1026  ///
1027  /// This function returns the target node of the given path.
1028  /// If the path is empty, then it returns \c INVALID.
1029  template <typename Digraph, typename Path>
1030  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1031    return path.empty() ? INVALID : digraph.target(path.back());
1032  }
1033
1034  /// \brief Class which helps to iterate through the nodes of a path
1035  ///
1036  /// In a sense, the path can be treated as a list of arcs. The
1037  /// lemon path type stores only this list. As a consequence, it
1038  /// cannot enumerate the nodes in the path and the zero length paths
1039  /// cannot have a source node.
1040  ///
1041  /// This class implements the node iterator of a path structure. To
1042  /// provide this feature, the underlying digraph should be passed to
1043  /// the constructor of the iterator.
1044  template <typename Path>
1045  class PathNodeIt {
1046  private:
1047    const typename Path::Digraph *_digraph;
1048    typename Path::ArcIt _it;
1049    typename Path::Digraph::Node _nd;
1050
1051  public:
1052
1053    typedef typename Path::Digraph Digraph;
1054    typedef typename Digraph::Node Node;
1055
1056    /// Default constructor
1057    PathNodeIt() {}
1058    /// Invalid constructor
1059    PathNodeIt(Invalid)
1060      : _digraph(0), _it(INVALID), _nd(INVALID) {}
1061    /// Constructor
1062    PathNodeIt(const Digraph& digraph, const Path& path)
1063      : _digraph(&digraph), _it(path) {
1064      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1065    }
1066    /// Constructor
1067    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
1068      : _digraph(&digraph), _it(path), _nd(src) {}
1069
1070    ///Conversion to Digraph::Node
1071    operator Node() const {
1072      return _nd;
1073    }
1074
1075    /// Next node
1076    PathNodeIt& operator++() {
1077      if (_it == INVALID) _nd = INVALID;
1078      else {
1079        _nd = _digraph->target(_it);
1080        ++_it;
1081      }
1082      return *this;
1083    }
1084
1085    /// Comparison operator
1086    bool operator==(const PathNodeIt& n) const {
1087      return _it == n._it && _nd == n._nd;
1088    }
1089    /// Comparison operator
1090    bool operator!=(const PathNodeIt& n) const {
1091      return _it != n._it || _nd != n._nd;
1092    }
1093    /// Comparison operator
1094    bool operator<(const PathNodeIt& n) const {
1095      return (_it < n._it && _nd != INVALID);
1096    }
1097
1098  };
1099
1100  ///@}
1101
1102} // namespace lemon
1103
1104#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.