COIN-OR::LEMON - Graph Library

source: lemon/lemon/path.h @ 1337:4add05447ca0

Last change on this file since 1337:4add05447ca0 was 1336:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 10 years ago

STL style iterators (#325)

For

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