Functions added to compute the gradient of Bezier curve.
2 * src/lemon/path.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
18 @defgroup paths Path Structures
20 \brief Path structures implemented in LEMON.
22 LEMON provides flexible data structures
25 All of them have the same interface, especially they can be built or extended
26 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
27 algorithm to store its result in any kind of path structure.
29 \sa lemon::concept::Path
35 ///\brief Classes for representing paths in graphs.
44 #include <lemon/invalid.h>
52 //! \brief A structure for representing directed paths in a graph.
54 //! A structure for representing directed path in a graph.
55 //! \param Graph The graph type in which the path is.
56 //! \param DM DebugMode, defaults to DefaultDebugMode.
58 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
59 //! and \c EdgeIt with the same usage. These types converts to the \c Node
60 //! and \c Edge of the original graph.
62 //! \todo Thoroughfully check all the range and consistency tests.
63 template<typename Graph>
66 /// Edge type of the underlying graph.
67 typedef typename Graph::Edge GraphEdge;
68 /// Node type of the underlying graph.
69 typedef typename Graph::Node GraphNode;
75 typedef std::vector<GraphEdge> Container;
80 /// \param _G The graph in which the path is.
82 DirPath(const Graph &_G) : gr(&_G) {}
84 /// \brief Subpath constructor.
86 /// Subpath defined by two nodes.
87 /// \warning It is an error if the two edges are not in order!
88 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
90 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
93 /// \brief Subpath constructor.
95 /// Subpath defined by two edges. Contains edges in [a,b)
96 /// \warning It is an error if the two edges are not in order!
97 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
99 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
102 /// Length of the path.
103 size_t length() const { return edges.size(); }
104 /// Returns whether the path is empty.
105 bool empty() const { return edges.empty(); }
107 /// Resets the path to an empty path.
108 void clear() { edges.clear(); }
110 /// \brief Starting point of the path.
112 /// Starting point of the path.
113 /// Returns INVALID if the path is empty.
114 GraphNode source() const {
115 return empty() ? INVALID : gr->source(edges[0]);
117 /// \brief End point of the path.
119 /// End point of the path.
120 /// Returns INVALID if the path is empty.
121 GraphNode target() const {
122 return empty() ? INVALID : gr->target(edges[length()-1]);
125 /// \brief Initializes node or edge iterator to point to the first
129 template<typename It>
130 It& first(It &i) const { return i=It(*this); }
132 /// \brief Initializes node iterator to point to the node of a given index.
133 NodeIt& nth(NodeIt &i, int n) const {
134 return i=NodeIt(*this, n);
137 /// \brief Initializes edge iterator to point to the edge of a given index.
138 EdgeIt& nth(EdgeIt &i, int n) const {
139 return i=EdgeIt(*this, n);
142 /// \brief Returns node iterator pointing to the target node of the
143 /// given edge iterator.
144 NodeIt target(const EdgeIt& e) const {
145 return NodeIt(*this, e.idx+1);
148 /// \brief Returns node iterator pointing to the source node of the
149 /// given edge iterator.
150 NodeIt source(const EdgeIt& e) const {
151 return NodeIt(*this, e.idx);
155 /* Iterator classes */
158 * \brief Iterator class to iterate on the edges of the paths
161 * This class is used to iterate on the edges of the paths
163 * Of course it converts to Graph::Edge
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
214 friend class DirPath;
219 /// Default constructor
221 /// Invalid constructor
222 NodeIt(Invalid) : idx(-1), p(0) {}
223 /// Constructor with starting point
224 NodeIt(const DirPath &_p, int _idx = 0) :
225 idx(_idx), p(&_p) { validate(); }
228 bool valid() const { return idx!=-1; }
230 ///Conversion to Graph::Node
231 operator const GraphNode& () const {
232 if(idx >= p->length())
235 return p->gr->source(p->edges[idx]);
240 NodeIt& operator++() { ++idx; validate(); return *this; }
242 /// Comparison operator
243 bool operator==(const NodeIt& e) const { return idx==e.idx; }
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; }
250 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
253 friend class Builder;
256 * \brief Class to build paths
259 * This class is used to fill a path with edges.
261 * You can push new edges to the front and to the back of the path in
262 * arbitrary order then you should commit these changes to the graph.
264 * Fundamentally, for most "Paths" (classes fulfilling the
265 * PathConcept) while the builder is active (after the first modifying
266 * operation and until the commit()) the original Path is in a
267 * "transitional" state (operations on it have undefined result). But
268 * in the case of DirPath the original path remains unchanged until the
269 * commit. However we don't recomend that you use this feature.
273 Container front, back;
276 ///\param _P the path you want to fill in.
278 Builder(DirPath &_P) : P(_P) {}
280 /// Sets the starting node of the path.
282 /// Sets the starting node of the path. Edge added to the path
283 /// afterwards have to be incident to this node.
284 /// It should be called if and only if
285 /// the path is empty and before any call to
286 /// \ref pushFront() or \ref pushBack()
287 void setStartNode(const GraphNode &) {}
289 ///Push a new edge to the front of the path
291 ///Push a new edge to the front of the path.
293 void pushFront(const GraphEdge& e) {
297 ///Push a new edge to the back of the path
299 ///Push a new edge to the back of the path.
301 void pushBack(const GraphEdge& e) {
305 ///Commit the changes to the path.
307 if( !front.empty() || !back.empty() ) {
309 tmp.reserve(front.size()+back.size()+P.length());
310 tmp.insert(tmp.end(), front.rbegin(), front.rend());
311 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
312 tmp.insert(tmp.end(), back.begin(), back.end());
319 ///Reserve storage for the builder in advance.
321 ///If you know a reasonable upper bound of the number of the edges
322 ///to add to the front, using this function you can speed up the building.
324 void reserveFront(size_t r) {front.reserve(r);}
326 ///Reserve storage for the builder in advance.
328 ///If you know a reasonable upper bound of the number of the edges
329 ///to add to the back, using this function you can speed up the building.
331 void reserveBack(size_t r) {back.reserve(r);}
335 return front.empty() && back.empty() && P.empty();
338 GraphNode source() const {
339 if( ! front.empty() )
340 return P.gr->source(front[front.size()-1]);
341 else if( ! P.empty() )
342 return P.gr->source(P.edges[0]);
343 else if( ! back.empty() )
344 return P.gr->source(back[0]);
348 GraphNode target() const {
350 return P.gr->target(back[back.size()-1]);
351 else if( ! P.empty() )
352 return P.gr->target(P.edges[P.length()-1]);
353 else if( ! front.empty() )
354 return P.gr->target(front[0]);
372 /**********************************************************************/
375 //! \brief A structure for representing undirected path in a graph.
377 //! A structure for representing undirected path in a graph. Ie. this is
378 //! a path in a \e directed graph but the edges should not be directed
381 //! \param Graph The graph type in which the path is.
382 //! \param DM DebugMode, defaults to DefaultDebugMode.
384 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
385 //! and \c EdgeIt with the same usage. These types converts to the \c Node
386 //! and \c Edge of the original graph.
388 //! \todo Thoroughfully check all the range and consistency tests.
389 template<typename Graph>
392 /// Edge type of the underlying graph.
393 typedef typename Graph::Edge GraphEdge;
394 /// Node type of the underlying graph.
395 typedef typename Graph::Node GraphNode;
401 typedef std::vector<GraphEdge> Container;
406 /// \param _G The graph in which the path is.
408 UndirPath(const Graph &_G) : gr(&_G) {}
410 /// \brief Subpath constructor.
412 /// Subpath defined by two nodes.
413 /// \warning It is an error if the two edges are not in order!
414 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
416 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
419 /// \brief Subpath constructor.
421 /// Subpath defined by two edges. Contains edges in [a,b)
422 /// \warning It is an error if the two edges are not in order!
423 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
425 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
428 /// Length of the path.
429 size_t length() const { return edges.size(); }
430 /// Returns whether the path is empty.
431 bool empty() const { return edges.empty(); }
433 /// Resets the path to an empty path.
434 void clear() { edges.clear(); }
436 /// \brief Starting point of the path.
438 /// Starting point of the path.
439 /// Returns INVALID if the path is empty.
440 GraphNode source() const {
441 return empty() ? INVALID : gr->source(edges[0]);
443 /// \brief End point of the path.
445 /// End point of the path.
446 /// Returns INVALID if the path is empty.
447 GraphNode target() const {
448 return empty() ? INVALID : gr->target(edges[length()-1]);
451 /// \brief Initializes node or edge iterator to point to the first
455 template<typename It>
456 It& first(It &i) const { return i=It(*this); }
458 /// \brief Initializes node iterator to point to the node of a given index.
459 NodeIt& nth(NodeIt &i, int n) const {
460 return i=NodeIt(*this, n);
463 /// \brief Initializes edge iterator to point to the edge of a given index.
464 EdgeIt& nth(EdgeIt &i, int n) const {
465 return i=EdgeIt(*this, n);
468 /// Checks validity of a node or edge iterator.
469 template<typename It>
471 bool valid(const It &i) { return i.valid(); }
473 /// Steps the given node or edge iterator.
474 template<typename It>
480 /// \brief Returns node iterator pointing to the target node of the
481 /// given edge iterator.
482 NodeIt target(const EdgeIt& e) const {
483 return NodeIt(*this, e.idx+1);
486 /// \brief Returns node iterator pointing to the source node of the
487 /// given edge iterator.
488 NodeIt source(const EdgeIt& e) const {
489 return NodeIt(*this, e.idx);
495 * \brief Iterator class to iterate on the edges of the paths
498 * This class is used to iterate on the edges of the paths
500 * Of course it converts to Graph::Edge
502 * \todo Its interface differs from the standard edge iterator.
506 friend class UndirPath;
511 /// Default constructor
513 /// Invalid constructor
514 EdgeIt(Invalid) : idx(-1), p(0) {}
515 /// Constructor with starting point
516 EdgeIt(const UndirPath &_p, int _idx = 0) :
517 idx(_idx), p(&_p) { validate(); }
520 bool valid() const { return idx!=-1; }
522 ///Conversion to Graph::Edge
523 operator GraphEdge () const {
524 return valid() ? p->edges[idx] : INVALID;
527 EdgeIt& operator++() { ++idx; validate(); return *this; }
529 /// Comparison operator
530 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
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; }
537 // FIXME: comparison between signed and unsigned...
538 // Jo ez igy? Vagy esetleg legyen a length() int?
539 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
543 * \brief Iterator class to iterate on the nodes of the paths
546 * This class is used to iterate on the nodes of the paths
548 * Of course it converts to Graph::Node
550 * \todo Its interface differs from the standard node iterator.
554 friend class UndirPath;
559 /// Default constructor
561 /// Invalid constructor
562 NodeIt(Invalid) : idx(-1), p(0) {}
563 /// Constructor with starting point
564 NodeIt(const UndirPath &_p, int _idx = 0) :
565 idx(_idx), p(&_p) { validate(); }
568 bool valid() const { return idx!=-1; }
570 ///Conversion to Graph::Node
571 operator const GraphNode& () const {
572 if(idx >= p->length())
575 return p->gr->source(p->edges[idx]);
580 NodeIt& operator++() { ++idx; validate(); return *this; }
582 /// Comparison operator
583 bool operator==(const NodeIt& e) const { return idx==e.idx; }
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; }
590 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
593 friend class Builder;
596 * \brief Class to build paths
599 * This class is used to fill a path with edges.
601 * You can push new edges to the front and to the back of the path in
602 * arbitrary order then you should commit these changes to the graph.
604 * Fundamentally, for most "Paths" (classes fulfilling the
605 * PathConcept) while the builder is active (after the first modifying
606 * operation and until the commit()) the original Path is in a
607 * "transitional" state (operations ot it have undefined result). But
608 * in the case of UndirPath the original path is unchanged until the
609 * commit. However we don't recomend that you use this feature.
613 Container front, back;
616 ///\param _P the path you want to fill in.
618 Builder(UndirPath &_P) : P(_P) {}
620 /// Sets the starting node of the path.
622 /// Sets the starting node of the path. Edge added to the path
623 /// afterwards have to be incident to this node.
624 /// It should be called if and only if
625 /// the path is empty and before any call to
626 /// \ref pushFront() or \ref pushBack()
627 void setStartNode(const GraphNode &) {}
629 ///Push a new edge to the front of the path
631 ///Push a new edge to the front of the path.
633 void pushFront(const GraphEdge& e) {
637 ///Push a new edge to the back of the path
639 ///Push a new edge to the back of the path.
641 void pushBack(const GraphEdge& e) {
645 ///Commit the changes to the path.
647 if( !(front.empty() && back.empty()) ) {
649 tmp.reserve(front.size()+back.size()+P.length());
650 tmp.insert(tmp.end(), front.rbegin(), front.rend());
651 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
652 tmp.insert(tmp.end(), back.begin(), back.end());
660 ///Reserve storage for the builder in advance.
662 ///If you know a reasonable upper bound of the number of the edges
663 ///to add to the front, using this function you can speed up the building.
665 void reserveFront(size_t r) {front.reserve(r);}
667 ///Reserve storage for the builder in advance.
669 ///If you know a reasonable upper bound of the number of the edges
670 ///to add to the back, using this function you can speed up the building.
672 void reserveBack(size_t r) {back.reserve(r);}
676 return front.empty() && back.empty() && P.empty();
679 GraphNode source() const {
680 if( ! front.empty() )
681 return P.gr->source(front[front.size()-1]);
682 else if( ! P.empty() )
683 return P.gr->source(P.edges[0]);
684 else if( ! back.empty() )
685 return P.gr->source(back[0]);
689 GraphNode target() const {
691 return P.gr->target(back[back.size()-1]);
692 else if( ! P.empty() )
693 return P.gr->target(P.edges[P.length()-1]);
694 else if( ! front.empty() )
695 return P.gr->target(front[0]);
709 #endif // LEMON_PATH_H