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