COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/path.h

tip
Last change on this file was 1202:4fd76139b69e, checked in by Peter Kovacs <kpeter@…>, 21 months ago

Add operator[] to Path structures (#250)

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