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