40 |
39 |
41 //! \brief A structure for representing directed paths in a graph. |
40 //! \brief A structure for representing directed paths in a graph. |
42 //! |
41 //! |
43 //! A structure for representing directed path in a graph. |
42 //! A structure for representing directed path in a graph. |
44 //! \param Graph The graph type in which the path is. |
43 //! \param Graph The graph type in which the path is. |
45 //! \param DM DebugMode, defaults to DefaultDebugMode. |
|
46 //! |
44 //! |
47 //! In a sense, the path can be treated as a graph, for is has \c NodeIt |
45 //! In a sense, the path can be treated as a graph, for is has \c NodeIt |
48 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
46 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
49 //! and \c Edge of the original graph. |
47 //! and \c Edge of the original graph. |
50 //! |
48 //! |
51 //! \todo Thoroughfully check all the range and consistency tests. |
49 //! \todo Thoroughfully check all the range and consistency tests. |
52 template<typename Graph> |
50 template<typename Graph> |
53 class DirPath { |
51 class Path { |
54 public: |
52 public: |
55 /// Edge type of the underlying graph. |
53 /// Edge type of the underlying graph. |
56 typedef typename Graph::Edge GraphEdge; |
54 typedef typename Graph::Edge Edge; |
57 /// Node type of the underlying graph. |
55 /// Node type of the underlying graph. |
58 typedef typename Graph::Node GraphNode; |
56 typedef typename Graph::Node Node; |
|
57 |
59 class NodeIt; |
58 class NodeIt; |
60 class EdgeIt; |
59 class EdgeIt; |
61 |
60 |
62 protected: |
61 struct PathError : public LogicError { |
63 const Graph *gr; |
62 virtual const char* what() const throw() { |
64 typedef std::vector<GraphEdge> Container; |
63 return "lemon::PathError"; |
65 Container edges; |
64 } |
|
65 }; |
66 |
66 |
67 public: |
67 public: |
68 |
68 |
|
69 /// \brief Constructor |
|
70 /// |
|
71 /// Constructor |
69 /// \param _G The graph in which the path is. |
72 /// \param _G The graph in which the path is. |
70 /// |
73 Path(const Graph &_graph) : graph(&_graph), start(INVALID) {} |
71 DirPath(const Graph &_G) : gr(&_G) {} |
74 |
72 |
|
73 /// \brief Subpath constructor. |
75 /// \brief Subpath constructor. |
74 /// |
76 /// |
75 /// Subpath defined by two nodes. |
77 /// Subpath defined by two nodes. |
76 /// \warning It is an error if the two edges are not in order! |
78 /// \warning It is an error if the two edges are not in order! |
77 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) { |
79 Path(const Path &other, const NodeIt &a, const NodeIt &b) { |
78 gr = P.gr; |
80 graph = other.graph; |
79 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
81 start = a; |
|
82 edges.insert(edges.end(), |
|
83 other.edges.begin() + a.id, other.edges.begin() + b.id); |
80 } |
84 } |
81 |
85 |
82 /// \brief Subpath constructor. |
86 /// \brief Subpath constructor. |
83 /// |
87 /// |
84 /// Subpath defined by two edges. Contains edges in [a,b) |
88 /// Subpath defined by two edges. Contains edges in [a,b) |
85 /// \warning It is an error if the two edges are not in order! |
89 /// \warning It is an error if the two edges are not in order! |
86 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) { |
90 Path(const Path &other, const EdgeIt &a, const EdgeIt &b) { |
87 gr = P.gr; |
91 graph = other.graph; |
88 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
92 start = graph->source(a); |
89 } |
93 edges.insert(edges.end(), |
90 |
94 other.edges.begin() + a.id, other.edges.begin() + b.id); |
91 /// Length of the path. |
95 } |
|
96 |
|
97 /// \brief Length of the path. |
|
98 /// |
|
99 /// The number of the edges in the path. It can be zero if the |
|
100 /// path has only one node or it is empty. |
92 int length() const { return edges.size(); } |
101 int length() const { return edges.size(); } |
93 /// Returns whether the path is empty. |
102 |
94 bool empty() const { return edges.empty(); } |
103 /// \brief Returns whether the path is empty. |
95 |
104 /// |
|
105 /// Returns true when the path does not contain neither edge nor |
|
106 /// node. |
|
107 bool empty() const { return start == INVALID; } |
|
108 |
|
109 /// \brief Resets the path to an empty path. |
|
110 /// |
96 /// Resets the path to an empty path. |
111 /// Resets the path to an empty path. |
97 void clear() { edges.clear(); } |
112 void clear() { edges.clear(); start = INVALID; } |
98 |
113 |
99 /// \brief Starting point of the path. |
114 /// \brief Starting point of the path. |
100 /// |
115 /// |
101 /// Starting point of the path. |
116 /// Starting point of the path. |
102 /// Returns INVALID if the path is empty. |
117 /// Returns INVALID if the path is empty. |
103 GraphNode source() const { |
118 Node source() const { |
104 return empty() ? INVALID : gr->source(edges[0]); |
119 return start; |
105 } |
120 } |
106 /// \brief End point of the path. |
121 /// \brief End point of the path. |
107 /// |
122 /// |
108 /// End point of the path. |
123 /// End point of the path. |
109 /// Returns INVALID if the path is empty. |
124 /// Returns INVALID if the path is empty. |
110 GraphNode target() const { |
125 Node target() const { |
111 return empty() ? INVALID : gr->target(edges[length()-1]); |
126 return length() == 0 ? start : graph->target(edges[length()-1]); |
112 } |
127 } |
113 |
128 |
114 /// \brief Initializes node or edge iterator to point to the first |
129 /// \brief Gives back a node iterator to point to the node of a |
115 /// node or edge. |
130 /// given index. |
116 /// |
131 /// |
117 /// \sa nth |
132 /// Gives back a node iterator to point to the node of a given |
118 template<typename It> |
133 /// index. |
119 It& first(It &i) const { return i=It(*this); } |
134 /// \pre n should less or equal to \c length() |
120 |
135 NodeIt nthNode(int n) const { |
121 /// \brief Initializes node iterator to point to the node of a given index. |
136 return NodeIt(*this, n); |
122 NodeIt& nth(NodeIt &i, int n) const { |
137 } |
123 return i=NodeIt(*this, n); |
138 |
124 } |
139 /// \brief Gives back an edge iterator to point to the edge of a |
125 |
140 /// given index. |
126 /// \brief Initializes edge iterator to point to the edge of a given index. |
141 /// |
127 EdgeIt& nth(EdgeIt &i, int n) const { |
142 /// Gives back an edge iterator to point to the node of a given |
128 return i=EdgeIt(*this, n); |
143 /// index. |
|
144 /// \pre n should less than \c length() |
|
145 EdgeIt nthEdge(int n) const { |
|
146 return EdgeIt(*this, n); |
|
147 } |
|
148 |
|
149 /// \brief Returns node iterator pointing to the source node of the |
|
150 /// given edge iterator. |
|
151 /// |
|
152 /// Returns node iterator pointing to the source node of the given |
|
153 /// edge iterator. |
|
154 NodeIt source(const EdgeIt& e) const { |
|
155 return NodeIt(*this, e.id); |
129 } |
156 } |
130 |
157 |
131 /// \brief Returns node iterator pointing to the target node of the |
158 /// \brief Returns node iterator pointing to the target node of the |
132 /// given edge iterator. |
159 /// given edge iterator. |
|
160 /// |
|
161 /// Returns node iterator pointing to the target node of the given |
|
162 /// edge iterator. |
133 NodeIt target(const EdgeIt& e) const { |
163 NodeIt target(const EdgeIt& e) const { |
134 return NodeIt(*this, e.idx+1); |
164 return NodeIt(*this, e.id + 1); |
135 } |
165 } |
136 |
166 |
137 /// \brief Returns node iterator pointing to the source node of the |
167 |
138 /// given edge iterator. |
168 /// \brief Iterator class to iterate on the nodes of the paths |
139 NodeIt source(const EdgeIt& e) const { |
169 /// |
140 return NodeIt(*this, e.idx); |
170 /// This class is used to iterate on the nodes of the paths |
141 } |
171 /// |
142 |
172 /// Of course it converts to Graph::Node |
143 |
173 class NodeIt { |
144 /* Iterator classes */ |
174 friend class Path; |
145 |
175 public: |
146 /** |
176 |
147 * \brief Iterator class to iterate on the edges of the paths |
177 /// \brief Default constructor |
148 * |
178 /// |
149 * This class is used to iterate on the edges of the paths |
179 /// Default constructor |
150 * |
180 NodeIt() {} |
151 * Of course it converts to Graph::Edge |
181 |
152 * |
182 /// \brief Invalid constructor |
153 */ |
183 /// |
|
184 /// Invalid constructor |
|
185 NodeIt(Invalid) : id(-1), path(0) {} |
|
186 |
|
187 /// \brief Constructor with starting point |
|
188 /// |
|
189 /// Constructor with starting point |
|
190 NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { |
|
191 if (id > path->length()) id = -1; |
|
192 } |
|
193 |
|
194 /// \brief Conversion to Graph::Node |
|
195 /// |
|
196 /// Conversion to Graph::Node |
|
197 operator Node() const { |
|
198 if (id > 0) { |
|
199 return path->graph->target(path->edges[id - 1]); |
|
200 } else if (id == 0) { |
|
201 return path->start; |
|
202 } else { |
|
203 return INVALID; |
|
204 } |
|
205 } |
|
206 |
|
207 /// \brief Steps to the next node |
|
208 /// |
|
209 /// Steps to the next node |
|
210 NodeIt& operator++() { |
|
211 ++id; |
|
212 if (id > path->length()) id = -1; |
|
213 return *this; |
|
214 } |
|
215 |
|
216 /// \brief Comparison operator |
|
217 /// |
|
218 /// Comparison operator |
|
219 bool operator==(const NodeIt& n) const { return id == n.id; } |
|
220 |
|
221 /// \brief Comparison operator |
|
222 /// |
|
223 /// Comparison operator |
|
224 bool operator!=(const NodeIt& n) const { return id != n.id; } |
|
225 |
|
226 /// \brief Comparison operator |
|
227 /// |
|
228 /// Comparison operator |
|
229 bool operator<(const NodeIt& n) const { return id < n.id; } |
|
230 |
|
231 private: |
|
232 int id; |
|
233 const Path *path; |
|
234 }; |
|
235 |
|
236 /// \brief Iterator class to iterate on the edges of the paths |
|
237 /// |
|
238 /// This class is used to iterate on the edges of the paths |
|
239 /// Of course it converts to Graph::Edge |
154 class EdgeIt { |
240 class EdgeIt { |
155 friend class DirPath; |
241 friend class Path; |
156 |
|
157 int idx; |
|
158 const DirPath *p; |
|
159 public: |
242 public: |
|
243 |
|
244 /// \brief Default constructor |
|
245 /// |
160 /// Default constructor |
246 /// Default constructor |
161 EdgeIt() {} |
247 EdgeIt() {} |
|
248 |
|
249 /// \brief Invalid constructor |
|
250 /// |
162 /// Invalid constructor |
251 /// Invalid constructor |
163 EdgeIt(Invalid) : idx(-1), p(0) {} |
252 EdgeIt(Invalid) : id(-1), path(0) {} |
|
253 |
|
254 /// \brief Constructor with starting point |
|
255 /// |
164 /// Constructor with starting point |
256 /// Constructor with starting point |
165 EdgeIt(const DirPath &_p, int _idx = 0) : |
257 EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { |
166 idx(_idx), p(&_p) { validate(); } |
258 if (id >= path->length()) id = -1; |
167 |
259 } |
168 ///Validity check |
260 |
169 bool valid() const { return idx!=-1; } |
261 /// \brief Conversion to Graph::Edge |
170 |
262 /// |
171 ///Conversion to Graph::Edge |
263 /// Conversion to Graph::Edge |
172 operator GraphEdge () const { |
264 operator Edge() const { |
173 return valid() ? p->edges[idx] : INVALID; |
265 return id != -1 ? path->edges[id] : INVALID; |
174 } |
266 } |
175 |
267 |
176 /// Next edge |
268 /// \brief Steps to the next edge |
177 EdgeIt& operator++() { ++idx; validate(); return *this; } |
269 /// |
178 |
270 /// Steps to the next edge |
179 /// Comparison operator |
271 EdgeIt& operator++() { |
180 bool operator==(const EdgeIt& e) const { return idx==e.idx; } |
272 ++id; |
181 /// Comparison operator |
273 if (id >= path->length()) id = -1; |
182 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } |
274 return *this; |
183 /// Comparison operator |
275 } |
184 bool operator<(const EdgeIt& e) const { return idx<e.idx; } |
276 |
|
277 /// \brief Comparison operator |
|
278 /// |
|
279 /// Comparison operator |
|
280 bool operator==(const EdgeIt& e) const { return id == e.id; } |
|
281 |
|
282 /// \brief Comparison operator |
|
283 /// |
|
284 /// Comparison operator |
|
285 bool operator!=(const EdgeIt& e) const { return id != e.id; } |
|
286 |
|
287 /// \brief Comparison operator |
|
288 /// |
|
289 /// Comparison operator |
|
290 bool operator<(const EdgeIt& e) const { return id < e.id; } |
185 |
291 |
186 private: |
292 private: |
187 void validate() { if(idx >= p->length() ) idx=-1; } |
293 |
|
294 int id; |
|
295 const Path *path; |
188 }; |
296 }; |
189 |
297 |
190 /** |
298 protected: |
191 * \brief Iterator class to iterate on the nodes of the paths |
299 |
192 * |
300 const Graph *graph; |
193 * This class is used to iterate on the nodes of the paths |
301 |
194 * |
302 typedef std::vector<Edge> Container; |
195 * Of course it converts to Graph::Node |
303 Container edges; |
196 * |
304 Node start; |
197 */ |
305 |
198 class NodeIt { |
306 public: |
199 friend class DirPath; |
307 |
200 |
308 friend class Builder; |
201 int idx; |
309 |
202 const DirPath *p; |
310 /// \brief Class to build paths |
|
311 /// |
|
312 /// This class is used to fill a path with edges. |
|
313 /// |
|
314 /// You can push new edges to the front and to the back of the |
|
315 /// path in arbitrary order then you should commit these changes |
|
316 /// to the graph. |
|
317 /// |
|
318 /// Fundamentally, for most "Paths" (classes fulfilling the |
|
319 /// PathConcept) while the builder is active (after the first |
|
320 /// modifying operation and until the commit()) the original Path |
|
321 /// is in a "transitional" state (operations on it have undefined |
|
322 /// result). But in the case of Path the original path remains |
|
323 /// unchanged until the commit. However we don't recomend that you |
|
324 /// use this feature. |
|
325 class Builder { |
203 public: |
326 public: |
204 /// Default constructor |
327 /// \brief Constructor |
205 NodeIt() {} |
328 /// |
206 /// Invalid constructor |
329 /// Constructor |
207 NodeIt(Invalid) : idx(-1), p(0) {} |
330 /// \param _path the path you want to fill in. |
208 /// Constructor with starting point |
331 Builder(Path &_path) : path(_path), start(INVALID) {} |
209 NodeIt(const DirPath &_p, int _idx = 0) : |
332 |
210 idx(_idx), p(&_p) { validate(); } |
333 /// \brief Destructor |
211 |
334 /// |
212 ///Validity check |
335 /// Destructor |
213 bool valid() const { return idx!=-1; } |
336 ~Builder() { |
214 |
337 LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, |
215 ///Conversion to Graph::Node |
338 PathError()); |
216 operator GraphNode () const { |
339 } |
217 if(idx >= p->length()) |
340 |
218 return p->target(); |
341 /// \brief Sets the starting node of the path. |
219 else if(idx >= 0) |
342 /// |
220 return p->gr->source(p->edges[idx]); |
|
221 else |
|
222 return INVALID; |
|
223 } |
|
224 /// Next node |
|
225 NodeIt& operator++() { ++idx; validate(); return *this; } |
|
226 |
|
227 /// Comparison operator |
|
228 bool operator==(const NodeIt& e) const { return idx==e.idx; } |
|
229 /// Comparison operator |
|
230 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } |
|
231 /// Comparison operator |
|
232 bool operator<(const NodeIt& e) const { return idx<e.idx; } |
|
233 |
|
234 private: |
|
235 void validate() { if(idx > p->length() ) idx=-1; } |
|
236 }; |
|
237 |
|
238 friend class Builder; |
|
239 |
|
240 /** |
|
241 * \brief Class to build paths |
|
242 * |
|
243 * This class is used to fill a path with edges. |
|
244 * |
|
245 * You can push new edges to the front and to the back of the path in |
|
246 * arbitrary order then you should commit these changes to the graph. |
|
247 * |
|
248 * Fundamentally, for most "Paths" (classes fulfilling the |
|
249 * PathConcept) while the builder is active (after the first modifying |
|
250 * operation and until the commit()) the original Path is in a |
|
251 * "transitional" state (operations on it have undefined result). But |
|
252 * in the case of DirPath the original path remains unchanged until the |
|
253 * commit. However we don't recomend that you use this feature. |
|
254 */ |
|
255 class Builder { |
|
256 DirPath &P; |
|
257 Container front, back; |
|
258 |
|
259 public: |
|
260 ///\param _p the path you want to fill in. |
|
261 /// |
|
262 Builder(DirPath &_p) : P(_p) {} |
|
263 |
|
264 /// Sets the starting node of the path. |
|
265 |
|
266 /// Sets the starting node of the path. Edge added to the path |
343 /// Sets the starting node of the path. Edge added to the path |
267 /// afterwards have to be incident to this node. |
344 /// afterwards have to be incident to this node. It should be |
268 /// It should be called if and only if |
345 /// called if and only if the path is empty and before any call |
269 /// the path is empty and before any call to |
346 /// to \ref pushFront() or \ref pushBack() |
270 /// \ref pushFront() or \ref pushBack() |
347 void setStartNode(const Node &_start) { |
271 void setStartNode(const GraphNode &) {} |
348 LEMON_ASSERT(path.empty() && start == INVALID, PathError()); |
272 |
349 start = _start; |
273 ///Push a new edge to the front of the path |
350 } |
274 |
351 |
275 ///Push a new edge to the front of the path. |
352 /// \brief Push a new edge to the front of the path |
276 ///\sa setStartNode |
353 /// |
277 void pushFront(const GraphEdge& e) { |
354 /// Push a new edge to the front of the path. |
|
355 /// \sa setStartNode |
|
356 void pushFront(const Edge& e) { |
|
357 LEMON_ASSERT(front.empty() || |
|
358 (path.graph->source(front.back()) == |
|
359 path.graph->target(e)), PathError()); |
|
360 LEMON_ASSERT(path.empty() || |
|
361 (path.source() == path.graph->target(e)), PathError()); |
|
362 LEMON_ASSERT(!path.empty() || !front.empty() || |
|
363 (start == path.graph->target(e)), PathError()); |
278 front.push_back(e); |
364 front.push_back(e); |
279 } |
365 } |
280 |
366 |
281 ///Push a new edge to the back of the path |
367 /// \brief Push a new edge to the back of the path |
282 |
368 /// |
283 ///Push a new edge to the back of the path. |
369 /// Push a new edge to the back of the path. |
284 ///\sa setStartNode |
370 /// \sa setStartNode |
285 void pushBack(const GraphEdge& e) { |
371 void pushBack(const Edge& e) { |
|
372 LEMON_ASSERT(back.empty() || |
|
373 (path.graph->target(back.back()) == |
|
374 path.graph->source(e)), PathError()); |
|
375 LEMON_ASSERT(path.empty() || |
|
376 (path.target() == path.graph->source(e)), PathError()); |
|
377 LEMON_ASSERT(!path.empty() || !back.empty() || |
|
378 (start == path.graph->source(e)), PathError()); |
286 back.push_back(e); |
379 back.push_back(e); |
287 } |
380 } |
288 |
381 |
289 ///Commit the changes to the path. |
382 /// \brief Commit the changes to the path. |
|
383 /// |
|
384 /// Commit the changes to the path. |
290 void commit() { |
385 void commit() { |
291 if( !front.empty() || !back.empty() ) { |
386 if( !front.empty() || !back.empty() || start != INVALID) { |
292 Container tmp; |
387 Container tmp; |
293 tmp.reserve(front.size()+back.size()+P.length()); |
388 tmp.reserve(front.size() + back.size() + path.length()); |
294 tmp.insert(tmp.end(), front.rbegin(), front.rend()); |
389 tmp.insert(tmp.end(), front.rbegin(), front.rend()); |
295 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); |
390 tmp.insert(tmp.end(), path.edges.begin(), path.edges.end()); |
296 tmp.insert(tmp.end(), back.begin(), back.end()); |
391 tmp.insert(tmp.end(), back.begin(), back.end()); |
297 P.edges.swap(tmp); |
392 path.edges.swap(tmp); |
|
393 if (!front.empty()) { |
|
394 path.start = path.graph->source(front.back()); |
|
395 } else { |
|
396 path.start = start; |
|
397 } |
|
398 start = INVALID; |
298 front.clear(); |
399 front.clear(); |
299 back.clear(); |
400 back.clear(); |
300 } |
401 } |
301 } |
402 } |
302 |
403 |
303 ///Reserve storage for the builder in advance. |
404 /// \brief Reserve storage for the builder in advance. |
304 |
405 /// |
305 ///If you know a reasonable upper bound of the number of the edges |
406 /// If you know a reasonable upper bound of the number of the |
306 ///to add to the front, using this function you can speed up the building. |
407 /// edges to add to the front, using this function you can speed |
307 |
408 /// up the building. |
308 void reserveFront(size_t r) {front.reserve(r);} |
409 void reserveFront(size_t r) {front.reserve(r);} |
309 |
410 |
310 ///Reserve storage for the builder in advance. |
411 /// \brief Reserve storage for the builder in advance. |
311 |
412 /// |
312 ///If you know a reasonable upper bound of the number of the edges |
413 /// If you know a reasonable upper bound of the number of the |
313 ///to add to the back, using this function you can speed up the building. |
414 /// edges to add to the back, using this function you can speed |
314 |
415 /// up the building. |
315 void reserveBack(size_t r) {back.reserve(r);} |
416 void reserveBack(size_t r) {back.reserve(r);} |
316 |
417 |
317 private: |
418 private: |
318 bool empty() { |
419 |
319 return front.empty() && back.empty() && P.empty(); |
420 Path &path; |
320 } |
421 Container front, back; |
321 |
422 Node start; |
322 GraphNode source() const { |
|
323 if( ! front.empty() ) |
|
324 return P.gr->source(front[front.size()-1]); |
|
325 else if( ! P.empty() ) |
|
326 return P.gr->source(P.edges[0]); |
|
327 else if( ! back.empty() ) |
|
328 return P.gr->source(back[0]); |
|
329 else |
|
330 return INVALID; |
|
331 } |
|
332 GraphNode target() const { |
|
333 if( ! back.empty() ) |
|
334 return P.gr->target(back[back.size()-1]); |
|
335 else if( ! P.empty() ) |
|
336 return P.gr->target(P.edges[P.length()-1]); |
|
337 else if( ! front.empty() ) |
|
338 return P.gr->target(front[0]); |
|
339 else |
|
340 return INVALID; |
|
341 } |
|
342 |
423 |
343 }; |
424 }; |
344 |
425 |
345 }; |
426 }; |
346 |
427 |
347 |
|
348 |
|
349 |
|
350 |
|
351 |
|
352 |
|
353 |
|
354 |
|
355 |
|
356 /**********************************************************************/ |
|
357 |
|
358 |
|
359 //! \brief A structure for representing undirected path in a graph. |
|
360 //! |
|
361 //! A structure for representing undirected path in a graph. Ie. this is |
|
362 //! a path in a \e directed graph but the edges should not be directed |
|
363 //! forward. |
|
364 //! |
|
365 //! \param Graph The graph type in which the path is. |
|
366 //! \param DM DebugMode, defaults to DefaultDebugMode. |
|
367 //! |
|
368 //! In a sense, the path can be treated as a graph, for is has \c NodeIt |
|
369 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
|
370 //! and \c Edge of the original graph. |
|
371 //! |
|
372 //! \todo Thoroughfully check all the range and consistency tests. |
|
373 /// \todo May we need just path for undirected graph instead of this. |
|
374 template<typename Graph> |
|
375 class UPath { |
|
376 public: |
|
377 /// Edge type of the underlying graph. |
|
378 typedef typename Graph::Edge GraphEdge; |
|
379 /// Node type of the underlying graph. |
|
380 typedef typename Graph::Node GraphNode; |
|
381 class NodeIt; |
|
382 class EdgeIt; |
|
383 |
|
384 protected: |
|
385 const Graph *gr; |
|
386 typedef std::vector<GraphEdge> Container; |
|
387 Container edges; |
|
388 |
|
389 public: |
|
390 |
|
391 /// \param _G The graph in which the path is. |
|
392 /// |
|
393 UPath(const Graph &_G) : gr(&_G) {} |
|
394 |
|
395 /// \brief Subpath constructor. |
|
396 /// |
|
397 /// Subpath defined by two nodes. |
|
398 /// \warning It is an error if the two edges are not in order! |
|
399 UPath(const UPath &P, const NodeIt &a, const NodeIt &b) { |
|
400 gr = P.gr; |
|
401 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
|
402 } |
|
403 |
|
404 /// \brief Subpath constructor. |
|
405 /// |
|
406 /// Subpath defined by two edges. Contains edges in [a,b) |
|
407 /// \warning It is an error if the two edges are not in order! |
|
408 UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) { |
|
409 gr = P.gr; |
|
410 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
|
411 } |
|
412 |
|
413 /// Length of the path. |
|
414 size_t length() const { return edges.size(); } |
|
415 /// Returns whether the path is empty. |
|
416 bool empty() const { return edges.empty(); } |
|
417 |
|
418 /// Resets the path to an empty path. |
|
419 void clear() { edges.clear(); } |
|
420 |
|
421 /// \brief Starting point of the path. |
|
422 /// |
|
423 /// Starting point of the path. |
|
424 /// Returns INVALID if the path is empty. |
|
425 GraphNode source() const { |
|
426 return empty() ? INVALID : gr->source(edges[0]); |
|
427 } |
|
428 /// \brief End point of the path. |
|
429 /// |
|
430 /// End point of the path. |
|
431 /// Returns INVALID if the path is empty. |
|
432 GraphNode target() const { |
|
433 return empty() ? INVALID : gr->target(edges[length()-1]); |
|
434 } |
|
435 |
|
436 /// \brief Initializes node or edge iterator to point to the first |
|
437 /// node or edge. |
|
438 /// |
|
439 /// \sa nth |
|
440 template<typename It> |
|
441 It& first(It &i) const { return i=It(*this); } |
|
442 |
|
443 /// \brief Initializes node iterator to point to the node of a given index. |
|
444 NodeIt& nth(NodeIt &i, int n) const { |
|
445 return i=NodeIt(*this, n); |
|
446 } |
|
447 |
|
448 /// \brief Initializes edge iterator to point to the edge of a given index. |
|
449 EdgeIt& nth(EdgeIt &i, int n) const { |
|
450 return i=EdgeIt(*this, n); |
|
451 } |
|
452 |
|
453 /// Checks validity of a node or edge iterator. |
|
454 template<typename It> |
|
455 static |
|
456 bool valid(const It &i) { return i.valid(); } |
|
457 |
|
458 /// Steps the given node or edge iterator. |
|
459 template<typename It> |
|
460 static |
|
461 It& next(It &e) { |
|
462 return ++e; |
|
463 } |
|
464 |
|
465 /// \brief Returns node iterator pointing to the target node of the |
|
466 /// given edge iterator. |
|
467 NodeIt target(const EdgeIt& e) const { |
|
468 return NodeIt(*this, e.idx+1); |
|
469 } |
|
470 |
|
471 /// \brief Returns node iterator pointing to the source node of the |
|
472 /// given edge iterator. |
|
473 NodeIt source(const EdgeIt& e) const { |
|
474 return NodeIt(*this, e.idx); |
|
475 } |
|
476 |
|
477 |
|
478 |
|
479 /** |
|
480 * \brief Iterator class to iterate on the edges of the paths |
|
481 * |
|
482 * This class is used to iterate on the edges of the paths |
|
483 * |
|
484 * Of course it converts to Graph::Edge |
|
485 * |
|
486 * \todo Its interface differs from the standard edge iterator. |
|
487 * Yes, it shouldn't. |
|
488 */ |
|
489 class EdgeIt { |
|
490 friend class UPath; |
|
491 |
|
492 int idx; |
|
493 const UPath *p; |
|
494 public: |
|
495 /// Default constructor |
|
496 EdgeIt() {} |
|
497 /// Invalid constructor |
|
498 EdgeIt(Invalid) : idx(-1), p(0) {} |
|
499 /// Constructor with starting point |
|
500 EdgeIt(const UPath &_p, int _idx = 0) : |
|
501 idx(_idx), p(&_p) { validate(); } |
|
502 |
|
503 ///Validity check |
|
504 bool valid() const { return idx!=-1; } |
|
505 |
|
506 ///Conversion to Graph::Edge |
|
507 operator GraphEdge () const { |
|
508 return valid() ? p->edges[idx] : INVALID; |
|
509 } |
|
510 /// Next edge |
|
511 EdgeIt& operator++() { ++idx; validate(); return *this; } |
|
512 |
|
513 /// Comparison operator |
|
514 bool operator==(const EdgeIt& e) const { return idx==e.idx; } |
|
515 /// Comparison operator |
|
516 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } |
|
517 /// Comparison operator |
|
518 bool operator<(const EdgeIt& e) const { return idx<e.idx; } |
|
519 |
|
520 private: |
|
521 // FIXME: comparison between signed and unsigned... |
|
522 // Jo ez igy? Vagy esetleg legyen a length() int? |
|
523 void validate() { if( size_t(idx) >= p->length() ) idx=-1; } |
|
524 }; |
|
525 |
|
526 /** |
|
527 * \brief Iterator class to iterate on the nodes of the paths |
|
528 * |
|
529 * This class is used to iterate on the nodes of the paths |
|
530 * |
|
531 * Of course it converts to Graph::Node |
|
532 * |
|
533 * \todo Its interface differs from the standard node iterator. |
|
534 * Yes, it shouldn't. |
|
535 */ |
|
536 class NodeIt { |
|
537 friend class UPath; |
|
538 |
|
539 int idx; |
|
540 const UPath *p; |
|
541 public: |
|
542 /// Default constructor |
|
543 NodeIt() {} |
|
544 /// Invalid constructor |
|
545 NodeIt(Invalid) : idx(-1), p(0) {} |
|
546 /// Constructor with starting point |
|
547 NodeIt(const UPath &_p, int _idx = 0) : |
|
548 idx(_idx), p(&_p) { validate(); } |
|
549 |
|
550 ///Validity check |
|
551 bool valid() const { return idx!=-1; } |
|
552 |
|
553 ///Conversion to Graph::Node |
|
554 operator const GraphNode& () const { |
|
555 if(idx >= p->length()) |
|
556 return p->target(); |
|
557 else if(idx >= 0) |
|
558 return p->gr->source(p->edges[idx]); |
|
559 else |
|
560 return INVALID; |
|
561 } |
|
562 /// Next node |
|
563 NodeIt& operator++() { ++idx; validate(); return *this; } |
|
564 |
|
565 /// Comparison operator |
|
566 bool operator==(const NodeIt& e) const { return idx==e.idx; } |
|
567 /// Comparison operator |
|
568 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } |
|
569 /// Comparison operator |
|
570 bool operator<(const NodeIt& e) const { return idx<e.idx; } |
|
571 |
|
572 private: |
|
573 void validate() { if( size_t(idx) > p->length() ) idx=-1; } |
|
574 }; |
|
575 |
|
576 friend class Builder; |
|
577 |
|
578 /** |
|
579 * \brief Class to build paths |
|
580 * |
|
581 * This class is used to fill a path with edges. |
|
582 * |
|
583 * You can push new edges to the front and to the back of the path in |
|
584 * arbitrary order then you should commit these changes to the graph. |
|
585 * |
|
586 * Fundamentally, for most "Paths" (classes fulfilling the |
|
587 * PathConcept) while the builder is active (after the first modifying |
|
588 * operation and until the commit()) the original Path is in a |
|
589 * "transitional" state (operations ot it have undefined result). But |
|
590 * in the case of UPath the original path is unchanged until the |
|
591 * commit. However we don't recomend that you use this feature. |
|
592 */ |
|
593 class Builder { |
|
594 UPath &P; |
|
595 Container front, back; |
|
596 |
|
597 public: |
|
598 ///\param _p the path you want to fill in. |
|
599 /// |
|
600 Builder(UPath &_p) : P(_p) {} |
|
601 |
|
602 /// Sets the starting node of the path. |
|
603 |
|
604 /// Sets the starting node of the path. Edge added to the path |
|
605 /// afterwards have to be incident to this node. |
|
606 /// It should be called if and only if |
|
607 /// the path is empty and before any call to |
|
608 /// \ref pushFront() or \ref pushBack() |
|
609 void setStartNode(const GraphNode &) {} |
|
610 |
|
611 ///Push a new edge to the front of the path |
|
612 |
|
613 ///Push a new edge to the front of the path. |
|
614 ///\sa setStartNode |
|
615 void pushFront(const GraphEdge& e) { |
|
616 front.push_back(e); |
|
617 } |
|
618 |
|
619 ///Push a new edge to the back of the path |
|
620 |
|
621 ///Push a new edge to the back of the path. |
|
622 ///\sa setStartNode |
|
623 void pushBack(const GraphEdge& e) { |
|
624 back.push_back(e); |
|
625 } |
|
626 |
|
627 ///Commit the changes to the path. |
|
628 void commit() { |
|
629 if( !(front.empty() && back.empty()) ) { |
|
630 Container tmp; |
|
631 tmp.reserve(front.size()+back.size()+P.length()); |
|
632 tmp.insert(tmp.end(), front.rbegin(), front.rend()); |
|
633 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); |
|
634 tmp.insert(tmp.end(), back.begin(), back.end()); |
|
635 P.edges.swap(tmp); |
|
636 front.clear(); |
|
637 back.clear(); |
|
638 } |
|
639 } |
|
640 |
|
641 |
|
642 ///Reserve storage for the builder in advance. |
|
643 |
|
644 ///If you know a reasonable upper bound of the number of the edges |
|
645 ///to add to the front, using this function you can speed up the building. |
|
646 |
|
647 void reserveFront(size_t r) {front.reserve(r);} |
|
648 |
|
649 ///Reserve storage for the builder in advance. |
|
650 |
|
651 ///If you know a reasonable upper bound of the number of the edges |
|
652 ///to add to the back, using this function you can speed up the building. |
|
653 |
|
654 void reserveBack(size_t r) {back.reserve(r);} |
|
655 |
|
656 private: |
|
657 bool empty() { |
|
658 return front.empty() && back.empty() && P.empty(); |
|
659 } |
|
660 |
|
661 GraphNode source() const { |
|
662 if( ! front.empty() ) |
|
663 return P.gr->source(front[front.size()-1]); |
|
664 else if( ! P.empty() ) |
|
665 return P.gr->source(P.edges[0]); |
|
666 else if( ! back.empty() ) |
|
667 return P.gr->source(back[0]); |
|
668 else |
|
669 return INVALID; |
|
670 } |
|
671 GraphNode target() const { |
|
672 if( ! back.empty() ) |
|
673 return P.gr->target(back[back.size()-1]); |
|
674 else if( ! P.empty() ) |
|
675 return P.gr->target(P.edges[P.length()-1]); |
|
676 else if( ! front.empty() ) |
|
677 return P.gr->target(front[0]); |
|
678 else |
|
679 return INVALID; |
|
680 } |
|
681 |
|
682 }; |
|
683 |
|
684 }; |
|
685 |
|
686 |
|
687 ///@} |
428 ///@} |
688 |
429 |
689 } // namespace lemon |
430 } // namespace lemon |
690 |
431 |
691 #endif // LEMON_PATH_H |
432 #endif // LEMON_PATH_H |