Csak a te kedvedert.
2 * src/lemon/path.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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.
37 ///\todo Iterators have obsolete style
46 #include <lemon/invalid.h>
54 //! \brief A structure for representing directed paths in a graph.
56 //! A structure for representing directed path in a graph.
57 //! \param Graph The graph type in which the path is.
58 //! \param DM DebugMode, defaults to DefaultDebugMode.
60 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
61 //! and \c EdgeIt with the same usage. These types converts to the \c Node
62 //! and \c Edge of the original graph.
64 //! \todo Thoroughfully check all the range and consistency tests.
65 template<typename Graph>
68 /// Edge type of the underlying graph.
69 typedef typename Graph::Edge GraphEdge;
70 /// Node type of the underlying graph.
71 typedef typename Graph::Node GraphNode;
77 typedef std::vector<GraphEdge> Container;
82 /// \param _G The graph in which the path is.
84 DirPath(const Graph &_G) : gr(&_G) {}
86 /// \brief Subpath constructor.
88 /// Subpath defined by two nodes.
89 /// \warning It is an error if the two edges are not in order!
90 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
92 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
95 /// \brief Subpath constructor.
97 /// Subpath defined by two edges. Contains edges in [a,b)
98 /// \warning It is an error if the two edges are not in order!
99 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
101 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
104 /// Length of the path.
105 size_t length() const { return edges.size(); }
106 /// Returns whether the path is empty.
107 bool empty() const { return edges.empty(); }
109 /// Resets the path to an empty path.
110 void clear() { edges.clear(); }
112 /// \brief Starting point of the path.
114 /// Starting point of the path.
115 /// Returns INVALID if the path is empty.
116 GraphNode source() const {
117 return empty() ? INVALID : gr->source(edges[0]);
119 /// \brief End point of the path.
121 /// End point of the path.
122 /// Returns INVALID if the path is empty.
123 GraphNode target() const {
124 return empty() ? INVALID : gr->target(edges[length()-1]);
127 /// \brief Initializes node or edge iterator to point to the first
131 template<typename It>
132 It& first(It &i) const { return i=It(*this); }
134 /// \brief Initializes node iterator to point to the node of a given index.
135 NodeIt& nth(NodeIt &i, int n) const {
136 return i=NodeIt(*this, n);
139 /// \brief Initializes edge iterator to point to the edge of a given index.
140 EdgeIt& nth(EdgeIt &i, int n) const {
141 return i=EdgeIt(*this, n);
144 /// \brief Returns node iterator pointing to the target node of the
145 /// given edge iterator.
146 NodeIt target(const EdgeIt& e) const {
147 return NodeIt(*this, e.idx+1);
150 /// \brief Returns node iterator pointing to the source node of the
151 /// given edge iterator.
152 NodeIt source(const EdgeIt& e) const {
153 return NodeIt(*this, e.idx);
157 /* Iterator classes */
160 * \brief Iterator class to iterate on the edges of the paths
162 * This class is used to iterate on the edges of the paths
164 * Of course it converts to Graph::Edge
168 friend class DirPath;
173 /// Default constructor
175 /// Invalid constructor
176 EdgeIt(Invalid) : idx(-1), p(0) {}
177 /// Constructor with starting point
178 EdgeIt(const DirPath &_p, int _idx = 0) :
179 idx(_idx), p(&_p) { validate(); }
182 bool valid() const { return idx!=-1; }
184 ///Conversion to Graph::Edge
185 operator GraphEdge () const {
186 return valid() ? p->edges[idx] : INVALID;
190 EdgeIt& operator++() { ++idx; validate(); return *this; }
192 /// Comparison operator
193 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
194 /// Comparison operator
195 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
196 /// Comparison operator
197 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
200 // FIXME: comparison between signed and unsigned...
201 // Jo ez igy? Vagy esetleg legyen a length() int?
202 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
206 * \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
258 * This class is used to fill a path with edges.
260 * You can push new edges to the front and to the back of the path in
261 * arbitrary order then you should commit these changes to the graph.
263 * Fundamentally, for most "Paths" (classes fulfilling the
264 * PathConcept) while the builder is active (after the first modifying
265 * operation and until the commit()) the original Path is in a
266 * "transitional" state (operations on it have undefined result). But
267 * in the case of DirPath the original path remains unchanged until the
268 * commit. However we don't recomend that you use this feature.
272 Container front, back;
275 ///\param _p the path you want to fill in.
277 Builder(DirPath &_p) : P(_p) {}
279 /// Sets the starting node of the path.
281 /// Sets the starting node of the path. Edge added to the path
282 /// afterwards have to be incident to this node.
283 /// It should be called if and only if
284 /// the path is empty and before any call to
285 /// \ref pushFront() or \ref pushBack()
286 void setStartNode(const GraphNode &) {}
288 ///Push a new edge to the front of the path
290 ///Push a new edge to the front of the path.
292 void pushFront(const GraphEdge& e) {
296 ///Push a new edge to the back of the path
298 ///Push a new edge to the back of the path.
300 void pushBack(const GraphEdge& e) {
304 ///Commit the changes to the path.
306 if( !front.empty() || !back.empty() ) {
308 tmp.reserve(front.size()+back.size()+P.length());
309 tmp.insert(tmp.end(), front.rbegin(), front.rend());
310 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
311 tmp.insert(tmp.end(), back.begin(), back.end());
318 ///Reserve storage for the builder in advance.
320 ///If you know a reasonable upper bound of the number of the edges
321 ///to add to the front, using this function you can speed up the building.
323 void reserveFront(size_t r) {front.reserve(r);}
325 ///Reserve storage for the builder in advance.
327 ///If you know a reasonable upper bound of the number of the edges
328 ///to add to the back, using this function you can speed up the building.
330 void reserveBack(size_t r) {back.reserve(r);}
334 return front.empty() && back.empty() && P.empty();
337 GraphNode source() const {
338 if( ! front.empty() )
339 return P.gr->source(front[front.size()-1]);
340 else if( ! P.empty() )
341 return P.gr->source(P.edges[0]);
342 else if( ! back.empty() )
343 return P.gr->source(back[0]);
347 GraphNode target() const {
349 return P.gr->target(back[back.size()-1]);
350 else if( ! P.empty() )
351 return P.gr->target(P.edges[P.length()-1]);
352 else if( ! front.empty() )
353 return P.gr->target(front[0]);
371 /**********************************************************************/
374 //! \brief A structure for representing undirected path in a graph.
376 //! A structure for representing undirected path in a graph. Ie. this is
377 //! a path in a \e directed graph but the edges should not be directed
380 //! \param Graph The graph type in which the path is.
381 //! \param DM DebugMode, defaults to DefaultDebugMode.
383 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
384 //! and \c EdgeIt with the same usage. These types converts to the \c Node
385 //! and \c Edge of the original graph.
387 //! \todo Thoroughfully check all the range and consistency tests.
388 template<typename Graph>
391 /// Edge type of the underlying graph.
392 typedef typename Graph::Edge GraphEdge;
393 /// Node type of the underlying graph.
394 typedef typename Graph::Node GraphNode;
400 typedef std::vector<GraphEdge> Container;
405 /// \param _G The graph in which the path is.
407 UndirPath(const Graph &_G) : gr(&_G) {}
409 /// \brief Subpath constructor.
411 /// Subpath defined by two nodes.
412 /// \warning It is an error if the two edges are not in order!
413 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
415 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
418 /// \brief Subpath constructor.
420 /// Subpath defined by two edges. Contains edges in [a,b)
421 /// \warning It is an error if the two edges are not in order!
422 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
424 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
427 /// Length of the path.
428 size_t length() const { return edges.size(); }
429 /// Returns whether the path is empty.
430 bool empty() const { return edges.empty(); }
432 /// Resets the path to an empty path.
433 void clear() { edges.clear(); }
435 /// \brief Starting point of the path.
437 /// Starting point of the path.
438 /// Returns INVALID if the path is empty.
439 GraphNode source() const {
440 return empty() ? INVALID : gr->source(edges[0]);
442 /// \brief End point of the path.
444 /// End point of the path.
445 /// Returns INVALID if the path is empty.
446 GraphNode target() const {
447 return empty() ? INVALID : gr->target(edges[length()-1]);
450 /// \brief Initializes node or edge iterator to point to the first
454 template<typename It>
455 It& first(It &i) const { return i=It(*this); }
457 /// \brief Initializes node iterator to point to the node of a given index.
458 NodeIt& nth(NodeIt &i, int n) const {
459 return i=NodeIt(*this, n);
462 /// \brief Initializes edge iterator to point to the edge of a given index.
463 EdgeIt& nth(EdgeIt &i, int n) const {
464 return i=EdgeIt(*this, n);
467 /// Checks validity of a node or edge iterator.
468 template<typename It>
470 bool valid(const It &i) { return i.valid(); }
472 /// Steps the given node or edge iterator.
473 template<typename It>
479 /// \brief Returns node iterator pointing to the target node of the
480 /// given edge iterator.
481 NodeIt target(const EdgeIt& e) const {
482 return NodeIt(*this, e.idx+1);
485 /// \brief Returns node iterator pointing to the source node of the
486 /// given edge iterator.
487 NodeIt source(const EdgeIt& e) const {
488 return NodeIt(*this, e.idx);
494 * \brief Iterator class to iterate on the edges of the paths
496 * This class is used to iterate on the edges of the paths
498 * Of course it converts to Graph::Edge
500 * \todo Its interface differs from the standard edge iterator.
504 friend class UndirPath;
509 /// Default constructor
511 /// Invalid constructor
512 EdgeIt(Invalid) : idx(-1), p(0) {}
513 /// Constructor with starting point
514 EdgeIt(const UndirPath &_p, int _idx = 0) :
515 idx(_idx), p(&_p) { validate(); }
518 bool valid() const { return idx!=-1; }
520 ///Conversion to Graph::Edge
521 operator GraphEdge () const {
522 return valid() ? p->edges[idx] : INVALID;
525 EdgeIt& operator++() { ++idx; validate(); return *this; }
527 /// Comparison operator
528 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
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; }
535 // FIXME: comparison between signed and unsigned...
536 // Jo ez igy? Vagy esetleg legyen a length() int?
537 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
541 * \brief Iterator class to iterate on the nodes of the paths
543 * This class is used to iterate on the nodes of the paths
545 * Of course it converts to Graph::Node
547 * \todo Its interface differs from the standard node iterator.
551 friend class UndirPath;
556 /// Default constructor
558 /// Invalid constructor
559 NodeIt(Invalid) : idx(-1), p(0) {}
560 /// Constructor with starting point
561 NodeIt(const UndirPath &_p, int _idx = 0) :
562 idx(_idx), p(&_p) { validate(); }
565 bool valid() const { return idx!=-1; }
567 ///Conversion to Graph::Node
568 operator const GraphNode& () const {
569 if(idx >= p->length())
572 return p->gr->source(p->edges[idx]);
577 NodeIt& operator++() { ++idx; validate(); return *this; }
579 /// Comparison operator
580 bool operator==(const NodeIt& e) const { return idx==e.idx; }
581 /// Comparison operator
582 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
583 /// Comparison operator
584 bool operator<(const NodeIt& e) const { return idx<e.idx; }
587 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
590 friend class Builder;
593 * \brief Class to build paths
595 * This class is used to fill a path with edges.
597 * You can push new edges to the front and to the back of the path in
598 * arbitrary order then you should commit these changes to the graph.
600 * Fundamentally, for most "Paths" (classes fulfilling the
601 * PathConcept) while the builder is active (after the first modifying
602 * operation and until the commit()) the original Path is in a
603 * "transitional" state (operations ot it have undefined result). But
604 * in the case of UndirPath the original path is unchanged until the
605 * commit. However we don't recomend that you use this feature.
609 Container front, back;
612 ///\param _p the path you want to fill in.
614 Builder(UndirPath &_p) : P(_p) {}
616 /// Sets the starting node of the path.
618 /// Sets the starting node of the path. Edge added to the path
619 /// afterwards have to be incident to this node.
620 /// It should be called if and only if
621 /// the path is empty and before any call to
622 /// \ref pushFront() or \ref pushBack()
623 void setStartNode(const GraphNode &) {}
625 ///Push a new edge to the front of the path
627 ///Push a new edge to the front of the path.
629 void pushFront(const GraphEdge& e) {
633 ///Push a new edge to the back of the path
635 ///Push a new edge to the back of the path.
637 void pushBack(const GraphEdge& e) {
641 ///Commit the changes to the path.
643 if( !(front.empty() && back.empty()) ) {
645 tmp.reserve(front.size()+back.size()+P.length());
646 tmp.insert(tmp.end(), front.rbegin(), front.rend());
647 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
648 tmp.insert(tmp.end(), back.begin(), back.end());
656 ///Reserve storage for the builder in advance.
658 ///If you know a reasonable upper bound of the number of the edges
659 ///to add to the front, using this function you can speed up the building.
661 void reserveFront(size_t r) {front.reserve(r);}
663 ///Reserve storage for the builder in advance.
665 ///If you know a reasonable upper bound of the number of the edges
666 ///to add to the back, using this function you can speed up the building.
668 void reserveBack(size_t r) {back.reserve(r);}
672 return front.empty() && back.empty() && P.empty();
675 GraphNode source() const {
676 if( ! front.empty() )
677 return P.gr->source(front[front.size()-1]);
678 else if( ! P.empty() )
679 return P.gr->source(P.edges[0]);
680 else if( ! back.empty() )
681 return P.gr->source(back[0]);
685 GraphNode target() const {
687 return P.gr->target(back[back.size()-1]);
688 else if( ! P.empty() )
689 return P.gr->target(P.edges[P.length()-1]);
690 else if( ! front.empty() )
691 return P.gr->target(front[0]);
705 #endif // LEMON_PATH_H