|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 ///\ingroup paths |
|
20 ///\file |
|
21 ///\brief Classes for representing paths in digraphs. |
|
22 /// |
|
23 |
|
24 #ifndef LEMON_PATH_H |
|
25 #define LEMON_PATH_H |
|
26 |
|
27 #include <vector> |
|
28 #include <algorithm> |
|
29 |
|
30 #include <lemon/path_utils.h> |
|
31 #include <lemon/error.h> |
|
32 #include <lemon/bits/invalid.h> |
|
33 |
|
34 namespace lemon { |
|
35 |
|
36 /// \addtogroup paths |
|
37 /// @{ |
|
38 |
|
39 |
|
40 /// \brief A structure for representing directed paths in a digraph. |
|
41 /// |
|
42 /// A structure for representing directed path in a digraph. |
|
43 /// \param Digraph The digraph type in which the path is. |
|
44 /// |
|
45 /// In a sense, the path can be treated as a list of arcs. The |
|
46 /// lemon path type stores just this list. As a consequence it |
|
47 /// cannot enumerate the nodes in the path and the zero length paths |
|
48 /// cannot store the source. |
|
49 /// |
|
50 /// This implementation is a back and front insertable and erasable |
|
51 /// path type. It can be indexed in O(1) time. The front and back |
|
52 /// insertion and erasure is amortized O(1) time. The |
|
53 /// impelementation is based on two opposite organized vectors. |
|
54 template <typename _Digraph> |
|
55 class Path { |
|
56 public: |
|
57 |
|
58 typedef _Digraph Digraph; |
|
59 typedef typename Digraph::Arc Arc; |
|
60 |
|
61 /// \brief Default constructor |
|
62 /// |
|
63 /// Default constructor |
|
64 Path() {} |
|
65 |
|
66 /// \brief Template copy constructor |
|
67 /// |
|
68 /// This path can be initialized with any other path type. It just |
|
69 /// makes a copy of the given path. |
|
70 template <typename CPath> |
|
71 Path(const CPath& cpath) { |
|
72 copyPath(*this, cpath); |
|
73 } |
|
74 |
|
75 /// \brief Template copy assignment |
|
76 /// |
|
77 /// This path can be initialized with any other path type. It just |
|
78 /// makes a copy of the given path. |
|
79 template <typename CPath> |
|
80 Path& operator=(const CPath& cpath) { |
|
81 copyPath(*this, cpath); |
|
82 return *this; |
|
83 } |
|
84 |
|
85 /// \brief Lemon style iterator for path arcs |
|
86 /// |
|
87 /// This class is used to iterate on the arcs of the paths. |
|
88 class ArcIt { |
|
89 friend class Path; |
|
90 public: |
|
91 /// \brief Default constructor |
|
92 ArcIt() {} |
|
93 /// \brief Invalid constructor |
|
94 ArcIt(Invalid) : path(0), idx(-1) {} |
|
95 /// \brief Initializate the constructor to the first arc of path |
|
96 ArcIt(const Path &_path) |
|
97 : path(&_path), idx(_path.empty() ? -1 : 0) {} |
|
98 |
|
99 private: |
|
100 |
|
101 ArcIt(const Path &_path, int _idx) |
|
102 : path(&_path), idx(_idx) {} |
|
103 |
|
104 public: |
|
105 |
|
106 /// \brief Conversion to Arc |
|
107 operator const Arc&() const { |
|
108 return path->nth(idx); |
|
109 } |
|
110 |
|
111 /// \brief Next arc |
|
112 ArcIt& operator++() { |
|
113 ++idx; |
|
114 if (idx >= path->length()) idx = -1; |
|
115 return *this; |
|
116 } |
|
117 |
|
118 /// \brief Comparison operator |
|
119 bool operator==(const ArcIt& e) const { return idx==e.idx; } |
|
120 /// \brief Comparison operator |
|
121 bool operator!=(const ArcIt& e) const { return idx!=e.idx; } |
|
122 /// \brief Comparison operator |
|
123 bool operator<(const ArcIt& e) const { return idx<e.idx; } |
|
124 |
|
125 private: |
|
126 const Path *path; |
|
127 int idx; |
|
128 }; |
|
129 |
|
130 /// \brief Length of the path. |
|
131 int length() const { return head.size() + tail.size(); } |
|
132 /// \brief Returns whether the path is empty. |
|
133 bool empty() const { return head.empty() && tail.empty(); } |
|
134 |
|
135 /// \brief Resets the path to an empty path. |
|
136 void clear() { head.clear(); tail.clear(); } |
|
137 |
|
138 /// \brief Gives back the nth arc. |
|
139 /// |
|
140 /// \pre n is in the [0..length() - 1] range |
|
141 const Arc& nth(int n) const { |
|
142 return n < int(head.size()) ? *(head.rbegin() + n) : |
|
143 *(tail.begin() + (n - head.size())); |
|
144 } |
|
145 |
|
146 /// \brief Initializes arc iterator to point to the nth arc |
|
147 /// |
|
148 /// \pre n is in the [0..length() - 1] range |
|
149 ArcIt nthIt(int n) const { |
|
150 return ArcIt(*this, n); |
|
151 } |
|
152 |
|
153 /// \brief Gives back the first arc of the path |
|
154 const Arc& front() const { |
|
155 return head.empty() ? tail.front() : head.back(); |
|
156 } |
|
157 |
|
158 /// \brief Add a new arc before the current path |
|
159 void addFront(const Arc& arc) { |
|
160 head.push_back(arc); |
|
161 } |
|
162 |
|
163 /// \brief Erase the first arc of the path |
|
164 void eraseFront() { |
|
165 if (!head.empty()) { |
|
166 head.pop_back(); |
|
167 } else { |
|
168 head.clear(); |
|
169 int halfsize = tail.size() / 2; |
|
170 head.resize(halfsize); |
|
171 std::copy(tail.begin() + 1, tail.begin() + halfsize + 1, |
|
172 head.rbegin()); |
|
173 std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin()); |
|
174 tail.resize(tail.size() - halfsize - 1); |
|
175 } |
|
176 } |
|
177 |
|
178 /// \brief Gives back the last arc of the path |
|
179 const Arc& back() const { |
|
180 return tail.empty() ? head.front() : tail.back(); |
|
181 } |
|
182 |
|
183 /// \brief Add a new arc behind the current path |
|
184 void addBack(const Arc& arc) { |
|
185 tail.push_back(arc); |
|
186 } |
|
187 |
|
188 /// \brief Erase the last arc of the path |
|
189 void eraseBack() { |
|
190 if (!tail.empty()) { |
|
191 tail.pop_back(); |
|
192 } else { |
|
193 int halfsize = head.size() / 2; |
|
194 tail.resize(halfsize); |
|
195 std::copy(head.begin() + 1, head.begin() + halfsize + 1, |
|
196 tail.rbegin()); |
|
197 std::copy(head.begin() + halfsize + 1, head.end(), head.begin()); |
|
198 head.resize(head.size() - halfsize - 1); |
|
199 } |
|
200 } |
|
201 |
|
202 |
|
203 |
|
204 typedef True BuildTag; |
|
205 |
|
206 template <typename CPath> |
|
207 void build(const CPath& path) { |
|
208 int len = path.length(); |
|
209 tail.reserve(len); |
|
210 for (typename CPath::ArcIt it(path); it != INVALID; ++it) { |
|
211 tail.push_back(it); |
|
212 } |
|
213 } |
|
214 |
|
215 template <typename CPath> |
|
216 void buildRev(const CPath& path) { |
|
217 int len = path.length(); |
|
218 head.reserve(len); |
|
219 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { |
|
220 head.push_back(it); |
|
221 } |
|
222 } |
|
223 |
|
224 protected: |
|
225 typedef std::vector<Arc> Container; |
|
226 Container head, tail; |
|
227 |
|
228 }; |
|
229 |
|
230 /// \brief A structure for representing directed paths in a digraph. |
|
231 /// |
|
232 /// A structure for representing directed path in a digraph. |
|
233 /// \param Digraph The digraph type in which the path is. |
|
234 /// |
|
235 /// In a sense, the path can be treated as a list of arcs. The |
|
236 /// lemon path type stores just this list. As a consequence it |
|
237 /// cannot enumerate the nodes in the path and the zero length paths |
|
238 /// cannot store the source. |
|
239 /// |
|
240 /// This implementation is a just back insertable and erasable path |
|
241 /// type. It can be indexed in O(1) time. The back insertion and |
|
242 /// erasure is amortized O(1) time. This implementation is faster |
|
243 /// then the \c Path type because it use just one vector for the |
|
244 /// arcs. |
|
245 template <typename _Digraph> |
|
246 class SimplePath { |
|
247 public: |
|
248 |
|
249 typedef _Digraph Digraph; |
|
250 typedef typename Digraph::Arc Arc; |
|
251 |
|
252 /// \brief Default constructor |
|
253 /// |
|
254 /// Default constructor |
|
255 SimplePath() {} |
|
256 |
|
257 /// \brief Template copy constructor |
|
258 /// |
|
259 /// This path can be initialized with any other path type. It just |
|
260 /// makes a copy of the given path. |
|
261 template <typename CPath> |
|
262 SimplePath(const CPath& cpath) { |
|
263 copyPath(*this, cpath); |
|
264 } |
|
265 |
|
266 /// \brief Template copy assignment |
|
267 /// |
|
268 /// This path can be initialized with any other path type. It just |
|
269 /// makes a copy of the given path. |
|
270 template <typename CPath> |
|
271 SimplePath& operator=(const CPath& cpath) { |
|
272 copyPath(*this, cpath); |
|
273 return *this; |
|
274 } |
|
275 |
|
276 /// \brief Iterator class to iterate on the arcs of the paths |
|
277 /// |
|
278 /// This class is used to iterate on the arcs of the paths |
|
279 /// |
|
280 /// Of course it converts to Digraph::Arc |
|
281 class ArcIt { |
|
282 friend class SimplePath; |
|
283 public: |
|
284 /// Default constructor |
|
285 ArcIt() {} |
|
286 /// Invalid constructor |
|
287 ArcIt(Invalid) : path(0), idx(-1) {} |
|
288 /// \brief Initializate the constructor to the first arc of path |
|
289 ArcIt(const SimplePath &_path) |
|
290 : path(&_path), idx(_path.empty() ? -1 : 0) {} |
|
291 |
|
292 private: |
|
293 |
|
294 /// Constructor with starting point |
|
295 ArcIt(const SimplePath &_path, int _idx) |
|
296 : idx(_idx), path(&_path) {} |
|
297 |
|
298 public: |
|
299 |
|
300 ///Conversion to Digraph::Arc |
|
301 operator const Arc&() const { |
|
302 return path->nth(idx); |
|
303 } |
|
304 |
|
305 /// Next arc |
|
306 ArcIt& operator++() { |
|
307 ++idx; |
|
308 if (idx >= path->length()) idx = -1; |
|
309 return *this; |
|
310 } |
|
311 |
|
312 /// Comparison operator |
|
313 bool operator==(const ArcIt& e) const { return idx==e.idx; } |
|
314 /// Comparison operator |
|
315 bool operator!=(const ArcIt& e) const { return idx!=e.idx; } |
|
316 /// Comparison operator |
|
317 bool operator<(const ArcIt& e) const { return idx<e.idx; } |
|
318 |
|
319 private: |
|
320 const SimplePath *path; |
|
321 int idx; |
|
322 }; |
|
323 |
|
324 /// \brief Length of the path. |
|
325 int length() const { return data.size(); } |
|
326 /// \brief Returns whether the path is empty. |
|
327 bool empty() const { return data.empty(); } |
|
328 |
|
329 /// \brief Resets the path to an empty path. |
|
330 void clear() { data.clear(); } |
|
331 |
|
332 /// \brief Gives back the nth arc. |
|
333 /// |
|
334 /// \pre n is in the [0..length() - 1] range |
|
335 const Arc& nth(int n) const { |
|
336 return data[n]; |
|
337 } |
|
338 |
|
339 /// \brief Initializes arc iterator to point to the nth arc. |
|
340 ArcIt nthIt(int n) const { |
|
341 return ArcIt(*this, n); |
|
342 } |
|
343 |
|
344 /// \brief Gives back the first arc of the path. |
|
345 const Arc& front() const { |
|
346 return data.front(); |
|
347 } |
|
348 |
|
349 /// \brief Gives back the last arc of the path. |
|
350 const Arc& back() const { |
|
351 return data.back(); |
|
352 } |
|
353 |
|
354 /// \brief Add a new arc behind the current path. |
|
355 void addBack(const Arc& arc) { |
|
356 data.push_back(arc); |
|
357 } |
|
358 |
|
359 /// \brief Erase the last arc of the path |
|
360 void eraseBack() { |
|
361 data.pop_back(); |
|
362 } |
|
363 |
|
364 typedef True BuildTag; |
|
365 |
|
366 template <typename CPath> |
|
367 void build(const CPath& path) { |
|
368 int len = path.length(); |
|
369 data.resize(len); |
|
370 int index = 0; |
|
371 for (typename CPath::ArcIt it(path); it != INVALID; ++it) { |
|
372 data[index] = it;; |
|
373 ++index; |
|
374 } |
|
375 } |
|
376 |
|
377 template <typename CPath> |
|
378 void buildRev(const CPath& path) { |
|
379 int len = path.length(); |
|
380 data.resize(len); |
|
381 int index = len; |
|
382 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { |
|
383 --index; |
|
384 data[index] = it;; |
|
385 } |
|
386 } |
|
387 |
|
388 protected: |
|
389 typedef std::vector<Arc> Container; |
|
390 Container data; |
|
391 |
|
392 }; |
|
393 |
|
394 /// \brief A structure for representing directed paths in a digraph. |
|
395 /// |
|
396 /// A structure for representing directed path in a digraph. |
|
397 /// \param Digraph The digraph type in which the path is. |
|
398 /// |
|
399 /// In a sense, the path can be treated as a list of arcs. The |
|
400 /// lemon path type stores just this list. As a consequence it |
|
401 /// cannot enumerate the nodes in the path and the zero length paths |
|
402 /// cannot store the source. |
|
403 /// |
|
404 /// This implementation is a back and front insertable and erasable |
|
405 /// path type. It can be indexed in O(k) time, where k is the rank |
|
406 /// of the arc in the path. The length can be computed in O(n) |
|
407 /// time. The front and back insertion and erasure is O(1) time |
|
408 /// and it can be splited and spliced in O(1) time. |
|
409 template <typename _Digraph> |
|
410 class ListPath { |
|
411 public: |
|
412 |
|
413 typedef _Digraph Digraph; |
|
414 typedef typename Digraph::Arc Arc; |
|
415 |
|
416 protected: |
|
417 |
|
418 // the std::list<> is incompatible |
|
419 // hard to create invalid iterator |
|
420 struct Node { |
|
421 Arc arc; |
|
422 Node *next, *prev; |
|
423 }; |
|
424 |
|
425 Node *first, *last; |
|
426 |
|
427 std::allocator<Node> alloc; |
|
428 |
|
429 public: |
|
430 |
|
431 /// \brief Default constructor |
|
432 /// |
|
433 /// Default constructor |
|
434 ListPath() : first(0), last(0) {} |
|
435 |
|
436 /// \brief Template copy constructor |
|
437 /// |
|
438 /// This path can be initialized with any other path type. It just |
|
439 /// makes a copy of the given path. |
|
440 template <typename CPath> |
|
441 ListPath(const CPath& cpath) : first(0), last(0) { |
|
442 copyPath(*this, cpath); |
|
443 } |
|
444 |
|
445 /// \brief Destructor of the path |
|
446 /// |
|
447 /// Destructor of the path |
|
448 ~ListPath() { |
|
449 clear(); |
|
450 } |
|
451 |
|
452 /// \brief Template copy assignment |
|
453 /// |
|
454 /// This path can be initialized with any other path type. It just |
|
455 /// makes a copy of the given path. |
|
456 template <typename CPath> |
|
457 ListPath& operator=(const CPath& cpath) { |
|
458 copyPath(*this, cpath); |
|
459 return *this; |
|
460 } |
|
461 |
|
462 /// \brief Iterator class to iterate on the arcs of the paths |
|
463 /// |
|
464 /// This class is used to iterate on the arcs of the paths |
|
465 /// |
|
466 /// Of course it converts to Digraph::Arc |
|
467 class ArcIt { |
|
468 friend class ListPath; |
|
469 public: |
|
470 /// Default constructor |
|
471 ArcIt() {} |
|
472 /// Invalid constructor |
|
473 ArcIt(Invalid) : path(0), node(0) {} |
|
474 /// \brief Initializate the constructor to the first arc of path |
|
475 ArcIt(const ListPath &_path) |
|
476 : path(&_path), node(_path.first) {} |
|
477 |
|
478 protected: |
|
479 |
|
480 ArcIt(const ListPath &_path, Node *_node) |
|
481 : path(&_path), node(_node) {} |
|
482 |
|
483 |
|
484 public: |
|
485 |
|
486 ///Conversion to Digraph::Arc |
|
487 operator const Arc&() const { |
|
488 return node->arc; |
|
489 } |
|
490 |
|
491 /// Next arc |
|
492 ArcIt& operator++() { |
|
493 node = node->next; |
|
494 return *this; |
|
495 } |
|
496 |
|
497 /// Comparison operator |
|
498 bool operator==(const ArcIt& e) const { return node==e.node; } |
|
499 /// Comparison operator |
|
500 bool operator!=(const ArcIt& e) const { return node!=e.node; } |
|
501 /// Comparison operator |
|
502 bool operator<(const ArcIt& e) const { return node<e.node; } |
|
503 |
|
504 private: |
|
505 const ListPath *path; |
|
506 Node *node; |
|
507 }; |
|
508 |
|
509 /// \brief Gives back the nth arc. |
|
510 /// |
|
511 /// Gives back the nth arc in O(n) time. |
|
512 /// \pre n is in the [0..length() - 1] range |
|
513 const Arc& nth(int n) const { |
|
514 Node *node = first; |
|
515 for (int i = 0; i < n; ++i) { |
|
516 node = node->next; |
|
517 } |
|
518 return node->arc; |
|
519 } |
|
520 |
|
521 /// \brief Initializes arc iterator to point to the nth arc. |
|
522 ArcIt nthIt(int n) const { |
|
523 Node *node = first; |
|
524 for (int i = 0; i < n; ++i) { |
|
525 node = node->next; |
|
526 } |
|
527 return ArcIt(*this, node); |
|
528 } |
|
529 |
|
530 /// \brief Length of the path. |
|
531 int length() const { |
|
532 int len = 0; |
|
533 Node *node = first; |
|
534 while (node != 0) { |
|
535 node = node->next; |
|
536 ++len; |
|
537 } |
|
538 return len; |
|
539 } |
|
540 |
|
541 /// \brief Returns whether the path is empty. |
|
542 bool empty() const { return first == 0; } |
|
543 |
|
544 /// \brief Resets the path to an empty path. |
|
545 void clear() { |
|
546 while (first != 0) { |
|
547 last = first->next; |
|
548 alloc.destroy(first); |
|
549 alloc.deallocate(first, 1); |
|
550 first = last; |
|
551 } |
|
552 } |
|
553 |
|
554 /// \brief Gives back the first arc of the path |
|
555 const Arc& front() const { |
|
556 return first->arc; |
|
557 } |
|
558 |
|
559 /// \brief Add a new arc before the current path |
|
560 void addFront(const Arc& arc) { |
|
561 Node *node = alloc.allocate(1); |
|
562 alloc.construct(node, Node()); |
|
563 node->prev = 0; |
|
564 node->next = first; |
|
565 node->arc = arc; |
|
566 if (first) { |
|
567 first->prev = node; |
|
568 first = node; |
|
569 } else { |
|
570 first = last = node; |
|
571 } |
|
572 } |
|
573 |
|
574 /// \brief Erase the first arc of the path |
|
575 void eraseFront() { |
|
576 Node *node = first; |
|
577 first = first->next; |
|
578 if (first) { |
|
579 first->prev = 0; |
|
580 } else { |
|
581 last = 0; |
|
582 } |
|
583 alloc.destroy(node); |
|
584 alloc.deallocate(node, 1); |
|
585 } |
|
586 |
|
587 /// \brief Gives back the last arc of the path. |
|
588 const Arc& back() const { |
|
589 return last->arc; |
|
590 } |
|
591 |
|
592 /// \brief Add a new arc behind the current path. |
|
593 void addBack(const Arc& arc) { |
|
594 Node *node = alloc.allocate(1); |
|
595 alloc.construct(node, Node()); |
|
596 node->next = 0; |
|
597 node->prev = last; |
|
598 node->arc = arc; |
|
599 if (last) { |
|
600 last->next = node; |
|
601 last = node; |
|
602 } else { |
|
603 last = first = node; |
|
604 } |
|
605 } |
|
606 |
|
607 /// \brief Erase the last arc of the path |
|
608 void eraseBack() { |
|
609 Node *node = last; |
|
610 last = last->prev; |
|
611 if (last) { |
|
612 last->next = 0; |
|
613 } else { |
|
614 first = 0; |
|
615 } |
|
616 alloc.destroy(node); |
|
617 alloc.deallocate(node, 1); |
|
618 } |
|
619 |
|
620 /// \brief Splicing the given path to the current path. |
|
621 /// |
|
622 /// It splices the \c tpath to the back of the current path and \c |
|
623 /// tpath becomes empty. The time complexity of this function is |
|
624 /// O(1). |
|
625 void spliceBack(ListPath& tpath) { |
|
626 if (first) { |
|
627 if (tpath.first) { |
|
628 last->next = tpath.first; |
|
629 tpath.first->prev = last; |
|
630 last = tpath.last; |
|
631 } |
|
632 } else { |
|
633 first = tpath.first; |
|
634 last = tpath.last; |
|
635 } |
|
636 tpath.first = tpath.last = 0; |
|
637 } |
|
638 |
|
639 /// \brief Splicing the given path to the current path. |
|
640 /// |
|
641 /// It splices the \c tpath before the current path and \c tpath |
|
642 /// becomes empty. The time complexity of this function |
|
643 /// is O(1). |
|
644 void spliceFront(ListPath& tpath) { |
|
645 if (first) { |
|
646 if (tpath.first) { |
|
647 first->prev = tpath.last; |
|
648 tpath.last->next = first; |
|
649 first = tpath.first; |
|
650 } |
|
651 } else { |
|
652 first = tpath.first; |
|
653 last = tpath.last; |
|
654 } |
|
655 tpath.first = tpath.last = 0; |
|
656 } |
|
657 |
|
658 /// \brief Splicing the given path into the current path. |
|
659 /// |
|
660 /// It splices the \c tpath into the current path before the |
|
661 /// position of \c it iterator and \c tpath becomes empty. The |
|
662 /// time complexity of this function is O(1). If the \c it is \c |
|
663 /// INVALID then it will splice behind the current path. |
|
664 void splice(ArcIt it, ListPath& tpath) { |
|
665 if (it.node) { |
|
666 if (tpath.first) { |
|
667 tpath.first->prev = it.node->prev; |
|
668 if (it.node->prev) { |
|
669 it.node->prev->next = tpath.first; |
|
670 } else { |
|
671 first = tpath.first; |
|
672 } |
|
673 it.node->prev = tpath.last; |
|
674 tpath.last->next = it.node; |
|
675 } |
|
676 } else { |
|
677 if (first) { |
|
678 if (tpath.first) { |
|
679 last->next = tpath.first; |
|
680 tpath.first->prev = last; |
|
681 last = tpath.last; |
|
682 } |
|
683 } else { |
|
684 first = tpath.first; |
|
685 last = tpath.last; |
|
686 } |
|
687 } |
|
688 tpath.first = tpath.last = 0; |
|
689 } |
|
690 |
|
691 /// \brief Spliting the current path. |
|
692 /// |
|
693 /// It splits the current path into two parts. The part before \c |
|
694 /// it iterator will remain in the current path and the part from |
|
695 /// the it will put into the \c tpath. If the \c tpath had arcs |
|
696 /// before the operation they will be removed first. The time |
|
697 /// complexity of this function is O(1) plus the clearing of \c |
|
698 /// tpath. If the \c it is \c INVALID then it just clears \c |
|
699 /// tpath. |
|
700 void split(ArcIt it, ListPath& tpath) { |
|
701 tpath.clear(); |
|
702 if (it.node) { |
|
703 tpath.first = it.node; |
|
704 tpath.last = last; |
|
705 if (it.node->prev) { |
|
706 last = it.node->prev; |
|
707 last->next = 0; |
|
708 } else { |
|
709 first = last = 0; |
|
710 } |
|
711 it.node->prev = 0; |
|
712 } |
|
713 } |
|
714 |
|
715 |
|
716 typedef True BuildTag; |
|
717 |
|
718 template <typename CPath> |
|
719 void build(const CPath& path) { |
|
720 for (typename CPath::ArcIt it(path); it != INVALID; ++it) { |
|
721 addBack(it); |
|
722 } |
|
723 } |
|
724 |
|
725 template <typename CPath> |
|
726 void buildRev(const CPath& path) { |
|
727 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { |
|
728 addFront(it); |
|
729 } |
|
730 } |
|
731 |
|
732 }; |
|
733 |
|
734 /// \brief A structure for representing directed paths in a digraph. |
|
735 /// |
|
736 /// A structure for representing directed path in a digraph. |
|
737 /// \param Digraph The digraph type in which the path is. |
|
738 /// |
|
739 /// In a sense, the path can be treated as a list of arcs. The |
|
740 /// lemon path type stores just this list. As a consequence it |
|
741 /// cannot enumerate the nodes in the path and the zero length paths |
|
742 /// cannot store the source. |
|
743 /// |
|
744 /// This implementation is completly static, so it cannot be |
|
745 /// modified exclude the assign an other path. It is intented to be |
|
746 /// used when you want to store a large number of paths because it is |
|
747 /// the most memory efficient path type in the lemon. |
|
748 template <typename _Digraph> |
|
749 class StaticPath { |
|
750 public: |
|
751 |
|
752 typedef _Digraph Digraph; |
|
753 typedef typename Digraph::Arc Arc; |
|
754 |
|
755 /// \brief Default constructor |
|
756 /// |
|
757 /// Default constructor |
|
758 StaticPath() : len(0), arcs(0) {} |
|
759 |
|
760 /// \brief Template copy constructor |
|
761 /// |
|
762 /// This path can be initialized with any other path type. It just |
|
763 /// makes a copy of the given path. |
|
764 template <typename CPath> |
|
765 StaticPath(const CPath& cpath) : arcs(0) { |
|
766 copyPath(*this, cpath); |
|
767 } |
|
768 |
|
769 /// \brief Destructor of the path |
|
770 /// |
|
771 /// Destructor of the path |
|
772 ~StaticPath() { |
|
773 if (arcs) delete[] arcs; |
|
774 } |
|
775 |
|
776 /// \brief Template copy assignment |
|
777 /// |
|
778 /// This path can be initialized with any other path type. It just |
|
779 /// makes a copy of the given path. |
|
780 template <typename CPath> |
|
781 StaticPath& operator=(const CPath& cpath) { |
|
782 copyPath(*this, cpath); |
|
783 return *this; |
|
784 } |
|
785 |
|
786 /// \brief Iterator class to iterate on the arcs of the paths |
|
787 /// |
|
788 /// This class is used to iterate on the arcs of the paths |
|
789 /// |
|
790 /// Of course it converts to Digraph::Arc |
|
791 class ArcIt { |
|
792 friend class StaticPath; |
|
793 public: |
|
794 /// Default constructor |
|
795 ArcIt() {} |
|
796 /// Invalid constructor |
|
797 ArcIt(Invalid) : path(0), idx(-1) {} |
|
798 /// Initializate the constructor to the first arc of path |
|
799 ArcIt(const StaticPath &_path) |
|
800 : path(&_path), idx(_path.empty() ? -1 : 0) {} |
|
801 |
|
802 private: |
|
803 |
|
804 /// Constructor with starting point |
|
805 ArcIt(const StaticPath &_path, int _idx) |
|
806 : idx(_idx), path(&_path) {} |
|
807 |
|
808 public: |
|
809 |
|
810 ///Conversion to Digraph::Arc |
|
811 operator const Arc&() const { |
|
812 return path->nth(idx); |
|
813 } |
|
814 |
|
815 /// Next arc |
|
816 ArcIt& operator++() { |
|
817 ++idx; |
|
818 if (idx >= path->length()) idx = -1; |
|
819 return *this; |
|
820 } |
|
821 |
|
822 /// Comparison operator |
|
823 bool operator==(const ArcIt& e) const { return idx==e.idx; } |
|
824 /// Comparison operator |
|
825 bool operator!=(const ArcIt& e) const { return idx!=e.idx; } |
|
826 /// Comparison operator |
|
827 bool operator<(const ArcIt& e) const { return idx<e.idx; } |
|
828 |
|
829 private: |
|
830 const StaticPath *path; |
|
831 int idx; |
|
832 }; |
|
833 |
|
834 /// \brief Gives back the nth arc. |
|
835 /// |
|
836 /// \pre n is in the [0..length() - 1] range |
|
837 const Arc& nth(int n) const { |
|
838 return arcs[n]; |
|
839 } |
|
840 |
|
841 /// \brief Initializes arc iterator to point to the nth arc. |
|
842 ArcIt nthIt(int n) const { |
|
843 return ArcIt(*this, n); |
|
844 } |
|
845 |
|
846 /// \brief Gives back the length of the path. |
|
847 int length() const { return len; } |
|
848 |
|
849 /// \brief Returns true when the path is empty. |
|
850 int empty() const { return len == 0; } |
|
851 |
|
852 /// \break Erase all arc in the digraph. |
|
853 void clear() { |
|
854 len = 0; |
|
855 if (arcs) delete[] arcs; |
|
856 arcs = 0; |
|
857 } |
|
858 |
|
859 /// \brief Gives back the first arc of the path. |
|
860 const Arc& front() const { |
|
861 return arcs[0]; |
|
862 } |
|
863 |
|
864 /// \brief Gives back the last arc of the path. |
|
865 const Arc& back() const { |
|
866 return arcs[len - 1]; |
|
867 } |
|
868 |
|
869 |
|
870 typedef True BuildTag; |
|
871 |
|
872 template <typename CPath> |
|
873 void build(const CPath& path) { |
|
874 len = path.length(); |
|
875 arcs = new Arc[len]; |
|
876 int index = 0; |
|
877 for (typename CPath::ArcIt it(path); it != INVALID; ++it) { |
|
878 arcs[index] = it; |
|
879 ++index; |
|
880 } |
|
881 } |
|
882 |
|
883 template <typename CPath> |
|
884 void buildRev(const CPath& path) { |
|
885 len = path.length(); |
|
886 arcs = new Arc[len]; |
|
887 int index = len; |
|
888 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { |
|
889 --index; |
|
890 arcs[index] = it; |
|
891 } |
|
892 } |
|
893 |
|
894 private: |
|
895 int len; |
|
896 Arc* arcs; |
|
897 }; |
|
898 |
|
899 ///@} |
|
900 |
|
901 } // namespace lemon |
|
902 |
|
903 #endif // LEMON_PATH_H |