COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path.h @ 2339:c329fe995b40

Last change on this file since 2339:c329fe995b40 was 2336:215a6f3e33c9, checked in by athos, 13 years ago

Nothing serious.

File size: 23.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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
20///\ingroup paths
21///\file
22///\brief Classes for representing paths in graphs.
23///
24
25#ifndef LEMON_PATH_H
26#define LEMON_PATH_H
27
28#include <vector>
29#include <algorithm>
30
31#include <lemon/path_utils.h>
32#include <lemon/error.h>
33#include <lemon/bits/invalid.h>
34
35namespace lemon {
36
37  /// \addtogroup paths
38  /// @{
39
40
41  /// \brief A structure for representing directed paths in a graph.
42  ///
43  /// A structure for representing directed path in a graph.
44  /// \param Graph The graph type in which the path is.
45  ///
46  /// In a sense, the path can be treated as a list of edges. The
47  /// lemon path type stores just this list. As a consequence it
48  /// cannot enumerate the nodes in the path and the zero length paths
49  /// cannot store the source.
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 erasure is amortized O(1) time. The
54  /// impelementation is based on two opposite organized vectors.
55  template <typename _Graph>
56  class Path {
57  public:
58
59    typedef _Graph Graph;
60    typedef typename Graph::Edge Edge;
61
62    /// \brief Default constructor
63    ///
64    /// Default constructor
65    Path() {}
66
67    /// \brief Template copy constructor
68    ///
69    /// This path can be initialized with any other path type. It just
70    /// makes a copy of the given path.
71    template <typename CPath>
72    Path(const CPath& cpath) {
73      copyPath(*this, cpath);
74    }
75
76    /// \brief Template copy assignment
77    ///
78    /// This path can be initialized with any other path type. It just
79    /// makes a copy of the given path.
80    template <typename CPath>
81    Path& operator=(const CPath& cpath) {
82      copyPath(*this, cpath);
83      return *this;
84    }
85
86    /// \brief Lemon style iterator for path edges
87    ///
88    /// This class is used to iterate on the edges of the paths.
89    class EdgeIt {
90      friend class Path;
91    public:
92      /// \brief Default constructor
93      EdgeIt() {}
94      /// \brief Invalid constructor
95      EdgeIt(Invalid) : path(0), idx(-1) {}
96      /// \brief Initializate the constructor to the first edge of path
97      EdgeIt(const Path &_path)
98        : path(&_path), idx(_path.empty() ? -1 : 0) {}
99
100    private:
101
102      EdgeIt(const Path &_path, int _idx)
103        : idx(_idx), path(&_path) {}
104
105    public:
106
107      /// \brief Conversion to Edge
108      operator const Edge&() const {
109        return path->nth(idx);
110      }
111
112      /// \brief Next edge
113      EdgeIt& operator++() {
114        ++idx;
115        if (idx >= path->length()) idx = -1;
116        return *this;
117      }
118
119      /// \brief Comparison operator
120      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
121      /// \brief Comparison operator
122      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
123      /// \brief Comparison operator
124      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
125
126    private:
127      const Path *path;
128      int idx;
129    };
130
131    /// \brief Length of the path.
132    int length() const { return head.size() + tail.size(); }
133    /// \brief Returns whether the path is empty.
134    bool empty() const { return head.empty() && tail.empty(); }
135
136    /// \brief Resets the path to an empty path.
137    void clear() { head.clear(); tail.clear(); }
138
139    /// \brief Gives back the nth edge.
140    ///
141    /// \pre n is in the [0..length() - 1] range
142    const Edge& nth(int n) const {
143      return n < (int)head.size() ? *(head.rbegin() + n) :
144        *(tail.begin() + (n - head.size()));
145    }
146
147    /// \brief Initializes edge iterator to point to the nth edge
148    ///
149    /// \pre n is in the [0..length() - 1] range
150    EdgeIt nthIt(int n) const {
151      return EdgeIt(*this, n);
152    }
153
154    /// \brief Gives back the first edge of the path
155    const Edge& front() const {
156      return head.empty() ? tail.front() : head.back();
157    }
158
159    /// \brief Add a new edge before the current path
160    void addFront(const Edge& edge) {
161      head.push_back(edge);
162    }
163
164    /// \brief Erase the first edge of the path
165    void eraseFront() {
166      if (!head.empty()) {
167        head.pop_back();
168      } else {
169        head.clear();
170        int halfsize = tail.size() / 2;
171        head.resize(halfsize);
172        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
173                  head.rbegin());
174        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
175        tail.resize(tail.size() - halfsize - 1);
176      }
177    }
178
179    /// \brief Gives back the last edge of the path
180    const Edge& back() const {
181      return tail.empty() ? head.front() : tail.back();
182    }
183
184    /// \brief Add a new edge behind the current path
185    void addBack(const Edge& edge) {
186      tail.push_back(edge);
187    }
188
189    /// \brief Erase the last edge of the path
190    void eraseBack() {
191      if (!tail.empty()) {
192        tail.pop_back();
193      } else {
194        int halfsize = head.size() / 2;
195        tail.resize(halfsize);
196        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
197                  tail.rbegin());
198        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
199        head.resize(head.size() - halfsize - 1);
200      }
201    }
202
203
204
205    typedef True BuildTag;
206
207    template <typename CPath>
208    void build(const CPath& path) {
209      int len = path.length();
210      tail.reserve(len);
211      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
212        tail.push_back(it);
213      }
214    }
215
216    template <typename CPath>
217    void buildRev(const CPath& path) {
218      int len = path.length();
219      head.reserve(len);
220      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
221        head.push_back(it);
222      }
223    }
224
225  protected:
226    typedef std::vector<Edge> Container;
227    Container head, tail;
228
229  };
230
231  /// \brief A structure for representing directed paths in a graph.
232  ///
233  /// A structure for representing directed path in a graph.
234  /// \param Graph The graph type in which the path is.
235  ///
236  /// In a sense, the path can be treated as a list of edges. The
237  /// lemon path type stores just this list. As a consequence it
238  /// cannot enumerate the nodes in the path and the zero length paths
239  /// cannot store the source.
240  ///
241  /// This implementation is a just back insertable and erasable path
242  /// type. It can be indexed in O(1) time. The back insertion and
243  /// erasure is amortized O(1) time. This implementation is faster
244  /// then the \c Path type because it use just one vector for the
245  /// edges.
246  template <typename _Graph>
247  class SimplePath {
248  public:
249
250    typedef _Graph Graph;
251    typedef typename Graph::Edge Edge;
252
253    /// \brief Default constructor
254    ///
255    /// Default constructor
256    SimplePath() {}
257
258    /// \brief Template copy constructor
259    ///
260    /// This path can be initialized with any other path type. It just
261    /// makes a copy of the given path.
262    template <typename CPath>
263    SimplePath(const CPath& cpath) {
264      copyPath(*this, cpath);
265    }
266
267    /// \brief Template copy assignment
268    ///
269    /// This path can be initialized with any other path type. It just
270    /// makes a copy of the given path.
271    template <typename CPath>
272    SimplePath& operator=(const CPath& cpath) {
273      copyPath(*this, cpath);
274      return *this;
275    }
276
277    /// \brief Iterator class to iterate on the edges of the paths
278    ///
279    /// This class is used to iterate on the edges of the paths
280    ///
281    /// Of course it converts to Graph::Edge
282    class EdgeIt {
283      friend class SimplePath;
284    public:
285      /// Default constructor
286      EdgeIt() {}
287      /// Invalid constructor
288      EdgeIt(Invalid) : path(0), idx(-1) {}
289      /// \brief Initializate the constructor to the first edge of path
290      EdgeIt(const SimplePath &_path)
291        : path(&_path), idx(_path.empty() ? -1 : 0) {}
292
293    private:
294
295      /// Constructor with starting point
296      EdgeIt(const SimplePath &_path, int _idx)
297        : idx(_idx), path(&_path) {}
298
299    public:
300
301      ///Conversion to Graph::Edge
302      operator const Edge&() const {
303        return path->nth(idx);
304      }
305
306      /// Next edge
307      EdgeIt& operator++() {
308        ++idx;
309        if (idx >= path->length()) idx = -1;
310        return *this;
311      }
312
313      /// Comparison operator
314      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
315      /// Comparison operator
316      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
317      /// Comparison operator
318      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
319
320    private:
321      const SimplePath *path;
322      int idx;
323    };
324
325    /// \brief Length of the path.
326    int length() const { return data.size(); }
327    /// \brief Returns whether the path is empty.
328    bool empty() const { return data.empty(); }
329
330    /// \brief Resets the path to an empty path.
331    void clear() { data.clear(); }
332
333    /// \brief Gives back the nth edge.
334    ///
335    /// \pre n is in the [0..length() - 1] range
336    const Edge& nth(int n) const {
337      return data[n];
338    }
339
340    /// \brief  Initializes edge iterator to point to the nth edge.
341    EdgeIt nthIt(int n) const {
342      return EdgeIt(*this, n);
343    }
344
345    /// \brief Gives back the last edge of the path.
346    const Edge& back() const {
347      return data.back();
348    }
349
350    /// \brief Add a new edge behind the current path.
351    void addBack(const Edge& edge) {
352      data.push_back(edge);
353    }
354
355    /// \brief Erase the last edge of the path
356    void eraseBack() {
357      data.pop_back();
358    }
359
360    typedef True BuildTag;
361
362    template <typename CPath>
363    void build(const CPath& path) {
364      int len = path.length();
365      data.resize(len);
366      int index = 0;
367      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
368        data[index] = it;;
369        ++index;
370      }
371    }
372
373    template <typename CPath>
374    void buildRev(const CPath& path) {
375      int len = path.length();
376      data.resize(len);
377      int index = len;
378      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
379        --index;
380        data[index] = it;;
381      }
382    }
383
384  protected:
385    typedef std::vector<Edge> Container;
386    Container data;
387
388  };
389
390  /// \brief A structure for representing directed paths in a graph.
391  ///
392  /// A structure for representing directed path in a graph.
393  /// \param Graph The graph type in which the path is.
394  ///
395  /// In a sense, the path can be treated as a list of edges. The
396  /// lemon path type stores just this list. As a consequence it
397  /// cannot enumerate the nodes in the path and the zero length paths
398  /// cannot store the source.
399  ///
400  /// This implementation is a back and front insertable and erasable
401  /// path type. It can be indexed in O(k) time, where k is the rank
402  /// of the edge in the path. The length can be computed in O(n)
403  /// time. The front and back insertion and erasure is O(1) time
404  /// and it can be splited and spliced in O(1) time.
405  template <typename _Graph>
406  class ListPath {
407  public:
408
409    typedef _Graph Graph;
410    typedef typename Graph::Edge Edge;
411
412  protected:
413
414    // the std::list<> is incompatible
415    // hard to create invalid iterator
416    struct Node {
417      Edge edge;
418      Node *next, *prev;
419    };
420
421    Node *first, *last;
422
423    std::allocator<Node> alloc;
424
425  public:
426 
427    /// \brief Default constructor
428    ///
429    /// Default constructor
430    ListPath() : first(0), last(0) {}
431
432    /// \brief Template copy constructor
433    ///
434    /// This path can be initialized with any other path type. It just
435    /// makes a copy of the given path.
436    template <typename CPath>
437    ListPath(const CPath& cpath) : first(0), last(0) {
438      copyPath(*this, cpath);
439    }
440
441    /// \brief Destructor of the path
442    ///
443    /// Destructor of the path
444    ~ListPath() {
445      clear();
446    }
447
448    /// \brief Template copy assignment
449    ///
450    /// This path can be initialized with any other path type. It just
451    /// makes a copy of the given path.
452    template <typename CPath>
453    ListPath& operator=(const CPath& cpath) {
454      copyPath(*this, cpath);
455      return *this;
456    }
457
458    /// \brief Iterator class to iterate on the edges of the paths
459    ///
460    /// This class is used to iterate on the edges of the paths
461    ///
462    /// Of course it converts to Graph::Edge
463    class EdgeIt {
464      friend class ListPath;
465    public:
466      /// Default constructor
467      EdgeIt() {}
468      /// Invalid constructor
469      EdgeIt(Invalid) : path(0), node(0) {}
470      /// \brief Initializate the constructor to the first edge of path
471      EdgeIt(const ListPath &_path)
472        : path(&_path), node(_path.first) {}
473
474    protected:
475
476      EdgeIt(const ListPath &_path, Node *_node)
477        : path(&_path), node(_node) {}
478
479
480    public:
481
482      ///Conversion to Graph::Edge
483      operator const Edge&() const {
484        return node->edge;
485      }
486
487      /// Next edge
488      EdgeIt& operator++() {
489        node = node->next;
490        return *this;
491      }
492
493      /// Comparison operator
494      bool operator==(const EdgeIt& e) const { return node==e.node; }
495      /// Comparison operator
496      bool operator!=(const EdgeIt& e) const { return node!=e.node; }
497      /// Comparison operator
498      bool operator<(const EdgeIt& e) const { return node<e.node; }
499
500    private:
501      const ListPath *path;
502      Node *node;
503    };
504
505    /// \brief Gives back the nth edge.
506    ///
507    /// Gives back the nth edge in O(n) time.
508    /// \pre n is in the [0..length() - 1] range
509    const Edge& nth(int n) const {
510      Node *node = first;
511      for (int i = 0; i < n; ++i) {
512        node = node->next;
513      }
514      return node->edge;
515    }
516
517    /// \brief Initializes edge iterator to point to the nth edge.
518    EdgeIt nthIt(int n) const {
519      Node *node = first;
520      for (int i = 0; i < n; ++i) {
521        node = node->next;
522      }
523      return EdgeIt(*this, node);
524    }
525
526    /// \brief Length of the path.
527    int length() const {
528      int len = 0;
529      Node *node = first;
530      while (node != 0) {
531        node = node->next;
532        ++len;
533      }
534      return len;
535    }
536
537    /// \brief Returns whether the path is empty.
538    bool empty() const { return first == 0; }
539
540    /// \brief Resets the path to an empty path.
541    void clear() {
542      while (first != 0) {
543        last = first->next;
544        alloc.destroy(first);
545        alloc.deallocate(first, 1);
546        first = last;
547      }
548    }
549
550    /// \brief Gives back the first edge of the path
551    const Edge& front() const {
552      return first->edge;
553    }
554
555    /// \brief Add a new edge before the current path
556    void addFront(const Edge& edge) {
557      Node *node = alloc.allocate(1);
558      alloc.construct(node, Node());
559      node->prev = 0;
560      node->next = first;
561      node->edge = edge;
562      if (first) {
563        first->prev = node;
564        first = node;
565      } else {
566        first = last = node;
567      }
568    }
569
570    /// \brief Erase the first edge of the path
571    void eraseFront() {
572      Node *node = first;
573      first = first->next;
574      if (first) {
575        first->prev = 0;
576      } else {
577        last = 0;
578      }
579      alloc.destroy(node);
580      alloc.deallocate(node, 1);
581    }
582
583    /// \brief Gives back the last edge of the path.
584    const Edge& back() const {
585      return last->edge;
586    }
587
588    /// \brief Add a new edge behind the current path.
589    void addBack(const Edge& edge) {
590      Node *node = alloc.allocate(1);
591      alloc.construct(node, Node());
592      node->next = 0;
593      node->prev = last;
594      node->edge = edge;
595      if (last) {
596        last->next = node;
597        last = node;
598      } else {
599        last = first = node;
600      }
601    }
602
603    /// \brief Erase the last edge of the path
604    void eraseBack() {
605      Node *node = last;
606      last = last->prev;
607      if (last) {
608        last->next = 0;
609      } else {
610        first = 0;
611      }
612      alloc.destroy(node);
613      alloc.deallocate(node, 1);
614    }
615
616    /// \brief Splicing the given path to the current path.
617    ///
618    /// It splices the \c tpath to the back of the current path and \c
619    /// tpath becomes empty. The time complexity of this function is
620    /// O(1).
621    void spliceBack(ListPath& tpath) {
622      if (first) {
623        if (tpath.first) {
624          last->next = tpath.first;
625          tpath.first->prev = last;
626          last = tpath.last;
627        }
628      } else {
629        first = tpath.first;
630        last = tpath.last;
631      }
632      tpath.first = tpath.last = 0;
633    }
634
635    /// \brief Splicing the given path to the current path.
636    ///
637    /// It splices the \c tpath before the current path and \c tpath
638    /// becomes empty. The time complexity of this function
639    /// is O(1).
640    void spliceFront(ListPath& tpath) {
641      if (first) {
642        if (tpath.first) {
643          first->prev = tpath.last;
644          tpath.last->next = first;
645          first = tpath.first;
646        }
647      } else {
648        first = tpath.first;
649        last = tpath.last;
650      }
651      tpath.first = tpath.last = 0;
652    }
653
654    /// \brief Splicing the given path into the current path.
655    ///
656    /// It splices the \c tpath into the current path before the
657    /// position of \c it iterator and \c tpath becomes empty. The
658    /// time complexity of this function is O(1). If the \c it is \c
659    /// INVALID then it will splice behind the current path.
660    void splice(EdgeIt it, ListPath& tpath) {
661      if (it.node) {
662        if (tpath.first) {
663          tpath.first->prev = it.node->prev;
664          if (it.node->prev) {
665            it.node->prev->next = tpath.first;
666          } else {
667            first = tpath.first;
668          }
669          it.node->prev = tpath.last;
670          tpath.last->next = it.node;
671        }
672      } else {
673        if (first) {
674          if (tpath.first) {
675            last->next = tpath.first;
676            tpath.first->prev = last;
677            last = tpath.last;
678          }
679        } else {
680          first = tpath.first;
681          last = tpath.last;
682        }
683      }
684      tpath.first = tpath.last = 0;
685    }
686
687    /// \brief Spliting the current path.
688    ///
689    /// It splits the current path into two parts. The part before \c
690    /// it iterator will remain in the current path and the part from
691    /// the it will put into the \c tpath. If the \c tpath had edges
692    /// before the operation they will be removed first.  The time
693    /// complexity of this function is O(1) plus the clearing of \c
694    /// tpath. If the \c it is \c INVALID then it just clears \c
695    /// tpath.
696    void split(EdgeIt it, ListPath& tpath) {
697      tpath.clear();
698      if (it.node) {
699        tpath.first = it.node;
700        tpath.last = last;
701        if (it.node->prev) {
702          last = it.node->prev;
703          last->next = 0;
704        } else {
705          first = last = 0;
706        }
707        it.node->prev = 0;
708      }
709    }
710
711
712    typedef True BuildTag;
713
714    template <typename CPath>
715    void build(const CPath& path) {
716      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
717        addBack(it);
718      }
719    }
720
721    template <typename CPath>
722    void buildRev(const CPath& path) {
723      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
724        addFront(it);
725      }
726    }
727
728  };
729
730  /// \brief A structure for representing directed paths in a graph.
731  ///
732  /// A structure for representing directed path in a graph.
733  /// \param Graph The graph type in which the path is.
734  ///
735  /// In a sense, the path can be treated as a list of edges. The
736  /// lemon path type stores just this list. As a consequence it
737  /// cannot enumerate the nodes in the path and the zero length paths
738  /// cannot store the source.
739  ///
740  /// This implementation is completly static, so it cannot be
741  /// modified exclude the assign an other path. It is intented to be
742  /// used when you want to store a large number of paths because it is
743  /// the most memory efficient path type in the lemon.
744  template <typename _Graph>
745  class StaticPath {
746  public:
747
748    typedef _Graph Graph;
749    typedef typename Graph::Edge Edge;
750
751    /// \brief Default constructor
752    ///
753    /// Default constructor
754    StaticPath() : len(0), edges(0) {}
755   
756    /// \brief Template copy constructor
757    ///
758    /// This path can be initialized with any other path type. It just
759    /// makes a copy of the given path.
760    template <typename CPath>
761    StaticPath(const CPath& cpath) : edges(0) {
762      copyPath(*this, cpath);
763    }
764
765    /// \brief Destructor of the path
766    ///
767    /// Destructor of the path
768    ~StaticPath() {
769      if (edges) delete[] edges;
770    }
771
772    /// \brief Template copy assignment
773    ///
774    /// This path can be initialized with any other path type. It just
775    /// makes a copy of the given path.
776    template <typename CPath>
777    StaticPath& operator=(const CPath& cpath) {
778      copyPath(*this, cpath);
779      return *this;
780    }
781
782    /// \brief Iterator class to iterate on the edges of the paths
783    ///
784    /// This class is used to iterate on the edges of the paths
785    ///
786    /// Of course it converts to Graph::Edge
787    class EdgeIt {
788      friend class StaticPath;
789    public:
790      /// Default constructor
791      EdgeIt() {}
792      /// Invalid constructor
793      EdgeIt(Invalid) : path(0), idx(-1) {}
794      /// Initializate the constructor to the first edge of path
795      EdgeIt(const StaticPath &_path)
796        : path(&_path), idx(_path.empty() ? -1 : 0) {}
797
798    private:
799
800      /// Constructor with starting point
801      EdgeIt(const StaticPath &_path, int _idx)
802        : idx(_idx), path(&_path) {}
803
804    public:
805
806      ///Conversion to Graph::Edge
807      operator const Edge&() const {
808        return path->nth(idx);
809      }
810
811      /// Next edge
812      EdgeIt& operator++() {
813        ++idx;
814        if (idx >= path->length()) idx = -1;
815        return *this;
816      }
817
818      /// Comparison operator
819      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
820      /// Comparison operator
821      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
822      /// Comparison operator
823      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
824
825    private:
826      const StaticPath *path;
827      int idx;
828    };
829
830    /// \brief Gives back the nth edge.
831    ///
832    /// \pre n is in the [0..length() - 1] range
833    const Edge& nth(int n) const {
834      return edges[n];
835    }
836
837    /// \brief Initializes edge iterator to point to the nth edge.
838    EdgeIt nthIt(int n) const {
839      return EdgeIt(*this, n);
840    }
841
842    /// \brief Gives back the length of the path.
843    int length() const { return len; }
844
845    /// \brief Returns true when the path is empty.
846    int empty() const { return len == 0; }
847
848    /// \break Erase all edge in the graph.
849    void clear() {
850      len = 0;
851      if (edges) delete[] edges;
852      edges = 0;
853    }
854
855    /// \brief Gives back the first edge of the path.
856    const Edge& front() const {
857      return edges[0];
858    }
859
860    /// \brief Gives back the last edge of the path.
861    const Edge& back() const {
862      return edges[len - 1];
863    }
864
865
866    typedef True BuildTag;
867
868    template <typename CPath>
869    void build(const CPath& path) {
870      len = path.length();
871      edges = new Edge[len];
872      int index = 0;
873      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
874        edges[index] = it;
875        ++index;
876      }
877    }
878
879    template <typename CPath>
880    void buildRev(const CPath& path) {
881      len = path.length();
882      edges = new Edge[len];
883      int index = len;
884      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
885        --index;
886        edges[index] = it;
887      }
888    }
889
890  private:
891    int len;
892    Edge* edges;
893  };
894
895  ///@}
896
897} // namespace lemon
898
899#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.