1 /* -*- C++ -*- |
|
2 * src/lemon/path.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
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. |
|
10 * |
|
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 |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 /** |
|
18 @defgroup paths Path Structures |
|
19 @ingroup datas |
|
20 \brief Path structures implemented in LEMON. |
|
21 |
|
22 LEMON provides flexible data structures |
|
23 to work with paths. |
|
24 |
|
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. |
|
28 |
|
29 \sa lemon::concept::Path |
|
30 |
|
31 */ |
|
32 |
|
33 ///\ingroup paths |
|
34 ///\file |
|
35 ///\brief Classes for representing paths in graphs. |
|
36 /// |
|
37 ///\todo Iterators have obsolete style |
|
38 |
|
39 #ifndef LEMON_PATH_H |
|
40 #define LEMON_PATH_H |
|
41 |
|
42 #include <deque> |
|
43 #include <vector> |
|
44 #include <algorithm> |
|
45 |
|
46 #include <lemon/invalid.h> |
|
47 |
|
48 namespace lemon { |
|
49 |
|
50 /// \addtogroup paths |
|
51 /// @{ |
|
52 |
|
53 |
|
54 //! \brief A structure for representing directed paths in a graph. |
|
55 //! |
|
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. |
|
59 //! |
|
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. |
|
63 //! |
|
64 //! \todo Thoroughfully check all the range and consistency tests. |
|
65 template<typename Graph> |
|
66 class DirPath { |
|
67 public: |
|
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; |
|
72 class NodeIt; |
|
73 class EdgeIt; |
|
74 |
|
75 protected: |
|
76 const Graph *gr; |
|
77 typedef std::vector<GraphEdge> Container; |
|
78 Container edges; |
|
79 |
|
80 public: |
|
81 |
|
82 /// \param _G The graph in which the path is. |
|
83 /// |
|
84 DirPath(const Graph &_G) : gr(&_G) {} |
|
85 |
|
86 /// \brief Subpath constructor. |
|
87 /// |
|
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) { |
|
91 gr = P.gr; |
|
92 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
|
93 } |
|
94 |
|
95 /// \brief Subpath constructor. |
|
96 /// |
|
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) { |
|
100 gr = P.gr; |
|
101 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
|
102 } |
|
103 |
|
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(); } |
|
108 |
|
109 /// Resets the path to an empty path. |
|
110 void clear() { edges.clear(); } |
|
111 |
|
112 /// \brief Starting point of the path. |
|
113 /// |
|
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]); |
|
118 } |
|
119 /// \brief End point of the path. |
|
120 /// |
|
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]); |
|
125 } |
|
126 |
|
127 /// \brief Initializes node or edge iterator to point to the first |
|
128 /// node or edge. |
|
129 /// |
|
130 /// \sa nth |
|
131 template<typename It> |
|
132 It& first(It &i) const { return i=It(*this); } |
|
133 |
|
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); |
|
137 } |
|
138 |
|
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); |
|
142 } |
|
143 |
|
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); |
|
148 } |
|
149 |
|
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); |
|
154 } |
|
155 |
|
156 |
|
157 /* Iterator classes */ |
|
158 |
|
159 /** |
|
160 * \brief Iterator class to iterate on the edges of the paths |
|
161 * |
|
162 * This class is used to iterate on the edges of the paths |
|
163 * |
|
164 * Of course it converts to Graph::Edge |
|
165 * |
|
166 */ |
|
167 class EdgeIt { |
|
168 friend class DirPath; |
|
169 |
|
170 int idx; |
|
171 const DirPath *p; |
|
172 public: |
|
173 /// Default constructor |
|
174 EdgeIt() {} |
|
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(); } |
|
180 |
|
181 ///Validity check |
|
182 bool valid() const { return idx!=-1; } |
|
183 |
|
184 ///Conversion to Graph::Edge |
|
185 operator GraphEdge () const { |
|
186 return valid() ? p->edges[idx] : INVALID; |
|
187 } |
|
188 |
|
189 /// Next edge |
|
190 EdgeIt& operator++() { ++idx; validate(); return *this; } |
|
191 |
|
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; } |
|
198 |
|
199 private: |
|
200 void validate() { if(idx >= p->length() ) idx=-1; } |
|
201 }; |
|
202 |
|
203 /** |
|
204 * \brief Iterator class to iterate on the nodes of the paths |
|
205 * |
|
206 * This class is used to iterate on the nodes of the paths |
|
207 * |
|
208 * Of course it converts to Graph::Node |
|
209 * |
|
210 */ |
|
211 class NodeIt { |
|
212 friend class DirPath; |
|
213 |
|
214 int idx; |
|
215 const DirPath *p; |
|
216 public: |
|
217 /// Default constructor |
|
218 NodeIt() {} |
|
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(); } |
|
224 |
|
225 ///Validity check |
|
226 bool valid() const { return idx!=-1; } |
|
227 |
|
228 ///Conversion to Graph::Node |
|
229 operator const GraphNode& () const { |
|
230 if(idx >= p->length()) |
|
231 return p->target(); |
|
232 else if(idx >= 0) |
|
233 return p->gr->source(p->edges[idx]); |
|
234 else |
|
235 return INVALID; |
|
236 } |
|
237 /// Next node |
|
238 NodeIt& operator++() { ++idx; validate(); return *this; } |
|
239 |
|
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; } |
|
246 |
|
247 private: |
|
248 void validate() { if(idx > p->length() ) idx=-1; } |
|
249 }; |
|
250 |
|
251 friend class Builder; |
|
252 |
|
253 /** |
|
254 * \brief Class to build paths |
|
255 * |
|
256 * This class is used to fill a path with edges. |
|
257 * |
|
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. |
|
260 * |
|
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. |
|
267 */ |
|
268 class Builder { |
|
269 DirPath &P; |
|
270 Container front, back; |
|
271 |
|
272 public: |
|
273 ///\param _p the path you want to fill in. |
|
274 /// |
|
275 Builder(DirPath &_p) : P(_p) {} |
|
276 |
|
277 /// Sets the starting node of the path. |
|
278 |
|
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 &) {} |
|
285 |
|
286 ///Push a new edge to the front of the path |
|
287 |
|
288 ///Push a new edge to the front of the path. |
|
289 ///\sa setStartNode |
|
290 void pushFront(const GraphEdge& e) { |
|
291 front.push_back(e); |
|
292 } |
|
293 |
|
294 ///Push a new edge to the back of the path |
|
295 |
|
296 ///Push a new edge to the back of the path. |
|
297 ///\sa setStartNode |
|
298 void pushBack(const GraphEdge& e) { |
|
299 back.push_back(e); |
|
300 } |
|
301 |
|
302 ///Commit the changes to the path. |
|
303 void commit() { |
|
304 if( !front.empty() || !back.empty() ) { |
|
305 Container tmp; |
|
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()); |
|
310 P.edges.swap(tmp); |
|
311 front.clear(); |
|
312 back.clear(); |
|
313 } |
|
314 } |
|
315 |
|
316 ///Reserve storage for the builder in advance. |
|
317 |
|
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. |
|
320 |
|
321 void reserveFront(size_t r) {front.reserve(r);} |
|
322 |
|
323 ///Reserve storage for the builder in advance. |
|
324 |
|
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. |
|
327 |
|
328 void reserveBack(size_t r) {back.reserve(r);} |
|
329 |
|
330 private: |
|
331 bool empty() { |
|
332 return front.empty() && back.empty() && P.empty(); |
|
333 } |
|
334 |
|
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]); |
|
342 else |
|
343 return INVALID; |
|
344 } |
|
345 GraphNode target() const { |
|
346 if( ! back.empty() ) |
|
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]); |
|
352 else |
|
353 return INVALID; |
|
354 } |
|
355 |
|
356 }; |
|
357 |
|
358 }; |
|
359 |
|
360 |
|
361 |
|
362 |
|
363 |
|
364 |
|
365 |
|
366 |
|
367 |
|
368 |
|
369 /**********************************************************************/ |
|
370 |
|
371 |
|
372 //! \brief A structure for representing undirected path in a graph. |
|
373 //! |
|
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 |
|
376 //! forward. |
|
377 //! |
|
378 //! \param Graph The graph type in which the path is. |
|
379 //! \param DM DebugMode, defaults to DefaultDebugMode. |
|
380 //! |
|
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. |
|
384 //! |
|
385 //! \todo Thoroughfully check all the range and consistency tests. |
|
386 template<typename Graph> |
|
387 class UndirPath { |
|
388 public: |
|
389 /// Edge type of the underlying graph. |
|
390 typedef typename Graph::Edge GraphEdge; |
|
391 /// Node type of the underlying graph. |
|
392 typedef typename Graph::Node GraphNode; |
|
393 class NodeIt; |
|
394 class EdgeIt; |
|
395 |
|
396 protected: |
|
397 const Graph *gr; |
|
398 typedef std::vector<GraphEdge> Container; |
|
399 Container edges; |
|
400 |
|
401 public: |
|
402 |
|
403 /// \param _G The graph in which the path is. |
|
404 /// |
|
405 UndirPath(const Graph &_G) : gr(&_G) {} |
|
406 |
|
407 /// \brief Subpath constructor. |
|
408 /// |
|
409 /// Subpath defined by two nodes. |
|
410 /// \warning It is an error if the two edges are not in order! |
|
411 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) { |
|
412 gr = P.gr; |
|
413 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
|
414 } |
|
415 |
|
416 /// \brief Subpath constructor. |
|
417 /// |
|
418 /// Subpath defined by two edges. Contains edges in [a,b) |
|
419 /// \warning It is an error if the two edges are not in order! |
|
420 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) { |
|
421 gr = P.gr; |
|
422 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
|
423 } |
|
424 |
|
425 /// Length of the path. |
|
426 size_t length() const { return edges.size(); } |
|
427 /// Returns whether the path is empty. |
|
428 bool empty() const { return edges.empty(); } |
|
429 |
|
430 /// Resets the path to an empty path. |
|
431 void clear() { edges.clear(); } |
|
432 |
|
433 /// \brief Starting point of the path. |
|
434 /// |
|
435 /// Starting point of the path. |
|
436 /// Returns INVALID if the path is empty. |
|
437 GraphNode source() const { |
|
438 return empty() ? INVALID : gr->source(edges[0]); |
|
439 } |
|
440 /// \brief End point of the path. |
|
441 /// |
|
442 /// End point of the path. |
|
443 /// Returns INVALID if the path is empty. |
|
444 GraphNode target() const { |
|
445 return empty() ? INVALID : gr->target(edges[length()-1]); |
|
446 } |
|
447 |
|
448 /// \brief Initializes node or edge iterator to point to the first |
|
449 /// node or edge. |
|
450 /// |
|
451 /// \sa nth |
|
452 template<typename It> |
|
453 It& first(It &i) const { return i=It(*this); } |
|
454 |
|
455 /// \brief Initializes node iterator to point to the node of a given index. |
|
456 NodeIt& nth(NodeIt &i, int n) const { |
|
457 return i=NodeIt(*this, n); |
|
458 } |
|
459 |
|
460 /// \brief Initializes edge iterator to point to the edge of a given index. |
|
461 EdgeIt& nth(EdgeIt &i, int n) const { |
|
462 return i=EdgeIt(*this, n); |
|
463 } |
|
464 |
|
465 /// Checks validity of a node or edge iterator. |
|
466 template<typename It> |
|
467 static |
|
468 bool valid(const It &i) { return i.valid(); } |
|
469 |
|
470 /// Steps the given node or edge iterator. |
|
471 template<typename It> |
|
472 static |
|
473 It& next(It &e) { |
|
474 return ++e; |
|
475 } |
|
476 |
|
477 /// \brief Returns node iterator pointing to the target node of the |
|
478 /// given edge iterator. |
|
479 NodeIt target(const EdgeIt& e) const { |
|
480 return NodeIt(*this, e.idx+1); |
|
481 } |
|
482 |
|
483 /// \brief Returns node iterator pointing to the source node of the |
|
484 /// given edge iterator. |
|
485 NodeIt source(const EdgeIt& e) const { |
|
486 return NodeIt(*this, e.idx); |
|
487 } |
|
488 |
|
489 |
|
490 |
|
491 /** |
|
492 * \brief Iterator class to iterate on the edges of the paths |
|
493 * |
|
494 * This class is used to iterate on the edges of the paths |
|
495 * |
|
496 * Of course it converts to Graph::Edge |
|
497 * |
|
498 * \todo Its interface differs from the standard edge iterator. |
|
499 * Yes, it shouldn't. |
|
500 */ |
|
501 class EdgeIt { |
|
502 friend class UndirPath; |
|
503 |
|
504 int idx; |
|
505 const UndirPath *p; |
|
506 public: |
|
507 /// Default constructor |
|
508 EdgeIt() {} |
|
509 /// Invalid constructor |
|
510 EdgeIt(Invalid) : idx(-1), p(0) {} |
|
511 /// Constructor with starting point |
|
512 EdgeIt(const UndirPath &_p, int _idx = 0) : |
|
513 idx(_idx), p(&_p) { validate(); } |
|
514 |
|
515 ///Validity check |
|
516 bool valid() const { return idx!=-1; } |
|
517 |
|
518 ///Conversion to Graph::Edge |
|
519 operator GraphEdge () const { |
|
520 return valid() ? p->edges[idx] : INVALID; |
|
521 } |
|
522 /// Next edge |
|
523 EdgeIt& operator++() { ++idx; validate(); return *this; } |
|
524 |
|
525 /// Comparison operator |
|
526 bool operator==(const EdgeIt& e) const { return idx==e.idx; } |
|
527 /// Comparison operator |
|
528 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } |
|
529 /// Comparison operator |
|
530 bool operator<(const EdgeIt& e) const { return idx<e.idx; } |
|
531 |
|
532 private: |
|
533 // FIXME: comparison between signed and unsigned... |
|
534 // Jo ez igy? Vagy esetleg legyen a length() int? |
|
535 void validate() { if( size_t(idx) >= p->length() ) idx=-1; } |
|
536 }; |
|
537 |
|
538 /** |
|
539 * \brief Iterator class to iterate on the nodes of the paths |
|
540 * |
|
541 * This class is used to iterate on the nodes of the paths |
|
542 * |
|
543 * Of course it converts to Graph::Node |
|
544 * |
|
545 * \todo Its interface differs from the standard node iterator. |
|
546 * Yes, it shouldn't. |
|
547 */ |
|
548 class NodeIt { |
|
549 friend class UndirPath; |
|
550 |
|
551 int idx; |
|
552 const UndirPath *p; |
|
553 public: |
|
554 /// Default constructor |
|
555 NodeIt() {} |
|
556 /// Invalid constructor |
|
557 NodeIt(Invalid) : idx(-1), p(0) {} |
|
558 /// Constructor with starting point |
|
559 NodeIt(const UndirPath &_p, int _idx = 0) : |
|
560 idx(_idx), p(&_p) { validate(); } |
|
561 |
|
562 ///Validity check |
|
563 bool valid() const { return idx!=-1; } |
|
564 |
|
565 ///Conversion to Graph::Node |
|
566 operator const GraphNode& () const { |
|
567 if(idx >= p->length()) |
|
568 return p->target(); |
|
569 else if(idx >= 0) |
|
570 return p->gr->source(p->edges[idx]); |
|
571 else |
|
572 return INVALID; |
|
573 } |
|
574 /// Next node |
|
575 NodeIt& operator++() { ++idx; validate(); return *this; } |
|
576 |
|
577 /// Comparison operator |
|
578 bool operator==(const NodeIt& e) const { return idx==e.idx; } |
|
579 /// Comparison operator |
|
580 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } |
|
581 /// Comparison operator |
|
582 bool operator<(const NodeIt& e) const { return idx<e.idx; } |
|
583 |
|
584 private: |
|
585 void validate() { if( size_t(idx) > p->length() ) idx=-1; } |
|
586 }; |
|
587 |
|
588 friend class Builder; |
|
589 |
|
590 /** |
|
591 * \brief Class to build paths |
|
592 * |
|
593 * This class is used to fill a path with edges. |
|
594 * |
|
595 * You can push new edges to the front and to the back of the path in |
|
596 * arbitrary order then you should commit these changes to the graph. |
|
597 * |
|
598 * Fundamentally, for most "Paths" (classes fulfilling the |
|
599 * PathConcept) while the builder is active (after the first modifying |
|
600 * operation and until the commit()) the original Path is in a |
|
601 * "transitional" state (operations ot it have undefined result). But |
|
602 * in the case of UndirPath the original path is unchanged until the |
|
603 * commit. However we don't recomend that you use this feature. |
|
604 */ |
|
605 class Builder { |
|
606 UndirPath &P; |
|
607 Container front, back; |
|
608 |
|
609 public: |
|
610 ///\param _p the path you want to fill in. |
|
611 /// |
|
612 Builder(UndirPath &_p) : P(_p) {} |
|
613 |
|
614 /// Sets the starting node of the path. |
|
615 |
|
616 /// Sets the starting node of the path. Edge added to the path |
|
617 /// afterwards have to be incident to this node. |
|
618 /// It should be called if and only if |
|
619 /// the path is empty and before any call to |
|
620 /// \ref pushFront() or \ref pushBack() |
|
621 void setStartNode(const GraphNode &) {} |
|
622 |
|
623 ///Push a new edge to the front of the path |
|
624 |
|
625 ///Push a new edge to the front of the path. |
|
626 ///\sa setStartNode |
|
627 void pushFront(const GraphEdge& e) { |
|
628 front.push_back(e); |
|
629 } |
|
630 |
|
631 ///Push a new edge to the back of the path |
|
632 |
|
633 ///Push a new edge to the back of the path. |
|
634 ///\sa setStartNode |
|
635 void pushBack(const GraphEdge& e) { |
|
636 back.push_back(e); |
|
637 } |
|
638 |
|
639 ///Commit the changes to the path. |
|
640 void commit() { |
|
641 if( !(front.empty() && back.empty()) ) { |
|
642 Container tmp; |
|
643 tmp.reserve(front.size()+back.size()+P.length()); |
|
644 tmp.insert(tmp.end(), front.rbegin(), front.rend()); |
|
645 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); |
|
646 tmp.insert(tmp.end(), back.begin(), back.end()); |
|
647 P.edges.swap(tmp); |
|
648 front.clear(); |
|
649 back.clear(); |
|
650 } |
|
651 } |
|
652 |
|
653 |
|
654 ///Reserve storage for the builder in advance. |
|
655 |
|
656 ///If you know a reasonable upper bound of the number of the edges |
|
657 ///to add to the front, using this function you can speed up the building. |
|
658 |
|
659 void reserveFront(size_t r) {front.reserve(r);} |
|
660 |
|
661 ///Reserve storage for the builder in advance. |
|
662 |
|
663 ///If you know a reasonable upper bound of the number of the edges |
|
664 ///to add to the back, using this function you can speed up the building. |
|
665 |
|
666 void reserveBack(size_t r) {back.reserve(r);} |
|
667 |
|
668 private: |
|
669 bool empty() { |
|
670 return front.empty() && back.empty() && P.empty(); |
|
671 } |
|
672 |
|
673 GraphNode source() const { |
|
674 if( ! front.empty() ) |
|
675 return P.gr->source(front[front.size()-1]); |
|
676 else if( ! P.empty() ) |
|
677 return P.gr->source(P.edges[0]); |
|
678 else if( ! back.empty() ) |
|
679 return P.gr->source(back[0]); |
|
680 else |
|
681 return INVALID; |
|
682 } |
|
683 GraphNode target() const { |
|
684 if( ! back.empty() ) |
|
685 return P.gr->target(back[back.size()-1]); |
|
686 else if( ! P.empty() ) |
|
687 return P.gr->target(P.edges[P.length()-1]); |
|
688 else if( ! front.empty() ) |
|
689 return P.gr->target(front[0]); |
|
690 else |
|
691 return INVALID; |
|
692 } |
|
693 |
|
694 }; |
|
695 |
|
696 }; |
|
697 |
|
698 |
|
699 ///@} |
|
700 |
|
701 } // namespace lemon |
|
702 |
|
703 #endif // LEMON_PATH_H |
|