COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/peter/path/path.h @ 1018:68beae6758a7

Last change on this file since 1018:68beae6758a7 was 986:e997802b855c, checked in by Alpar Juttner, 19 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 31.8 KB
Line 
1// -*- c++ -*- //
2
3/**
4@defgroup paths Path Structures
5@ingroup datas
6\brief Path structures implemented in LEMON.
7
8LEMON provides flexible data structures
9to work with paths.
10
11All of them have the same interface, especially they can be built or extended
12using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
13algorithm to store its result in any kind of path structure.
14
15\sa lemon::concept::Path
16
17*/
18
19///\ingroup paths
20///\file
21///\brief Classes for representing paths in graphs.
22
23#ifndef LEMON_PATH_H
24#define LEMON_PATH_H
25
26#include <deque>
27#include <vector>
28#include <algorithm>
29
30#include <lemon/invalid.h>
31#include <lemon/error.h>
32#include <debug.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  //! \param DM DebugMode, defaults to DefaultDebugMode.
45  //!
46  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
47  //! and \c EdgeIt with the same usage. These types converts to the \c Node
48  //! and \c Edge of the original graph.
49  //!
50  //! \todo Thoroughfully check all the range and consistency tests.
51  template<typename Graph, typename DM = DefaultDebugMode>
52  class DirPath {
53  public:
54    /// Edge type of the underlying graph.
55    typedef typename Graph::Edge GraphEdge;
56    /// Node type of the underlying graph.
57    typedef typename Graph::Node GraphNode;
58    class NodeIt;
59    class EdgeIt;
60
61  protected:
62    const Graph *gr;
63    typedef std::vector<GraphEdge> Container;
64    Container edges;
65
66  public:
67
68    /// \param _G The graph in which the path is.
69    ///
70    DirPath(const Graph &_G) : gr(&_G) {}
71
72    /// \brief Subpath constructor.
73    ///
74    /// Subpath defined by two nodes.
75    /// \warning It is an error if the two edges are not in order!
76    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
77      if( DM::range_check && (!a.valid() || !b.valid) ) {
78        // FIXME: this check should be more elaborate...
79        fault("DirPath, subpath ctor: invalid bounding nodes");
80      }
81      gr = P.gr;
82      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
83    }
84
85    /// \brief Subpath constructor.
86    ///
87    /// Subpath defined by two edges. Contains edges in [a,b)
88    /// \warning It is an error if the two edges are not in order!
89    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
90      if( DM::range_check && (!a.valid() || !b.valid) ) {
91        // FIXME: this check should be more elaborate...
92        fault("DirPath, subpath ctor: invalid bounding nodes");
93      }
94      gr = P.gr;
95      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
96    }
97
98    /// Length of the path.
99    size_t length() const { return edges.size(); }
100    /// Returns whether the path is empty.
101    bool empty() const { return edges.empty(); }
102
103    /// Resets the path to an empty path.
104    void clear() { edges.clear(); }
105
106    /// \brief Starting point of the path.
107    ///
108    /// Starting point of the path.
109    /// Returns INVALID if the path is empty.
110    GraphNode from() const {
111      return empty() ? INVALID : gr->source(edges[0]);
112    }
113    /// \brief End point of the path.
114    ///
115    /// End point of the path.
116    /// Returns INVALID if the path is empty.
117    GraphNode to() const {
118      return empty() ? INVALID : gr->target(edges[length()-1]);
119    }
120
121    /// \brief Initializes node or edge iterator to point to the first
122    /// node or edge.
123    ///
124    /// \sa nth
125    template<typename It>
126    It& first(It &i) const { return i=It(*this); }
127
128    /// \brief Initializes node iterator to point to the node of a given index.
129    NodeIt& nth(NodeIt &i, int n) const {
130      if( DM::range_check && (n<0 || n>int(length())) )
131        fault("DirPath::nth: index out of range");
132      return i=NodeIt(*this, n);
133    }
134
135    /// \brief Initializes edge iterator to point to the edge of a given index.
136    EdgeIt& nth(EdgeIt &i, int n) const {
137      if( DM::range_check && (n<0 || n>=int(length())) )
138        fault("DirPath::nth: index out of range");
139      return i=EdgeIt(*this, n);
140    }
141
142    /// Checks validity of a node or edge iterator.
143    template<typename It>
144    static
145    bool valid(const It &i) { return i.valid(); }
146
147    /// Steps the given node or edge iterator.
148    template<typename It>
149    static
150    It& next(It &e) {
151      if( DM::range_check && !e.valid() )
152        fault("DirPath::next() on invalid iterator");
153      return ++e;
154    }
155
156    /// \brief Returns node iterator pointing to the target node of the
157    /// given edge iterator.
158    NodeIt target(const EdgeIt& e) const {
159      if( DM::range_check && !e.valid() )
160        fault("DirPath::target() on invalid iterator");
161      return NodeIt(*this, e.idx+1);
162    }
163
164    /// \brief Returns node iterator pointing to the source node of the
165    /// given edge iterator.
166    NodeIt source(const EdgeIt& e) const {
167      if( DM::range_check && !e.valid() )
168        fault("DirPath::source() on invalid iterator");
169      return NodeIt(*this, e.idx);
170    }
171
172
173    /* Iterator classes */
174
175    /**
176     * \brief Iterator class to iterate on the edges of the paths
177     *
178     * \ingroup paths
179     * This class is used to iterate on the edges of the paths
180     *
181     * Of course it converts to Graph::Edge
182     *
183     * \todo Its interface differs from the standard edge iterator.
184     * Yes, it shouldn't.
185     */
186    class EdgeIt {
187      friend class DirPath;
188
189      int idx;
190      const DirPath *p;
191    public:
192      /// Default constructor
193      EdgeIt() {}
194      /// Invalid constructor
195      EdgeIt(Invalid) : idx(-1), p(0) {}
196      /// Constructor with starting point
197      EdgeIt(const DirPath &_p, int _idx = 0) :
198        idx(_idx), p(&_p) { validate(); }
199
200      ///Validity check
201      bool valid() const { return idx!=-1; }
202
203      ///Conversion to Graph::Edge
204      operator GraphEdge () const {
205        return valid() ? p->edges[idx] : INVALID;
206      }
207
208      /// Next edge
209      EdgeIt& operator++() { ++idx; validate(); return *this; }
210
211      /// Comparison operator
212      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
213      /// Comparison operator
214      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
215      /// Comparison operator
216      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
217
218    private:
219      // FIXME: comparison between signed and unsigned...
220      // Jo ez igy? Vagy esetleg legyen a length() int?
221      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
222    };
223
224    /**
225     * \brief Iterator class to iterate on the nodes of the paths
226     *
227     * \ingroup paths
228     * This class is used to iterate on the nodes of the paths
229     *
230     * Of course it converts to Graph::Node
231     *
232     * \todo Its interface differs from the standard node iterator.
233     * Yes, it shouldn't.
234     */
235    class NodeIt {
236      friend class DirPath;
237
238      int idx;
239      const DirPath *p;
240    public:
241      /// Default constructor
242      NodeIt() {}
243      /// Invalid constructor
244      NodeIt(Invalid) : idx(-1), p(0) {}
245      /// Constructor with starting point
246      NodeIt(const DirPath &_p, int _idx = 0) :
247        idx(_idx), p(&_p) { validate(); }
248
249      ///Validity check
250      bool valid() const { return idx!=-1; }
251
252      ///Conversion to Graph::Node
253      operator const GraphNode& () const {
254        if(idx >= p->length())
255          return p->to();
256        else if(idx >= 0)
257          return p->gr->source(p->edges[idx]);
258        else
259          return INVALID;
260      }
261      /// Next node
262      NodeIt& operator++() { ++idx; validate(); return *this; }
263
264      /// Comparison operator
265      bool operator==(const NodeIt& e) const { return idx==e.idx; }
266      /// Comparison operator
267      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
268      /// Comparison operator
269      bool operator<(const NodeIt& e) const { return idx<e.idx; }
270
271    private:
272      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
273    };
274
275    friend class Builder;   
276
277    /**
278     * \brief Class to build paths
279     *
280     * \ingroup paths
281     * This class is used to fill a path with edges.
282     *
283     * You can push new edges to the front and to the back of the path in
284     * arbitrary order then you should commit these changes to the graph.
285     *
286     * Fundamentally, for most "Paths" (classes fulfilling the
287     * PathConcept) while the builder is active (after the first modifying
288     * operation and until the commit()) the original Path is in a
289     * "transitional" state (operations on it have undefined result). But
290     * in the case of DirPath the original path remains unchanged until the
291     * commit. However we don't recomend that you use this feature.
292     */
293    class Builder {
294      DirPath &P;
295      Container front, back;
296
297    public:
298      ///\param _P the path you want to fill in.
299      ///
300      Builder(DirPath &_P) : P(_P) {}
301
302      /// Sets the starting node of the path.
303     
304      /// Sets the starting node of the path. Edge added to the path
305      /// afterwards have to be incident to this node.
306      /// It should be called iff the path is empty and before any call to
307      /// \ref pushFront() or \ref pushBack()
308      void setStartNode(const GraphNode &) {}
309
310      ///Push a new edge to the front of the path
311
312      ///Push a new edge to the front of the path.
313      ///\sa setStartNode
314      void pushFront(const GraphEdge& e) {
315        if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) {
316          fault("DirPath::Builder::pushFront: nonincident edge");
317        }
318        front.push_back(e);
319      }
320
321      ///Push a new edge to the back of the path
322
323      ///Push a new edge to the back of the path.
324      ///\sa setStartNode
325      void pushBack(const GraphEdge& e) {
326        if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) {
327          fault("DirPath::Builder::pushBack: nonincident edge");
328        }
329        back.push_back(e);
330      }
331
332      ///Commit the changes to the path.
333      void commit() {
334        if( !(front.empty() && back.empty()) ) {
335          Container tmp;
336          tmp.reserve(front.size()+back.size()+P.length());
337          tmp.insert(tmp.end(), front.rbegin(), front.rend());
338          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
339          tmp.insert(tmp.end(), back.begin(), back.end());
340          P.edges.swap(tmp);
341          front.clear();
342          back.clear();
343        }
344      }
345
346      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
347      // Hogy kenyelmes egy ilyet hasznalni?
348 
349      ///Reserve storage for the builder in advance.
350
351      ///If you know an reasonable upper bound of the number of the edges
352      ///to add, using this function you can speed up the building.
353      void reserve(size_t r) {
354        front.reserve(r);
355        back.reserve(r);
356      }
357
358    private:
359      bool empty() {
360        return front.empty() && back.empty() && P.empty();
361      }
362
363      GraphNode from() const {
364        if( ! front.empty() )
365          return P.gr->source(front[front.size()-1]);
366        else if( ! P.empty() )
367          return P.gr->source(P.edges[0]);
368        else if( ! back.empty() )
369          return P.gr->source(back[0]);
370        else
371          return INVALID;
372      }
373      GraphNode to() const {
374        if( ! back.empty() )
375          return P.gr->target(back[back.size()-1]);
376        else if( ! P.empty() )
377          return P.gr->target(P.edges[P.length()-1]);
378        else if( ! front.empty() )
379          return P.gr->target(front[0]);
380        else
381          return INVALID;
382      }
383
384    };
385
386  };
387
388
389
390
391
392
393
394
395
396
397  /**********************************************************************/
398
399
400  //! \brief A structure for representing undirected path in a graph.
401  //!
402  //! A structure for representing undirected path in a graph. Ie. this is
403  //! a path in a \e directed graph but the edges should not be directed
404  //! forward.
405  //!
406  //! \param Graph The graph type in which the path is.
407  //! \param DM DebugMode, defaults to DefaultDebugMode.
408  //!
409  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
410  //! and \c EdgeIt with the same usage. These types converts to the \c Node
411  //! and \c Edge of the original graph.
412  //!
413  //! \todo Thoroughfully check all the range and consistency tests.
414  template<typename Graph, typename DM = DefaultDebugMode>
415  class UndirPath {
416  public:
417    /// Edge type of the underlying graph.
418    typedef typename Graph::Edge GraphEdge;
419     /// Node type of the underlying graph.
420   typedef typename Graph::Node GraphNode;
421    class NodeIt;
422    class EdgeIt;
423
424  protected:
425    const Graph *gr;
426    typedef std::vector<GraphEdge> Container;
427    Container edges;
428
429  public:
430
431    /// \param _G The graph in which the path is.
432    ///
433    UndirPath(const Graph &_G) : gr(&_G) {}
434
435    /// \brief Subpath constructor.
436    ///
437    /// Subpath defined by two nodes.
438    /// \warning It is an error if the two edges are not in order!
439    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
440      if( DM::range_check && (!a.valid() || !b.valid) ) {
441        // FIXME: this check should be more elaborate...
442        fault("UndirPath, subpath ctor: invalid bounding nodes");
443      }
444      gr = P.gr;
445      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
446    }
447
448    /// \brief Subpath constructor.
449    ///
450    /// Subpath defined by two edges. Contains edges in [a,b)
451    /// \warning It is an error if the two edges are not in order!
452    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
453      if( DM::range_check && (!a.valid() || !b.valid) ) {
454        // FIXME: this check should be more elaborate...
455        fault("UndirPath, subpath ctor: invalid bounding nodes");
456      }
457      gr = P.gr;
458      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
459    }
460
461    /// Length of the path.
462    size_t length() const { return edges.size(); }
463    /// Returns whether the path is empty.
464    bool empty() const { return edges.empty(); }
465
466    /// Resets the path to an empty path.
467    void clear() { edges.clear(); }
468
469    /// \brief Starting point of the path.
470    ///
471    /// Starting point of the path.
472    /// Returns INVALID if the path is empty.
473    GraphNode from() const {
474      return empty() ? INVALID : gr->source(edges[0]);
475    }
476    /// \brief End point of the path.
477    ///
478    /// End point of the path.
479    /// Returns INVALID if the path is empty.
480    GraphNode to() const {
481      return empty() ? INVALID : gr->target(edges[length()-1]);
482    }
483
484    /// \brief Initializes node or edge iterator to point to the first
485    /// node or edge.
486    ///
487    /// \sa nth
488    template<typename It>
489    It& first(It &i) const { return i=It(*this); }
490
491    /// \brief Initializes node iterator to point to the node of a given index.
492    NodeIt& nth(NodeIt &i, int n) const {
493      if( DM::range_check && (n<0 || n>int(length())) )
494        fault("UndirPath::nth: index out of range");
495      return i=NodeIt(*this, n);
496    }
497
498    /// \brief Initializes edge iterator to point to the edge of a given index.
499    EdgeIt& nth(EdgeIt &i, int n) const {
500      if( DM::range_check && (n<0 || n>=int(length())) )
501        fault("UndirPath::nth: index out of range");
502      return i=EdgeIt(*this, n);
503    }
504
505    /// Checks validity of a node or edge iterator.
506    template<typename It>
507    static
508    bool valid(const It &i) { return i.valid(); }
509
510    /// Steps the given node or edge iterator.
511    template<typename It>
512    static
513    It& next(It &e) {
514      if( DM::range_check && !e.valid() )
515        fault("UndirPath::next() on invalid iterator");
516      return ++e;
517    }
518
519    /// \brief Returns node iterator pointing to the target node of the
520    /// given edge iterator.
521    NodeIt target(const EdgeIt& e) const {
522      if( DM::range_check && !e.valid() )
523        fault("UndirPath::target() on invalid iterator");
524      return NodeIt(*this, e.idx+1);
525    }
526
527    /// \brief Returns node iterator pointing to the source node of the
528    /// given edge iterator.
529    NodeIt source(const EdgeIt& e) const {
530      if( DM::range_check && !e.valid() )
531        fault("UndirPath::source() on invalid iterator");
532      return NodeIt(*this, e.idx);
533    }
534
535
536
537    /**
538     * \brief Iterator class to iterate on the edges of the paths
539     *
540     * \ingroup paths
541     * This class is used to iterate on the edges of the paths
542     *
543     * Of course it converts to Graph::Edge
544     *
545     * \todo Its interface differs from the standard edge iterator.
546     * Yes, it shouldn't.
547     */
548    class EdgeIt {
549      friend class UndirPath;
550
551      int idx;
552      const UndirPath *p;
553    public:
554      /// Default constructor
555      EdgeIt() {}
556      /// Invalid constructor
557      EdgeIt(Invalid) : idx(-1), p(0) {}
558      /// Constructor with starting point
559      EdgeIt(const UndirPath &_p, int _idx = 0) :
560        idx(_idx), p(&_p) { validate(); }
561
562      ///Validity check
563      bool valid() const { return idx!=-1; }
564
565      ///Conversion to Graph::Edge
566      operator GraphEdge () const {
567        return valid() ? p->edges[idx] : INVALID;
568      }
569      /// Next edge
570     EdgeIt& operator++() { ++idx; validate(); return *this; }
571
572      /// Comparison operator
573      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
574      /// Comparison operator
575      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
576      /// Comparison operator
577      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
578
579    private:
580      // FIXME: comparison between signed and unsigned...
581      // Jo ez igy? Vagy esetleg legyen a length() int?
582      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
583    };
584
585    /**
586     * \brief Iterator class to iterate on the nodes of the paths
587     *
588     * \ingroup paths
589     * This class is used to iterate on the nodes of the paths
590     *
591     * Of course it converts to Graph::Node
592     *
593     * \todo Its interface differs from the standard node iterator.
594     * Yes, it shouldn't.
595     */
596    class NodeIt {
597      friend class UndirPath;
598
599      int idx;
600      const UndirPath *p;
601    public:
602      /// Default constructor
603      NodeIt() {}
604      /// Invalid constructor
605      NodeIt(Invalid) : idx(-1), p(0) {}
606      /// Constructor with starting point
607      NodeIt(const UndirPath &_p, int _idx = 0) :
608        idx(_idx), p(&_p) { validate(); }
609
610      ///Validity check
611      bool valid() const { return idx!=-1; }
612
613      ///Conversion to Graph::Node
614      operator const GraphNode& () const {
615        if(idx >= p->length())
616          return p->to();
617        else if(idx >= 0)
618          return p->gr->source(p->edges[idx]);
619        else
620          return INVALID;
621      }
622      /// Next node
623      NodeIt& operator++() { ++idx; validate(); return *this; }
624
625      /// Comparison operator
626      bool operator==(const NodeIt& e) const { return idx==e.idx; }
627      /// Comparison operator
628      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
629       /// Comparison operator
630     bool operator<(const NodeIt& e) const { return idx<e.idx; }
631
632    private:
633      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
634    };
635
636    friend class Builder;   
637
638    /**
639     * \brief Class to build paths
640     *
641     * \ingroup paths
642     * This class is used to fill a path with edges.
643     *
644     * You can push new edges to the front and to the back of the path in
645     * arbitrary order then you should commit these changes to the graph.
646     *
647     * Fundamentally, for most "Paths" (classes fulfilling the
648     * PathConcept) while the builder is active (after the first modifying
649     * operation and until the commit()) the original Path is in a
650     * "transitional" state (operations ot it have undefined result). But
651     * in the case of UndirPath the original path is unchanged until the
652     * commit. However we don't recomend that you use this feature.
653     */
654    class Builder {
655      UndirPath &P;
656      Container front, back;
657
658    public:
659      ///\param _P the path you want to fill in.
660      ///
661      Builder(UndirPath &_P) : P(_P) {}
662
663      /// Sets the starting node of the path.
664     
665      /// Sets the starting node of the path. Edge added to the path
666      /// afterwards have to be incident to this node.
667      /// It should be called iff the path is empty and before any call to
668      /// \ref pushFront() or \ref pushBack()
669      void setStartNode(const GraphNode &) {}
670
671      ///Push a new edge to the front of the path
672
673      ///Push a new edge to the front of the path.
674      ///\sa setStartNode
675      void pushFront(const GraphEdge& e) {
676        if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) {
677          fault("UndirPath::Builder::pushFront: nonincident edge");
678        }
679        front.push_back(e);
680      }
681
682      ///Push a new edge to the back of the path
683
684      ///Push a new edge to the back of the path.
685      ///\sa setStartNode
686      void pushBack(const GraphEdge& e) {
687        if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) {
688          fault("UndirPath::Builder::pushBack: nonincident edge");
689        }
690        back.push_back(e);
691      }
692
693      ///Commit the changes to the path.
694      void commit() {
695        if( !(front.empty() && back.empty()) ) {
696          Container tmp;
697          tmp.reserve(front.size()+back.size()+P.length());
698          tmp.insert(tmp.end(), front.rbegin(), front.rend());
699          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
700          tmp.insert(tmp.end(), back.begin(), back.end());
701          P.edges.swap(tmp);
702          front.clear();
703          back.clear();
704        }
705      }
706
707      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
708      // Hogy kenyelmes egy ilyet hasznalni?
709
710      ///Reserve storage for the builder in advance.
711
712      ///If you know an reasonable upper bound of the number of the edges
713      ///to add, using this function you can speed up the building.
714       void reserve(size_t r) {
715        front.reserve(r);
716        back.reserve(r);
717      }
718
719    private:
720      bool empty() {
721        return front.empty() && back.empty() && P.empty();
722      }
723
724      GraphNode from() const {
725        if( ! front.empty() )
726          return P.gr->source(front[front.size()-1]);
727        else if( ! P.empty() )
728          return P.gr->source(P.edges[0]);
729        else if( ! back.empty() )
730          return P.gr->source(back[0]);
731        else
732          return INVALID;
733      }
734      GraphNode to() const {
735        if( ! back.empty() )
736          return P.gr->target(back[back.size()-1]);
737        else if( ! P.empty() )
738          return P.gr->target(P.edges[P.length()-1]);
739        else if( ! front.empty() )
740          return P.gr->target(front[0]);
741        else
742          return INVALID;
743      }
744
745    };
746
747  };
748
749
750
751
752
753
754
755
756
757
758  /**********************************************************************/
759
760
761  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
762     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
763
764  template<typename Graph>
765  class DynamicPath {
766
767  public:
768    typedef typename Graph::Edge GraphEdge;
769    typedef typename Graph::Node GraphNode;
770    class NodeIt;
771    class EdgeIt;
772
773  protected:
774    Graph& G;
775    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
776    // iranyitasat:
777    GraphNode _first, _last;
778    typedef std::deque<GraphEdge> Container;
779    Container edges;
780
781  public:
782
783    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
784
785    /// Subpath defined by two nodes.
786    /// Nodes may be in reversed order, then
787    /// we contstruct the reversed path.
788    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
789    /// Subpath defined by two edges. Contains edges in [a,b)
790    /// It is an error if the two edges are not in order!
791    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
792   
793    size_t length() const { return edges.size(); }
794    GraphNode from() const { return _first; }
795    GraphNode to() const { return _last; }
796
797    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
798    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
799    template<typename It>
800    It first() const {
801      It e;
802      first(e);
803      return e;
804    }
805
806    NodeIt& nth(NodeIt &, size_t) const;
807    EdgeIt& nth(EdgeIt &, size_t) const;
808    template<typename It>
809    It nth(size_t n) const {
810      It e;
811      nth(e, n);
812      return e;
813    }
814
815    bool valid(const NodeIt &n) const { return n.idx <= length(); }
816    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
817
818    bool isForward(const EdgeIt &e) const { return e.forw; }
819
820    /// index of a node on the path. Returns length+2 for the invalid NodeIt
821    int index(const NodeIt &n) const { return n.idx; }
822    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
823    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
824
825    EdgeIt& next(EdgeIt &e) const;
826    NodeIt& next(NodeIt &n) const;
827    template <typename It>
828    It getNext(It it) const {
829      It tmp(it); return next(tmp);
830    }
831
832    // A path is constructed using the following four functions.
833    // They return false if the requested operation is inconsistent
834    // with the path constructed so far.
835    // If your path has only one edge you MUST set either "from" or "to"!
836    // So you probably SHOULD call it in any case to be safe (and check the
837    // returned value to check if your path is consistent with your idea).
838    bool pushFront(const GraphEdge &e);
839    bool pushBack(const GraphEdge &e);
840    bool setFrom(const GraphNode &n);
841    bool setTo(const GraphNode &n);
842
843    // WARNING: these two functions return the target/source of an edge with
844    // respect to the direction of the path!
845    // So G.target(P.graphEdge(e)) == P.graphNode(P.target(e)) holds only if
846    // P.forward(e) is true (or the edge is a loop)!
847    NodeIt target(const EdgeIt& e) const;
848    NodeIt source(const EdgeIt& e) const;
849
850    // FIXME: ezeknek valami jobb nev kellene!!!
851    GraphEdge graphEdge(const EdgeIt& e) const;
852    GraphNode graphNode(const NodeIt& n) const;
853
854
855    /*** Iterator classes ***/
856    class EdgeIt {
857      friend class DynamicPath;
858
859      typename Container::const_iterator it;
860      bool forw;
861    public:
862      // FIXME: jarna neki ilyen is...
863      // EdgeIt(Invalid);
864
865      bool forward() const { return forw; }
866
867      bool operator==(const EdgeIt& e) const { return it==e.it; }
868      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
869      bool operator<(const EdgeIt& e) const { return it<e.it; }
870    };
871
872    class NodeIt {
873      friend class DynamicPath;
874
875      size_t idx;
876      bool source;  // Is this node the source of the edge with same idx?
877
878    public:
879      // FIXME: jarna neki ilyen is...
880      // NodeIt(Invalid);
881
882      bool operator==(const NodeIt& n) const { return idx==n.idx; }
883      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
884      bool operator<(const NodeIt& n) const { return idx<n.idx; }
885    };
886
887  private:
888    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
889                      GraphNode &b);
890    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
891  };
892
893  template<typename Gr>
894  typename DynamicPath<Gr>::EdgeIt&
895  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
896    if( e.it == edges.end() )
897      return e;
898
899    GraphNode common_node = ( e.forw ? G.target(*e.it) : G.source(*e.it) );
900    ++e.it;
901
902    // Invalid edgeit is always forward :)
903    if( e.it == edges.end() ) {
904      e.forw = true;
905      return e;
906    }
907
908    e.forw = ( G.source(*e.it) == common_node );
909    return e;
910  }
911
912  template<typename Gr>
913  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
914    if( n.idx >= length() ) {
915      // FIXME: invalid
916      n.idx = length()+1;
917      return n;
918    }
919
920   
921    GraphNode next_node = ( n.source ? G.target(edges[n.idx]) :
922                              G.source(edges[n.idx]) );
923    ++n.idx;
924    if( n.idx < length() ) {
925      n.source = ( next_node == G.source(edges[n.idx]) );
926    }
927    else {
928      n.source = true;
929    }
930
931    return n;
932  }
933
934  template<typename Gr>
935  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
936                          GraphNode &b) {
937    if( G.source(e) == a ) {
938      b=G.target(e);
939      return true;
940    }
941    if( G.target(e) == a ) {
942      b=G.source(e);
943      return true;
944    }
945    return false;
946  }
947
948  template<typename Gr>
949  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
950                             const GraphEdge &f) {
951    if( edgeIncident(f, G.source(e), _last) ) {
952      _first = G.target(e);
953      return true;
954    }
955    if( edgeIncident(f, G.target(e), _last) ) {
956      _first = G.source(e);
957      return true;
958    }
959    return false;
960  }
961
962  template<typename Gr>
963  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
964    if( G.valid(_first) ) {
965        if( edgeIncident(e, _first, _first) ) {
966          edges.push_front(e);
967          return true;
968        }
969        else
970          return false;
971    }
972    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
973      edges.push_front(e);
974      return true;
975    }
976    else
977      return false;
978  }
979
980  template<typename Gr>
981  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
982    if( G.valid(_last) ) {
983        if( edgeIncident(e, _last, _last) ) {
984          edges.push_back(e);
985          return true;
986        }
987        else
988          return false;
989    }
990    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
991      edges.push_back(e);
992      return true;
993    }
994    else
995      return false;
996  }
997
998
999  template<typename Gr>
1000  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
1001    if( G.valid(_first) ) {
1002      return _first == n;
1003    }
1004    else {
1005      if( length() > 0) {
1006        if( edgeIncident(edges[0], n, _last) ) {
1007          _first = n;
1008          return true;
1009        }
1010        else return false;
1011      }
1012      else {
1013        _first = _last = n;
1014        return true;
1015      }
1016    }
1017  }
1018
1019  template<typename Gr>
1020  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
1021    if( G.valid(_last) ) {
1022      return _last == n;
1023    }
1024    else {
1025      if( length() > 0) {
1026        if( edgeIncident(edges[0], n, _first) ) {
1027          _last = n;
1028          return true;
1029        }
1030        else return false;
1031      }
1032      else {
1033        _first = _last = n;
1034        return true;
1035      }
1036    }
1037  }
1038
1039
1040  template<typename Gr>
1041  typename DynamicPath<Gr>::NodeIt
1042  DynamicPath<Gr>::source(const EdgeIt& e) const {
1043    NodeIt n;
1044
1045    if( e.it == edges.end() ) {
1046      // FIXME: invalid-> invalid
1047      n.idx = length() + 1;
1048      n.source = true;
1049      return n;
1050    }
1051
1052    n.idx = e.it-edges.begin();
1053    n.source = e.forw;
1054    return n;
1055  }
1056
1057  template<typename Gr>
1058  typename DynamicPath<Gr>::NodeIt
1059  DynamicPath<Gr>::target(const EdgeIt& e) const {
1060    if( e.it == edges.end()-1 ) {
1061      return _last;
1062    }
1063
1064    EdgeIt next_edge = e;
1065    next(next_edge);
1066    return source(next_edge);
1067  }
1068     
1069  template<typename Gr>
1070  typename DynamicPath<Gr>::GraphEdge
1071  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1072    if( e.it != edges.end() ) {
1073      return *e.it;
1074    }
1075    else {
1076      return INVALID;
1077    }
1078  }
1079 
1080  template<typename Gr>
1081  typename DynamicPath<Gr>::GraphNode
1082  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1083    if( n.idx < length() ) {
1084      return n.source ? G.source(edges[n.idx]) : G.target(edges[n.idx]);
1085    }
1086    else if( n.idx == length() ) {
1087      return _last;
1088    }
1089    else {
1090      return INVALID;
1091    }
1092  }
1093
1094  template<typename Gr>
1095  typename DynamicPath<Gr>::EdgeIt&
1096  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1097    if( k>=length() ) {
1098      // FIXME: invalid EdgeIt
1099      e.it = edges.end();
1100      e.forw = true;
1101      return e;
1102    }
1103
1104    e.it = edges.begin()+k;
1105    if(k==0) {
1106      e.forw = ( G.source(*e.it) == _first );
1107    }
1108    else {
1109      e.forw = ( G.source(*e.it) == G.source(edges[k-1]) ||
1110                 G.source(*e.it) == G.target(edges[k-1]) );
1111    }
1112    return e;
1113  }
1114   
1115  template<typename Gr>
1116  typename DynamicPath<Gr>::NodeIt&
1117  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1118    if( k>length() ) {
1119      // FIXME: invalid NodeIt
1120      n.idx = length()+1;
1121      n.source = true;
1122      return n;
1123    }
1124    if( k==length() ) {
1125      n.idx = length();
1126      n.source = true;
1127      return n;
1128    }
1129    n = source(nth<EdgeIt>(k));
1130    return n;
1131  }
1132
1133  // Reszut konstruktorok:
1134
1135
1136  template<typename Gr>
1137  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1138                               const EdgeIt &b) :
1139    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up!
1140  {
1141    if( G.valid(P._first) && a.it < P.edges.end() ) {
1142      _first = ( a.forw ? G.source(*a.it) : G.target(*a.it) );
1143      if( b.it < P.edges.end() ) {
1144        _last = ( b.forw ? G.source(*b.it) : G.target(*b.it) );
1145      }
1146      else {
1147        _last = P._last;
1148      }
1149    }
1150  }
1151
1152  template<typename Gr>
1153  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1154                               const NodeIt &b) : G(P.G)
1155  {
1156    if( !P.valid(a) || !P.valid(b) )
1157      return;
1158
1159    int ai = a.idx, bi = b.idx;
1160    if( bi<ai )
1161      std::swap(ai,bi);
1162   
1163    edges.resize(bi-ai);
1164    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1165
1166    _first = P.graphNode(a);
1167    _last = P.graphNode(b);
1168  }
1169
1170  ///@}
1171
1172} // namespace lemon
1173
1174#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.