COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/path.h @ 96:b55e501a90ee

Last change on this file since 96:b55e501a90ee was 96:b55e501a90ee, checked in by Alpar Juttner <alpar@…>, 12 years ago

Path related files ported from svn -r3435
but ItemReader/Writer? for Path (originally belonging to path_utils.h)
hasn't ported yet.

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