Unionfind changes induced some bugs here. Also some augmentations made.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
20 @defgroup paths Path Structures
22 \brief Path structures implemented in LEMON.
24 LEMON provides flexible data structures
27 All of them have the same interface, especially they can be built or extended
28 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
29 algorithm to store its result in any kind of path structure.
31 \sa lemon::concept::Path
37 ///\brief Classes for representing paths in graphs.
39 ///\todo Iterators have obsolete style
48 #include <lemon/bits/invalid.h>
56 //! \brief A structure for representing directed paths in a graph.
58 //! A structure for representing directed path in a graph.
59 //! \param Graph The graph type in which the path is.
60 //! \param DM DebugMode, defaults to DefaultDebugMode.
62 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
63 //! and \c EdgeIt with the same usage. These types converts to the \c Node
64 //! and \c Edge of the original graph.
66 //! \todo Thoroughfully check all the range and consistency tests.
67 template<typename Graph>
70 /// Edge type of the underlying graph.
71 typedef typename Graph::Edge GraphEdge;
72 /// Node type of the underlying graph.
73 typedef typename Graph::Node GraphNode;
79 typedef std::vector<GraphEdge> Container;
84 /// \param _G The graph in which the path is.
86 DirPath(const Graph &_G) : gr(&_G) {}
88 /// \brief Subpath constructor.
90 /// Subpath defined by two nodes.
91 /// \warning It is an error if the two edges are not in order!
92 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
94 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
97 /// \brief Subpath constructor.
99 /// Subpath defined by two edges. Contains edges in [a,b)
100 /// \warning It is an error if the two edges are not in order!
101 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
103 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
106 /// Length of the path.
107 int length() const { return edges.size(); }
108 /// Returns whether the path is empty.
109 bool empty() const { return edges.empty(); }
111 /// Resets the path to an empty path.
112 void clear() { edges.clear(); }
114 /// \brief Starting point of the path.
116 /// Starting point of the path.
117 /// Returns INVALID if the path is empty.
118 GraphNode source() const {
119 return empty() ? INVALID : gr->source(edges[0]);
121 /// \brief End point of the path.
123 /// End point of the path.
124 /// Returns INVALID if the path is empty.
125 GraphNode target() const {
126 return empty() ? INVALID : gr->target(edges[length()-1]);
129 /// \brief Initializes node or edge iterator to point to the first
133 template<typename It>
134 It& first(It &i) const { return i=It(*this); }
136 /// \brief Initializes node iterator to point to the node of a given index.
137 NodeIt& nth(NodeIt &i, int n) const {
138 return i=NodeIt(*this, n);
141 /// \brief Initializes edge iterator to point to the edge of a given index.
142 EdgeIt& nth(EdgeIt &i, int n) const {
143 return i=EdgeIt(*this, n);
146 /// \brief Returns node iterator pointing to the target node of the
147 /// given edge iterator.
148 NodeIt target(const EdgeIt& e) const {
149 return NodeIt(*this, e.idx+1);
152 /// \brief Returns node iterator pointing to the source node of the
153 /// given edge iterator.
154 NodeIt source(const EdgeIt& e) const {
155 return NodeIt(*this, e.idx);
159 /* Iterator classes */
162 * \brief Iterator class to iterate on the edges of the paths
164 * This class is used to iterate on the edges of the paths
166 * Of course it converts to Graph::Edge
170 friend class DirPath;
175 /// Default constructor
177 /// Invalid constructor
178 EdgeIt(Invalid) : idx(-1), p(0) {}
179 /// Constructor with starting point
180 EdgeIt(const DirPath &_p, int _idx = 0) :
181 idx(_idx), p(&_p) { validate(); }
184 bool valid() const { return idx!=-1; }
186 ///Conversion to Graph::Edge
187 operator GraphEdge () const {
188 return valid() ? p->edges[idx] : INVALID;
192 EdgeIt& operator++() { ++idx; validate(); return *this; }
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; }
198 /// Comparison operator
199 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
202 void validate() { if(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(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 /// \todo May we need just path for undirected graph instead of this.
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 UPath(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 UPath(const UPath &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 UPath(const UPath &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
497 * This class is used to iterate on the edges of the paths
499 * Of course it converts to Graph::Edge
501 * \todo Its interface differs from the standard edge iterator.
510 /// Default constructor
512 /// Invalid constructor
513 EdgeIt(Invalid) : idx(-1), p(0) {}
514 /// Constructor with starting point
515 EdgeIt(const UPath &_p, int _idx = 0) :
516 idx(_idx), p(&_p) { validate(); }
519 bool valid() const { return idx!=-1; }
521 ///Conversion to Graph::Edge
522 operator GraphEdge () const {
523 return valid() ? p->edges[idx] : INVALID;
526 EdgeIt& operator++() { ++idx; validate(); return *this; }
528 /// Comparison operator
529 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
530 /// Comparison operator
531 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
532 /// Comparison operator
533 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
536 // FIXME: comparison between signed and unsigned...
537 // Jo ez igy? Vagy esetleg legyen a length() int?
538 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
542 * \brief Iterator class to iterate on the nodes of the paths
544 * This class is used to iterate on the nodes of the paths
546 * Of course it converts to Graph::Node
548 * \todo Its interface differs from the standard node iterator.
557 /// Default constructor
559 /// Invalid constructor
560 NodeIt(Invalid) : idx(-1), p(0) {}
561 /// Constructor with starting point
562 NodeIt(const UPath &_p, int _idx = 0) :
563 idx(_idx), p(&_p) { validate(); }
566 bool valid() const { return idx!=-1; }
568 ///Conversion to Graph::Node
569 operator const GraphNode& () const {
570 if(idx >= p->length())
573 return p->gr->source(p->edges[idx]);
578 NodeIt& operator++() { ++idx; validate(); return *this; }
580 /// Comparison operator
581 bool operator==(const NodeIt& e) const { return idx==e.idx; }
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; }
588 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
591 friend class Builder;
594 * \brief Class to build paths
596 * This class is used to fill a path with edges.
598 * You can push new edges to the front and to the back of the path in
599 * arbitrary order then you should commit these changes to the graph.
601 * Fundamentally, for most "Paths" (classes fulfilling the
602 * PathConcept) while the builder is active (after the first modifying
603 * operation and until the commit()) the original Path is in a
604 * "transitional" state (operations ot it have undefined result). But
605 * in the case of UPath the original path is unchanged until the
606 * commit. However we don't recomend that you use this feature.
610 Container front, back;
613 ///\param _p the path you want to fill in.
615 Builder(UPath &_p) : P(_p) {}
617 /// Sets the starting node of the path.
619 /// Sets the starting node of the path. Edge added to the path
620 /// afterwards have to be incident to this node.
621 /// It should be called if and only if
622 /// the path is empty and before any call to
623 /// \ref pushFront() or \ref pushBack()
624 void setStartNode(const GraphNode &) {}
626 ///Push a new edge to the front of the path
628 ///Push a new edge to the front of the path.
630 void pushFront(const GraphEdge& e) {
634 ///Push a new edge to the back of the path
636 ///Push a new edge to the back of the path.
638 void pushBack(const GraphEdge& e) {
642 ///Commit the changes to the path.
644 if( !(front.empty() && back.empty()) ) {
646 tmp.reserve(front.size()+back.size()+P.length());
647 tmp.insert(tmp.end(), front.rbegin(), front.rend());
648 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
649 tmp.insert(tmp.end(), back.begin(), back.end());
657 ///Reserve storage for the builder in advance.
659 ///If you know a reasonable upper bound of the number of the edges
660 ///to add to the front, using this function you can speed up the building.
662 void reserveFront(size_t r) {front.reserve(r);}
664 ///Reserve storage for the builder in advance.
666 ///If you know a reasonable upper bound of the number of the edges
667 ///to add to the back, using this function you can speed up the building.
669 void reserveBack(size_t r) {back.reserve(r);}
673 return front.empty() && back.empty() && P.empty();
676 GraphNode source() const {
677 if( ! front.empty() )
678 return P.gr->source(front[front.size()-1]);
679 else if( ! P.empty() )
680 return P.gr->source(P.edges[0]);
681 else if( ! back.empty() )
682 return P.gr->source(back[0]);
686 GraphNode target() const {
688 return P.gr->target(back[back.size()-1]);
689 else if( ! P.empty() )
690 return P.gr->target(P.edges[P.length()-1]);
691 else if( ! front.empty() )
692 return P.gr->target(front[0]);
706 #endif // LEMON_PATH_H