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 |
19 #ifndef LEMON_LIST_BPUGRAPH_H |
20 #define LEMON_LIST_GRAPH_H |
20 #define LEMON_LIST_BPUGRAPH_H |
21 |
21 |
22 ///\ingroup graphs |
22 ///\ingroup graphs |
23 ///\file |
23 ///\file |
24 ///\brief ListGraph, ListUGraph classes. |
24 ///\brief ListBpUGraph classes. |
25 |
25 |
26 #include <lemon/bits/base_extender.h> |
26 #include <lemon/bits/bpugraph_extender.h> |
27 #include <lemon/bits/graph_extender.h> |
|
28 |
27 |
29 #include <lemon/error.h> |
28 #include <lemon/error.h> |
30 |
29 |
31 #include <vector> |
30 #include <vector> |
32 #include <list> |
31 #include <list> |
33 |
32 |
34 namespace lemon { |
33 namespace lemon { |
35 |
|
36 class ListGraphBase { |
|
37 |
|
38 protected: |
|
39 struct NodeT { |
|
40 int first_in, first_out; |
|
41 int prev, next; |
|
42 }; |
|
43 |
|
44 struct EdgeT { |
|
45 int target, source; |
|
46 int prev_in, prev_out; |
|
47 int next_in, next_out; |
|
48 }; |
|
49 |
|
50 std::vector<NodeT> nodes; |
|
51 |
|
52 int first_node; |
|
53 |
|
54 int first_free_node; |
|
55 |
|
56 std::vector<EdgeT> edges; |
|
57 |
|
58 int first_free_edge; |
|
59 |
|
60 public: |
|
61 |
|
62 typedef ListGraphBase Graph; |
|
63 |
|
64 class Node { |
|
65 friend class ListGraphBase; |
|
66 protected: |
|
67 |
|
68 int id; |
|
69 explicit Node(int pid) { id = pid;} |
|
70 |
|
71 public: |
|
72 Node() {} |
|
73 Node (Invalid) { id = -1; } |
|
74 bool operator==(const Node& node) const {return id == node.id;} |
|
75 bool operator!=(const Node& node) const {return id != node.id;} |
|
76 bool operator<(const Node& node) const {return id < node.id;} |
|
77 }; |
|
78 |
|
79 class Edge { |
|
80 friend class ListGraphBase; |
|
81 protected: |
|
82 |
|
83 int id; |
|
84 explicit Edge(int pid) { id = pid;} |
|
85 |
|
86 public: |
|
87 Edge() {} |
|
88 Edge (Invalid) { id = -1; } |
|
89 bool operator==(const Edge& edge) const {return id == edge.id;} |
|
90 bool operator!=(const Edge& edge) const {return id != edge.id;} |
|
91 bool operator<(const Edge& edge) const {return id < edge.id;} |
|
92 }; |
|
93 |
|
94 |
|
95 |
|
96 ListGraphBase() |
|
97 : nodes(), first_node(-1), |
|
98 first_free_node(-1), edges(), first_free_edge(-1) {} |
|
99 |
|
100 |
|
101 /// Maximum node ID. |
|
102 |
|
103 /// Maximum node ID. |
|
104 ///\sa id(Node) |
|
105 int maxNodeId() const { return nodes.size()-1; } |
|
106 |
|
107 /// Maximum edge ID. |
|
108 |
|
109 /// Maximum edge ID. |
|
110 ///\sa id(Edge) |
|
111 int maxEdgeId() const { return edges.size()-1; } |
|
112 |
|
113 Node source(Edge e) const { return Node(edges[e.id].source); } |
|
114 Node target(Edge e) const { return Node(edges[e.id].target); } |
|
115 |
|
116 |
|
117 void first(Node& node) const { |
|
118 node.id = first_node; |
|
119 } |
|
120 |
|
121 void next(Node& node) const { |
|
122 node.id = nodes[node.id].next; |
|
123 } |
|
124 |
|
125 |
|
126 void first(Edge& e) const { |
|
127 int n; |
|
128 for(n = first_node; |
|
129 n!=-1 && nodes[n].first_in == -1; |
|
130 n = nodes[n].next); |
|
131 e.id = (n == -1) ? -1 : nodes[n].first_in; |
|
132 } |
|
133 |
|
134 void next(Edge& edge) const { |
|
135 if (edges[edge.id].next_in != -1) { |
|
136 edge.id = edges[edge.id].next_in; |
|
137 } else { |
|
138 int n; |
|
139 for(n = nodes[edges[edge.id].target].next; |
|
140 n!=-1 && nodes[n].first_in == -1; |
|
141 n = nodes[n].next); |
|
142 edge.id = (n == -1) ? -1 : nodes[n].first_in; |
|
143 } |
|
144 } |
|
145 |
|
146 void firstOut(Edge &e, const Node& v) const { |
|
147 e.id = nodes[v.id].first_out; |
|
148 } |
|
149 void nextOut(Edge &e) const { |
|
150 e.id=edges[e.id].next_out; |
|
151 } |
|
152 |
|
153 void firstIn(Edge &e, const Node& v) const { |
|
154 e.id = nodes[v.id].first_in; |
|
155 } |
|
156 void nextIn(Edge &e) const { |
|
157 e.id=edges[e.id].next_in; |
|
158 } |
|
159 |
|
160 |
|
161 static int id(Node v) { return v.id; } |
|
162 static int id(Edge e) { return e.id; } |
|
163 |
|
164 static Node nodeFromId(int id) { return Node(id);} |
|
165 static Edge edgeFromId(int id) { return Edge(id);} |
|
166 |
|
167 /// Adds a new node to the graph. |
|
168 |
|
169 /// \warning It adds the new node to the front of the list. |
|
170 /// (i.e. the lastly added node becomes the first.) |
|
171 Node addNode() { |
|
172 int n; |
|
173 |
|
174 if(first_free_node==-1) { |
|
175 n = nodes.size(); |
|
176 nodes.push_back(NodeT()); |
|
177 } else { |
|
178 n = first_free_node; |
|
179 first_free_node = nodes[n].next; |
|
180 } |
|
181 |
|
182 nodes[n].next = first_node; |
|
183 if(first_node != -1) nodes[first_node].prev = n; |
|
184 first_node = n; |
|
185 nodes[n].prev = -1; |
|
186 |
|
187 nodes[n].first_in = nodes[n].first_out = -1; |
|
188 |
|
189 return Node(n); |
|
190 } |
|
191 |
|
192 Edge addEdge(Node u, Node v) { |
|
193 int n; |
|
194 |
|
195 if (first_free_edge == -1) { |
|
196 n = edges.size(); |
|
197 edges.push_back(EdgeT()); |
|
198 } else { |
|
199 n = first_free_edge; |
|
200 first_free_edge = edges[n].next_in; |
|
201 } |
|
202 |
|
203 edges[n].source = u.id; |
|
204 edges[n].target = v.id; |
|
205 |
|
206 edges[n].next_out = nodes[u.id].first_out; |
|
207 if(nodes[u.id].first_out != -1) { |
|
208 edges[nodes[u.id].first_out].prev_out = n; |
|
209 } |
|
210 |
|
211 edges[n].next_in = nodes[v.id].first_in; |
|
212 if(nodes[v.id].first_in != -1) { |
|
213 edges[nodes[v.id].first_in].prev_in = n; |
|
214 } |
|
215 |
|
216 edges[n].prev_in = edges[n].prev_out = -1; |
|
217 |
|
218 nodes[u.id].first_out = nodes[v.id].first_in = n; |
|
219 |
|
220 return Edge(n); |
|
221 } |
|
222 |
|
223 void erase(const Node& node) { |
|
224 int n = node.id; |
|
225 |
|
226 if(nodes[n].next != -1) { |
|
227 nodes[nodes[n].next].prev = nodes[n].prev; |
|
228 } |
|
229 |
|
230 if(nodes[n].prev != -1) { |
|
231 nodes[nodes[n].prev].next = nodes[n].next; |
|
232 } else { |
|
233 first_node = nodes[n].next; |
|
234 } |
|
235 |
|
236 nodes[n].next = first_free_node; |
|
237 first_free_node = n; |
|
238 |
|
239 } |
|
240 |
|
241 void erase(const Edge& edge) { |
|
242 int n = edge.id; |
|
243 |
|
244 if(edges[n].next_in!=-1) { |
|
245 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
|
246 } |
|
247 |
|
248 if(edges[n].prev_in!=-1) { |
|
249 edges[edges[n].prev_in].next_in = edges[n].next_in; |
|
250 } else { |
|
251 nodes[edges[n].target].first_in = edges[n].next_in; |
|
252 } |
|
253 |
|
254 |
|
255 if(edges[n].next_out!=-1) { |
|
256 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
|
257 } |
|
258 |
|
259 if(edges[n].prev_out!=-1) { |
|
260 edges[edges[n].prev_out].next_out = edges[n].next_out; |
|
261 } else { |
|
262 nodes[edges[n].source].first_out = edges[n].next_out; |
|
263 } |
|
264 |
|
265 edges[n].next_in = first_free_edge; |
|
266 first_free_edge = n; |
|
267 |
|
268 } |
|
269 |
|
270 void clear() { |
|
271 edges.clear(); |
|
272 nodes.clear(); |
|
273 first_node = first_free_node = first_free_edge = -1; |
|
274 } |
|
275 |
|
276 protected: |
|
277 void changeTarget(Edge e, Node n) |
|
278 { |
|
279 if(edges[e.id].next_in != -1) |
|
280 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; |
|
281 if(edges[e.id].prev_in != -1) |
|
282 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; |
|
283 else nodes[edges[e.id].target].first_in = edges[e.id].next_in; |
|
284 if (nodes[n.id].first_in != -1) { |
|
285 edges[nodes[n.id].first_in].prev_in = e.id; |
|
286 } |
|
287 edges[e.id].target = n.id; |
|
288 edges[e.id].prev_in = -1; |
|
289 edges[e.id].next_in = nodes[n.id].first_in; |
|
290 nodes[n.id].first_in = e.id; |
|
291 } |
|
292 void changeSource(Edge e, Node n) |
|
293 { |
|
294 if(edges[e.id].next_out != -1) |
|
295 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
|
296 if(edges[e.id].prev_out != -1) |
|
297 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
|
298 else nodes[edges[e.id].source].first_out = edges[e.id].next_out; |
|
299 if (nodes[n.id].first_out != -1) { |
|
300 edges[nodes[n.id].first_out].prev_out = e.id; |
|
301 } |
|
302 edges[e.id].source = n.id; |
|
303 edges[e.id].prev_out = -1; |
|
304 edges[e.id].next_out = nodes[n.id].first_out; |
|
305 nodes[n.id].first_out = e.id; |
|
306 } |
|
307 |
|
308 }; |
|
309 |
|
310 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; |
|
311 |
|
312 /// \addtogroup graphs |
|
313 /// @{ |
|
314 |
|
315 ///A list graph class. |
|
316 |
|
317 ///This is a simple and fast erasable graph implementation. |
|
318 /// |
|
319 ///It conforms to the \ref concept::Graph "Graph" concept and it |
|
320 ///also provides several additional useful extra functionalities. |
|
321 ///The most of the member functions and nested classes are |
|
322 ///documented only in the concept class. |
|
323 ///\sa concept::Graph. |
|
324 |
|
325 class ListGraph : public ExtendedListGraphBase { |
|
326 public: |
|
327 |
|
328 typedef ExtendedListGraphBase Parent; |
|
329 |
|
330 ///Add a new node to the graph. |
|
331 |
|
332 /// \return the new node. |
|
333 /// |
|
334 Node addNode() { return Parent::addNode(); } |
|
335 |
|
336 ///Add a new edge to the graph. |
|
337 |
|
338 ///Add a new edge to the graph with source node \c s |
|
339 ///and target node \c t. |
|
340 ///\return the new edge. |
|
341 Edge addEdge(const Node& s, const Node& t) { |
|
342 return Parent::addEdge(s, t); |
|
343 } |
|
344 |
|
345 /// Changes the target of \c e to \c n |
|
346 |
|
347 /// Changes the target of \c e to \c n |
|
348 /// |
|
349 ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing |
|
350 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are |
|
351 ///invalidated. |
|
352 void changeTarget(Edge e, Node n) { |
|
353 Parent::changeTarget(e,n); |
|
354 } |
|
355 /// Changes the source of \c e to \c n |
|
356 |
|
357 /// Changes the source of \c e to \c n |
|
358 /// |
|
359 ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing |
|
360 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are |
|
361 ///invalidated. |
|
362 void changeSource(Edge e, Node n) { |
|
363 Parent::changeSource(e,n); |
|
364 } |
|
365 |
|
366 /// Invert the direction of an edge. |
|
367 |
|
368 ///\note The <tt>Edge</tt>s referencing the changed edge remain |
|
369 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are |
|
370 ///invalidated. |
|
371 void reverseEdge(Edge e) { |
|
372 Node t=target(e); |
|
373 changeTarget(e,source(e)); |
|
374 changeSource(e,t); |
|
375 } |
|
376 |
|
377 /// \brief Using this it is possible to avoid the superfluous memory |
|
378 /// allocation. |
|
379 |
|
380 ///Using this it is possible to avoid the superfluous memory |
|
381 ///allocation: if you know that the graph you want to build will |
|
382 ///contain at least 10 million nodes then it is worth to reserve |
|
383 ///space for this amount before starting to build the graph. |
|
384 void reserveNode(int n) { nodes.reserve(n); }; |
|
385 |
|
386 /// \brief Using this it is possible to avoid the superfluous memory |
|
387 /// allocation. |
|
388 |
|
389 ///Using this it is possible to avoid the superfluous memory |
|
390 ///allocation: see the \ref reserveNode function. |
|
391 void reserveEdge(int n) { edges.reserve(n); }; |
|
392 |
|
393 |
|
394 ///Contract two nodes. |
|
395 |
|
396 ///This function contracts two nodes. |
|
397 /// |
|
398 ///Node \p b will be removed but instead of deleting |
|
399 ///incident edges, they will be joined to \p a. |
|
400 ///The last parameter \p r controls whether to remove loops. \c true |
|
401 ///means that loops will be removed. |
|
402 /// |
|
403 ///\note The <tt>Edge</tt>s |
|
404 ///referencing a moved edge remain |
|
405 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s |
|
406 ///may be invalidated. |
|
407 void contract(Node a, Node b, bool r = true) |
|
408 { |
|
409 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
|
410 OutEdgeIt f=e; |
|
411 ++f; |
|
412 if(r && target(e)==a) erase(e); |
|
413 else changeSource(e,a); |
|
414 e=f; |
|
415 } |
|
416 for(InEdgeIt e(*this,b);e!=INVALID;) { |
|
417 InEdgeIt f=e; |
|
418 ++f; |
|
419 if(r && source(e)==a) erase(e); |
|
420 else changeTarget(e,a); |
|
421 e=f; |
|
422 } |
|
423 erase(b); |
|
424 } |
|
425 |
|
426 ///Split a node. |
|
427 |
|
428 ///This function splits a node. First a new node is added to the graph, |
|
429 ///then the source of each outgoing edge of \c n is moved to this new node. |
|
430 ///If \c connect is \c true (this is the default value), then a new edge |
|
431 ///from \c n to the newly created node is also added. |
|
432 ///\return The newly created node. |
|
433 /// |
|
434 ///\note The <tt>Edge</tt>s |
|
435 ///referencing a moved edge remain |
|
436 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s |
|
437 ///may be invalidated. |
|
438 ///\warning This functionality cannot be used together with the Snapshot |
|
439 ///feature. |
|
440 ///\todo It could be implemented in a bit faster way. |
|
441 Node split(Node n, bool connect = true) { |
|
442 Node b = addNode(); |
|
443 for(OutEdgeIt e(*this,n);e!=INVALID;) { |
|
444 OutEdgeIt f=e; |
|
445 ++f; |
|
446 changeSource(e,b); |
|
447 e=f; |
|
448 } |
|
449 if (connect) addEdge(n,b); |
|
450 return b; |
|
451 } |
|
452 |
|
453 ///Split an edge. |
|
454 |
|
455 ///This function splits an edge. First a new node \c b is added to |
|
456 ///the graph, then the original edge is re-targeted to \c |
|
457 ///b. Finally an edge from \c b to the original target is added. |
|
458 ///\return The newly created node. |
|
459 ///\warning This functionality |
|
460 ///cannot be used together with the Snapshot feature. |
|
461 Node split(Edge e) { |
|
462 Node b = addNode(); |
|
463 addEdge(b,target(e)); |
|
464 changeTarget(e,b); |
|
465 return b; |
|
466 } |
|
467 |
|
468 /// \brief Class to make a snapshot of the graph and restore |
|
469 /// to it later. |
|
470 /// |
|
471 /// Class to make a snapshot of the graph and to restore it |
|
472 /// later. |
|
473 /// |
|
474 /// The newly added nodes and edges can be removed using the |
|
475 /// restore() function. |
|
476 /// |
|
477 /// \warning Edge and node deletions cannot be restored. |
|
478 class Snapshot { |
|
479 public: |
|
480 |
|
481 class UnsupportedOperation : public LogicError { |
|
482 public: |
|
483 virtual const char* exceptionName() const { |
|
484 return "lemon::ListGraph::Snapshot::UnsupportedOperation"; |
|
485 } |
|
486 }; |
|
487 |
|
488 |
|
489 protected: |
|
490 |
|
491 typedef Parent::NodeNotifier NodeNotifier; |
|
492 |
|
493 class NodeObserverProxy : public NodeNotifier::ObserverBase { |
|
494 public: |
|
495 |
|
496 NodeObserverProxy(Snapshot& _snapshot) |
|
497 : snapshot(_snapshot) {} |
|
498 |
|
499 using NodeNotifier::ObserverBase::attach; |
|
500 using NodeNotifier::ObserverBase::detach; |
|
501 using NodeNotifier::ObserverBase::attached; |
|
502 |
|
503 protected: |
|
504 |
|
505 virtual void add(const Node& node) { |
|
506 snapshot.addNode(node); |
|
507 } |
|
508 virtual void add(const std::vector<Node>& nodes) { |
|
509 for (int i = nodes.size() - 1; i >= 0; ++i) { |
|
510 snapshot.addNode(nodes[i]); |
|
511 } |
|
512 } |
|
513 virtual void erase(const Node& node) { |
|
514 snapshot.eraseNode(node); |
|
515 } |
|
516 virtual void erase(const std::vector<Node>& nodes) { |
|
517 for (int i = 0; i < (int)nodes.size(); ++i) { |
|
518 if (!snapshot.eraseNode(nodes[i])) break; |
|
519 } |
|
520 } |
|
521 virtual void build() { |
|
522 NodeNotifier* notifier = getNotifier(); |
|
523 Node node; |
|
524 std::vector<Node> nodes; |
|
525 for (notifier->first(node); node != INVALID; notifier->next(node)) { |
|
526 nodes.push_back(node); |
|
527 } |
|
528 for (int i = nodes.size() - 1; i >= 0; --i) { |
|
529 snapshot.addNode(nodes[i]); |
|
530 } |
|
531 } |
|
532 virtual void clear() { |
|
533 NodeNotifier* notifier = getNotifier(); |
|
534 Node node; |
|
535 for (notifier->first(node); node != INVALID; notifier->next(node)) { |
|
536 if (!snapshot.eraseNode(node)) break; |
|
537 } |
|
538 } |
|
539 |
|
540 Snapshot& snapshot; |
|
541 }; |
|
542 |
|
543 class EdgeObserverProxy : public EdgeNotifier::ObserverBase { |
|
544 public: |
|
545 |
|
546 EdgeObserverProxy(Snapshot& _snapshot) |
|
547 : snapshot(_snapshot) {} |
|
548 |
|
549 using EdgeNotifier::ObserverBase::attach; |
|
550 using EdgeNotifier::ObserverBase::detach; |
|
551 using EdgeNotifier::ObserverBase::attached; |
|
552 |
|
553 protected: |
|
554 |
|
555 virtual void add(const Edge& edge) { |
|
556 snapshot.addEdge(edge); |
|
557 } |
|
558 virtual void add(const std::vector<Edge>& edges) { |
|
559 for (int i = edges.size() - 1; i >= 0; ++i) { |
|
560 snapshot.addEdge(edges[i]); |
|
561 } |
|
562 } |
|
563 virtual void erase(const Edge& edge) { |
|
564 snapshot.eraseEdge(edge); |
|
565 } |
|
566 virtual void erase(const std::vector<Edge>& edges) { |
|
567 for (int i = 0; i < (int)edges.size(); ++i) { |
|
568 if (!snapshot.eraseEdge(edges[i])) break; |
|
569 } |
|
570 } |
|
571 virtual void build() { |
|
572 EdgeNotifier* notifier = getNotifier(); |
|
573 Edge edge; |
|
574 std::vector<Edge> edges; |
|
575 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { |
|
576 edges.push_back(edge); |
|
577 } |
|
578 for (int i = edges.size() - 1; i >= 0; --i) { |
|
579 snapshot.addEdge(edges[i]); |
|
580 } |
|
581 } |
|
582 virtual void clear() { |
|
583 EdgeNotifier* notifier = getNotifier(); |
|
584 Edge edge; |
|
585 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { |
|
586 if (!snapshot.eraseEdge(edge)) break; |
|
587 } |
|
588 } |
|
589 |
|
590 Snapshot& snapshot; |
|
591 }; |
|
592 |
|
593 ListGraph *graph; |
|
594 |
|
595 NodeObserverProxy node_observer_proxy; |
|
596 EdgeObserverProxy edge_observer_proxy; |
|
597 |
|
598 std::list<Node> added_nodes; |
|
599 std::list<Edge> added_edges; |
|
600 |
|
601 |
|
602 void addNode(const Node& node) { |
|
603 added_nodes.push_front(node); |
|
604 } |
|
605 bool eraseNode(const Node& node) { |
|
606 std::list<Node>::iterator it = |
|
607 std::find(added_nodes.begin(), added_nodes.end(), node); |
|
608 if (it == added_nodes.end()) { |
|
609 clear(); |
|
610 return false; |
|
611 } else { |
|
612 added_nodes.erase(it); |
|
613 return true; |
|
614 } |
|
615 } |
|
616 |
|
617 void addEdge(const Edge& edge) { |
|
618 added_edges.push_front(edge); |
|
619 } |
|
620 bool eraseEdge(const Edge& edge) { |
|
621 std::list<Edge>::iterator it = |
|
622 std::find(added_edges.begin(), added_edges.end(), edge); |
|
623 if (it == added_edges.end()) { |
|
624 clear(); |
|
625 return false; |
|
626 } else { |
|
627 added_edges.erase(it); |
|
628 return true; |
|
629 } |
|
630 } |
|
631 |
|
632 void attach(ListGraph &_graph) { |
|
633 graph = &_graph; |
|
634 node_observer_proxy.attach(graph->getNotifier(Node())); |
|
635 edge_observer_proxy.attach(graph->getNotifier(Edge())); |
|
636 } |
|
637 |
|
638 void detach() { |
|
639 node_observer_proxy.detach(); |
|
640 edge_observer_proxy.detach(); |
|
641 } |
|
642 |
|
643 void clear() { |
|
644 detach(); |
|
645 added_nodes.clear(); |
|
646 added_edges.clear(); |
|
647 } |
|
648 |
|
649 public: |
|
650 |
|
651 /// \brief Default constructur. |
|
652 /// |
|
653 /// Default constructor. |
|
654 /// To actually make a snapshot you must call save(). |
|
655 Snapshot() |
|
656 : graph(0), node_observer_proxy(*this), |
|
657 edge_observer_proxy(*this) {} |
|
658 |
|
659 /// \brief Constructor that immediately makes a snapshot. |
|
660 /// |
|
661 /// This constructor immediately makes a snapshot of the graph. |
|
662 /// \param _graph The graph we make a snapshot of. |
|
663 Snapshot(ListGraph &_graph) |
|
664 : node_observer_proxy(*this), |
|
665 edge_observer_proxy(*this) { |
|
666 attach(_graph); |
|
667 } |
|
668 |
|
669 /// \brief Make a snapshot. |
|
670 /// |
|
671 /// Make a snapshot of the graph. |
|
672 /// |
|
673 /// This function can be called more than once. In case of a repeated |
|
674 /// call, the previous snapshot gets lost. |
|
675 /// \param _graph The graph we make the snapshot of. |
|
676 void save(ListGraph &_graph) { |
|
677 clear(); |
|
678 attach(_graph); |
|
679 } |
|
680 |
|
681 /// \brief Undo the changes until the last snapshot. |
|
682 // |
|
683 /// Undo the changes until last snapshot created by save(). |
|
684 /// |
|
685 /// \todo This function might be called undo(). |
|
686 void restore() { |
|
687 detach(); |
|
688 while(!added_edges.empty()) { |
|
689 graph->erase(added_edges.front()); |
|
690 added_edges.pop_front(); |
|
691 } |
|
692 while(!added_nodes.empty()) { |
|
693 graph->erase(added_nodes.front()); |
|
694 added_nodes.pop_front(); |
|
695 } |
|
696 } |
|
697 |
|
698 /// \brief Gives back true when the snapshot is valid. |
|
699 /// |
|
700 /// Gives back true when the snapshot is valid. |
|
701 bool valid() const { |
|
702 return node_observer_proxy.attached(); |
|
703 } |
|
704 }; |
|
705 |
|
706 }; |
|
707 |
|
708 ///@} |
|
709 |
|
710 /**************** Undirected List Graph ****************/ |
|
711 |
|
712 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > |
|
713 ExtendedListUGraphBase; |
|
714 |
|
715 /// \addtogroup graphs |
|
716 /// @{ |
|
717 |
|
718 ///An undirected list graph class. |
|
719 |
|
720 ///This is a simple and fast erasable undirected graph implementation. |
|
721 /// |
|
722 ///It conforms to the |
|
723 ///\ref concept::UGraph "UGraph" concept. |
|
724 /// |
|
725 ///\sa concept::UGraph. |
|
726 /// |
|
727 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() |
|
728 ///haven't been implemented yet. |
|
729 /// |
|
730 class ListUGraph : public ExtendedListUGraphBase { |
|
731 public: |
|
732 typedef ExtendedListUGraphBase Parent; |
|
733 /// \brief Add a new node to the graph. |
|
734 /// |
|
735 /// \return the new node. |
|
736 /// |
|
737 Node addNode() { return Parent::addNode(); } |
|
738 |
|
739 /// \brief Add a new edge to the graph. |
|
740 /// |
|
741 /// Add a new edge to the graph with source node \c s |
|
742 /// and target node \c t. |
|
743 /// \return the new undirected edge. |
|
744 UEdge addEdge(const Node& s, const Node& t) { |
|
745 return Parent::addEdge(s, t); |
|
746 } |
|
747 /// \brief Changes the target of \c e to \c n |
|
748 /// |
|
749 /// Changes the target of \c e to \c n |
|
750 /// |
|
751 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
|
752 /// referencing the changed edge remain |
|
753 /// valid. However <tt>InEdge</tt>'s are invalidated. |
|
754 void changeTarget(UEdge e, Node n) { |
|
755 Parent::changeTarget(e,n); |
|
756 } |
|
757 /// Changes the source of \c e to \c n |
|
758 /// |
|
759 /// Changes the source of \c e to \c n |
|
760 /// |
|
761 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
|
762 ///referencing the changed edge remain |
|
763 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
|
764 void changeSource(UEdge e, Node n) { |
|
765 Parent::changeSource(e,n); |
|
766 } |
|
767 /// \brief Contract two nodes. |
|
768 /// |
|
769 /// This function contracts two nodes. |
|
770 /// |
|
771 /// Node \p b will be removed but instead of deleting |
|
772 /// its neighboring edges, they will be joined to \p a. |
|
773 /// The last parameter \p r controls whether to remove loops. \c true |
|
774 /// means that loops will be removed. |
|
775 /// |
|
776 /// \note The <tt>Edge</tt>s |
|
777 /// referencing a moved edge remain |
|
778 /// valid. |
|
779 void contract(Node a, Node b, bool r = true) { |
|
780 for(IncEdgeIt e(*this, b); e!=INVALID;) { |
|
781 IncEdgeIt f = e; ++f; |
|
782 if (r && runningNode(e) == a) { |
|
783 erase(e); |
|
784 } else if (source(e) == b) { |
|
785 changeSource(e, a); |
|
786 } else { |
|
787 changeTarget(e, a); |
|
788 } |
|
789 e = f; |
|
790 } |
|
791 erase(b); |
|
792 } |
|
793 }; |
|
794 |
|
795 |
34 |
796 class ListBpUGraphBase { |
35 class ListBpUGraphBase { |
797 public: |
36 public: |
798 |
37 |
799 class NodeSetError : public LogicError { |
38 class NodeSetError : public LogicError { |