COIN-OR::LEMON - Graph Library

source: lemon/lemon/path.h @ 1420:1f4f01870c1e

Last change on this file since 1420:1f4f01870c1e was 1420:1f4f01870c1e, checked in by Peter Kovacs <kpeter@…>, 14 months ago

API doc improvements for Path structures (#250)

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