COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/path.h @ 991:a10624ed1997

Last change on this file since 991:a10624ed1997 was 991:a10624ed1997, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge bugfix #444

File size: 30.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-2010
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 GR The digraph type in which the path is.
44  ///
45  /// In a sense, the path can be treated as a list of arcs. The
46  /// LEMON path type stores just this list. As a consequence, it
47  /// cannot enumerate the nodes of the path and the source node of
48  /// a zero length path is undefined.
49  ///
50  /// This implementation is a back and front insertable and erasable
51  /// path type. It can be indexed in O(1) time. The front and back
52  /// insertion and erase is done in O(1) (amortized) time. The
53  /// implementation uses two vectors for storing the front and back
54  /// insertions.
55  template <typename GR>
56  class Path {
57  public:
58
59    typedef GR Digraph;
60    typedef typename Digraph::Arc Arc;
61
62    /// \brief Default constructor
63    ///
64    /// Default constructor
65    Path() {}
66
67    /// \brief Copy constructor
68    ///
69    Path(const Path& cpath) {
70      pathCopy(cpath, *this);
71    }
72
73    /// \brief Template copy constructor
74    ///
75    /// This constuctor initializes the path from any other path type.
76    /// It simply makes a copy of the given path.
77    template <typename CPath>
78    Path(const CPath& cpath) {
79      pathCopy(cpath, *this);
80    }
81
82    /// \brief Copy assignment
83    ///
84    Path& operator=(const Path& cpath) {
85      pathCopy(cpath, *this);
86      return *this;
87    }
88
89    /// \brief Template copy assignment
90    ///
91    /// This operator makes a copy of a path of any other type.
92    template <typename CPath>
93    Path& operator=(const CPath& cpath) {
94      pathCopy(cpath, *this);
95      return *this;
96    }
97
98    /// \brief LEMON style iterator for path arcs
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) {}
108      /// \brief Initializate the iterator to the first arc of path
109      ArcIt(const Path &_path)
110        : path(&_path), idx(_path.empty() ? -1 : 0) {}
111
112    private:
113
114      ArcIt(const Path &_path, int _idx)
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
125      ArcIt& operator++() {
126        ++idx;
127        if (idx >= path->length()) idx = -1;
128        return *this;
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(); }
145    /// \brief Return whether the path is empty.
146    bool empty() const { return head.empty() && tail.empty(); }
147
148    /// \brief Reset the path to an empty one.
149    void clear() { head.clear(); tail.clear(); }
150
151    /// \brief The n-th arc.
152    ///
153    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
154    const Arc& nth(int n) const {
155      return n < int(head.size()) ? *(head.rbegin() + n) :
156        *(tail.begin() + (n - head.size()));
157    }
158
159    /// \brief Initialize arc iterator to point to the n-th arc
160    ///
161    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
162    ArcIt nthIt(int n) const {
163      return ArcIt(*this, n);
164    }
165
166    /// \brief The first arc of the path
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
191    /// \brief The last arc of the path
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.
244  /// \tparam GR The digraph type in which the path is.
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.
256  template <typename GR>
257  class SimplePath {
258  public:
259
260    typedef GR Digraph;
261    typedef typename Digraph::Arc Arc;
262
263    /// \brief Default constructor
264    ///
265    /// Default constructor
266    SimplePath() {}
267
268    /// \brief Copy constructor
269    ///
270    SimplePath(const SimplePath& cpath) {
271      pathCopy(cpath, *this);
272    }
273
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) {
280      pathCopy(cpath, *this);
281    }
282
283    /// \brief Copy assignment
284    ///
285    SimplePath& operator=(const SimplePath& cpath) {
286      pathCopy(cpath, *this);
287      return *this;
288    }
289
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) {
296      pathCopy(cpath, *this);
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
313      ArcIt(const SimplePath &_path)
314        : path(&_path), idx(_path.empty() ? -1 : 0) {}
315
316    private:
317
318      /// Constructor with starting point
319      ArcIt(const SimplePath &_path, int _idx)
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
330      ArcIt& operator++() {
331        ++idx;
332        if (idx >= path->length()) idx = -1;
333        return *this;
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(); }
350    /// \brief Return true if the path is empty.
351    bool empty() const { return data.empty(); }
352
353    /// \brief Reset the path to an empty one.
354    void clear() { data.clear(); }
355
356    /// \brief The n-th arc.
357    ///
358    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
359    const Arc& nth(int n) const {
360      return data[n];
361    }
362
363    /// \brief  Initializes arc iterator to point to the n-th arc.
364    ArcIt nthIt(int n) const {
365      return ArcIt(*this, n);
366    }
367
368    /// \brief The first arc of the path.
369    const Arc& front() const {
370      return data.front();
371    }
372
373    /// \brief The last arc of the path.
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.
421  /// \tparam GR The digraph type in which the path is.
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.
433  template <typename GR>
434  class ListPath {
435  public:
436
437    typedef GR Digraph;
438    typedef typename Digraph::Arc Arc;
439
440  protected:
441
442    // the std::list<> is incompatible
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:
454
455    /// \brief Default constructor
456    ///
457    /// Default constructor
458    ListPath() : first(0), last(0) {}
459
460    /// \brief Copy constructor
461    ///
462    ListPath(const ListPath& cpath) : first(0), last(0) {
463      pathCopy(cpath, *this);
464    }
465
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) {
472      pathCopy(cpath, *this);
473    }
474
475    /// \brief Destructor of the path
476    ///
477    /// Destructor of the path
478    ~ListPath() {
479      clear();
480    }
481
482    /// \brief Copy assignment
483    ///
484    ListPath& operator=(const ListPath& cpath) {
485      pathCopy(cpath, *this);
486      return *this;
487    }
488
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) {
495      pathCopy(cpath, *this);
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
512      ArcIt(const ListPath &_path)
513        : path(&_path), node(_path.first) {}
514
515    protected:
516
517      ArcIt(const ListPath &_path, Node *_node)
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
529      ArcIt& operator++() {
530        node = node->next;
531        return *this;
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
546    /// \brief The n-th arc.
547    ///
548    /// This function looks for the n-th arc in O(n) time.
549    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
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 n-th 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
578    /// \brief Return true if the path is empty.
579    bool empty() const { return first == 0; }
580
581    /// \brief Reset the path to an empty one.
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
591    /// \brief The first arc of the path
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
624    /// \brief The last arc of the path.
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
657    /// \brief Splice a path to the back of the current path.
658    ///
659    /// It splices \c tpath to the back of the current path and \c
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
676    /// \brief Splice a path to the front of the current path.
677    ///
678    /// It splices \c tpath before the current path and \c tpath
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
695    /// \brief Splice a path into the current path.
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
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.
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
728    /// \brief Split the current path.
729    ///
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
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.
774  /// \tparam GR The digraph type in which the path is.
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
778  /// cannot enumerate the nodes in the path and the source node of
779  /// a zero length path is undefined.
780  ///
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.
788  template <typename GR>
789  class StaticPath {
790  public:
791
792    typedef GR Digraph;
793    typedef typename Digraph::Arc Arc;
794
795    /// \brief Default constructor
796    ///
797    /// Default constructor
798    StaticPath() : len(0), arcs(0) {}
799
800    /// \brief Copy constructor
801    ///
802    StaticPath(const StaticPath& cpath) : arcs(0) {
803      pathCopy(cpath, *this);
804    }
805
806    /// \brief Template copy constructor
807    ///
808    /// This path can be initialized from any other path type.
809    template <typename CPath>
810    StaticPath(const CPath& cpath) : arcs(0) {
811      pathCopy(cpath, *this);
812    }
813
814    /// \brief Destructor of the path
815    ///
816    /// Destructor of the path
817    ~StaticPath() {
818      if (arcs) delete[] arcs;
819    }
820
821    /// \brief Copy assignment
822    ///
823    StaticPath& operator=(const StaticPath& cpath) {
824      pathCopy(cpath, *this);
825      return *this;
826    }
827
828    /// \brief Template copy assignment
829    ///
830    /// This path can be made equal to any other path type. It simply
831    /// makes a copy of the given path.
832    template <typename CPath>
833    StaticPath& operator=(const CPath& cpath) {
834      pathCopy(cpath, *this);
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
851      ArcIt(const StaticPath &_path)
852        : path(&_path), idx(_path.empty() ? -1 : 0) {}
853
854    private:
855
856      /// Constructor with starting point
857      ArcIt(const StaticPath &_path, int _idx)
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
868      ArcIt& operator++() {
869        ++idx;
870        if (idx >= path->length()) idx = -1;
871        return *this;
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
886    /// \brief The n-th arc.
887    ///
888    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
889    const Arc& nth(int n) const {
890      return arcs[n];
891    }
892
893    /// \brief The arc iterator pointing to the n-th arc.
894    ArcIt nthIt(int n) const {
895      return ArcIt(*this, n);
896    }
897
898    /// \brief The length of the path.
899    int length() const { return len; }
900
901    /// \brief Return true when the path is empty.
902    int empty() const { return len == 0; }
903
904    /// \brief Erase all arcs in the digraph.
905    void clear() {
906      len = 0;
907      if (arcs) delete[] arcs;
908      arcs = 0;
909    }
910
911    /// \brief The first arc of the path.
912    const Arc& front() const {
913      return arcs[0];
914    }
915
916    /// \brief The last arc of the path.
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
951  ///////////////////////////////////////////////////////////////////////
952  // Additional utilities
953  ///////////////////////////////////////////////////////////////////////
954
955  namespace _path_bits {
956
957    template <typename Path, typename Enable = void>
958    struct RevPathTagIndicator {
959      static const bool value = false;
960    };
961
962    template <typename Path>
963    struct RevPathTagIndicator<
964      Path,
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<
977      Path,
978      typename enable_if<typename Path::BuildTag, void>::type
979    > {
980      static const bool value = true;
981    };
982
983    template <typename From, typename To,
984              bool buildEnable = BuildTagIndicator<To>::value>
985    struct PathCopySelectorForward {
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);
990        }
991      }
992    };
993
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);
999      }
1000    };
1001
1002    template <typename From, typename To,
1003              bool buildEnable = BuildTagIndicator<To>::value>
1004    struct PathCopySelectorBackward {
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);
1009        }
1010      }
1011    };
1012
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);
1018      }
1019    };
1020
1021
1022    template <typename From, typename To,
1023              bool revEnable = RevPathTagIndicator<From>::value>
1024    struct PathCopySelector {
1025      static void copy(const From& from, To& to) {
1026        PathCopySelectorForward<From, To>::copy(from, to);
1027      }
1028    };
1029
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);
1034      }
1035    };
1036
1037  }
1038
1039
1040  /// \brief Make a copy of a path.
1041  ///
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);
1055  }
1056
1057  /// \brief Check the consistency of a path.
1058  ///
1059  /// This function checks that the target of each arc is the same
1060  /// as the source of the next one.
1061  ///
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  ///
1078  /// This function returns the source node of the given path.
1079  /// If the path is empty, then it returns \c INVALID.
1080  template <typename Digraph, typename Path>
1081  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1082    return path.empty() ? INVALID : digraph.source(path.front());
1083  }
1084
1085  /// \brief The target of a path
1086  ///
1087  /// This function returns the target node of the given path.
1088  /// If the path is empty, then it returns \c INVALID.
1089  template <typename Digraph, typename Path>
1090  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1091    return path.empty() ? INVALID : digraph.target(path.back());
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;
1115
1116    /// Default constructor
1117    PathNodeIt() {}
1118    /// Invalid constructor
1119    PathNodeIt(Invalid)
1120      : _digraph(0), _it(INVALID), _nd(INVALID) {}
1121    /// Constructor
1122    PathNodeIt(const Digraph& digraph, const Path& path)
1123      : _digraph(&digraph), _it(path) {
1124      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1125    }
1126    /// Constructor
1127    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
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 {
1139        _nd = _digraph->target(_it);
1140        ++_it;
1141      }
1142      return *this;
1143    }
1144
1145    /// Comparison operator
1146    bool operator==(const PathNodeIt& n) const {
1147      return _it == n._it && _nd == n._nd;
1148    }
1149    /// Comparison operator
1150    bool operator!=(const PathNodeIt& n) const {
1151      return _it != n._it || _nd != n._nd;
1152    }
1153    /// Comparison operator
1154    bool operator<(const PathNodeIt& n) const {
1155      return (_it < n._it && _nd != INVALID);
1156    }
1157
1158  };
1159
1160  ///@}
1161
1162} // namespace lemon
1163
1164#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.