The default constructors are removed from the maps.
The ArrayMap is the map structure of the graphs.
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 /// \brief Returns node iterator pointing to the head node of the
129 /// given edge iterator.
130 NodeIt head(const EdgeIt& e) const {
131 return NodeIt(*this, e.idx+1);
134 /// \brief Returns node iterator pointing to the tail node of the
135 /// given edge iterator.
136 NodeIt tail(const EdgeIt& e) const {
137 return NodeIt(*this, e.idx);
141 /* Iterator classes */
144 * \brief Iterator class to iterate on the edges of the paths
147 * This class is used to iterate on the edges of the paths
149 * Of course it converts to Graph::Edge
153 friend class DirPath;
158 /// Default constructor
160 /// Invalid constructor
161 EdgeIt(Invalid) : idx(-1), p(0) {}
162 /// Constructor with starting point
163 EdgeIt(const DirPath &_p, int _idx = 0) :
164 idx(_idx), p(&_p) { validate(); }
167 bool valid() const { return idx!=-1; }
169 ///Conversion to Graph::Edge
170 operator GraphEdge () const {
171 return valid() ? p->edges[idx] : INVALID;
175 EdgeIt& operator++() { ++idx; validate(); return *this; }
177 /// Comparison operator
178 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
179 /// Comparison operator
180 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
181 /// Comparison operator
182 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
185 // FIXME: comparison between signed and unsigned...
186 // Jo ez igy? Vagy esetleg legyen a length() int?
187 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
191 * \brief Iterator class to iterate on the nodes of the paths
194 * This class is used to iterate on the nodes of the paths
196 * Of course it converts to Graph::Node
200 friend class DirPath;
205 /// Default constructor
207 /// Invalid constructor
208 NodeIt(Invalid) : idx(-1), p(0) {}
209 /// Constructor with starting point
210 NodeIt(const DirPath &_p, int _idx = 0) :
211 idx(_idx), p(&_p) { validate(); }
214 bool valid() const { return idx!=-1; }
216 ///Conversion to Graph::Node
217 operator const GraphNode& () const {
218 if(idx >= p->length())
221 return p->gr->tail(p->edges[idx]);
226 NodeIt& operator++() { ++idx; validate(); return *this; }
228 /// Comparison operator
229 bool operator==(const NodeIt& e) const { return idx==e.idx; }
230 /// Comparison operator
231 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
232 /// Comparison operator
233 bool operator<(const NodeIt& e) const { return idx<e.idx; }
236 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
239 friend class Builder;
242 * \brief Class to build paths
245 * This class is used to fill a path with edges.
247 * You can push new edges to the front and to the back of the path in
248 * arbitrary order then you should commit these changes to the graph.
250 * Fundamentally, for most "Paths" (classes fulfilling the
251 * PathConcept) while the builder is active (after the first modifying
252 * operation and until the commit()) the original Path is in a
253 * "transitional" state (operations on it have undefined result). But
254 * in the case of DirPath the original path remains unchanged until the
255 * commit. However we don't recomend that you use this feature.
259 Container front, back;
262 ///\param _P the path you want to fill in.
264 Builder(DirPath &_P) : P(_P) {}
266 /// Sets the starting node of the path.
268 /// Sets the starting node of the path. Edge added to the path
269 /// afterwards have to be incident to this node.
270 /// It should be called iff the path is empty and before any call to
271 /// \ref pushFront() or \ref pushBack()
272 void setStartNode(const GraphNode &) {}
274 ///Push a new edge to the front of the path
276 ///Push a new edge to the front of the path.
278 void pushFront(const GraphEdge& e) {
282 ///Push a new edge to the back of the path
284 ///Push a new edge to the back of the path.
286 void pushBack(const GraphEdge& e) {
290 ///Commit the changes to the path.
292 if( !front.empty() || !back.empty() ) {
294 tmp.reserve(front.size()+back.size()+P.length());
295 tmp.insert(tmp.end(), front.rbegin(), front.rend());
296 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
297 tmp.insert(tmp.end(), back.begin(), back.end());
304 ///Reserve storage for the builder in advance.
306 ///If you know a reasonable upper bound of the number of the edges
307 ///to add to the front, using this function you can speed up the building.
309 void reserveFront(size_t r) {front.reserve(r);}
311 ///Reserve storage for the builder in advance.
313 ///If you know a reasonable upper bound of the number of the edges
314 ///to add to the back, using this function you can speed up the building.
316 void reserveBack(size_t r) {back.reserve(r);}
320 return front.empty() && back.empty() && P.empty();
323 GraphNode tail() const {
324 if( ! front.empty() )
325 return P.gr->tail(front[front.size()-1]);
326 else if( ! P.empty() )
327 return P.gr->tail(P.edges[0]);
328 else if( ! back.empty() )
329 return P.gr->tail(back[0]);
333 GraphNode head() const {
335 return P.gr->head(back[back.size()-1]);
336 else if( ! P.empty() )
337 return P.gr->head(P.edges[P.length()-1]);
338 else if( ! front.empty() )
339 return P.gr->head(front[0]);
357 /**********************************************************************/
360 //! \brief A structure for representing undirected path in a graph.
362 //! A structure for representing undirected path in a graph. Ie. this is
363 //! a path in a \e directed graph but the edges should not be directed
366 //! \param Graph The graph type in which the path is.
367 //! \param DM DebugMode, defaults to DefaultDebugMode.
369 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
370 //! and \c EdgeIt with the same usage. These types converts to the \c Node
371 //! and \c Edge of the original graph.
373 //! \todo Thoroughfully check all the range and consistency tests.
374 template<typename Graph>
377 /// Edge type of the underlying graph.
378 typedef typename Graph::Edge GraphEdge;
379 /// Node type of the underlying graph.
380 typedef typename Graph::Node GraphNode;
386 typedef std::vector<GraphEdge> Container;
391 /// \param _G The graph in which the path is.
393 UndirPath(const Graph &_G) : gr(&_G) {}
395 /// \brief Subpath constructor.
397 /// Subpath defined by two nodes.
398 /// \warning It is an error if the two edges are not in order!
399 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
401 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
404 /// \brief Subpath constructor.
406 /// Subpath defined by two edges. Contains edges in [a,b)
407 /// \warning It is an error if the two edges are not in order!
408 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
410 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
413 /// Length of the path.
414 size_t length() const { return edges.size(); }
415 /// Returns whether the path is empty.
416 bool empty() const { return edges.empty(); }
418 /// Resets the path to an empty path.
419 void clear() { edges.clear(); }
421 /// \brief Starting point of the path.
423 /// Starting point of the path.
424 /// Returns INVALID if the path is empty.
425 GraphNode tail() const {
426 return empty() ? INVALID : gr->tail(edges[0]);
428 /// \brief End point of the path.
430 /// End point of the path.
431 /// Returns INVALID if the path is empty.
432 GraphNode head() const {
433 return empty() ? INVALID : gr->head(edges[length()-1]);
436 /// \brief Initializes node or edge iterator to point to the first
440 template<typename It>
441 It& first(It &i) const { return i=It(*this); }
443 /// \brief Initializes node iterator to point to the node of a given index.
444 NodeIt& nth(NodeIt &i, int n) const {
445 return i=NodeIt(*this, n);
448 /// \brief Initializes edge iterator to point to the edge of a given index.
449 EdgeIt& nth(EdgeIt &i, int n) const {
450 return i=EdgeIt(*this, n);
453 /// Checks validity of a node or edge iterator.
454 template<typename It>
456 bool valid(const It &i) { return i.valid(); }
458 /// Steps the given node or edge iterator.
459 template<typename It>
465 /// \brief Returns node iterator pointing to the head node of the
466 /// given edge iterator.
467 NodeIt head(const EdgeIt& e) const {
468 return NodeIt(*this, e.idx+1);
471 /// \brief Returns node iterator pointing to the tail node of the
472 /// given edge iterator.
473 NodeIt tail(const EdgeIt& e) const {
474 return NodeIt(*this, e.idx);
480 * \brief Iterator class to iterate on the edges of the paths
483 * This class is used to iterate on the edges of the paths
485 * Of course it converts to Graph::Edge
487 * \todo Its interface differs from the standard edge iterator.
491 friend class UndirPath;
496 /// Default constructor
498 /// Invalid constructor
499 EdgeIt(Invalid) : idx(-1), p(0) {}
500 /// Constructor with starting point
501 EdgeIt(const UndirPath &_p, int _idx = 0) :
502 idx(_idx), p(&_p) { validate(); }
505 bool valid() const { return idx!=-1; }
507 ///Conversion to Graph::Edge
508 operator GraphEdge () const {
509 return valid() ? p->edges[idx] : INVALID;
512 EdgeIt& operator++() { ++idx; validate(); return *this; }
514 /// Comparison operator
515 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
516 /// Comparison operator
517 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
518 /// Comparison operator
519 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
522 // FIXME: comparison between signed and unsigned...
523 // Jo ez igy? Vagy esetleg legyen a length() int?
524 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
528 * \brief Iterator class to iterate on the nodes of the paths
531 * This class is used to iterate on the nodes of the paths
533 * Of course it converts to Graph::Node
535 * \todo Its interface differs from the standard node iterator.
539 friend class UndirPath;
544 /// Default constructor
546 /// Invalid constructor
547 NodeIt(Invalid) : idx(-1), p(0) {}
548 /// Constructor with starting point
549 NodeIt(const UndirPath &_p, int _idx = 0) :
550 idx(_idx), p(&_p) { validate(); }
553 bool valid() const { return idx!=-1; }
555 ///Conversion to Graph::Node
556 operator const GraphNode& () const {
557 if(idx >= p->length())
560 return p->gr->tail(p->edges[idx]);
565 NodeIt& operator++() { ++idx; validate(); return *this; }
567 /// Comparison operator
568 bool operator==(const NodeIt& e) const { return idx==e.idx; }
569 /// Comparison operator
570 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
571 /// Comparison operator
572 bool operator<(const NodeIt& e) const { return idx<e.idx; }
575 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
578 friend class Builder;
581 * \brief Class to build paths
584 * This class is used to fill a path with edges.
586 * You can push new edges to the front and to the back of the path in
587 * arbitrary order then you should commit these changes to the graph.
589 * Fundamentally, for most "Paths" (classes fulfilling the
590 * PathConcept) while the builder is active (after the first modifying
591 * operation and until the commit()) the original Path is in a
592 * "transitional" state (operations ot it have undefined result). But
593 * in the case of UndirPath the original path is unchanged until the
594 * commit. However we don't recomend that you use this feature.
598 Container front, back;
601 ///\param _P the path you want to fill in.
603 Builder(UndirPath &_P) : P(_P) {}
605 /// Sets the starting node of the path.
607 /// Sets the starting node of the path. Edge added to the path
608 /// afterwards have to be incident to this node.
609 /// It should be called iff the path is empty and before any call to
610 /// \ref pushFront() or \ref pushBack()
611 void setStartNode(const GraphNode &) {}
613 ///Push a new edge to the front of the path
615 ///Push a new edge to the front of the path.
617 void pushFront(const GraphEdge& e) {
621 ///Push a new edge to the back of the path
623 ///Push a new edge to the back of the path.
625 void pushBack(const GraphEdge& e) {
629 ///Commit the changes to the path.
631 if( !(front.empty() && back.empty()) ) {
633 tmp.reserve(front.size()+back.size()+P.length());
634 tmp.insert(tmp.end(), front.rbegin(), front.rend());
635 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
636 tmp.insert(tmp.end(), back.begin(), back.end());
644 ///Reserve storage for the builder in advance.
646 ///If you know a reasonable upper bound of the number of the edges
647 ///to add to the front, using this function you can speed up the building.
649 void reserveFront(size_t r) {front.reserve(r);}
651 ///Reserve storage for the builder in advance.
653 ///If you know a reasonable upper bound of the number of the edges
654 ///to add to the back, using this function you can speed up the building.
656 void reserveBack(size_t r) {back.reserve(r);}
660 return front.empty() && back.empty() && P.empty();
663 GraphNode tail() const {
664 if( ! front.empty() )
665 return P.gr->tail(front[front.size()-1]);
666 else if( ! P.empty() )
667 return P.gr->tail(P.edges[0]);
668 else if( ! back.empty() )
669 return P.gr->tail(back[0]);
673 GraphNode head() const {
675 return P.gr->head(back[back.size()-1]);
676 else if( ! P.empty() )
677 return P.gr->head(P.edges[P.length()-1]);
678 else if( ! front.empty() )
679 return P.gr->head(front[0]);
693 #endif // HUGO_PATH_H