1 #define SKELETON |
|
2 // -*- c++ -*- // |
|
3 |
|
4 ///\ingroup concept |
|
5 ///\file |
|
6 ///\brief Classes for representing paths in graphs. |
|
7 |
|
8 #ifndef LEMON_PATH_H |
|
9 #define LEMON_PATH_H |
|
10 |
|
11 #include <lemon/invalid.h> |
|
12 |
|
13 namespace lemon { |
|
14 namespace concept { |
|
15 /// \addtogroup concept |
|
16 /// @{ |
|
17 |
|
18 |
|
19 //! \brief A skeleton structure for representing directed paths in a graph. |
|
20 //! |
|
21 //! A skeleton structure for representing directed paths in a graph. |
|
22 //! \param GR The graph type in which the path is. |
|
23 //! |
|
24 //! In a sense, the path can be treated as a graph, for is has \c NodeIt |
|
25 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
|
26 //! and \c Edge of the original graph. |
|
27 template<typename GR> |
|
28 class Path { |
|
29 public: |
|
30 |
|
31 /// Type of the underlying graph. |
|
32 typedef /*typename*/ GR Graph; |
|
33 /// Edge type of the underlying graph. |
|
34 typedef typename Graph::Edge GraphEdge; |
|
35 /// Node type of the underlying graph. |
|
36 typedef typename Graph::Node GraphNode; |
|
37 class NodeIt; |
|
38 class EdgeIt; |
|
39 |
|
40 /// \param _G The graph in which the path is. |
|
41 /// |
|
42 Path(const Graph &_G) {} |
|
43 |
|
44 /// Length of the path. |
|
45 size_t length() const {} |
|
46 /// Returns whether the path is empty. |
|
47 bool empty() const {} |
|
48 |
|
49 /// Resets the path to an empty path. |
|
50 void clear() {} |
|
51 |
|
52 /// \brief Starting point of the path. |
|
53 /// |
|
54 /// Starting point of the path. |
|
55 /// Returns INVALID if the path is empty. |
|
56 GraphNode target() const {} |
|
57 /// \brief End point of the path. |
|
58 /// |
|
59 /// End point of the path. |
|
60 /// Returns INVALID if the path is empty. |
|
61 GraphNode source() const {} |
|
62 |
|
63 /// \brief First NodeIt/EdgeIt. |
|
64 /// |
|
65 /// Initializes node or edge iterator to point to the first |
|
66 /// node or edge. |
|
67 template<typename It> |
|
68 It& first(It &i) const { return i=It(*this); } |
|
69 |
|
70 /// \brief The target of an edge. |
|
71 /// |
|
72 /// Returns node iterator pointing to the target node of the |
|
73 /// given edge iterator. |
|
74 NodeIt target(const EdgeIt& e) const {} |
|
75 |
|
76 /// \brief The source of an edge. |
|
77 /// |
|
78 /// Returns node iterator pointing to the source node of the |
|
79 /// given edge iterator. |
|
80 NodeIt source(const EdgeIt& e) const {} |
|
81 |
|
82 |
|
83 /* Iterator classes */ |
|
84 |
|
85 /** |
|
86 * \brief Iterator class to iterate on the edges of the paths |
|
87 * |
|
88 * \ingroup concept |
|
89 * This class is used to iterate on the edges of the paths |
|
90 * |
|
91 * Of course it converts to Graph::Edge |
|
92 * |
|
93 */ |
|
94 class EdgeIt { |
|
95 public: |
|
96 /// Default constructor |
|
97 EdgeIt() {} |
|
98 /// Invalid constructor |
|
99 EdgeIt(Invalid) {} |
|
100 /// Constructor with starting point |
|
101 EdgeIt(const Path &_p) {} |
|
102 |
|
103 operator GraphEdge () const {} |
|
104 |
|
105 /// Next edge |
|
106 EdgeIt& operator++() {} |
|
107 |
|
108 /// Comparison operator |
|
109 bool operator==(const EdgeIt& e) const {} |
|
110 /// Comparison operator |
|
111 bool operator!=(const EdgeIt& e) const {} |
|
112 // /// Comparison operator |
|
113 // /// \todo It is not clear what is the "natural" ordering. |
|
114 // bool operator<(const EdgeIt& e) const {} |
|
115 |
|
116 }; |
|
117 |
|
118 /** |
|
119 * \brief Iterator class to iterate on the nodes of the paths |
|
120 * |
|
121 * \ingroup concept |
|
122 * This class is used to iterate on the nodes of the paths |
|
123 * |
|
124 * Of course it converts to Graph::Node. |
|
125 * |
|
126 */ |
|
127 class NodeIt { |
|
128 public: |
|
129 /// Default constructor |
|
130 NodeIt() {} |
|
131 /// Invalid constructor |
|
132 NodeIt(Invalid) {} |
|
133 /// Constructor with starting point |
|
134 NodeIt(const Path &_p) {} |
|
135 |
|
136 ///Conversion to Graph::Node |
|
137 operator const GraphNode& () const {} |
|
138 /// Next node |
|
139 NodeIt& operator++() {} |
|
140 |
|
141 /// Comparison operator |
|
142 bool operator==(const NodeIt& e) const {} |
|
143 /// Comparison operator |
|
144 bool operator!=(const NodeIt& e) const {} |
|
145 // /// Comparison operator |
|
146 // /// \todo It is not clear what is the "natural" ordering. |
|
147 // bool operator<(const NodeIt& e) const {} |
|
148 |
|
149 }; |
|
150 |
|
151 friend class Builder; |
|
152 |
|
153 /** |
|
154 * \brief Class to build paths |
|
155 * |
|
156 * \ingroup concept |
|
157 * This class is used to fill a path with edges. |
|
158 * |
|
159 * You can push new edges to the front and to the back of the path in |
|
160 * arbitrary order then you should commit these changes to the graph. |
|
161 * |
|
162 * While the builder is active (after the first modifying |
|
163 * operation and until the call of \ref commit()) |
|
164 * the underlining Path is in a |
|
165 * "transitional" state (operations on it have undefined result). |
|
166 */ |
|
167 class Builder { |
|
168 public: |
|
169 |
|
170 Path &P; |
|
171 |
|
172 ///\param _P the path you want to fill in. |
|
173 /// |
|
174 Builder(Path &_P) : P(_P) {} |
|
175 |
|
176 /// Sets the starting node of the path. |
|
177 |
|
178 /// Sets the starting node of the path. Edge added to the path |
|
179 /// afterwards have to be incident to this node. |
|
180 /// You \em must start building an empry path with this functions. |
|
181 /// (And you \em must \em not use it later). |
|
182 /// \sa pushFront() |
|
183 /// \sa pushBack() |
|
184 void setStartNode(const GraphNode &) {} |
|
185 |
|
186 ///Push a new edge to the front of the path |
|
187 |
|
188 ///Push a new edge to the front of the path. |
|
189 ///If the path is empty, you \em must call \ref setStartNode() before |
|
190 ///the first use of \ref pushFront(). |
|
191 void pushFront(const GraphEdge& e) {} |
|
192 |
|
193 ///Push a new edge to the back of the path |
|
194 |
|
195 ///Push a new edge to the back of the path. |
|
196 ///If the path is empty, you \em must call \ref setStartNode() before |
|
197 ///the first use of \ref pushBack(). |
|
198 void pushBack(const GraphEdge& e) {} |
|
199 |
|
200 ///Commit the changes to the path. |
|
201 void commit() {} |
|
202 |
|
203 ///Reserve (front) storage for the builder in advance. |
|
204 |
|
205 ///If you know an reasonable upper bound of the number of the edges |
|
206 ///to add to the front of the path, |
|
207 ///using this function you may speed up the building. |
|
208 void reserveFront(size_t r) {} |
|
209 ///Reserve (back) storage for the builder in advance. |
|
210 |
|
211 ///If you know an reasonable upper bound of the number of the edges |
|
212 ///to add to the back of the path, |
|
213 ///using this function you may speed up the building. |
|
214 void reserveBack(size_t r) {} |
|
215 }; |
|
216 }; |
|
217 |
|
218 ///@} |
|
219 } |
|
220 |
|
221 } // namespace lemon |
|
222 |
|
223 #endif // LEMON_PATH_H |
|