COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

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