5 ///\brief Classes for representing paths in graphs.
14 #include <hugo/invalid.h>
15 #include <hugo/error.h>
24 //! \brief A structure for representing directed path in a graph.
26 //! A structure for representing directed path in a graph.
27 //! \param Graph The graph type in which the path is.
28 //! \param DM DebugMode, defaults to DefaultDebugMode.
30 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
31 //! and \c EdgeIt with the same usage. These types converts to the \c Node
32 //! and \c Edge of the original graph.
34 //! \todo Thoroughfully check all the range and consistency tests.
35 template<typename Graph, typename DM = DefaultDebugMode>
38 typedef typename Graph::Edge GraphEdge;
39 typedef typename Graph::Node GraphNode;
45 typedef std::vector<GraphEdge> Container;
50 /// \param _G The graph in which the path is.
52 DirPath(const Graph &_G) : gr(&_G) {}
54 /// \brief Subpath constructor.
56 /// Subpath defined by two nodes.
57 /// \warning It is an error if the two edges are not in order!
58 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
59 if( DM::range_check && (!a.valid() || !b.valid) ) {
60 // FIXME: this check should be more elaborate...
61 fault("DirPath, subpath ctor: invalid bounding nodes");
64 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
67 /// \brief Subpath constructor.
69 /// Subpath defined by two edges. Contains edges in [a,b)
70 /// \warning It is an error if the two edges are not in order!
71 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
72 if( DM::range_check && (!a.valid() || !b.valid) ) {
73 // FIXME: this check should be more elaborate...
74 fault("DirPath, subpath ctor: invalid bounding nodes");
77 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
80 /// Length of the path.
81 size_t length() const { return edges.size(); }
82 /// Returns whether the path is empty.
83 bool empty() const { return edges.empty(); }
85 /// Resets the path to an empty path.
86 void clear() { edges.clear(); }
88 /// \brief Starting point of the path.
90 /// Starting point of the path.
91 /// Returns INVALID if the path is empty.
92 GraphNode from() const {
93 return empty() ? INVALID : gr->tail(edges[0]);
95 /// \brief End point of the path.
97 /// End point of the path.
98 /// Returns INVALID if the path is empty.
99 GraphNode to() const {
100 return empty() ? INVALID : gr->head(edges[length()-1]);
103 /// \brief Initializes node or edge iterator to point to the first
107 template<typename It>
108 It& first(It &i) const { return i=It(*this); }
110 /// \brief Initializes node iterator to point to the node of a given index.
111 NodeIt& nth(NodeIt &i, int n) const {
112 if( DM::range_check && (n<0 || n>int(length())) )
113 fault("DirPath::nth: index out of range");
114 return i=NodeIt(*this, n);
117 /// \brief Initializes edge iterator to point to the edge of a given index.
118 EdgeIt& nth(EdgeIt &i, int n) const {
119 if( DM::range_check && (n<0 || n>=int(length())) )
120 fault("DirPath::nth: index out of range");
121 return i=EdgeIt(*this, n);
124 /// Checks validity of a node or edge iterator.
125 template<typename It>
127 bool valid(const It &i) { return i.valid(); }
129 /// Steps the given node or edge iterator.
130 template<typename It>
133 if( DM::range_check && !e.valid() )
134 fault("DirPath::next() on invalid iterator");
138 /// \brief Returns node iterator pointing to the head node of the
139 /// given edge iterator.
140 NodeIt head(const EdgeIt& e) const {
141 if( DM::range_check && !e.valid() )
142 fault("DirPath::head() on invalid iterator");
143 return NodeIt(*this, e.idx+1);
146 /// \brief Returns node iterator pointing to the tail node of the
147 /// given edge iterator.
148 NodeIt tail(const EdgeIt& e) const {
149 if( DM::range_check && !e.valid() )
150 fault("DirPath::tail() on invalid iterator");
151 return NodeIt(*this, e.idx);
155 /*** Iterator classes ***/
157 friend class DirPath;
163 EdgeIt(Invalid) : idx(-1), p(0) {}
164 EdgeIt(const DirPath &_p, int _idx = 0) :
165 idx(_idx), p(&_p) { validate(); }
167 bool valid() const { return idx!=-1; }
169 operator GraphEdge () const {
170 return valid() ? p->edges[idx] : INVALID;
172 EdgeIt& operator++() { ++idx; validate(); return *this; }
174 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
175 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
176 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
179 // FIXME: comparison between signed and unsigned...
180 // Jo ez igy? Vagy esetleg legyen a length() int?
181 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
185 friend class DirPath;
191 NodeIt(Invalid) : idx(-1), p(0) {}
192 NodeIt(const DirPath &_p, int _idx = 0) :
193 idx(_idx), p(&_p) { validate(); }
195 bool valid() const { return idx!=-1; }
197 operator const GraphNode& () const {
198 if(idx >= p->length())
201 return p->gr->tail(p->edges[idx]);
205 NodeIt& operator++() { ++idx; validate(); return *this; }
207 bool operator==(const NodeIt& e) const { return idx==e.idx; }
208 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
209 bool operator<(const NodeIt& e) const { return idx<e.idx; }
212 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
215 friend class Builder;
218 * \brief Class to build paths
221 * This class is used to fill a path with edges.
223 * You can push new edges to the front and to the back of the path in
224 * arbitrary order then you should commit these changes to the graph.
226 * Fundamentally, for most "Paths" (classes fulfilling the
227 * PathConcept) while the builder is active (after the first modifying
228 * operation and until the commit()) the original Path is in a
229 * "transitional" state (operations on it have undefined result). But
230 * in the case of DirPath the original path remains unchanged until the
231 * commit. However we don't recomend that you use this feature.
235 Container front, back;
238 ///\param _P the path you want to fill in.
240 Builder(DirPath &_P) : P(_P) {}
242 /// Sets the starting node of the path.
244 /// Sets the starting node of the path. Edge added to the path
245 /// afterwards have to be incident to this node.
246 /// It should be called iff the path is empty and before any call to
247 /// \ref pushFront() or \ref pushBack()
248 void setStart(const GraphNode &) {}
250 ///Push a new edge to the front of the path
252 ///Push a new edge to the front of the path.
254 void pushFront(const GraphEdge& e) {
255 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
256 fault("DirPath::Builder::pushFront: nonincident edge");
261 ///Push a new edge to the back of the path
263 ///Push a new edge to the back of the path.
265 void pushBack(const GraphEdge& e) {
266 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
267 fault("DirPath::Builder::pushBack: nonincident edge");
272 ///Commit the changes to the path.
274 if( !(front.empty() && back.empty()) ) {
276 tmp.reserve(front.size()+back.size()+P.length());
277 tmp.insert(tmp.end(), front.rbegin(), front.rend());
278 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
279 tmp.insert(tmp.end(), back.begin(), back.end());
286 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
287 // Hogy kenyelmes egy ilyet hasznalni?
288 void reserve(size_t r) {
295 return front.empty() && back.empty() && P.empty();
298 GraphNode from() const {
299 if( ! front.empty() )
300 return P.gr->tail(front[front.size()-1]);
301 else if( ! P.empty() )
302 return P.gr->tail(P.edges[0]);
303 else if( ! back.empty() )
304 return P.gr->tail(back[0]);
308 GraphNode to() const {
310 return P.gr->head(back[back.size()-1]);
311 else if( ! P.empty() )
312 return P.gr->head(P.edges[P.length()-1]);
313 else if( ! front.empty() )
314 return P.gr->head(front[0]);
332 /**********************************************************************/
335 //! \brief A structure for representing undirected path in a graph.
337 //! A structure for representing undirected path in a graph. Ie. this is
338 //! a path in a \e directed graph but the edges should not be directed
341 //! \param Graph The graph type in which the path is.
342 //! \param DM DebugMode, defaults to DefaultDebugMode.
344 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
345 //! and \c EdgeIt with the same usage. These types converts to the \c Node
346 //! and \c Edge of the original graph.
348 //! \todo Thoroughfully check all the range and consistency tests.
349 template<typename Graph, typename DM = DefaultDebugMode>
352 typedef typename Graph::Edge GraphEdge;
353 typedef typename Graph::Node GraphNode;
359 typedef std::vector<GraphEdge> Container;
364 /// \param _G The graph in which the path is.
366 UndirPath(const Graph &_G) : gr(&_G) {}
368 /// \brief Subpath constructor.
370 /// Subpath defined by two nodes.
371 /// \warning It is an error if the two edges are not in order!
372 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
373 if( DM::range_check && (!a.valid() || !b.valid) ) {
374 // FIXME: this check should be more elaborate...
375 fault("UndirPath, subpath ctor: invalid bounding nodes");
378 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
381 /// \brief Subpath constructor.
383 /// Subpath defined by two edges. Contains edges in [a,b)
384 /// \warning It is an error if the two edges are not in order!
385 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
386 if( DM::range_check && (!a.valid() || !b.valid) ) {
387 // FIXME: this check should be more elaborate...
388 fault("UndirPath, subpath ctor: invalid bounding nodes");
391 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
394 /// Length of the path.
395 size_t length() const { return edges.size(); }
396 /// Returns whether the path is empty.
397 bool empty() const { return edges.empty(); }
399 /// Resets the path to an empty path.
400 void clear() { edges.clear(); }
402 /// \brief Starting point of the path.
404 /// Starting point of the path.
405 /// Returns INVALID if the path is empty.
406 GraphNode from() const {
407 return empty() ? INVALID : gr->tail(edges[0]);
409 /// \brief End point of the path.
411 /// End point of the path.
412 /// Returns INVALID if the path is empty.
413 GraphNode to() const {
414 return empty() ? INVALID : gr->head(edges[length()-1]);
417 /// \brief Initializes node or edge iterator to point to the first
421 template<typename It>
422 It& first(It &i) const { return i=It(*this); }
424 /// \brief Initializes node iterator to point to the node of a given index.
425 NodeIt& nth(NodeIt &i, int n) const {
426 if( DM::range_check && (n<0 || n>int(length())) )
427 fault("UndirPath::nth: index out of range");
428 return i=NodeIt(*this, n);
431 /// \brief Initializes edge iterator to point to the edge of a given index.
432 EdgeIt& nth(EdgeIt &i, int n) const {
433 if( DM::range_check && (n<0 || n>=int(length())) )
434 fault("UndirPath::nth: index out of range");
435 return i=EdgeIt(*this, n);
438 /// Checks validity of a node or edge iterator.
439 template<typename It>
441 bool valid(const It &i) { return i.valid(); }
443 /// Steps the given node or edge iterator.
444 template<typename It>
447 if( DM::range_check && !e.valid() )
448 fault("UndirPath::next() on invalid iterator");
452 /// \brief Returns node iterator pointing to the head node of the
453 /// given edge iterator.
454 NodeIt head(const EdgeIt& e) const {
455 if( DM::range_check && !e.valid() )
456 fault("UndirPath::head() on invalid iterator");
457 return NodeIt(*this, e.idx+1);
460 /// \brief Returns node iterator pointing to the tail node of the
461 /// given edge iterator.
462 NodeIt tail(const EdgeIt& e) const {
463 if( DM::range_check && !e.valid() )
464 fault("UndirPath::tail() on invalid iterator");
465 return NodeIt(*this, e.idx);
469 /*** Iterator classes ***/
471 friend class UndirPath;
477 EdgeIt(Invalid) : idx(-1), p(0) {}
478 EdgeIt(const UndirPath &_p, int _idx = 0) :
479 idx(_idx), p(&_p) { validate(); }
481 bool valid() const { return idx!=-1; }
483 operator GraphEdge () const {
484 return valid() ? p->edges[idx] : INVALID;
486 EdgeIt& operator++() { ++idx; validate(); return *this; }
488 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
489 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
490 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
493 // FIXME: comparison between signed and unsigned...
494 // Jo ez igy? Vagy esetleg legyen a length() int?
495 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
499 friend class UndirPath;
505 NodeIt(Invalid) : idx(-1), p(0) {}
506 NodeIt(const UndirPath &_p, int _idx = 0) :
507 idx(_idx), p(&_p) { validate(); }
509 bool valid() const { return idx!=-1; }
511 operator const GraphNode& () const {
512 if(idx >= p->length())
515 return p->gr->tail(p->edges[idx]);
519 NodeIt& operator++() { ++idx; validate(); return *this; }
521 bool operator==(const NodeIt& e) const { return idx==e.idx; }
522 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
523 bool operator<(const NodeIt& e) const { return idx<e.idx; }
526 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
529 friend class Builder;
532 * \brief Class to build paths
535 * This class is used to fill a path with edges.
537 * You can push new edges to the front and to the back of the path in
538 * arbitrary order then you should commit these changes to the graph.
540 * Fundamentally, for most "Paths" (classes fulfilling the
541 * PathConcept) while the builder is active (after the first modifying
542 * operation and until the commit()) the original Path is in a
543 * "transitional" state (operations ot it have undefined result). But
544 * in the case of UndirPath the original path is unchanged until the
545 * commit. However we don't recomend that you use this feature.
549 Container front, back;
552 ///\param _P the path you want to fill in.
554 Builder(UndirPath &_P) : P(_P) {}
556 /// Sets the starting node of the path.
558 /// Sets the starting node of the path. Edge added to the path
559 /// afterwards have to be incident to this node.
560 /// It should be called iff the path is empty and before any call to
561 /// \ref pushFront() or \ref pushBack()
562 void setStart(const GraphNode &) {}
564 ///Push a new edge to the front of the path
566 ///Push a new edge to the front of the path.
568 void pushFront(const GraphEdge& e) {
569 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
570 fault("UndirPath::Builder::pushFront: nonincident edge");
575 ///Push a new edge to the back of the path
577 ///Push a new edge to the back of the path.
579 void pushBack(const GraphEdge& e) {
580 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
581 fault("UndirPath::Builder::pushBack: nonincident edge");
586 ///Commit the changes to the path.
588 if( !(front.empty() && back.empty()) ) {
590 tmp.reserve(front.size()+back.size()+P.length());
591 tmp.insert(tmp.end(), front.rbegin(), front.rend());
592 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
593 tmp.insert(tmp.end(), back.begin(), back.end());
600 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
601 // Hogy kenyelmes egy ilyet hasznalni?
602 void reserve(size_t r) {
609 return front.empty() && back.empty() && P.empty();
612 GraphNode from() const {
613 if( ! front.empty() )
614 return P.gr->tail(front[front.size()-1]);
615 else if( ! P.empty() )
616 return P.gr->tail(P.edges[0]);
617 else if( ! back.empty() )
618 return P.gr->tail(back[0]);
622 GraphNode to() const {
624 return P.gr->head(back[back.size()-1]);
625 else if( ! P.empty() )
626 return P.gr->head(P.edges[P.length()-1]);
627 else if( ! front.empty() )
628 return P.gr->head(front[0]);
646 /**********************************************************************/
649 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
650 elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
652 template<typename Graph>
656 typedef typename Graph::Edge GraphEdge;
657 typedef typename Graph::Node GraphNode;
663 // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
665 GraphNode _first, _last;
666 typedef std::deque<GraphEdge> Container;
671 DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
673 /// Subpath defined by two nodes.
674 /// Nodes may be in reversed order, then
675 /// we contstruct the reversed path.
676 DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
677 /// Subpath defined by two edges. Contains edges in [a,b)
678 /// It is an error if the two edges are not in order!
679 DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
681 size_t length() const { return edges.size(); }
682 GraphNode from() const { return _first; }
683 GraphNode to() const { return _last; }
685 NodeIt& first(NodeIt &n) const { return nth(n, 0); }
686 EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
687 template<typename It>
694 NodeIt& nth(NodeIt &, size_t) const;
695 EdgeIt& nth(EdgeIt &, size_t) const;
696 template<typename It>
697 It nth(size_t n) const {
703 bool valid(const NodeIt &n) const { return n.idx <= length(); }
704 bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
706 bool isForward(const EdgeIt &e) const { return e.forw; }
708 /// index of a node on the path. Returns length+2 for the invalid NodeIt
709 int index(const NodeIt &n) const { return n.idx; }
710 /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
711 int index(const EdgeIt &e) const { return e.it - edges.begin(); }
713 EdgeIt& next(EdgeIt &e) const;
714 NodeIt& next(NodeIt &n) const;
715 template <typename It>
716 It getNext(It it) const {
717 It tmp(it); return next(tmp);
720 // A path is constructed using the following four functions.
721 // They return false if the requested operation is inconsistent
722 // with the path constructed so far.
723 // If your path has only one edge you MUST set either "from" or "to"!
724 // So you probably SHOULD call it in any case to be safe (and check the
725 // returned value to check if your path is consistent with your idea).
726 bool pushFront(const GraphEdge &e);
727 bool pushBack(const GraphEdge &e);
728 bool setFrom(const GraphNode &n);
729 bool setTo(const GraphNode &n);
731 // WARNING: these two functions return the head/tail of an edge with
732 // respect to the direction of the path!
733 // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
734 // P.forward(e) is true (or the edge is a loop)!
735 NodeIt head(const EdgeIt& e) const;
736 NodeIt tail(const EdgeIt& e) const;
738 // FIXME: ezeknek valami jobb nev kellene!!!
739 GraphEdge graphEdge(const EdgeIt& e) const;
740 GraphNode graphNode(const NodeIt& n) const;
743 /*** Iterator classes ***/
745 friend class DynamicPath;
747 typename Container::const_iterator it;
750 // FIXME: jarna neki ilyen is...
753 bool forward() const { return forw; }
755 bool operator==(const EdgeIt& e) const { return it==e.it; }
756 bool operator!=(const EdgeIt& e) const { return it!=e.it; }
757 bool operator<(const EdgeIt& e) const { return it<e.it; }
761 friend class DynamicPath;
764 bool tail; // Is this node the tail of the edge with same idx?
767 // FIXME: jarna neki ilyen is...
770 bool operator==(const NodeIt& n) const { return idx==n.idx; }
771 bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
772 bool operator<(const NodeIt& n) const { return idx<n.idx; }
776 bool edgeIncident(const GraphEdge &e, const GraphNode &a,
778 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
781 template<typename Gr>
782 typename DynamicPath<Gr>::EdgeIt&
783 DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
784 if( e.it == edges.end() )
787 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
790 // Invalid edgeit is always forward :)
791 if( e.it == edges.end() ) {
796 e.forw = ( G.tail(*e.it) == common_node );
800 template<typename Gr>
801 typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
802 if( n.idx >= length() ) {
809 GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
810 G.tail(edges[n.idx]) );
812 if( n.idx < length() ) {
813 n.tail = ( next_node == G.tail(edges[n.idx]) );
822 template<typename Gr>
823 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
825 if( G.tail(e) == a ) {
829 if( G.head(e) == a ) {
836 template<typename Gr>
837 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
838 const GraphEdge &f) {
839 if( edgeIncident(f, G.tail(e), _last) ) {
843 if( edgeIncident(f, G.head(e), _last) ) {
850 template<typename Gr>
851 bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
852 if( G.valid(_first) ) {
853 if( edgeIncident(e, _first, _first) ) {
860 else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
868 template<typename Gr>
869 bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
870 if( G.valid(_last) ) {
871 if( edgeIncident(e, _last, _last) ) {
878 else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
887 template<typename Gr>
888 bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
889 if( G.valid(_first) ) {
894 if( edgeIncident(edges[0], n, _last) ) {
907 template<typename Gr>
908 bool DynamicPath<Gr>::setTo(const GraphNode &n) {
909 if( G.valid(_last) ) {
914 if( edgeIncident(edges[0], n, _first) ) {
928 template<typename Gr>
929 typename DynamicPath<Gr>::NodeIt
930 DynamicPath<Gr>::tail(const EdgeIt& e) const {
933 if( e.it == edges.end() ) {
934 // FIXME: invalid-> invalid
935 n.idx = length() + 1;
940 n.idx = e.it-edges.begin();
945 template<typename Gr>
946 typename DynamicPath<Gr>::NodeIt
947 DynamicPath<Gr>::head(const EdgeIt& e) const {
948 if( e.it == edges.end()-1 ) {
952 EdgeIt next_edge = e;
954 return tail(next_edge);
957 template<typename Gr>
958 typename DynamicPath<Gr>::GraphEdge
959 DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
960 if( e.it != edges.end() ) {
968 template<typename Gr>
969 typename DynamicPath<Gr>::GraphNode
970 DynamicPath<Gr>::graphNode(const NodeIt& n) const {
971 if( n.idx < length() ) {
972 return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
974 else if( n.idx == length() ) {
982 template<typename Gr>
983 typename DynamicPath<Gr>::EdgeIt&
984 DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
986 // FIXME: invalid EdgeIt
992 e.it = edges.begin()+k;
994 e.forw = ( G.tail(*e.it) == _first );
997 e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
998 G.tail(*e.it) == G.head(edges[k-1]) );
1003 template<typename Gr>
1004 typename DynamicPath<Gr>::NodeIt&
1005 DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1007 // FIXME: invalid NodeIt
1017 n = tail(nth<EdgeIt>(k));
1021 // Reszut konstruktorok:
1024 template<typename Gr>
1025 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1027 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
1029 if( G.valid(P._first) && a.it < P.edges.end() ) {
1030 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1031 if( b.it < P.edges.end() ) {
1032 _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1040 template<typename Gr>
1041 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1042 const NodeIt &b) : G(P.G)
1044 if( !P.valid(a) || !P.valid(b) )
1047 int ai = a.idx, bi = b.idx;
1051 edges.resize(bi-ai);
1052 copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1054 _first = P.graphNode(a);
1055 _last = P.graphNode(b);
1062 #endif // HUGO_PATH_H