14 * express or implied, and with no claim as to its suitability for any |
14 * express or implied, and with no claim as to its suitability for any |
15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
|
19 #ifndef LEMON_LIST_GRAPH_H |
|
20 #define LEMON_LIST_GRAPH_H |
|
21 |
|
22 ///\ingroup graphs |
|
23 ///\file |
|
24 ///\brief ListDigraph, ListGraph classes. |
|
25 |
|
26 #include <lemon/bits/graph_extender.h> |
|
27 |
|
28 #include <vector> |
|
29 #include <list> |
|
30 |
|
31 namespace lemon { |
|
32 |
|
33 class ListDigraphBase { |
|
34 |
|
35 protected: |
|
36 struct NodeT { |
|
37 int first_in, first_out; |
|
38 int prev, next; |
|
39 }; |
|
40 |
|
41 struct ArcT { |
|
42 int target, source; |
|
43 int prev_in, prev_out; |
|
44 int next_in, next_out; |
|
45 }; |
|
46 |
|
47 std::vector<NodeT> nodes; |
|
48 |
|
49 int first_node; |
|
50 |
|
51 int first_free_node; |
|
52 |
|
53 std::vector<ArcT> arcs; |
|
54 |
|
55 int first_free_arc; |
|
56 |
|
57 public: |
|
58 |
|
59 typedef ListDigraphBase Digraph; |
|
60 |
|
61 class Node { |
|
62 friend class ListDigraphBase; |
|
63 protected: |
|
64 |
|
65 int id; |
|
66 explicit Node(int pid) { id = pid;} |
|
67 |
|
68 public: |
|
69 Node() {} |
|
70 Node (Invalid) { id = -1; } |
|
71 bool operator==(const Node& node) const {return id == node.id;} |
|
72 bool operator!=(const Node& node) const {return id != node.id;} |
|
73 bool operator<(const Node& node) const {return id < node.id;} |
|
74 }; |
|
75 |
|
76 class Arc { |
|
77 friend class ListDigraphBase; |
|
78 protected: |
|
79 |
|
80 int id; |
|
81 explicit Arc(int pid) { id = pid;} |
|
82 |
|
83 public: |
|
84 Arc() {} |
|
85 Arc (Invalid) { id = -1; } |
|
86 bool operator==(const Arc& arc) const {return id == arc.id;} |
|
87 bool operator!=(const Arc& arc) const {return id != arc.id;} |
|
88 bool operator<(const Arc& arc) const {return id < arc.id;} |
|
89 }; |
|
90 |
|
91 |
|
92 |
|
93 ListDigraphBase() |
|
94 : nodes(), first_node(-1), |
|
95 first_free_node(-1), arcs(), first_free_arc(-1) {} |
|
96 |
|
97 |
|
98 int maxNodeId() const { return nodes.size()-1; } |
|
99 int maxArcId() const { return arcs.size()-1; } |
|
100 |
|
101 Node source(Arc e) const { return Node(arcs[e.id].source); } |
|
102 Node target(Arc e) const { return Node(arcs[e.id].target); } |
|
103 |
|
104 |
|
105 void first(Node& node) const { |
|
106 node.id = first_node; |
|
107 } |
|
108 |
|
109 void next(Node& node) const { |
|
110 node.id = nodes[node.id].next; |
|
111 } |
|
112 |
|
113 |
|
114 void first(Arc& e) const { |
|
115 int n; |
|
116 for(n = first_node; |
|
117 n!=-1 && nodes[n].first_in == -1; |
|
118 n = nodes[n].next); |
|
119 e.id = (n == -1) ? -1 : nodes[n].first_in; |
|
120 } |
|
121 |
|
122 void next(Arc& arc) const { |
|
123 if (arcs[arc.id].next_in != -1) { |
|
124 arc.id = arcs[arc.id].next_in; |
|
125 } else { |
|
126 int n; |
|
127 for(n = nodes[arcs[arc.id].target].next; |
|
128 n!=-1 && nodes[n].first_in == -1; |
|
129 n = nodes[n].next); |
|
130 arc.id = (n == -1) ? -1 : nodes[n].first_in; |
|
131 } |
|
132 } |
|
133 |
|
134 void firstOut(Arc &e, const Node& v) const { |
|
135 e.id = nodes[v.id].first_out; |
|
136 } |
|
137 void nextOut(Arc &e) const { |
|
138 e.id=arcs[e.id].next_out; |
|
139 } |
|
140 |
|
141 void firstIn(Arc &e, const Node& v) const { |
|
142 e.id = nodes[v.id].first_in; |
|
143 } |
|
144 void nextIn(Arc &e) const { |
|
145 e.id=arcs[e.id].next_in; |
|
146 } |
|
147 |
|
148 |
|
149 static int id(Node v) { return v.id; } |
|
150 static int id(Arc e) { return e.id; } |
|
151 |
|
152 static Node nodeFromId(int id) { return Node(id);} |
|
153 static Arc arcFromId(int id) { return Arc(id);} |
|
154 |
|
155 Node addNode() { |
|
156 int n; |
|
157 |
|
158 if(first_free_node==-1) { |
|
159 n = nodes.size(); |
|
160 nodes.push_back(NodeT()); |
|
161 } else { |
|
162 n = first_free_node; |
|
163 first_free_node = nodes[n].next; |
|
164 } |
|
165 |
|
166 nodes[n].next = first_node; |
|
167 if(first_node != -1) nodes[first_node].prev = n; |
|
168 first_node = n; |
|
169 nodes[n].prev = -1; |
|
170 |
|
171 nodes[n].first_in = nodes[n].first_out = -1; |
|
172 |
|
173 return Node(n); |
|
174 } |
|
175 |
|
176 Arc addArc(Node u, Node v) { |
|
177 int n; |
|
178 |
|
179 if (first_free_arc == -1) { |
|
180 n = arcs.size(); |
|
181 arcs.push_back(ArcT()); |
|
182 } else { |
|
183 n = first_free_arc; |
|
184 first_free_arc = arcs[n].next_in; |
|
185 } |
|
186 |
|
187 arcs[n].source = u.id; |
|
188 arcs[n].target = v.id; |
|
189 |
|
190 arcs[n].next_out = nodes[u.id].first_out; |
|
191 if(nodes[u.id].first_out != -1) { |
|
192 arcs[nodes[u.id].first_out].prev_out = n; |
|
193 } |
|
194 |
|
195 arcs[n].next_in = nodes[v.id].first_in; |
|
196 if(nodes[v.id].first_in != -1) { |
|
197 arcs[nodes[v.id].first_in].prev_in = n; |
|
198 } |
|
199 |
|
200 arcs[n].prev_in = arcs[n].prev_out = -1; |
|
201 |
|
202 nodes[u.id].first_out = nodes[v.id].first_in = n; |
|
203 |
|
204 return Arc(n); |
|
205 } |
|
206 |
|
207 void erase(const Node& node) { |
|
208 int n = node.id; |
|
209 |
|
210 if(nodes[n].next != -1) { |
|
211 nodes[nodes[n].next].prev = nodes[n].prev; |
|
212 } |
|
213 |
|
214 if(nodes[n].prev != -1) { |
|
215 nodes[nodes[n].prev].next = nodes[n].next; |
|
216 } else { |
|
217 first_node = nodes[n].next; |
|
218 } |
|
219 |
|
220 nodes[n].next = first_free_node; |
|
221 first_free_node = n; |
|
222 |
|
223 } |
|
224 |
|
225 void erase(const Arc& arc) { |
|
226 int n = arc.id; |
|
227 |
|
228 if(arcs[n].next_in!=-1) { |
|
229 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in; |
|
230 } |
|
231 |
|
232 if(arcs[n].prev_in!=-1) { |
|
233 arcs[arcs[n].prev_in].next_in = arcs[n].next_in; |
|
234 } else { |
|
235 nodes[arcs[n].target].first_in = arcs[n].next_in; |
|
236 } |
|
237 |
|
238 |
|
239 if(arcs[n].next_out!=-1) { |
|
240 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; |
|
241 } |
|
242 |
|
243 if(arcs[n].prev_out!=-1) { |
|
244 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; |
|
245 } else { |
|
246 nodes[arcs[n].source].first_out = arcs[n].next_out; |
|
247 } |
|
248 |
|
249 arcs[n].next_in = first_free_arc; |
|
250 first_free_arc = n; |
|
251 |
|
252 } |
|
253 |
|
254 void clear() { |
|
255 arcs.clear(); |
|
256 nodes.clear(); |
|
257 first_node = first_free_node = first_free_arc = -1; |
|
258 } |
|
259 |
|
260 protected: |
|
261 void changeTarget(Arc e, Node n) |
|
262 { |
|
263 if(arcs[e.id].next_in != -1) |
|
264 arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in; |
|
265 if(arcs[e.id].prev_in != -1) |
|
266 arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in; |
|
267 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in; |
|
268 if (nodes[n.id].first_in != -1) { |
|
269 arcs[nodes[n.id].first_in].prev_in = e.id; |
|
270 } |
|
271 arcs[e.id].target = n.id; |
|
272 arcs[e.id].prev_in = -1; |
|
273 arcs[e.id].next_in = nodes[n.id].first_in; |
|
274 nodes[n.id].first_in = e.id; |
|
275 } |
|
276 void changeSource(Arc e, Node n) |
|
277 { |
|
278 if(arcs[e.id].next_out != -1) |
|
279 arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out; |
|
280 if(arcs[e.id].prev_out != -1) |
|
281 arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out; |
|
282 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out; |
|
283 if (nodes[n.id].first_out != -1) { |
|
284 arcs[nodes[n.id].first_out].prev_out = e.id; |
|
285 } |
|
286 arcs[e.id].source = n.id; |
|
287 arcs[e.id].prev_out = -1; |
|
288 arcs[e.id].next_out = nodes[n.id].first_out; |
|
289 nodes[n.id].first_out = e.id; |
|
290 } |
|
291 |
|
292 }; |
|
293 |
|
294 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase; |
|
295 |
|
296 /// \addtogroup digraphs |
|
297 /// @{ |
|
298 |
|
299 ///A list digraph class. |
|
300 |
|
301 ///This is a simple and fast digraph implementation. |
|
302 /// |
|
303 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it |
|
304 ///also provides several additional useful extra functionalities. |
|
305 ///The most of the member functions and nested classes are |
|
306 ///documented only in the concept class. |
|
307 /// |
|
308 ///An important extra feature of this digraph implementation is that |
|
309 ///its maps are real \ref concepts::ReferenceMap "reference map"s. |
|
310 /// |
|
311 ///\sa concepts::Digraph. |
|
312 |
|
313 class ListDigraph : public ExtendedListDigraphBase { |
|
314 private: |
|
315 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. |
|
316 |
|
317 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. |
|
318 /// |
|
319 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; |
|
320 ///\brief Assignment of ListDigraph to another one is \e not allowed. |
|
321 ///Use DigraphCopy() instead. |
|
322 |
|
323 ///Assignment of ListDigraph to another one is \e not allowed. |
|
324 ///Use DigraphCopy() instead. |
|
325 void operator=(const ListDigraph &) {} |
|
326 public: |
|
327 |
|
328 typedef ExtendedListDigraphBase Parent; |
|
329 |
|
330 /// Constructor |
|
331 |
|
332 /// Constructor. |
|
333 /// |
|
334 ListDigraph() {} |
|
335 |
|
336 ///Add a new node to the digraph. |
|
337 |
|
338 /// \return the new node. |
|
339 /// |
|
340 Node addNode() { return Parent::addNode(); } |
|
341 |
|
342 ///Add a new arc to the digraph. |
|
343 |
|
344 ///Add a new arc to the digraph with source node \c s |
|
345 ///and target node \c t. |
|
346 ///\return the new arc. |
|
347 Arc addArc(const Node& s, const Node& t) { |
|
348 return Parent::addArc(s, t); |
|
349 } |
|
350 |
|
351 /// Changes the target of \c e to \c n |
|
352 |
|
353 /// Changes the target of \c e to \c n |
|
354 /// |
|
355 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing |
|
356 ///the changed arc remain valid. However <tt>InArcIt</tt>s are |
|
357 ///invalidated. |
|
358 ///\warning This functionality cannot be used together with the Snapshot |
|
359 ///feature. |
|
360 void changeTarget(Arc e, Node n) { |
|
361 Parent::changeTarget(e,n); |
|
362 } |
|
363 /// Changes the source of \c e to \c n |
|
364 |
|
365 /// Changes the source of \c e to \c n |
|
366 /// |
|
367 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing |
|
368 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are |
|
369 ///invalidated. |
|
370 ///\warning This functionality cannot be used together with the Snapshot |
|
371 ///feature. |
|
372 void changeSource(Arc e, Node n) { |
|
373 Parent::changeSource(e,n); |
|
374 } |
|
375 |
|
376 /// Invert the direction of an arc. |
|
377 |
|
378 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain |
|
379 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are |
|
380 ///invalidated. |
|
381 ///\warning This functionality cannot be used together with the Snapshot |
|
382 ///feature. |
|
383 void reverseArc(Arc e) { |
|
384 Node t=target(e); |
|
385 changeTarget(e,source(e)); |
|
386 changeSource(e,t); |
|
387 } |
|
388 |
|
389 /// Using this it is possible to avoid the superfluous memory |
|
390 /// allocation: if you know that the digraph you want to build will |
|
391 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
|
392 /// then it is worth reserving space for this amount before starting |
|
393 /// to build the digraph. |
|
394 /// \sa reserveArc |
|
395 void reserveNode(int n) { nodes.reserve(n); }; |
|
396 |
|
397 /// \brief Using this it is possible to avoid the superfluous memory |
|
398 /// allocation. |
|
399 |
|
400 /// Using this it is possible to avoid the superfluous memory |
|
401 /// allocation: if you know that the digraph you want to build will |
|
402 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
|
403 /// then it is worth reserving space for this amount before starting |
|
404 /// to build the digraph. |
|
405 /// \sa reserveNode |
|
406 void reserveArc(int m) { arcs.reserve(m); }; |
|
407 |
|
408 ///Contract two nodes. |
|
409 |
|
410 ///This function contracts two nodes. |
|
411 /// |
|
412 ///Node \p b will be removed but instead of deleting |
|
413 ///incident arcs, they will be joined to \p a. |
|
414 ///The last parameter \p r controls whether to remove loops. \c true |
|
415 ///means that loops will be removed. |
|
416 /// |
|
417 ///\note The <tt>ArcIt</tt>s |
|
418 ///referencing a moved arc remain |
|
419 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s |
|
420 ///may be invalidated. |
|
421 ///\warning This functionality cannot be used together with the Snapshot |
|
422 ///feature. |
|
423 void contract(Node a, Node b, bool r = true) |
|
424 { |
|
425 for(OutArcIt e(*this,b);e!=INVALID;) { |
|
426 OutArcIt f=e; |
|
427 ++f; |
|
428 if(r && target(e)==a) erase(e); |
|
429 else changeSource(e,a); |
|
430 e=f; |
|
431 } |
|
432 for(InArcIt e(*this,b);e!=INVALID;) { |
|
433 InArcIt f=e; |
|
434 ++f; |
|
435 if(r && source(e)==a) erase(e); |
|
436 else changeTarget(e,a); |
|
437 e=f; |
|
438 } |
|
439 erase(b); |
|
440 } |
|
441 |
|
442 ///Split a node. |
|
443 |
|
444 ///This function splits a node. First a new node is added to the digraph, |
|
445 ///then the source of each outgoing arc of \c n is moved to this new node. |
|
446 ///If \c connect is \c true (this is the default value), then a new arc |
|
447 ///from \c n to the newly created node is also added. |
|
448 ///\return The newly created node. |
|
449 /// |
|
450 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain |
|
451 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may |
|
452 ///be invalidated. |
|
453 /// |
|
454 ///\warning This functionality cannot be used together with the |
|
455 ///Snapshot feature. \todo It could be implemented in a bit |
|
456 ///faster way. |
|
457 Node split(Node n, bool connect = true) { |
|
458 Node b = addNode(); |
|
459 for(OutArcIt e(*this,n);e!=INVALID;) { |
|
460 OutArcIt f=e; |
|
461 ++f; |
|
462 changeSource(e,b); |
|
463 e=f; |
|
464 } |
|
465 if (connect) addArc(n,b); |
|
466 return b; |
|
467 } |
|
468 |
|
469 ///Split an arc. |
|
470 |
|
471 ///This function splits an arc. First a new node \c b is added to |
|
472 ///the digraph, then the original arc is re-targeted to \c |
|
473 ///b. Finally an arc from \c b to the original target is added. |
|
474 ///\return The newly created node. |
|
475 ///\warning This functionality |
|
476 ///cannot be used together with the Snapshot feature. |
|
477 Node split(Arc e) { |
|
478 Node b = addNode(); |
|
479 addArc(b,target(e)); |
|
480 changeTarget(e,b); |
|
481 return b; |
|
482 } |
|
483 |
|
484 /// \brief Class to make a snapshot of the digraph and restore |
|
485 /// to it later. |
|
486 /// |
|
487 /// Class to make a snapshot of the digraph and to restore it |
|
488 /// later. |
|
489 /// |
|
490 /// The newly added nodes and arcs can be removed using the |
|
491 /// restore() function. |
|
492 /// |
|
493 /// \warning Arc and node deletions cannot be restored. This |
|
494 /// events invalidate the snapshot. |
|
495 class Snapshot { |
|
496 protected: |
|
497 |
|
498 typedef Parent::NodeNotifier NodeNotifier; |
|
499 |
|
500 class NodeObserverProxy : public NodeNotifier::ObserverBase { |
|
501 public: |
|
502 |
|
503 NodeObserverProxy(Snapshot& _snapshot) |
|
504 : snapshot(_snapshot) {} |
|
505 |
|
506 using NodeNotifier::ObserverBase::attach; |
|
507 using NodeNotifier::ObserverBase::detach; |
|
508 using NodeNotifier::ObserverBase::attached; |
|
509 |
|
510 protected: |
|
511 |
|
512 virtual void add(const Node& node) { |
|
513 snapshot.addNode(node); |
|
514 } |
|
515 virtual void add(const std::vector<Node>& nodes) { |
|
516 for (int i = nodes.size() - 1; i >= 0; ++i) { |
|
517 snapshot.addNode(nodes[i]); |
|
518 } |
|
519 } |
|
520 virtual void erase(const Node& node) { |
|
521 snapshot.eraseNode(node); |
|
522 } |
|
523 virtual void erase(const std::vector<Node>& nodes) { |
|
524 for (int i = 0; i < int(nodes.size()); ++i) { |
|
525 snapshot.eraseNode(nodes[i]); |
|
526 } |
|
527 } |
|
528 virtual void build() { |
|
529 Node node; |
|
530 std::vector<Node> nodes; |
|
531 for (notifier()->first(node); node != INVALID; |
|
532 notifier()->next(node)) { |
|
533 nodes.push_back(node); |
|
534 } |
|
535 for (int i = nodes.size() - 1; i >= 0; --i) { |
|
536 snapshot.addNode(nodes[i]); |
|
537 } |
|
538 } |
|
539 virtual void clear() { |
|
540 Node node; |
|
541 for (notifier()->first(node); node != INVALID; |
|
542 notifier()->next(node)) { |
|
543 snapshot.eraseNode(node); |
|
544 } |
|
545 } |
|
546 |
|
547 Snapshot& snapshot; |
|
548 }; |
|
549 |
|
550 class ArcObserverProxy : public ArcNotifier::ObserverBase { |
|
551 public: |
|
552 |
|
553 ArcObserverProxy(Snapshot& _snapshot) |
|
554 : snapshot(_snapshot) {} |
|
555 |
|
556 using ArcNotifier::ObserverBase::attach; |
|
557 using ArcNotifier::ObserverBase::detach; |
|
558 using ArcNotifier::ObserverBase::attached; |
|
559 |
|
560 protected: |
|
561 |
|
562 virtual void add(const Arc& arc) { |
|
563 snapshot.addArc(arc); |
|
564 } |
|
565 virtual void add(const std::vector<Arc>& arcs) { |
|
566 for (int i = arcs.size() - 1; i >= 0; ++i) { |
|
567 snapshot.addArc(arcs[i]); |
|
568 } |
|
569 } |
|
570 virtual void erase(const Arc& arc) { |
|
571 snapshot.eraseArc(arc); |
|
572 } |
|
573 virtual void erase(const std::vector<Arc>& arcs) { |
|
574 for (int i = 0; i < int(arcs.size()); ++i) { |
|
575 snapshot.eraseArc(arcs[i]); |
|
576 } |
|
577 } |
|
578 virtual void build() { |
|
579 Arc arc; |
|
580 std::vector<Arc> arcs; |
|
581 for (notifier()->first(arc); arc != INVALID; |
|
582 notifier()->next(arc)) { |
|
583 arcs.push_back(arc); |
|
584 } |
|
585 for (int i = arcs.size() - 1; i >= 0; --i) { |
|
586 snapshot.addArc(arcs[i]); |
|
587 } |
|
588 } |
|
589 virtual void clear() { |
|
590 Arc arc; |
|
591 for (notifier()->first(arc); arc != INVALID; |
|
592 notifier()->next(arc)) { |
|
593 snapshot.eraseArc(arc); |
|
594 } |
|
595 } |
|
596 |
|
597 Snapshot& snapshot; |
|
598 }; |
|
599 |
|
600 ListDigraph *digraph; |
|
601 |
|
602 NodeObserverProxy node_observer_proxy; |
|
603 ArcObserverProxy arc_observer_proxy; |
|
604 |
|
605 std::list<Node> added_nodes; |
|
606 std::list<Arc> added_arcs; |
|
607 |
|
608 |
|
609 void addNode(const Node& node) { |
|
610 added_nodes.push_front(node); |
|
611 } |
|
612 void eraseNode(const Node& node) { |
|
613 std::list<Node>::iterator it = |
|
614 std::find(added_nodes.begin(), added_nodes.end(), node); |
|
615 if (it == added_nodes.end()) { |
|
616 clear(); |
|
617 arc_observer_proxy.detach(); |
|
618 throw NodeNotifier::ImmediateDetach(); |
|
619 } else { |
|
620 added_nodes.erase(it); |
|
621 } |
|
622 } |
|
623 |
|
624 void addArc(const Arc& arc) { |
|
625 added_arcs.push_front(arc); |
|
626 } |
|
627 void eraseArc(const Arc& arc) { |
|
628 std::list<Arc>::iterator it = |
|
629 std::find(added_arcs.begin(), added_arcs.end(), arc); |
|
630 if (it == added_arcs.end()) { |
|
631 clear(); |
|
632 node_observer_proxy.detach(); |
|
633 throw ArcNotifier::ImmediateDetach(); |
|
634 } else { |
|
635 added_arcs.erase(it); |
|
636 } |
|
637 } |
|
638 |
|
639 void attach(ListDigraph &_digraph) { |
|
640 digraph = &_digraph; |
|
641 node_observer_proxy.attach(digraph->notifier(Node())); |
|
642 arc_observer_proxy.attach(digraph->notifier(Arc())); |
|
643 } |
|
644 |
|
645 void detach() { |
|
646 node_observer_proxy.detach(); |
|
647 arc_observer_proxy.detach(); |
|
648 } |
|
649 |
|
650 bool attached() const { |
|
651 return node_observer_proxy.attached(); |
|
652 } |
|
653 |
|
654 void clear() { |
|
655 added_nodes.clear(); |
|
656 added_arcs.clear(); |
|
657 } |
|
658 |
|
659 public: |
|
660 |
|
661 /// \brief Default constructor. |
|
662 /// |
|
663 /// Default constructor. |
|
664 /// To actually make a snapshot you must call save(). |
|
665 Snapshot() |
|
666 : digraph(0), node_observer_proxy(*this), |
|
667 arc_observer_proxy(*this) {} |
|
668 |
|
669 /// \brief Constructor that immediately makes a snapshot. |
|
670 /// |
|
671 /// This constructor immediately makes a snapshot of the digraph. |
|
672 /// \param _digraph The digraph we make a snapshot of. |
|
673 Snapshot(ListDigraph &_digraph) |
|
674 : node_observer_proxy(*this), |
|
675 arc_observer_proxy(*this) { |
|
676 attach(_digraph); |
|
677 } |
|
678 |
|
679 /// \brief Make a snapshot. |
|
680 /// |
|
681 /// Make a snapshot of the digraph. |
|
682 /// |
|
683 /// This function can be called more than once. In case of a repeated |
|
684 /// call, the previous snapshot gets lost. |
|
685 /// \param _digraph The digraph we make the snapshot of. |
|
686 void save(ListDigraph &_digraph) { |
|
687 if (attached()) { |
|
688 detach(); |
|
689 clear(); |
|
690 } |
|
691 attach(_digraph); |
|
692 } |
|
693 |
|
694 /// \brief Undo the changes until the last snapshot. |
|
695 // |
|
696 /// Undo the changes until the last snapshot created by save(). |
|
697 void restore() { |
|
698 detach(); |
|
699 for(std::list<Arc>::iterator it = added_arcs.begin(); |
|
700 it != added_arcs.end(); ++it) { |
|
701 digraph->erase(*it); |
|
702 } |
|
703 for(std::list<Node>::iterator it = added_nodes.begin(); |
|
704 it != added_nodes.end(); ++it) { |
|
705 digraph->erase(*it); |
|
706 } |
|
707 clear(); |
|
708 } |
|
709 |
|
710 /// \brief Gives back true when the snapshot is valid. |
|
711 /// |
|
712 /// Gives back true when the snapshot is valid. |
|
713 bool valid() const { |
|
714 return attached(); |
|
715 } |
|
716 }; |
|
717 |
|
718 }; |
|
719 |
|
720 ///@} |
|
721 |
|
722 class ListGraphBase { |
|
723 |
|
724 protected: |
|
725 |
|
726 struct NodeT { |
|
727 int first_out; |
|
728 int prev, next; |
|
729 }; |
|
730 |
|
731 struct ArcT { |
|
732 int target; |
|
733 int prev_out, next_out; |
|
734 }; |
|
735 |
|
736 std::vector<NodeT> nodes; |
|
737 |
|
738 int first_node; |
|
739 |
|
740 int first_free_node; |
|
741 |
|
742 std::vector<ArcT> arcs; |
|
743 |
|
744 int first_free_arc; |
|
745 |
|
746 public: |
|
747 |
|
748 typedef ListGraphBase Digraph; |
|
749 |
|
750 class Node; |
|
751 class Arc; |
|
752 class Edge; |
|
753 |
|
754 class Node { |
|
755 friend class ListGraphBase; |
|
756 protected: |
|
757 |
|
758 int id; |
|
759 explicit Node(int pid) { id = pid;} |
|
760 |
|
761 public: |
|
762 Node() {} |
|
763 Node (Invalid) { id = -1; } |
|
764 bool operator==(const Node& node) const {return id == node.id;} |
|
765 bool operator!=(const Node& node) const {return id != node.id;} |
|
766 bool operator<(const Node& node) const {return id < node.id;} |
|
767 }; |
|
768 |
|
769 class Edge { |
|
770 friend class ListGraphBase; |
|
771 protected: |
|
772 |
|
773 int id; |
|
774 explicit Edge(int pid) { id = pid;} |
|
775 |
|
776 public: |
|
777 Edge() {} |
|
778 Edge (Invalid) { id = -1; } |
|
779 bool operator==(const Edge& arc) const {return id == arc.id;} |
|
780 bool operator!=(const Edge& arc) const {return id != arc.id;} |
|
781 bool operator<(const Edge& arc) const {return id < arc.id;} |
|
782 }; |
|
783 |
|
784 class Arc { |
|
785 friend class ListGraphBase; |
|
786 protected: |
|
787 |
|
788 int id; |
|
789 explicit Arc(int pid) { id = pid;} |
|
790 |
|
791 public: |
|
792 operator Edge() const { return edgeFromId(id / 2); } |
|
793 |
|
794 Arc() {} |
|
795 Arc (Invalid) { id = -1; } |
|
796 bool operator==(const Arc& arc) const {return id == arc.id;} |
|
797 bool operator!=(const Arc& arc) const {return id != arc.id;} |
|
798 bool operator<(const Arc& arc) const {return id < arc.id;} |
|
799 }; |
|
800 |
|
801 |
|
802 |
|
803 ListGraphBase() |
|
804 : nodes(), first_node(-1), |
|
805 first_free_node(-1), arcs(), first_free_arc(-1) {} |
|
806 |
|
807 |
|
808 int maxNodeId() const { return nodes.size()-1; } |
|
809 int maxEdgeId() const { return arcs.size() / 2 - 1; } |
|
810 int maxArcId() const { return arcs.size()-1; } |
|
811 |
|
812 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } |
|
813 Node target(Arc e) const { return Node(arcs[e.id].target); } |
|
814 |
|
815 Node u(Edge e) const { return Node(arcs[2 * e.id].target); } |
|
816 Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); } |
|
817 |
|
818 static bool direction(Arc e) { |
|
819 return (e.id & 1) == 1; |
|
820 } |
|
821 |
|
822 static Arc direct(Edge e, bool d) { |
|
823 return Arc(e.id * 2 + (d ? 1 : 0)); |
|
824 } |
|
825 |
|
826 void first(Node& node) const { |
|
827 node.id = first_node; |
|
828 } |
|
829 |
|
830 void next(Node& node) const { |
|
831 node.id = nodes[node.id].next; |
|
832 } |
|
833 |
|
834 void first(Arc& e) const { |
|
835 int n = first_node; |
|
836 while (n != -1 && nodes[n].first_out == -1) { |
|
837 n = nodes[n].next; |
|
838 } |
|
839 e.id = (n == -1) ? -1 : nodes[n].first_out; |
|
840 } |
|
841 |
|
842 void next(Arc& e) const { |
|
843 if (arcs[e.id].next_out != -1) { |
|
844 e.id = arcs[e.id].next_out; |
|
845 } else { |
|
846 int n = nodes[arcs[e.id ^ 1].target].next; |
|
847 while(n != -1 && nodes[n].first_out == -1) { |
|
848 n = nodes[n].next; |
|
849 } |
|
850 e.id = (n == -1) ? -1 : nodes[n].first_out; |
|
851 } |
|
852 } |
|
853 |
|
854 void first(Edge& e) const { |
|
855 int n = first_node; |
|
856 while (n != -1) { |
|
857 e.id = nodes[n].first_out; |
|
858 while ((e.id & 1) != 1) { |
|
859 e.id = arcs[e.id].next_out; |
|
860 } |
|
861 if (e.id != -1) { |
|
862 e.id /= 2; |
|
863 return; |
|
864 } |
|
865 n = nodes[n].next; |
|
866 } |
|
867 e.id = -1; |
|
868 } |
|
869 |
|
870 void next(Edge& e) const { |
|
871 int n = arcs[e.id * 2].target; |
|
872 e.id = arcs[(e.id * 2) | 1].next_out; |
|
873 while ((e.id & 1) != 1) { |
|
874 e.id = arcs[e.id].next_out; |
|
875 } |
|
876 if (e.id != -1) { |
|
877 e.id /= 2; |
|
878 return; |
|
879 } |
|
880 n = nodes[n].next; |
|
881 while (n != -1) { |
|
882 e.id = nodes[n].first_out; |
|
883 while ((e.id & 1) != 1) { |
|
884 e.id = arcs[e.id].next_out; |
|
885 } |
|
886 if (e.id != -1) { |
|
887 e.id /= 2; |
|
888 return; |
|
889 } |
|
890 n = nodes[n].next; |
|
891 } |
|
892 e.id = -1; |
|
893 } |
|
894 |
|
895 void firstOut(Arc &e, const Node& v) const { |
|
896 e.id = nodes[v.id].first_out; |
|
897 } |
|
898 void nextOut(Arc &e) const { |
|
899 e.id = arcs[e.id].next_out; |
|
900 } |
|
901 |
|
902 void firstIn(Arc &e, const Node& v) const { |
|
903 e.id = ((nodes[v.id].first_out) ^ 1); |
|
904 if (e.id == -2) e.id = -1; |
|
905 } |
|
906 void nextIn(Arc &e) const { |
|
907 e.id = ((arcs[e.id ^ 1].next_out) ^ 1); |
|
908 if (e.id == -2) e.id = -1; |
|
909 } |
|
910 |
|
911 void firstInc(Edge &e, bool& d, const Node& v) const { |
|
912 int de = nodes[v.id].first_out; |
|
913 if (de != -1 ) { |
|
914 e.id = de / 2; |
|
915 d = ((de & 1) == 1); |
|
916 } else { |
|
917 e.id = -1; |
|
918 d = true; |
|
919 } |
|
920 } |
|
921 void nextInc(Edge &e, bool& d) const { |
|
922 int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); |
|
923 if (de != -1 ) { |
|
924 e.id = de / 2; |
|
925 d = ((de & 1) == 1); |
|
926 } else { |
|
927 e.id = -1; |
|
928 d = true; |
|
929 } |
|
930 } |
|
931 |
|
932 static int id(Node v) { return v.id; } |
|
933 static int id(Arc e) { return e.id; } |
|
934 static int id(Edge e) { return e.id; } |
|
935 |
|
936 static Node nodeFromId(int id) { return Node(id);} |
|
937 static Arc arcFromId(int id) { return Arc(id);} |
|
938 static Edge edgeFromId(int id) { return Edge(id);} |
|
939 |
|
940 Node addNode() { |
|
941 int n; |
|
942 |
|
943 if(first_free_node==-1) { |
|
944 n = nodes.size(); |
|
945 nodes.push_back(NodeT()); |
|
946 } else { |
|
947 n = first_free_node; |
|
948 first_free_node = nodes[n].next; |
|
949 } |
|
950 |
|
951 nodes[n].next = first_node; |
|
952 if (first_node != -1) nodes[first_node].prev = n; |
|
953 first_node = n; |
|
954 nodes[n].prev = -1; |
|
955 |
|
956 nodes[n].first_out = -1; |
|
957 |
|
958 return Node(n); |
|
959 } |
|
960 |
|
961 Edge addEdge(Node u, Node v) { |
|
962 int n; |
|
963 |
|
964 if (first_free_arc == -1) { |
|
965 n = arcs.size(); |
|
966 arcs.push_back(ArcT()); |
|
967 arcs.push_back(ArcT()); |
|
968 } else { |
|
969 n = first_free_arc; |
|
970 first_free_arc = arcs[n].next_out; |
|
971 } |
|
972 |
|
973 arcs[n].target = u.id; |
|
974 arcs[n | 1].target = v.id; |
|
975 |
|
976 arcs[n].next_out = nodes[v.id].first_out; |
|
977 if (nodes[v.id].first_out != -1) { |
|
978 arcs[nodes[v.id].first_out].prev_out = n; |
|
979 } |
|
980 arcs[n].prev_out = -1; |
|
981 nodes[v.id].first_out = n; |
|
982 |
|
983 arcs[n | 1].next_out = nodes[u.id].first_out; |
|
984 if (nodes[u.id].first_out != -1) { |
|
985 arcs[nodes[u.id].first_out].prev_out = (n | 1); |
|
986 } |
|
987 arcs[n | 1].prev_out = -1; |
|
988 nodes[u.id].first_out = (n | 1); |
|
989 |
|
990 return Edge(n / 2); |
|
991 } |
|
992 |
|
993 void erase(const Node& node) { |
|
994 int n = node.id; |
|
995 |
|
996 if(nodes[n].next != -1) { |
|
997 nodes[nodes[n].next].prev = nodes[n].prev; |
|
998 } |
|
999 |
|
1000 if(nodes[n].prev != -1) { |
|
1001 nodes[nodes[n].prev].next = nodes[n].next; |
|
1002 } else { |
|
1003 first_node = nodes[n].next; |
|
1004 } |
|
1005 |
|
1006 nodes[n].next = first_free_node; |
|
1007 first_free_node = n; |
|
1008 |
|
1009 } |
|
1010 |
|
1011 void erase(const Edge& arc) { |
|
1012 int n = arc.id * 2; |
|
1013 |
|
1014 if (arcs[n].next_out != -1) { |
|
1015 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; |
|
1016 } |
|
1017 |
|
1018 if (arcs[n].prev_out != -1) { |
|
1019 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; |
|
1020 } else { |
|
1021 nodes[arcs[n | 1].target].first_out = arcs[n].next_out; |
|
1022 } |
|
1023 |
|
1024 if (arcs[n | 1].next_out != -1) { |
|
1025 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; |
|
1026 } |
|
1027 |
|
1028 if (arcs[n | 1].prev_out != -1) { |
|
1029 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; |
|
1030 } else { |
|
1031 nodes[arcs[n].target].first_out = arcs[n | 1].next_out; |
|
1032 } |
|
1033 |
|
1034 arcs[n].next_out = first_free_arc; |
|
1035 first_free_arc = n; |
|
1036 |
|
1037 } |
|
1038 |
|
1039 void clear() { |
|
1040 arcs.clear(); |
|
1041 nodes.clear(); |
|
1042 first_node = first_free_node = first_free_arc = -1; |
|
1043 } |
|
1044 |
|
1045 protected: |
|
1046 |
|
1047 void changeTarget(Edge e, Node n) { |
|
1048 if(arcs[2 * e.id].next_out != -1) { |
|
1049 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; |
|
1050 } |
|
1051 if(arcs[2 * e.id].prev_out != -1) { |
|
1052 arcs[arcs[2 * e.id].prev_out].next_out = |
|
1053 arcs[2 * e.id].next_out; |
|
1054 } else { |
|
1055 nodes[arcs[(2 * e.id) | 1].target].first_out = |
|
1056 arcs[2 * e.id].next_out; |
|
1057 } |
|
1058 |
|
1059 if (nodes[n.id].first_out != -1) { |
|
1060 arcs[nodes[n.id].first_out].prev_out = 2 * e.id; |
|
1061 } |
|
1062 arcs[(2 * e.id) | 1].target = n.id; |
|
1063 arcs[2 * e.id].prev_out = -1; |
|
1064 arcs[2 * e.id].next_out = nodes[n.id].first_out; |
|
1065 nodes[n.id].first_out = 2 * e.id; |
|
1066 } |
|
1067 |
|
1068 void changeSource(Edge e, Node n) { |
|
1069 if(arcs[(2 * e.id) | 1].next_out != -1) { |
|
1070 arcs[arcs[(2 * e.id) | 1].next_out].prev_out = |
|
1071 arcs[(2 * e.id) | 1].prev_out; |
|
1072 } |
|
1073 if(arcs[(2 * e.id) | 1].prev_out != -1) { |
|
1074 arcs[arcs[(2 * e.id) | 1].prev_out].next_out = |
|
1075 arcs[(2 * e.id) | 1].next_out; |
|
1076 } else { |
|
1077 nodes[arcs[2 * e.id].target].first_out = |
|
1078 arcs[(2 * e.id) | 1].next_out; |
|
1079 } |
|
1080 |
|
1081 if (nodes[n.id].first_out != -1) { |
|
1082 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); |
|
1083 } |
|
1084 arcs[2 * e.id].target = n.id; |
|
1085 arcs[(2 * e.id) | 1].prev_out = -1; |
|
1086 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; |
|
1087 nodes[n.id].first_out = ((2 * e.id) | 1); |
|
1088 } |
|
1089 |
|
1090 }; |
|
1091 |
|
1092 // typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > |
|
1093 // ExtendedListGraphBase; |
|
1094 |
|
1095 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; |
|
1096 |
|
1097 |
|
1098 |
|
1099 /// \addtogroup digraphs |
|
1100 /// @{ |
|
1101 |
|
1102 ///An undirected list digraph class. |
|
1103 |
|
1104 ///This is a simple and fast undirected digraph implementation. |
|
1105 /// |
|
1106 ///An important extra feature of this digraph implementation is that |
|
1107 ///its maps are real \ref concepts::ReferenceMap "reference map"s. |
|
1108 /// |
|
1109 ///It conforms to the |
|
1110 ///\ref concepts::Graph "Graph concept". |
|
1111 /// |
|
1112 ///\sa concepts::Graph. |
|
1113 /// |
|
1114 class ListGraph : public ExtendedListGraphBase { |
|
1115 private: |
|
1116 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. |
|
1117 |
|
1118 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. |
|
1119 /// |
|
1120 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; |
|
1121 ///\brief Assignment of ListGraph to another one is \e not allowed. |
|
1122 ///Use GraphCopy() instead. |
|
1123 |
|
1124 ///Assignment of ListGraph to another one is \e not allowed. |
|
1125 ///Use GraphCopy() instead. |
|
1126 void operator=(const ListGraph &) {} |
|
1127 public: |
|
1128 /// Constructor |
|
1129 |
|
1130 /// Constructor. |
|
1131 /// |
|
1132 ListGraph() {} |
|
1133 |
|
1134 typedef ExtendedListGraphBase Parent; |
|
1135 |
|
1136 typedef Parent::OutArcIt IncArcIt; |
|
1137 |
|
1138 /// \brief Add a new node to the digraph. |
|
1139 /// |
|
1140 /// \return the new node. |
|
1141 /// |
|
1142 Node addNode() { return Parent::addNode(); } |
|
1143 |
|
1144 /// \brief Add a new edge to the digraph. |
|
1145 /// |
|
1146 /// Add a new arc to the digraph with source node \c s |
|
1147 /// and target node \c t. |
|
1148 /// \return the new edge. |
|
1149 Edge addEdge(const Node& s, const Node& t) { |
|
1150 return Parent::addEdge(s, t); |
|
1151 } |
|
1152 /// \brief Changes the source of \c e to \c n |
|
1153 /// |
|
1154 /// Changes the source of \c e to \c n |
|
1155 /// |
|
1156 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
|
1157 ///referencing the changed arc remain |
|
1158 ///valid. However <tt>OutArcIt</tt>s are invalidated. |
|
1159 void changeSource(Edge e, Node n) { |
|
1160 Parent::changeSource(e,n); |
|
1161 } |
|
1162 /// \brief Changes the target of \c e to \c n |
|
1163 /// |
|
1164 /// Changes the target of \c e to \c n |
|
1165 /// |
|
1166 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain |
|
1167 /// valid. However the other iterators may be invalidated. |
|
1168 void changeTarget(Edge e, Node n) { |
|
1169 Parent::changeTarget(e,n); |
|
1170 } |
|
1171 /// \brief Changes the source of \c e to \c n |
|
1172 /// |
|
1173 /// Changes the source of \c e to \c n. It changes the proper |
|
1174 /// node of the represented edge. |
|
1175 /// |
|
1176 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
|
1177 ///referencing the changed arc remain |
|
1178 ///valid. However <tt>OutArcIt</tt>s are invalidated. |
|
1179 void changeSource(Arc e, Node n) { |
|
1180 if (Parent::direction(e)) { |
|
1181 Parent::changeSource(e,n); |
|
1182 } else { |
|
1183 Parent::changeTarget(e,n); |
|
1184 } |
|
1185 } |
|
1186 /// \brief Changes the target of \c e to \c n |
|
1187 /// |
|
1188 /// Changes the target of \c e to \c n. It changes the proper |
|
1189 /// node of the represented edge. |
|
1190 /// |
|
1191 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s |
|
1192 ///referencing the changed arc remain |
|
1193 ///valid. However <tt>InArcIt</tt>s are invalidated. |
|
1194 void changeTarget(Arc e, Node n) { |
|
1195 if (Parent::direction(e)) { |
|
1196 Parent::changeTarget(e,n); |
|
1197 } else { |
|
1198 Parent::changeSource(e,n); |
|
1199 } |
|
1200 } |
|
1201 /// \brief Contract two nodes. |
|
1202 /// |
|
1203 /// This function contracts two nodes. |
|
1204 /// |
|
1205 /// Node \p b will be removed but instead of deleting |
|
1206 /// its neighboring arcs, they will be joined to \p a. |
|
1207 /// The last parameter \p r controls whether to remove loops. \c true |
|
1208 /// means that loops will be removed. |
|
1209 /// |
|
1210 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain |
|
1211 /// valid. |
|
1212 void contract(Node a, Node b, bool r = true) { |
|
1213 for(IncArcIt e(*this, b); e!=INVALID;) { |
|
1214 IncArcIt f = e; ++f; |
|
1215 if (r && runningNode(e) == a) { |
|
1216 erase(e); |
|
1217 } else if (source(e) == b) { |
|
1218 changeSource(e, a); |
|
1219 } else { |
|
1220 changeTarget(e, a); |
|
1221 } |
|
1222 e = f; |
|
1223 } |
|
1224 erase(b); |
|
1225 } |
|
1226 |
|
1227 |
|
1228 /// \brief Class to make a snapshot of the digraph and restore |
|
1229 /// to it later. |
|
1230 /// |
|
1231 /// Class to make a snapshot of the digraph and to restore it |
|
1232 /// later. |
|
1233 /// |
|
1234 /// The newly added nodes and edges can be removed |
|
1235 /// using the restore() function. |
|
1236 /// |
|
1237 /// \warning Arc and node deletions cannot be restored. This |
|
1238 /// events invalidate the snapshot. |
|
1239 class Snapshot { |
|
1240 protected: |
|
1241 |
|
1242 typedef Parent::NodeNotifier NodeNotifier; |
|
1243 |
|
1244 class NodeObserverProxy : public NodeNotifier::ObserverBase { |
|
1245 public: |
|
1246 |
|
1247 NodeObserverProxy(Snapshot& _snapshot) |
|
1248 : snapshot(_snapshot) {} |
|
1249 |
|
1250 using NodeNotifier::ObserverBase::attach; |
|
1251 using NodeNotifier::ObserverBase::detach; |
|
1252 using NodeNotifier::ObserverBase::attached; |
|
1253 |
|
1254 protected: |
|
1255 |
|
1256 virtual void add(const Node& node) { |
|
1257 snapshot.addNode(node); |
|
1258 } |
|
1259 virtual void add(const std::vector<Node>& nodes) { |
|
1260 for (int i = nodes.size() - 1; i >= 0; ++i) { |
|
1261 snapshot.addNode(nodes[i]); |
|
1262 } |
|
1263 } |
|
1264 virtual void erase(const Node& node) { |
|
1265 snapshot.eraseNode(node); |
|
1266 } |
|
1267 virtual void erase(const std::vector<Node>& nodes) { |
|
1268 for (int i = 0; i < int(nodes.size()); ++i) { |
|
1269 snapshot.eraseNode(nodes[i]); |
|
1270 } |
|
1271 } |
|
1272 virtual void build() { |
|
1273 Node node; |
|
1274 std::vector<Node> nodes; |
|
1275 for (notifier()->first(node); node != INVALID; |
|
1276 notifier()->next(node)) { |
|
1277 nodes.push_back(node); |
|
1278 } |
|
1279 for (int i = nodes.size() - 1; i >= 0; --i) { |
|
1280 snapshot.addNode(nodes[i]); |
|
1281 } |
|
1282 } |
|
1283 virtual void clear() { |
|
1284 Node node; |
|
1285 for (notifier()->first(node); node != INVALID; |
|
1286 notifier()->next(node)) { |
|
1287 snapshot.eraseNode(node); |
|
1288 } |
|
1289 } |
|
1290 |
|
1291 Snapshot& snapshot; |
|
1292 }; |
|
1293 |
|
1294 class EdgeObserverProxy : public EdgeNotifier::ObserverBase { |
|
1295 public: |
|
1296 |
|
1297 EdgeObserverProxy(Snapshot& _snapshot) |
|
1298 : snapshot(_snapshot) {} |
|
1299 |
|
1300 using EdgeNotifier::ObserverBase::attach; |
|
1301 using EdgeNotifier::ObserverBase::detach; |
|
1302 using EdgeNotifier::ObserverBase::attached; |
|
1303 |
|
1304 protected: |
|
1305 |
|
1306 virtual void add(const Edge& arc) { |
|
1307 snapshot.addEdge(arc); |
|
1308 } |
|
1309 virtual void add(const std::vector<Edge>& arcs) { |
|
1310 for (int i = arcs.size() - 1; i >= 0; ++i) { |
|
1311 snapshot.addEdge(arcs[i]); |
|
1312 } |
|
1313 } |
|
1314 virtual void erase(const Edge& arc) { |
|
1315 snapshot.eraseEdge(arc); |
|
1316 } |
|
1317 virtual void erase(const std::vector<Edge>& arcs) { |
|
1318 for (int i = 0; i < int(arcs.size()); ++i) { |
|
1319 snapshot.eraseEdge(arcs[i]); |
|
1320 } |
|
1321 } |
|
1322 virtual void build() { |
|
1323 Edge arc; |
|
1324 std::vector<Edge> arcs; |
|
1325 for (notifier()->first(arc); arc != INVALID; |
|
1326 notifier()->next(arc)) { |
|
1327 arcs.push_back(arc); |
|
1328 } |
|
1329 for (int i = arcs.size() - 1; i >= 0; --i) { |
|
1330 snapshot.addEdge(arcs[i]); |
|
1331 } |
|
1332 } |
|
1333 virtual void clear() { |
|
1334 Edge arc; |
|
1335 for (notifier()->first(arc); arc != INVALID; |
|
1336 notifier()->next(arc)) { |
|
1337 snapshot.eraseEdge(arc); |
|
1338 } |
|
1339 } |
|
1340 |
|
1341 Snapshot& snapshot; |
|
1342 }; |
|
1343 |
|
1344 ListGraph *digraph; |
|
1345 |
|
1346 NodeObserverProxy node_observer_proxy; |
|
1347 EdgeObserverProxy arc_observer_proxy; |
|
1348 |
|
1349 std::list<Node> added_nodes; |
|
1350 std::list<Edge> added_arcs; |
|
1351 |
|
1352 |
|
1353 void addNode(const Node& node) { |
|
1354 added_nodes.push_front(node); |
|
1355 } |
|
1356 void eraseNode(const Node& node) { |
|
1357 std::list<Node>::iterator it = |
|
1358 std::find(added_nodes.begin(), added_nodes.end(), node); |
|
1359 if (it == added_nodes.end()) { |
|
1360 clear(); |
|
1361 arc_observer_proxy.detach(); |
|
1362 throw NodeNotifier::ImmediateDetach(); |
|
1363 } else { |
|
1364 added_nodes.erase(it); |
|
1365 } |
|
1366 } |
|
1367 |
|
1368 void addEdge(const Edge& arc) { |
|
1369 added_arcs.push_front(arc); |
|
1370 } |
|
1371 void eraseEdge(const Edge& arc) { |
|
1372 std::list<Edge>::iterator it = |
|
1373 std::find(added_arcs.begin(), added_arcs.end(), arc); |
|
1374 if (it == added_arcs.end()) { |
|
1375 clear(); |
|
1376 node_observer_proxy.detach(); |
|
1377 throw EdgeNotifier::ImmediateDetach(); |
|
1378 } else { |
|
1379 added_arcs.erase(it); |
|
1380 } |
|
1381 } |
|
1382 |
|
1383 void attach(ListGraph &_digraph) { |
|
1384 digraph = &_digraph; |
|
1385 node_observer_proxy.attach(digraph->notifier(Node())); |
|
1386 arc_observer_proxy.attach(digraph->notifier(Edge())); |
|
1387 } |
|
1388 |
|
1389 void detach() { |
|
1390 node_observer_proxy.detach(); |
|
1391 arc_observer_proxy.detach(); |
|
1392 } |
|
1393 |
|
1394 bool attached() const { |
|
1395 return node_observer_proxy.attached(); |
|
1396 } |
|
1397 |
|
1398 void clear() { |
|
1399 added_nodes.clear(); |
|
1400 added_arcs.clear(); |
|
1401 } |
|
1402 |
|
1403 public: |
|
1404 |
|
1405 /// \brief Default constructor. |
|
1406 /// |
|
1407 /// Default constructor. |
|
1408 /// To actually make a snapshot you must call save(). |
|
1409 Snapshot() |
|
1410 : digraph(0), node_observer_proxy(*this), |
|
1411 arc_observer_proxy(*this) {} |
|
1412 |
|
1413 /// \brief Constructor that immediately makes a snapshot. |
|
1414 /// |
|
1415 /// This constructor immediately makes a snapshot of the digraph. |
|
1416 /// \param _digraph The digraph we make a snapshot of. |
|
1417 Snapshot(ListGraph &_digraph) |
|
1418 : node_observer_proxy(*this), |
|
1419 arc_observer_proxy(*this) { |
|
1420 attach(_digraph); |
|
1421 } |
|
1422 |
|
1423 /// \brief Make a snapshot. |
|
1424 /// |
|
1425 /// Make a snapshot of the digraph. |
|
1426 /// |
|
1427 /// This function can be called more than once. In case of a repeated |
|
1428 /// call, the previous snapshot gets lost. |
|
1429 /// \param _digraph The digraph we make the snapshot of. |
|
1430 void save(ListGraph &_digraph) { |
|
1431 if (attached()) { |
|
1432 detach(); |
|
1433 clear(); |
|
1434 } |
|
1435 attach(_digraph); |
|
1436 } |
|
1437 |
|
1438 /// \brief Undo the changes until the last snapshot. |
|
1439 // |
|
1440 /// Undo the changes until the last snapshot created by save(). |
|
1441 void restore() { |
|
1442 detach(); |
|
1443 for(std::list<Edge>::iterator it = added_arcs.begin(); |
|
1444 it != added_arcs.end(); ++it) { |
|
1445 digraph->erase(*it); |
|
1446 } |
|
1447 for(std::list<Node>::iterator it = added_nodes.begin(); |
|
1448 it != added_nodes.end(); ++it) { |
|
1449 digraph->erase(*it); |
|
1450 } |
|
1451 clear(); |
|
1452 } |
|
1453 |
|
1454 /// \brief Gives back true when the snapshot is valid. |
|
1455 /// |
|
1456 /// Gives back true when the snapshot is valid. |
|
1457 bool valid() const { |
|
1458 return attached(); |
|
1459 } |
|
1460 }; |
|
1461 }; |
|
1462 |
|
1463 /// @} |
|
1464 } //namespace lemon |
|
1465 |
|
1466 |
|
1467 #endif |