- tolerance() added.
- better doc.
2 * lemon/concept/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
19 ///\brief Classes for representing paths in graphs.
21 ///\todo Iterators have obsolete style
23 #ifndef LEMON_CONCEPT_PATH_H
24 #define LEMON_CONCEPT_PATH_H
26 #include <lemon/invalid.h>
27 #include <lemon/concept_check.h>
31 /// \addtogroup concept
35 //! \brief A skeleton structure for representing directed paths in a graph.
37 //! A skeleton structure for representing directed paths in a graph.
38 //! \param GR The graph type in which the path is.
40 //! In a sense, the path can be treated as a graph, for it has \c NodeIt
41 //! and \c EdgeIt with the same usage. These types converts to the \c Node
42 //! and \c Edge of the original graph.
47 /// Type of the underlying graph.
48 typedef /*typename*/ GR Graph;
49 /// Edge type of the underlying graph.
50 typedef typename Graph::Edge GraphEdge;
51 /// Node type of the underlying graph.
52 typedef typename Graph::Node GraphNode;
56 /// \param _g The graph in which the path is.
58 Path(const Graph &_g) {
59 ignore_unused_variable_warning(_g);
62 /// Length of the path.
63 int length() const {return 0;}
64 /// Returns whether the path is empty.
65 bool empty() const { return true;}
67 /// Resets the path to an empty path.
70 /// \brief Starting point of the path.
72 /// Starting point of the path.
73 /// Returns INVALID if the path is empty.
74 GraphNode/*It*/ target() const {return INVALID;}
75 /// \brief End point of the path.
77 /// End point of the path.
78 /// Returns INVALID if the path is empty.
79 GraphNode/*It*/ source() const {return INVALID;}
81 /// \brief First NodeIt/EdgeIt.
83 /// Initializes node or edge iterator to point to the first
86 It& first(It &i) const { return i=It(*this); }
88 /// \brief The target of an edge.
90 /// Returns node iterator pointing to the target node of the
91 /// given edge iterator.
92 NodeIt target(const EdgeIt&) const {return INVALID;}
94 /// \brief The source of an edge.
96 /// Returns node iterator pointing to the source node of the
97 /// given edge iterator.
98 NodeIt source(const EdgeIt&) const {return INVALID;}
101 /* Iterator classes */
104 * \brief Iterator class to iterate on the edges of the paths
106 * This class is used to iterate on the edges of the paths
108 * Of course it converts to Graph::Edge
113 /// Default constructor
115 /// Invalid constructor
117 /// Constructor with starting point
118 EdgeIt(const Path &) {}
120 operator GraphEdge () const {}
123 EdgeIt& operator++() {return *this;}
125 /// Comparison operator
126 bool operator==(const EdgeIt&) const {return true;}
127 /// Comparison operator
128 bool operator!=(const EdgeIt&) const {return true;}
129 // /// Comparison operator
130 // /// \todo It is not clear what is the "natural" ordering.
131 // bool operator<(const EdgeIt& e) const {}
136 * \brief Iterator class to iterate on the nodes of the paths
138 * This class is used to iterate on the nodes of the paths
140 * Of course it converts to Graph::Node.
145 /// Default constructor
147 /// Invalid constructor
149 /// Constructor with starting point
150 NodeIt(const Path &) {}
152 ///Conversion to Graph::Node
153 operator const GraphNode& () const {}
155 NodeIt& operator++() {return *this;}
157 /// Comparison operator
158 bool operator==(const NodeIt&) const {return true;}
159 /// Comparison operator
160 bool operator!=(const NodeIt&) const {return true;}
161 // /// Comparison operator
162 // /// \todo It is not clear what is the "natural" ordering.
163 // bool operator<(const NodeIt& e) const {}
167 friend class Builder;
170 * \brief Class to build paths
172 * This class is used to fill a path with edges.
174 * You can push new edges to the front and to the back of the path in
175 * arbitrary order then you should commit these changes to the graph.
177 * While the builder is active (after the first modifying
178 * operation and until the call of \ref commit()) the
179 * underlining Path is in a "transitional" state (operations on
180 * it have undefined result).
187 ///\param _p the path you want to fill in.
190 Builder(Path &_p) : P(_p) {}
192 /// Sets the starting node of the path.
194 /// Sets the starting node of the path. Edge added to the path
195 /// afterwards have to be incident to this node.
196 /// You \em must start building an empty path with these functions.
197 /// (And you \em must \em not use it later).
200 void setStartNode(const GraphNode &) {}
202 ///Push a new edge to the front of the path
204 ///Push a new edge to the front of the path.
205 ///If the path is empty, you \em must call \ref setStartNode() before
206 ///the first use of \ref pushFront().
207 void pushFront(const GraphEdge&) {}
209 ///Push a new edge to the back of the path
211 ///Push a new edge to the back of the path.
212 ///If the path is empty, you \em must call \ref setStartNode() before
213 ///the first use of \ref pushBack().
214 void pushBack(const GraphEdge&) {}
216 ///Commit the changes to the path.
219 ///Reserve (front) storage for the builder in advance.
221 ///If you know a reasonable upper bound on the number of the edges
222 ///to add to the front of the path,
223 ///using this function you may speed up the building.
224 void reserveFront(size_t) {}
225 ///Reserve (back) storage for the builder in advance.
227 ///If you know a reasonable upper bound on the number of the edges
228 ///to add to the back of the path,
229 ///using this function you may speed up the building.
230 void reserveBack(size_t) {}
239 #endif // LEMON_CONCEPT_PATH_H