COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/path.h @ 98:c4582fc14f58

Last change on this file since 98:c4582fc14f58 was 98:c4582fc14f58, checked in by Alpar Juttner <alpar@…>, 17 years ago

Merge path_utils.h into path.h

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