Communication with algorithm window is developed.
2 * lemon/path.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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 int 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 void validate() { if(idx >= p->length() ) idx=-1; }
204 * \brief Iterator class to iterate on the nodes of the paths
206 * This class is used to iterate on the nodes of the paths
208 * Of course it converts to Graph::Node
212 friend class DirPath;
217 /// Default constructor
219 /// Invalid constructor
220 NodeIt(Invalid) : idx(-1), p(0) {}
221 /// Constructor with starting point
222 NodeIt(const DirPath &_p, int _idx = 0) :
223 idx(_idx), p(&_p) { validate(); }
226 bool valid() const { return idx!=-1; }
228 ///Conversion to Graph::Node
229 operator const GraphNode& () const {
230 if(idx >= p->length())
233 return p->gr->source(p->edges[idx]);
238 NodeIt& operator++() { ++idx; validate(); return *this; }
240 /// Comparison operator
241 bool operator==(const NodeIt& e) const { return idx==e.idx; }
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; }
248 void validate() { if(idx > p->length() ) idx=-1; }
251 friend class Builder;
254 * \brief Class to build paths
256 * This class is used to fill a path with edges.
258 * You can push new edges to the front and to the back of the path in
259 * arbitrary order then you should commit these changes to the graph.
261 * Fundamentally, for most "Paths" (classes fulfilling the
262 * PathConcept) while the builder is active (after the first modifying
263 * operation and until the commit()) the original Path is in a
264 * "transitional" state (operations on it have undefined result). But
265 * in the case of DirPath the original path remains unchanged until the
266 * commit. However we don't recomend that you use this feature.
270 Container front, back;
273 ///\param _p the path you want to fill in.
275 Builder(DirPath &_p) : P(_p) {}
277 /// Sets the starting node of the path.
279 /// Sets the starting node of the path. Edge added to the path
280 /// afterwards have to be incident to this node.
281 /// It should be called if and only if
282 /// the path is empty and before any call to
283 /// \ref pushFront() or \ref pushBack()
284 void setStartNode(const GraphNode &) {}
286 ///Push a new edge to the front of the path
288 ///Push a new edge to the front of the path.
290 void pushFront(const GraphEdge& e) {
294 ///Push a new edge to the back of the path
296 ///Push a new edge to the back of the path.
298 void pushBack(const GraphEdge& e) {
302 ///Commit the changes to the path.
304 if( !front.empty() || !back.empty() ) {
306 tmp.reserve(front.size()+back.size()+P.length());
307 tmp.insert(tmp.end(), front.rbegin(), front.rend());
308 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
309 tmp.insert(tmp.end(), back.begin(), back.end());
316 ///Reserve storage for the builder in advance.
318 ///If you know a reasonable upper bound of the number of the edges
319 ///to add to the front, using this function you can speed up the building.
321 void reserveFront(size_t r) {front.reserve(r);}
323 ///Reserve storage for the builder in advance.
325 ///If you know a reasonable upper bound of the number of the edges
326 ///to add to the back, using this function you can speed up the building.
328 void reserveBack(size_t r) {back.reserve(r);}
332 return front.empty() && back.empty() && P.empty();
335 GraphNode source() const {
336 if( ! front.empty() )
337 return P.gr->source(front[front.size()-1]);
338 else if( ! P.empty() )
339 return P.gr->source(P.edges[0]);
340 else if( ! back.empty() )
341 return P.gr->source(back[0]);
345 GraphNode target() const {
347 return P.gr->target(back[back.size()-1]);
348 else if( ! P.empty() )
349 return P.gr->target(P.edges[P.length()-1]);
350 else if( ! front.empty() )
351 return P.gr->target(front[0]);
369 /**********************************************************************/
372 //! \brief A structure for representing undirected path in a graph.
374 //! A structure for representing undirected path in a graph. Ie. this is
375 //! a path in a \e directed graph but the edges should not be directed
378 //! \param Graph The graph type in which the path is.
379 //! \param DM DebugMode, defaults to DefaultDebugMode.
381 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
382 //! and \c EdgeIt with the same usage. These types converts to the \c Node
383 //! and \c Edge of the original graph.
385 //! \todo Thoroughfully check all the range and consistency tests.
386 /// \todo May we need just path for undirected graph instead of this.
387 template<typename Graph>
390 /// Edge type of the underlying graph.
391 typedef typename Graph::Edge GraphEdge;
392 /// Node type of the underlying graph.
393 typedef typename Graph::Node GraphNode;
399 typedef std::vector<GraphEdge> Container;
404 /// \param _G The graph in which the path is.
406 UndirPath(const Graph &_G) : gr(&_G) {}
408 /// \brief Subpath constructor.
410 /// Subpath defined by two nodes.
411 /// \warning It is an error if the two edges are not in order!
412 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
414 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
417 /// \brief Subpath constructor.
419 /// Subpath defined by two edges. Contains edges in [a,b)
420 /// \warning It is an error if the two edges are not in order!
421 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
423 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
426 /// Length of the path.
427 size_t length() const { return edges.size(); }
428 /// Returns whether the path is empty.
429 bool empty() const { return edges.empty(); }
431 /// Resets the path to an empty path.
432 void clear() { edges.clear(); }
434 /// \brief Starting point of the path.
436 /// Starting point of the path.
437 /// Returns INVALID if the path is empty.
438 GraphNode source() const {
439 return empty() ? INVALID : gr->source(edges[0]);
441 /// \brief End point of the path.
443 /// End point of the path.
444 /// Returns INVALID if the path is empty.
445 GraphNode target() const {
446 return empty() ? INVALID : gr->target(edges[length()-1]);
449 /// \brief Initializes node or edge iterator to point to the first
453 template<typename It>
454 It& first(It &i) const { return i=It(*this); }
456 /// \brief Initializes node iterator to point to the node of a given index.
457 NodeIt& nth(NodeIt &i, int n) const {
458 return i=NodeIt(*this, n);
461 /// \brief Initializes edge iterator to point to the edge of a given index.
462 EdgeIt& nth(EdgeIt &i, int n) const {
463 return i=EdgeIt(*this, n);
466 /// Checks validity of a node or edge iterator.
467 template<typename It>
469 bool valid(const It &i) { return i.valid(); }
471 /// Steps the given node or edge iterator.
472 template<typename It>
478 /// \brief Returns node iterator pointing to the target node of the
479 /// given edge iterator.
480 NodeIt target(const EdgeIt& e) const {
481 return NodeIt(*this, e.idx+1);
484 /// \brief Returns node iterator pointing to the source node of the
485 /// given edge iterator.
486 NodeIt source(const EdgeIt& e) const {
487 return NodeIt(*this, e.idx);
493 * \brief Iterator class to iterate on the edges of the paths
495 * This class is used to iterate on the edges of the paths
497 * Of course it converts to Graph::Edge
499 * \todo Its interface differs from the standard edge iterator.
503 friend class UndirPath;
508 /// Default constructor
510 /// Invalid constructor
511 EdgeIt(Invalid) : idx(-1), p(0) {}
512 /// Constructor with starting point
513 EdgeIt(const UndirPath &_p, int _idx = 0) :
514 idx(_idx), p(&_p) { validate(); }
517 bool valid() const { return idx!=-1; }
519 ///Conversion to Graph::Edge
520 operator GraphEdge () const {
521 return valid() ? p->edges[idx] : INVALID;
524 EdgeIt& operator++() { ++idx; validate(); return *this; }
526 /// Comparison operator
527 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
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; }
534 // FIXME: comparison between signed and unsigned...
535 // Jo ez igy? Vagy esetleg legyen a length() int?
536 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
540 * \brief Iterator class to iterate on the nodes of the paths
542 * This class is used to iterate on the nodes of the paths
544 * Of course it converts to Graph::Node
546 * \todo Its interface differs from the standard node iterator.
550 friend class UndirPath;
555 /// Default constructor
557 /// Invalid constructor
558 NodeIt(Invalid) : idx(-1), p(0) {}
559 /// Constructor with starting point
560 NodeIt(const UndirPath &_p, int _idx = 0) :
561 idx(_idx), p(&_p) { validate(); }
564 bool valid() const { return idx!=-1; }
566 ///Conversion to Graph::Node
567 operator const GraphNode& () const {
568 if(idx >= p->length())
571 return p->gr->source(p->edges[idx]);
576 NodeIt& operator++() { ++idx; validate(); return *this; }
578 /// Comparison operator
579 bool operator==(const NodeIt& e) const { return idx==e.idx; }
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; }
586 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
589 friend class Builder;
592 * \brief Class to build paths
594 * This class is used to fill a path with edges.
596 * You can push new edges to the front and to the back of the path in
597 * arbitrary order then you should commit these changes to the graph.
599 * Fundamentally, for most "Paths" (classes fulfilling the
600 * PathConcept) while the builder is active (after the first modifying
601 * operation and until the commit()) the original Path is in a
602 * "transitional" state (operations ot it have undefined result). But
603 * in the case of UndirPath the original path is unchanged until the
604 * commit. However we don't recomend that you use this feature.
608 Container front, back;
611 ///\param _p the path you want to fill in.
613 Builder(UndirPath &_p) : P(_p) {}
615 /// Sets the starting node of the path.
617 /// Sets the starting node of the path. Edge added to the path
618 /// afterwards have to be incident to this node.
619 /// It should be called if and only if
620 /// the path is empty and before any call to
621 /// \ref pushFront() or \ref pushBack()
622 void setStartNode(const GraphNode &) {}
624 ///Push a new edge to the front of the path
626 ///Push a new edge to the front of the path.
628 void pushFront(const GraphEdge& e) {
632 ///Push a new edge to the back of the path
634 ///Push a new edge to the back of the path.
636 void pushBack(const GraphEdge& e) {
640 ///Commit the changes to the path.
642 if( !(front.empty() && back.empty()) ) {
644 tmp.reserve(front.size()+back.size()+P.length());
645 tmp.insert(tmp.end(), front.rbegin(), front.rend());
646 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
647 tmp.insert(tmp.end(), back.begin(), back.end());
655 ///Reserve storage for the builder in advance.
657 ///If you know a reasonable upper bound of the number of the edges
658 ///to add to the front, using this function you can speed up the building.
660 void reserveFront(size_t r) {front.reserve(r);}
662 ///Reserve storage for the builder in advance.
664 ///If you know a reasonable upper bound of the number of the edges
665 ///to add to the back, using this function you can speed up the building.
667 void reserveBack(size_t r) {back.reserve(r);}
671 return front.empty() && back.empty() && P.empty();
674 GraphNode source() const {
675 if( ! front.empty() )
676 return P.gr->source(front[front.size()-1]);
677 else if( ! P.empty() )
678 return P.gr->source(P.edges[0]);
679 else if( ! back.empty() )
680 return P.gr->source(back[0]);
684 GraphNode target() const {
686 return P.gr->target(back[back.size()-1]);
687 else if( ! P.empty() )
688 return P.gr->target(P.edges[P.length()-1]);
689 else if( ! front.empty() )
690 return P.gr->target(front[0]);
704 #endif // LEMON_PATH_H