4 @defgroup paths Path Structures
6 \brief Path structures implemented in Hugo.
8 Hugolib provides flexible data structures
11 All of them have the same interface, especially they can be built or extended
12 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
13 algorithm to store its result in any kind of path structure.
15 \sa hugo::skeleton::Path
21 ///\brief Classes for representing paths in graphs.
30 #include <hugo/invalid.h>
38 //! \brief A structure for representing directed paths in a graph.
40 //! A structure for representing directed path in a graph.
41 //! \param Graph The graph type in which the path is.
42 //! \param DM DebugMode, defaults to DefaultDebugMode.
44 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
45 //! and \c EdgeIt with the same usage. These types converts to the \c Node
46 //! and \c Edge of the original graph.
48 //! \todo Thoroughfully check all the range and consistency tests.
49 template<typename Graph>
52 /// Edge type of the underlying graph.
53 typedef typename Graph::Edge GraphEdge;
54 /// Node type of the underlying graph.
55 typedef typename Graph::Node GraphNode;
61 typedef std::vector<GraphEdge> Container;
66 /// \param _G The graph in which the path is.
68 DirPath(const Graph &_G) : gr(&_G) {}
70 /// \brief Subpath constructor.
72 /// Subpath defined by two nodes.
73 /// \warning It is an error if the two edges are not in order!
74 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
76 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
79 /// \brief Subpath constructor.
81 /// Subpath defined by two edges. Contains edges in [a,b)
82 /// \warning It is an error if the two edges are not in order!
83 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
85 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
88 /// Length of the path.
89 size_t length() const { return edges.size(); }
90 /// Returns whether the path is empty.
91 bool empty() const { return edges.empty(); }
93 /// Resets the path to an empty path.
94 void clear() { edges.clear(); }
96 /// \brief Starting point of the path.
98 /// Starting point of the path.
99 /// Returns INVALID if the path is empty.
100 GraphNode tail() const {
101 return empty() ? INVALID : gr->tail(edges[0]);
103 /// \brief End point of the path.
105 /// End point of the path.
106 /// Returns INVALID if the path is empty.
107 GraphNode head() const {
108 return empty() ? INVALID : gr->head(edges[length()-1]);
111 /// \brief Initializes node or edge iterator to point to the first
115 template<typename It>
116 It& first(It &i) const { return i=It(*this); }
118 /// \brief Initializes node iterator to point to the node of a given index.
119 NodeIt& nth(NodeIt &i, int n) const {
120 return i=NodeIt(*this, n);
123 /// \brief Initializes edge iterator to point to the edge of a given index.
124 EdgeIt& nth(EdgeIt &i, int n) const {
125 return i=EdgeIt(*this, n);
128 /// Checks validity of a node or edge iterator.
129 template<typename It>
131 bool valid(const It &i) { return i.valid(); }
133 /// Steps the given node or edge iterator.
134 template<typename It>
140 /// \brief Returns node iterator pointing to the head node of the
141 /// given edge iterator.
142 NodeIt head(const EdgeIt& e) const {
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 return NodeIt(*this, e.idx);
153 /* Iterator classes */
156 * \brief Iterator class to iterate on the edges of the paths
159 * This class is used to iterate on the edges of the paths
161 * Of course it converts to Graph::Edge
163 * \todo Its interface differs from the standard edge iterator.
167 friend class DirPath;
172 /// Default constructor
174 /// Invalid constructor
175 EdgeIt(Invalid) : idx(-1), p(0) {}
176 /// Constructor with starting point
177 EdgeIt(const DirPath &_p, int _idx = 0) :
178 idx(_idx), p(&_p) { validate(); }
181 bool valid() const { return idx!=-1; }
183 ///Conversion to Graph::Edge
184 operator GraphEdge () const {
185 return valid() ? p->edges[idx] : INVALID;
189 EdgeIt& operator++() { ++idx; validate(); return *this; }
191 /// Comparison operator
192 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
193 /// Comparison operator
194 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
195 /// Comparison operator
196 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
199 // FIXME: comparison between signed and unsigned...
200 // Jo ez igy? Vagy esetleg legyen a length() int?
201 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
205 * \brief Iterator class to iterate on the nodes of the paths
208 * This class is used to iterate on the nodes of the paths
210 * Of course it converts to Graph::Node
212 * \todo Its interface differs from the standard node iterator.
216 friend class DirPath;
221 /// Default constructor
223 /// Invalid constructor
224 NodeIt(Invalid) : idx(-1), p(0) {}
225 /// Constructor with starting point
226 NodeIt(const DirPath &_p, int _idx = 0) :
227 idx(_idx), p(&_p) { validate(); }
230 bool valid() const { return idx!=-1; }
232 ///Conversion to Graph::Node
233 operator const GraphNode& () const {
234 if(idx >= p->length())
237 return p->gr->tail(p->edges[idx]);
242 NodeIt& operator++() { ++idx; validate(); return *this; }
244 /// Comparison operator
245 bool operator==(const NodeIt& e) const { return idx==e.idx; }
246 /// Comparison operator
247 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
248 /// Comparison operator
249 bool operator<(const NodeIt& e) const { return idx<e.idx; }
252 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
255 friend class Builder;
258 * \brief Class to build paths
261 * This class is used to fill a path with edges.
263 * You can push new edges to the front and to the back of the path in
264 * arbitrary order then you should commit these changes to the graph.
266 * Fundamentally, for most "Paths" (classes fulfilling the
267 * PathConcept) while the builder is active (after the first modifying
268 * operation and until the commit()) the original Path is in a
269 * "transitional" state (operations on it have undefined result). But
270 * in the case of DirPath the original path remains unchanged until the
271 * commit. However we don't recomend that you use this feature.
275 Container front, back;
278 ///\param _P the path you want to fill in.
280 Builder(DirPath &_P) : P(_P) {}
282 /// Sets the starting node of the path.
284 /// Sets the starting node of the path. Edge added to the path
285 /// afterwards have to be incident to this node.
286 /// It should be called iff the path is empty and before any call to
287 /// \ref pushFront() or \ref pushBack()
288 void setStartNode(const GraphNode &) {}
290 ///Push a new edge to the front of the path
292 ///Push a new edge to the front of the path.
294 void pushFront(const GraphEdge& e) {
298 ///Push a new edge to the back of the path
300 ///Push a new edge to the back of the path.
302 void pushBack(const GraphEdge& e) {
306 ///Commit the changes to the path.
308 if( !(front.empty() && back.empty()) ) {
310 tmp.reserve(front.size()+back.size()+P.length());
311 tmp.insert(tmp.end(), front.rbegin(), front.rend());
312 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
313 tmp.insert(tmp.end(), back.begin(), back.end());
320 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
321 // Hogy kenyelmes egy ilyet hasznalni?
323 ///Reserve storage for the builder in advance.
325 ///If you know an reasonable upper bound of the number of the edges
326 ///to add, using this function you can speed up the building.
327 void reserve(size_t r) {
332 void reserveFront(size_t r) {}
333 void reserveBack(size_t r) {}
337 return front.empty() && back.empty() && P.empty();
340 GraphNode tail() const {
341 if( ! front.empty() )
342 return P.gr->tail(front[front.size()-1]);
343 else if( ! P.empty() )
344 return P.gr->tail(P.edges[0]);
345 else if( ! back.empty() )
346 return P.gr->tail(back[0]);
350 GraphNode head() const {
352 return P.gr->head(back[back.size()-1]);
353 else if( ! P.empty() )
354 return P.gr->head(P.edges[P.length()-1]);
355 else if( ! front.empty() )
356 return P.gr->head(front[0]);
374 /**********************************************************************/
377 //! \brief A structure for representing undirected path in a graph.
379 //! A structure for representing undirected path in a graph. Ie. this is
380 //! a path in a \e directed graph but the edges should not be directed
383 //! \param Graph The graph type in which the path is.
384 //! \param DM DebugMode, defaults to DefaultDebugMode.
386 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
387 //! and \c EdgeIt with the same usage. These types converts to the \c Node
388 //! and \c Edge of the original graph.
390 //! \todo Thoroughfully check all the range and consistency tests.
391 template<typename Graph>
394 /// Edge type of the underlying graph.
395 typedef typename Graph::Edge GraphEdge;
396 /// Node type of the underlying graph.
397 typedef typename Graph::Node GraphNode;
403 typedef std::vector<GraphEdge> Container;
408 /// \param _G The graph in which the path is.
410 UndirPath(const Graph &_G) : gr(&_G) {}
412 /// \brief Subpath constructor.
414 /// Subpath defined by two nodes.
415 /// \warning It is an error if the two edges are not in order!
416 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
418 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
421 /// \brief Subpath constructor.
423 /// Subpath defined by two edges. Contains edges in [a,b)
424 /// \warning It is an error if the two edges are not in order!
425 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
427 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
430 /// Length of the path.
431 size_t length() const { return edges.size(); }
432 /// Returns whether the path is empty.
433 bool empty() const { return edges.empty(); }
435 /// Resets the path to an empty path.
436 void clear() { edges.clear(); }
438 /// \brief Starting point of the path.
440 /// Starting point of the path.
441 /// Returns INVALID if the path is empty.
442 GraphNode tail() const {
443 return empty() ? INVALID : gr->tail(edges[0]);
445 /// \brief End point of the path.
447 /// End point of the path.
448 /// Returns INVALID if the path is empty.
449 GraphNode head() const {
450 return empty() ? INVALID : gr->head(edges[length()-1]);
453 /// \brief Initializes node or edge iterator to point to the first
457 template<typename It>
458 It& first(It &i) const { return i=It(*this); }
460 /// \brief Initializes node iterator to point to the node of a given index.
461 NodeIt& nth(NodeIt &i, int n) const {
462 return i=NodeIt(*this, n);
465 /// \brief Initializes edge iterator to point to the edge of a given index.
466 EdgeIt& nth(EdgeIt &i, int n) const {
467 return i=EdgeIt(*this, n);
470 /// Checks validity of a node or edge iterator.
471 template<typename It>
473 bool valid(const It &i) { return i.valid(); }
475 /// Steps the given node or edge iterator.
476 template<typename It>
482 /// \brief Returns node iterator pointing to the head node of the
483 /// given edge iterator.
484 NodeIt head(const EdgeIt& e) const {
485 return NodeIt(*this, e.idx+1);
488 /// \brief Returns node iterator pointing to the tail node of the
489 /// given edge iterator.
490 NodeIt tail(const EdgeIt& e) const {
491 return NodeIt(*this, e.idx);
497 * \brief Iterator class to iterate on the edges of the paths
500 * This class is used to iterate on the edges of the paths
502 * Of course it converts to Graph::Edge
504 * \todo Its interface differs from the standard edge iterator.
508 friend class UndirPath;
513 /// Default constructor
515 /// Invalid constructor
516 EdgeIt(Invalid) : idx(-1), p(0) {}
517 /// Constructor with starting point
518 EdgeIt(const UndirPath &_p, int _idx = 0) :
519 idx(_idx), p(&_p) { validate(); }
522 bool valid() const { return idx!=-1; }
524 ///Conversion to Graph::Edge
525 operator GraphEdge () const {
526 return valid() ? p->edges[idx] : INVALID;
529 EdgeIt& operator++() { ++idx; validate(); return *this; }
531 /// Comparison operator
532 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
533 /// Comparison operator
534 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
535 /// Comparison operator
536 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
539 // FIXME: comparison between signed and unsigned...
540 // Jo ez igy? Vagy esetleg legyen a length() int?
541 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
545 * \brief Iterator class to iterate on the nodes of the paths
548 * This class is used to iterate on the nodes of the paths
550 * Of course it converts to Graph::Node
552 * \todo Its interface differs from the standard node iterator.
556 friend class UndirPath;
561 /// Default constructor
563 /// Invalid constructor
564 NodeIt(Invalid) : idx(-1), p(0) {}
565 /// Constructor with starting point
566 NodeIt(const UndirPath &_p, int _idx = 0) :
567 idx(_idx), p(&_p) { validate(); }
570 bool valid() const { return idx!=-1; }
572 ///Conversion to Graph::Node
573 operator const GraphNode& () const {
574 if(idx >= p->length())
577 return p->gr->tail(p->edges[idx]);
582 NodeIt& operator++() { ++idx; validate(); return *this; }
584 /// Comparison operator
585 bool operator==(const NodeIt& e) const { return idx==e.idx; }
586 /// Comparison operator
587 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
588 /// Comparison operator
589 bool operator<(const NodeIt& e) const { return idx<e.idx; }
592 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
595 friend class Builder;
598 * \brief Class to build paths
601 * This class is used to fill a path with edges.
603 * You can push new edges to the front and to the back of the path in
604 * arbitrary order then you should commit these changes to the graph.
606 * Fundamentally, for most "Paths" (classes fulfilling the
607 * PathConcept) while the builder is active (after the first modifying
608 * operation and until the commit()) the original Path is in a
609 * "transitional" state (operations ot it have undefined result). But
610 * in the case of UndirPath the original path is unchanged until the
611 * commit. However we don't recomend that you use this feature.
615 Container front, back;
618 ///\param _P the path you want to fill in.
620 Builder(UndirPath &_P) : P(_P) {}
622 /// Sets the starting node of the path.
624 /// Sets the starting node of the path. Edge added to the path
625 /// afterwards have to be incident to this node.
626 /// It should be called iff the path is empty and before any call to
627 /// \ref pushFront() or \ref pushBack()
628 void setStartNode(const GraphNode &) {}
630 ///Push a new edge to the front of the path
632 ///Push a new edge to the front of the path.
634 void pushFront(const GraphEdge& e) {
638 ///Push a new edge to the back of the path
640 ///Push a new edge to the back of the path.
642 void pushBack(const GraphEdge& e) {
643 if( !empty() && P.gr->tail(e)!=head() ) {
644 fault("UndirPath::Builder::pushBack: nonincident edge");
649 ///Commit the changes to the path.
651 if( !(front.empty() && back.empty()) ) {
653 tmp.reserve(front.size()+back.size()+P.length());
654 tmp.insert(tmp.end(), front.rbegin(), front.rend());
655 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
656 tmp.insert(tmp.end(), back.begin(), back.end());
663 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
664 // Hogy kenyelmes egy ilyet hasznalni?
666 ///Reserve storage for the builder in advance.
668 ///If you know an reasonable upper bound of the number of the edges
669 ///to add, using this function you can speed up the building.
670 void reserve(size_t r) {
675 void reserveFront(size_t r) {}
676 void reserveBack(size_t r) {}
680 return front.empty() && back.empty() && P.empty();
683 GraphNode tail() const {
684 if( ! front.empty() )
685 return P.gr->tail(front[front.size()-1]);
686 else if( ! P.empty() )
687 return P.gr->tail(P.edges[0]);
688 else if( ! back.empty() )
689 return P.gr->tail(back[0]);
693 GraphNode head() const {
695 return P.gr->head(back[back.size()-1]);
696 else if( ! P.empty() )
697 return P.gr->head(P.edges[P.length()-1]);
698 else if( ! front.empty() )
699 return P.gr->head(front[0]);
717 /**********************************************************************/
720 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
721 elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
723 template<typename Graph>
727 typedef typename Graph::Edge GraphEdge;
728 typedef typename Graph::Node GraphNode;
734 // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
736 GraphNode _first, _last;
737 typedef std::deque<GraphEdge> Container;
742 DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
744 /// Subpath defined by two nodes.
745 /// Nodes may be in reversed order, then
746 /// we contstruct the reversed path.
747 DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
748 /// Subpath defined by two edges. Contains edges in [a,b)
749 /// It is an error if the two edges are not in order!
750 DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
752 size_t length() const { return edges.size(); }
753 GraphNode tail() const { return _first; }
754 GraphNode head() const { return _last; }
756 NodeIt& first(NodeIt &n) const { return nth(n, 0); }
757 EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
758 template<typename It>
765 NodeIt& nth(NodeIt &, size_t) const;
766 EdgeIt& nth(EdgeIt &, size_t) const;
767 template<typename It>
768 It nth(size_t n) const {
774 bool valid(const NodeIt &n) const { return n.idx <= length(); }
775 bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
777 bool isForward(const EdgeIt &e) const { return e.forw; }
779 /// index of a node on the path. Returns length+2 for the invalid NodeIt
780 int index(const NodeIt &n) const { return n.idx; }
781 /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
782 int index(const EdgeIt &e) const { return e.it - edges.begin(); }
784 EdgeIt& next(EdgeIt &e) const;
785 NodeIt& next(NodeIt &n) const;
786 template <typename It>
787 It getNext(It it) const {
788 It tmp(it); return next(tmp);
791 // A path is constructed using the following four functions.
792 // They return false if the requested operation is inconsistent
793 // with the path constructed so far.
794 // If your path has only one edge you MUST set either "from" or "to"!
795 // So you probably SHOULD call it in any case to be safe (and check the
796 // returned value to check if your path is consistent with your idea).
797 bool pushFront(const GraphEdge &e);
798 bool pushBack(const GraphEdge &e);
799 bool setFrom(const GraphNode &n);
800 bool setTo(const GraphNode &n);
802 // WARNING: these two functions return the head/tail of an edge with
803 // respect to the direction of the path!
804 // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
805 // P.forward(e) is true (or the edge is a loop)!
806 NodeIt head(const EdgeIt& e) const;
807 NodeIt tail(const EdgeIt& e) const;
809 // FIXME: ezeknek valami jobb nev kellene!!!
810 GraphEdge graphEdge(const EdgeIt& e) const;
811 GraphNode graphNode(const NodeIt& n) const;
814 /*** Iterator classes ***/
816 friend class DynamicPath;
818 typename Container::const_iterator it;
821 // FIXME: jarna neki ilyen is...
824 bool forward() const { return forw; }
826 bool operator==(const EdgeIt& e) const { return it==e.it; }
827 bool operator!=(const EdgeIt& e) const { return it!=e.it; }
828 bool operator<(const EdgeIt& e) const { return it<e.it; }
832 friend class DynamicPath;
835 bool tail; // Is this node the tail of the edge with same idx?
838 // FIXME: jarna neki ilyen is...
841 bool operator==(const NodeIt& n) const { return idx==n.idx; }
842 bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
843 bool operator<(const NodeIt& n) const { return idx<n.idx; }
847 bool edgeIncident(const GraphEdge &e, const GraphNode &a,
849 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
852 template<typename Gr>
853 typename DynamicPath<Gr>::EdgeIt&
854 DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
855 if( e.it == edges.end() )
858 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
861 // Invalid edgeit is always forward :)
862 if( e.it == edges.end() ) {
867 e.forw = ( G.tail(*e.it) == common_node );
871 template<typename Gr>
872 typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
873 if( n.idx >= length() ) {
880 GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
881 G.tail(edges[n.idx]) );
883 if( n.idx < length() ) {
884 n.tail = ( next_node == G.tail(edges[n.idx]) );
893 template<typename Gr>
894 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
896 if( G.tail(e) == a ) {
900 if( G.head(e) == a ) {
907 template<typename Gr>
908 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
909 const GraphEdge &f) {
910 if( edgeIncident(f, G.tail(e), _last) ) {
914 if( edgeIncident(f, G.head(e), _last) ) {
921 template<typename Gr>
922 bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
923 if( G.valid(_first) ) {
924 if( edgeIncident(e, _first, _first) ) {
931 else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
939 template<typename Gr>
940 bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
941 if( G.valid(_last) ) {
942 if( edgeIncident(e, _last, _last) ) {
949 else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
958 template<typename Gr>
959 bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
960 if( G.valid(_first) ) {
965 if( edgeIncident(edges[0], n, _last) ) {
978 template<typename Gr>
979 bool DynamicPath<Gr>::setTo(const GraphNode &n) {
980 if( G.valid(_last) ) {
985 if( edgeIncident(edges[0], n, _first) ) {
999 template<typename Gr>
1000 typename DynamicPath<Gr>::NodeIt
1001 DynamicPath<Gr>::tail(const EdgeIt& e) const {
1004 if( e.it == edges.end() ) {
1005 // FIXME: invalid-> invalid
1006 n.idx = length() + 1;
1011 n.idx = e.it-edges.begin();
1016 template<typename Gr>
1017 typename DynamicPath<Gr>::NodeIt
1018 DynamicPath<Gr>::head(const EdgeIt& e) const {
1019 if( e.it == edges.end()-1 ) {
1023 EdgeIt next_edge = e;
1025 return tail(next_edge);
1028 template<typename Gr>
1029 typename DynamicPath<Gr>::GraphEdge
1030 DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1031 if( e.it != edges.end() ) {
1039 template<typename Gr>
1040 typename DynamicPath<Gr>::GraphNode
1041 DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1042 if( n.idx < length() ) {
1043 return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1045 else if( n.idx == length() ) {
1053 template<typename Gr>
1054 typename DynamicPath<Gr>::EdgeIt&
1055 DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1057 // FIXME: invalid EdgeIt
1063 e.it = edges.begin()+k;
1065 e.forw = ( G.tail(*e.it) == _first );
1068 e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1069 G.tail(*e.it) == G.head(edges[k-1]) );
1074 template<typename Gr>
1075 typename DynamicPath<Gr>::NodeIt&
1076 DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1078 // FIXME: invalid NodeIt
1088 n = tail(nth<EdgeIt>(k));
1092 // Reszut konstruktorok:
1095 template<typename Gr>
1096 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1098 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
1100 if( G.valid(P._first) && a.it < P.edges.end() ) {
1101 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1102 if( b.it < P.edges.end() ) {
1103 _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1111 template<typename Gr>
1112 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1113 const NodeIt &b) : G(P.G)
1115 if( !P.valid(a) || !P.valid(b) )
1118 int ai = a.idx, bi = b.idx;
1122 edges.resize(bi-ai);
1123 copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1125 _first = P.graphNode(a);
1126 _last = P.graphNode(b);
1133 #endif // HUGO_PATH_H