path.h by Misi, committed by Peter. There is DirPath usw. in it.
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>
31 #include <hugo/error.h>
32 #include <hugo/debug.h>
40 //! \brief A structure for representing directed paths in a graph.
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.
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.
50 //! \todo Thoroughfully check all the range and consistency tests.
51 template<typename Graph, typename DM = DefaultDebugMode>
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;
63 typedef std::vector<GraphEdge> Container;
68 /// \param _G The graph in which the path is.
70 DirPath(const Graph &_G) : gr(&_G) {}
72 /// \brief Subpath constructor.
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");
82 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
85 /// \brief Subpath constructor.
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");
95 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
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(); }
103 /// Resets the path to an empty path.
104 void clear() { edges.clear(); }
106 /// \brief Starting point of the path.
108 /// Starting point of the path.
109 /// Returns INVALID if the path is empty.
110 GraphNode from() const {
111 return empty() ? INVALID : gr->tail(edges[0]);
113 /// \brief End point of the path.
115 /// End point of the path.
116 /// Returns INVALID if the path is empty.
117 GraphNode to() const {
118 return empty() ? INVALID : gr->head(edges[length()-1]);
121 /// \brief Initializes node or edge iterator to point to the first
125 template<typename It>
126 It& first(It &i) const { return i=It(*this); }
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);
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);
142 /// Checks validity of a node or edge iterator.
143 template<typename It>
145 bool valid(const It &i) { return i.valid(); }
147 /// Steps the given node or edge iterator.
148 template<typename It>
151 if( DM::range_check && !e.valid() )
152 fault("DirPath::next() on invalid iterator");
156 /// \brief Returns node iterator pointing to the head node of the
157 /// given edge iterator.
158 NodeIt head(const EdgeIt& e) const {
159 if( DM::range_check && !e.valid() )
160 fault("DirPath::head() on invalid iterator");
161 return NodeIt(*this, e.idx+1);
164 /// \brief Returns node iterator pointing to the tail node of the
165 /// given edge iterator.
166 NodeIt tail(const EdgeIt& e) const {
167 if( DM::range_check && !e.valid() )
168 fault("DirPath::tail() on invalid iterator");
169 return NodeIt(*this, e.idx);
173 /* Iterator classes */
176 * \brief Iterator class to iterate on the edges of the paths
179 * This class is used to iterate on the edges of the paths
181 * Of course it converts to Graph::Edge
183 * \todo Its interface differs from the standard edge iterator.
187 friend class DirPath;
192 /// Default constructor
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(); }
201 bool valid() const { return idx!=-1; }
203 ///Conversion to Graph::Edge
204 operator GraphEdge () const {
205 return valid() ? p->edges[idx] : INVALID;
209 EdgeIt& operator++() { ++idx; validate(); return *this; }
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; }
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; }
225 * \brief Iterator class to iterate on the nodes of the paths
228 * This class is used to iterate on the nodes of the paths
230 * Of course it converts to Graph::Node
232 * \todo Its interface differs from the standard node iterator.
236 friend class DirPath;
241 /// Default constructor
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(); }
250 bool valid() const { return idx!=-1; }
252 ///Conversion to Graph::Node
253 operator const GraphNode& () const {
254 if(idx >= p->length())
257 return p->gr->tail(p->edges[idx]);
262 NodeIt& operator++() { ++idx; validate(); return *this; }
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; }
272 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
275 friend class Builder;
278 * \brief Class to build paths
281 * This class is used to fill a path with edges.
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.
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.
295 Container front, back;
298 ///\param _P the path you want to fill in.
300 Builder(DirPath &_P) : P(_P) {}
302 /// Sets the starting node of the path.
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 &) {}
310 ///Push a new edge to the front of the path
312 ///Push a new edge to the front of the path.
314 void pushFront(const GraphEdge& e) {
315 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
316 fault("DirPath::Builder::pushFront: nonincident edge");
321 ///Push a new edge to the back of the path
323 ///Push a new edge to the back of the path.
325 void pushBack(const GraphEdge& e) {
326 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
327 fault("DirPath::Builder::pushBack: nonincident edge");
332 ///Commit the changes to the path.
334 if( !(front.empty() && back.empty()) ) {
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());
346 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
347 // Hogy kenyelmes egy ilyet hasznalni?
349 ///Reserve storage for the builder in advance.
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) {
360 return front.empty() && back.empty() && P.empty();
363 GraphNode from() const {
364 if( ! front.empty() )
365 return P.gr->tail(front[front.size()-1]);
366 else if( ! P.empty() )
367 return P.gr->tail(P.edges[0]);
368 else if( ! back.empty() )
369 return P.gr->tail(back[0]);
373 GraphNode to() const {
375 return P.gr->head(back[back.size()-1]);
376 else if( ! P.empty() )
377 return P.gr->head(P.edges[P.length()-1]);
378 else if( ! front.empty() )
379 return P.gr->head(front[0]);
397 /**********************************************************************/
400 //! \brief A structure for representing undirected path in a graph.
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
406 //! \param Graph The graph type in which the path is.
407 //! \param DM DebugMode, defaults to DefaultDebugMode.
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.
413 //! \todo Thoroughfully check all the range and consistency tests.
414 template<typename Graph, typename DM = DefaultDebugMode>
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;
426 typedef std::vector<GraphEdge> Container;
431 /// \param _G The graph in which the path is.
433 UndirPath(const Graph &_G) : gr(&_G) {}
435 /// \brief Subpath constructor.
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");
445 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
448 /// \brief Subpath constructor.
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");
458 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
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(); }
466 /// Resets the path to an empty path.
467 void clear() { edges.clear(); }
469 /// \brief Starting point of the path.
471 /// Starting point of the path.
472 /// Returns INVALID if the path is empty.
473 GraphNode from() const {
474 return empty() ? INVALID : gr->tail(edges[0]);
476 /// \brief End point of the path.
478 /// End point of the path.
479 /// Returns INVALID if the path is empty.
480 GraphNode to() const {
481 return empty() ? INVALID : gr->head(edges[length()-1]);
484 /// \brief Initializes node or edge iterator to point to the first
488 template<typename It>
489 It& first(It &i) const { return i=It(*this); }
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);
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);
505 /// Checks validity of a node or edge iterator.
506 template<typename It>
508 bool valid(const It &i) { return i.valid(); }
510 /// Steps the given node or edge iterator.
511 template<typename It>
514 if( DM::range_check && !e.valid() )
515 fault("UndirPath::next() on invalid iterator");
519 /// \brief Returns node iterator pointing to the head node of the
520 /// given edge iterator.
521 NodeIt head(const EdgeIt& e) const {
522 if( DM::range_check && !e.valid() )
523 fault("UndirPath::head() on invalid iterator");
524 return NodeIt(*this, e.idx+1);
527 /// \brief Returns node iterator pointing to the tail node of the
528 /// given edge iterator.
529 NodeIt tail(const EdgeIt& e) const {
530 if( DM::range_check && !e.valid() )
531 fault("UndirPath::tail() on invalid iterator");
532 return NodeIt(*this, e.idx);
538 * \brief Iterator class to iterate on the edges of the paths
541 * This class is used to iterate on the edges of the paths
543 * Of course it converts to Graph::Edge
545 * \todo Its interface differs from the standard edge iterator.
549 friend class UndirPath;
554 /// Default constructor
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(); }
563 bool valid() const { return idx!=-1; }
565 ///Conversion to Graph::Edge
566 operator GraphEdge () const {
567 return valid() ? p->edges[idx] : INVALID;
570 EdgeIt& operator++() { ++idx; validate(); return *this; }
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; }
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; }
586 * \brief Iterator class to iterate on the nodes of the paths
589 * This class is used to iterate on the nodes of the paths
591 * Of course it converts to Graph::Node
593 * \todo Its interface differs from the standard node iterator.
597 friend class UndirPath;
602 /// Default constructor
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(); }
611 bool valid() const { return idx!=-1; }
613 ///Conversion to Graph::Node
614 operator const GraphNode& () const {
615 if(idx >= p->length())
618 return p->gr->tail(p->edges[idx]);
623 NodeIt& operator++() { ++idx; validate(); return *this; }
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; }
633 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
636 friend class Builder;
639 * \brief Class to build paths
642 * This class is used to fill a path with edges.
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.
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.
656 Container front, back;
659 ///\param _P the path you want to fill in.
661 Builder(UndirPath &_P) : P(_P) {}
663 /// Sets the starting node of the path.
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 &) {}
671 ///Push a new edge to the front of the path
673 ///Push a new edge to the front of the path.
675 void pushFront(const GraphEdge& e) {
676 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
677 fault("UndirPath::Builder::pushFront: nonincident edge");
682 ///Push a new edge to the back of the path
684 ///Push a new edge to the back of the path.
686 void pushBack(const GraphEdge& e) {
687 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
688 fault("UndirPath::Builder::pushBack: nonincident edge");
693 ///Commit the changes to the path.
695 if( !(front.empty() && back.empty()) ) {
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());
707 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
708 // Hogy kenyelmes egy ilyet hasznalni?
710 ///Reserve storage for the builder in advance.
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) {
721 return front.empty() && back.empty() && P.empty();
724 GraphNode from() const {
725 if( ! front.empty() )
726 return P.gr->tail(front[front.size()-1]);
727 else if( ! P.empty() )
728 return P.gr->tail(P.edges[0]);
729 else if( ! back.empty() )
730 return P.gr->tail(back[0]);
734 GraphNode to() const {
736 return P.gr->head(back[back.size()-1]);
737 else if( ! P.empty() )
738 return P.gr->head(P.edges[P.length()-1]);
739 else if( ! front.empty() )
740 return P.gr->head(front[0]);
758 /**********************************************************************/
761 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
762 elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
764 template<typename Graph>
768 typedef typename Graph::Edge GraphEdge;
769 typedef typename Graph::Node GraphNode;
775 // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
777 GraphNode _first, _last;
778 typedef std::deque<GraphEdge> Container;
783 DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
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);
793 size_t length() const { return edges.size(); }
794 GraphNode from() const { return _first; }
795 GraphNode to() const { return _last; }
797 NodeIt& first(NodeIt &n) const { return nth(n, 0); }
798 EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
799 template<typename It>
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 {
815 bool valid(const NodeIt &n) const { return n.idx <= length(); }
816 bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
818 bool isForward(const EdgeIt &e) const { return e.forw; }
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(); }
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);
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);
843 // WARNING: these two functions return the head/tail of an edge with
844 // respect to the direction of the path!
845 // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
846 // P.forward(e) is true (or the edge is a loop)!
847 NodeIt head(const EdgeIt& e) const;
848 NodeIt tail(const EdgeIt& e) const;
850 // FIXME: ezeknek valami jobb nev kellene!!!
851 GraphEdge graphEdge(const EdgeIt& e) const;
852 GraphNode graphNode(const NodeIt& n) const;
855 /*** Iterator classes ***/
857 friend class DynamicPath;
859 typename Container::const_iterator it;
862 // FIXME: jarna neki ilyen is...
865 bool forward() const { return forw; }
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; }
873 friend class DynamicPath;
876 bool tail; // Is this node the tail of the edge with same idx?
879 // FIXME: jarna neki ilyen is...
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; }
888 bool edgeIncident(const GraphEdge &e, const GraphNode &a,
890 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
893 template<typename Gr>
894 typename DynamicPath<Gr>::EdgeIt&
895 DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
896 if( e.it == edges.end() )
899 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
902 // Invalid edgeit is always forward :)
903 if( e.it == edges.end() ) {
908 e.forw = ( G.tail(*e.it) == common_node );
912 template<typename Gr>
913 typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
914 if( n.idx >= length() ) {
921 GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
922 G.tail(edges[n.idx]) );
924 if( n.idx < length() ) {
925 n.tail = ( next_node == G.tail(edges[n.idx]) );
934 template<typename Gr>
935 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
937 if( G.tail(e) == a ) {
941 if( G.head(e) == a ) {
948 template<typename Gr>
949 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
950 const GraphEdge &f) {
951 if( edgeIncident(f, G.tail(e), _last) ) {
955 if( edgeIncident(f, G.head(e), _last) ) {
962 template<typename Gr>
963 bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
964 if( G.valid(_first) ) {
965 if( edgeIncident(e, _first, _first) ) {
972 else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
980 template<typename Gr>
981 bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
982 if( G.valid(_last) ) {
983 if( edgeIncident(e, _last, _last) ) {
990 else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
999 template<typename Gr>
1000 bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
1001 if( G.valid(_first) ) {
1006 if( edgeIncident(edges[0], n, _last) ) {
1019 template<typename Gr>
1020 bool DynamicPath<Gr>::setTo(const GraphNode &n) {
1021 if( G.valid(_last) ) {
1026 if( edgeIncident(edges[0], n, _first) ) {
1040 template<typename Gr>
1041 typename DynamicPath<Gr>::NodeIt
1042 DynamicPath<Gr>::tail(const EdgeIt& e) const {
1045 if( e.it == edges.end() ) {
1046 // FIXME: invalid-> invalid
1047 n.idx = length() + 1;
1052 n.idx = e.it-edges.begin();
1057 template<typename Gr>
1058 typename DynamicPath<Gr>::NodeIt
1059 DynamicPath<Gr>::head(const EdgeIt& e) const {
1060 if( e.it == edges.end()-1 ) {
1064 EdgeIt next_edge = e;
1066 return tail(next_edge);
1069 template<typename Gr>
1070 typename DynamicPath<Gr>::GraphEdge
1071 DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1072 if( e.it != edges.end() ) {
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.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1086 else if( n.idx == length() ) {
1094 template<typename Gr>
1095 typename DynamicPath<Gr>::EdgeIt&
1096 DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1098 // FIXME: invalid EdgeIt
1104 e.it = edges.begin()+k;
1106 e.forw = ( G.tail(*e.it) == _first );
1109 e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1110 G.tail(*e.it) == G.head(edges[k-1]) );
1115 template<typename Gr>
1116 typename DynamicPath<Gr>::NodeIt&
1117 DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1119 // FIXME: invalid NodeIt
1129 n = tail(nth<EdgeIt>(k));
1133 // Reszut konstruktorok:
1136 template<typename Gr>
1137 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1139 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
1141 if( G.valid(P._first) && a.it < P.edges.end() ) {
1142 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1143 if( b.it < P.edges.end() ) {
1144 _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1152 template<typename Gr>
1153 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1154 const NodeIt &b) : G(P.G)
1156 if( !P.valid(a) || !P.valid(b) )
1159 int ai = a.idx, bi = b.idx;
1163 edges.resize(bi-ai);
1164 copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1166 _first = P.graphNode(a);
1167 _last = P.graphNode(b);
1174 #endif // HUGO_PATH_H