1 /* -*- C++ -*- |
|
2 * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_LIST_GRAPH_H |
|
18 #define LEMON_LIST_GRAPH_H |
|
19 |
|
20 ///\ingroup graphs |
|
21 ///\file |
|
22 ///\brief ListGraph, SymListGraph classes. |
|
23 |
|
24 #include <lemon/bits/erasable_graph_extender.h> |
|
25 #include <lemon/bits/clearable_graph_extender.h> |
|
26 #include <lemon/bits/extendable_graph_extender.h> |
|
27 #include <lemon/bits/iterable_graph_extender.h> |
|
28 #include <lemon/bits/alteration_notifier.h> |
|
29 #include <lemon/bits/default_map.h> |
|
30 |
|
31 #include <lemon/bits/undir_graph_extender.h> |
|
32 |
|
33 #include <list> |
|
34 |
|
35 namespace lemon { |
|
36 |
|
37 class ListGraphBase { |
|
38 |
|
39 protected: |
|
40 struct NodeT { |
|
41 int first_in,first_out; |
|
42 int prev, next; |
|
43 }; |
|
44 |
|
45 struct EdgeT { |
|
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<EdgeT> edges; |
|
58 |
|
59 int first_free_edge; |
|
60 |
|
61 public: |
|
62 |
|
63 typedef ListGraphBase Graph; |
|
64 |
|
65 class Node { |
|
66 friend class ListGraphBase; |
|
67 protected: |
|
68 |
|
69 int id; |
|
70 Node(int pid) { id = pid;} |
|
71 |
|
72 public: |
|
73 Node() {} |
|
74 Node (Invalid) { id = -1; } |
|
75 bool operator==(const Node& node) const {return id == node.id;} |
|
76 bool operator!=(const Node& node) const {return id != node.id;} |
|
77 bool operator<(const Node& node) const {return id < node.id;} |
|
78 }; |
|
79 |
|
80 class Edge { |
|
81 friend class ListGraphBase; |
|
82 protected: |
|
83 |
|
84 int id; |
|
85 Edge(int pid) { id = pid;} |
|
86 |
|
87 public: |
|
88 Edge() {} |
|
89 Edge (Invalid) { id = -1; } |
|
90 bool operator==(const Edge& edge) const {return id == edge.id;} |
|
91 bool operator!=(const Edge& edge) const {return id != edge.id;} |
|
92 bool operator<(const Edge& edge) const {return id < edge.id;} |
|
93 }; |
|
94 |
|
95 |
|
96 |
|
97 ListGraphBase() |
|
98 : nodes(), first_node(-1), |
|
99 first_free_node(-1), edges(), first_free_edge(-1) {} |
|
100 |
|
101 |
|
102 /// Maximum node ID. |
|
103 |
|
104 /// Maximum node ID. |
|
105 ///\sa id(Node) |
|
106 int maxId(Node = INVALID) const { return nodes.size()-1; } |
|
107 |
|
108 /// Maximum edge ID. |
|
109 |
|
110 /// Maximum edge ID. |
|
111 ///\sa id(Edge) |
|
112 int maxId(Edge = INVALID) const { return edges.size()-1; } |
|
113 |
|
114 Node source(Edge e) const { return edges[e.id].source; } |
|
115 Node target(Edge e) const { return edges[e.id].target; } |
|
116 |
|
117 |
|
118 void first(Node& node) const { |
|
119 node.id = first_node; |
|
120 } |
|
121 |
|
122 void next(Node& node) const { |
|
123 node.id = nodes[node.id].next; |
|
124 } |
|
125 |
|
126 |
|
127 void first(Edge& e) const { |
|
128 int n; |
|
129 for(n = first_node; |
|
130 n!=-1 && nodes[n].first_in == -1; |
|
131 n = nodes[n].next); |
|
132 e.id = (n == -1) ? -1 : nodes[n].first_in; |
|
133 } |
|
134 |
|
135 void next(Edge& edge) const { |
|
136 if (edges[edge.id].next_in != -1) { |
|
137 edge.id = edges[edge.id].next_in; |
|
138 } else { |
|
139 int n; |
|
140 for(n = nodes[edges[edge.id].target].next; |
|
141 n!=-1 && nodes[n].first_in == -1; |
|
142 n = nodes[n].next); |
|
143 edge.id = (n == -1) ? -1 : nodes[n].first_in; |
|
144 } |
|
145 } |
|
146 |
|
147 void firstOut(Edge &e, const Node& v) const { |
|
148 e.id = nodes[v.id].first_out; |
|
149 } |
|
150 void nextOut(Edge &e) const { |
|
151 e.id=edges[e.id].next_out; |
|
152 } |
|
153 |
|
154 void firstIn(Edge &e, const Node& v) const { |
|
155 e.id = nodes[v.id].first_in; |
|
156 } |
|
157 void nextIn(Edge &e) const { |
|
158 e.id=edges[e.id].next_in; |
|
159 } |
|
160 |
|
161 |
|
162 static int id(Node v) { return v.id; } |
|
163 static int id(Edge e) { return e.id; } |
|
164 |
|
165 static Node fromId(int id, Node) { return Node(id);} |
|
166 static Edge fromId(int id, Edge) { return Edge(id);} |
|
167 |
|
168 /// Adds a new node to the graph. |
|
169 |
|
170 /// \warning It adds the new node to the front of the list. |
|
171 /// (i.e. the lastly added node becomes the first.) |
|
172 Node addNode() { |
|
173 int n; |
|
174 |
|
175 if(first_free_node==-1) { |
|
176 n = nodes.size(); |
|
177 nodes.push_back(NodeT()); |
|
178 } else { |
|
179 n = first_free_node; |
|
180 first_free_node = nodes[n].next; |
|
181 } |
|
182 |
|
183 nodes[n].next = first_node; |
|
184 if(first_node != -1) nodes[first_node].prev = n; |
|
185 first_node = n; |
|
186 nodes[n].prev = -1; |
|
187 |
|
188 nodes[n].first_in = nodes[n].first_out = -1; |
|
189 |
|
190 return Node(n); |
|
191 } |
|
192 |
|
193 Edge addEdge(Node u, Node v) { |
|
194 int n; |
|
195 |
|
196 if (first_free_edge == -1) { |
|
197 n = edges.size(); |
|
198 edges.push_back(EdgeT()); |
|
199 } else { |
|
200 n = first_free_edge; |
|
201 first_free_edge = edges[n].next_in; |
|
202 } |
|
203 |
|
204 edges[n].source = u.id; |
|
205 edges[n].target = v.id; |
|
206 |
|
207 edges[n].next_out = nodes[u.id].first_out; |
|
208 if(nodes[u.id].first_out != -1) { |
|
209 edges[nodes[u.id].first_out].prev_out = n; |
|
210 } |
|
211 |
|
212 edges[n].next_in = nodes[v.id].first_in; |
|
213 if(nodes[v.id].first_in != -1) { |
|
214 edges[nodes[v.id].first_in].prev_in = n; |
|
215 } |
|
216 |
|
217 edges[n].prev_in = edges[n].prev_out = -1; |
|
218 |
|
219 nodes[u.id].first_out = nodes[v.id].first_in = n; |
|
220 |
|
221 return Edge(n); |
|
222 } |
|
223 |
|
224 void erase(const Node& node) { |
|
225 int n = node.id; |
|
226 |
|
227 if(nodes[n].next != -1) { |
|
228 nodes[nodes[n].next].prev = nodes[n].prev; |
|
229 } |
|
230 |
|
231 if(nodes[n].prev != -1) { |
|
232 nodes[nodes[n].prev].next = nodes[n].next; |
|
233 } else { |
|
234 first_node = nodes[n].next; |
|
235 } |
|
236 |
|
237 nodes[n].next = first_free_node; |
|
238 first_free_node = n; |
|
239 |
|
240 } |
|
241 |
|
242 void erase(const Edge& edge) { |
|
243 int n = edge.id; |
|
244 |
|
245 if(edges[n].next_in!=-1) { |
|
246 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
|
247 } |
|
248 |
|
249 if(edges[n].prev_in!=-1) { |
|
250 edges[edges[n].prev_in].next_in = edges[n].next_in; |
|
251 } else { |
|
252 nodes[edges[n].target].first_in = edges[n].next_in; |
|
253 } |
|
254 |
|
255 |
|
256 if(edges[n].next_out!=-1) { |
|
257 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
|
258 } |
|
259 |
|
260 if(edges[n].prev_out!=-1) { |
|
261 edges[edges[n].prev_out].next_out = edges[n].next_out; |
|
262 } else { |
|
263 nodes[edges[n].source].first_out = edges[n].next_out; |
|
264 } |
|
265 |
|
266 edges[n].next_in = first_free_edge; |
|
267 first_free_edge = n; |
|
268 |
|
269 } |
|
270 |
|
271 void clear() { |
|
272 edges.clear(); |
|
273 nodes.clear(); |
|
274 first_node = first_free_node = first_free_edge = -1; |
|
275 } |
|
276 |
|
277 protected: |
|
278 void _moveTarget(Edge e, Node n) |
|
279 { |
|
280 if(edges[e.id].next_in != -1) |
|
281 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; |
|
282 if(edges[e.id].prev_in != -1) |
|
283 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; |
|
284 else nodes[edges[e.id].target].first_in = edges[e.id].next_in; |
|
285 edges[e.id].target = n.id; |
|
286 edges[e.id].prev_in = -1; |
|
287 edges[e.id].next_in = nodes[n.id].first_in; |
|
288 nodes[n.id].first_in = e.id; |
|
289 } |
|
290 void _moveSource(Edge e, Node n) |
|
291 { |
|
292 if(edges[e.id].next_out != -1) |
|
293 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
|
294 if(edges[e.id].prev_out != -1) |
|
295 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
|
296 else nodes[edges[e.id].source].first_out = edges[e.id].next_out; |
|
297 edges[e.id].source = n.id; |
|
298 edges[e.id].prev_out = -1; |
|
299 edges[e.id].next_out = nodes[n.id].first_out; |
|
300 nodes[n.id].first_out = e.id; |
|
301 } |
|
302 |
|
303 }; |
|
304 |
|
305 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase; |
|
306 typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase; |
|
307 typedef DefaultMappableGraphExtender<IterableListGraphBase> MappableListGraphBase; |
|
308 typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase; |
|
309 typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase; |
|
310 typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase; |
|
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 addition that it conforms to the |
|
320 ///\ref concept::ErasableGraph "ErasableGraph" concept, |
|
321 ///it also provides several additional useful extra functionalities. |
|
322 ///\sa concept::ErasableGraph. |
|
323 |
|
324 class ListGraph : public ErasableListGraphBase |
|
325 { |
|
326 public: |
|
327 /// Moves the target of \c e to \c n |
|
328 |
|
329 /// Moves the target of \c e to \c n |
|
330 /// |
|
331 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
|
332 ///referencing the moved edge remain |
|
333 ///valid. However <tt>InEdge</tt>'s are invalidated. |
|
334 void moveTarget(Edge e, Node n) { _moveTarget(e,n); } |
|
335 /// Moves the source of \c e to \c n |
|
336 |
|
337 /// Moves the source of \c e to \c n |
|
338 /// |
|
339 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
|
340 ///referencing the moved edge remain |
|
341 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
|
342 void moveSource(Edge e, Node n) { _moveSource(e,n); } |
|
343 |
|
344 /// Invert the direction of an edge. |
|
345 |
|
346 ///\note The <tt>Edge</tt>'s |
|
347 ///referencing the moved edge remain |
|
348 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated. |
|
349 void reverseEdge(Edge e) { |
|
350 Node t=target(e); |
|
351 _moveTarget(e,source(e)); |
|
352 _moveSource(e,t); |
|
353 } |
|
354 |
|
355 ///Using this it possible to avoid the superfluous memory allocation. |
|
356 |
|
357 ///Using this it possible to avoid the superfluous memory allocation. |
|
358 ///\todo more docs... |
|
359 void reserveEdge(int n) { edges.reserve(n); }; |
|
360 |
|
361 ///Contract two nodes. |
|
362 |
|
363 ///This function contracts two nodes. |
|
364 /// |
|
365 ///Node \p b will be removed but instead of deleting |
|
366 ///its neighboring edges, they will be joined to \p a. |
|
367 ///The last parameter \p r controls whether to remove loops. \c true |
|
368 ///means that loops will be removed. |
|
369 /// |
|
370 ///\note The <tt>Edge</tt>s |
|
371 ///referencing a moved edge remain |
|
372 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
|
373 ///may be invalidated. |
|
374 void contract(Node a,Node b,bool r=true) |
|
375 { |
|
376 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
|
377 OutEdgeIt f=e; |
|
378 ++f; |
|
379 if(r && target(e)==a) erase(e); |
|
380 else moveSource(e,a); |
|
381 e=f; |
|
382 } |
|
383 for(InEdgeIt e(*this,b);e!=INVALID;) { |
|
384 InEdgeIt f=e; |
|
385 ++f; |
|
386 if(r && source(e)==a) erase(e); |
|
387 else moveTarget(e,a); |
|
388 e=f; |
|
389 } |
|
390 erase(b); |
|
391 } |
|
392 |
|
393 ///Split a node. |
|
394 |
|
395 ///This function splits a node. First a new node is added to the graph, |
|
396 ///then the source of each outgoing edge of \c n is moved to this new node. |
|
397 ///If \c connect is \c true (this is the default value), then a new edge |
|
398 ///from \c n to the newly created node is also added. |
|
399 ///\return The newly created node. |
|
400 /// |
|
401 ///\note The <tt>Edge</tt>s |
|
402 ///referencing a moved edge remain |
|
403 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
|
404 ///may be invalidated. |
|
405 ///\warning This functionality cannot be used together with the SnapShot |
|
406 ///feature. |
|
407 ///\todo It could be implemented in a bit faster way. |
|
408 Node split(Node n, bool connect = true) |
|
409 { |
|
410 Node b = addNode(); |
|
411 for(OutEdgeIt e(*this,n);e!=INVALID;) { |
|
412 OutEdgeIt f=e; |
|
413 ++f; |
|
414 moveSource(e,b); |
|
415 e=f; |
|
416 } |
|
417 if(connect) addEdge(n,b); |
|
418 return b; |
|
419 } |
|
420 |
|
421 ///Class to make a snapshot of the graph and to restrore to it later. |
|
422 |
|
423 ///Class to make a snapshot of the graph and to restrore to it later. |
|
424 /// |
|
425 ///The newly added nodes and edges can be removed using the |
|
426 ///restore() function. |
|
427 /// |
|
428 ///\warning Edge and node deletions cannot be restored. |
|
429 ///\warning SnapShots cannot be nested. |
|
430 ///\todo \c SnapShot or \c Snapshot? |
|
431 class SnapShot : protected AlterationNotifier<Node>::ObserverBase, |
|
432 protected AlterationNotifier<Edge>::ObserverBase |
|
433 { |
|
434 protected: |
|
435 |
|
436 ListGraph *g; |
|
437 std::list<Node> added_nodes; |
|
438 std::list<Edge> added_edges; |
|
439 |
|
440 bool active; |
|
441 virtual void add(const Node& n) { |
|
442 added_nodes.push_back(n); |
|
443 }; |
|
444 ///\bug Exception... |
|
445 /// |
|
446 virtual void erase(const Node&) |
|
447 { |
|
448 exit(1); |
|
449 } |
|
450 virtual void add(const Edge& n) { |
|
451 added_edges.push_back(n); |
|
452 }; |
|
453 ///\bug Exception... |
|
454 /// |
|
455 virtual void erase(const Edge&) |
|
456 { |
|
457 exit(1); |
|
458 } |
|
459 |
|
460 void regist(ListGraph &_g) { |
|
461 g=&_g; |
|
462 AlterationNotifier<Node>::ObserverBase:: |
|
463 attach(g->getNotifier(Node())); |
|
464 AlterationNotifier<Edge>::ObserverBase:: |
|
465 attach(g->getNotifier(Edge())); |
|
466 } |
|
467 |
|
468 void deregist() { |
|
469 AlterationNotifier<Node>::ObserverBase:: |
|
470 detach(); |
|
471 AlterationNotifier<Edge>::ObserverBase:: |
|
472 detach(); |
|
473 g=0; |
|
474 } |
|
475 |
|
476 public: |
|
477 ///Default constructur. |
|
478 |
|
479 ///Default constructur. |
|
480 ///To actually make a snapshot you must call save(). |
|
481 /// |
|
482 SnapShot() : g(0) {} |
|
483 ///Constructor that immediately makes a snapshot. |
|
484 |
|
485 ///This constructor immediately makes a snapshot of the graph. |
|
486 ///\param _g The graph we make a snapshot of. |
|
487 SnapShot(ListGraph &_g) { |
|
488 regist(_g); |
|
489 } |
|
490 ///\bug Is it necessary? |
|
491 /// |
|
492 ~SnapShot() |
|
493 { |
|
494 if(g) deregist(); |
|
495 } |
|
496 |
|
497 ///Make a snapshot. |
|
498 |
|
499 ///Make a snapshot of the graph. |
|
500 /// |
|
501 ///This function can be called more than once. In case of a repeated |
|
502 ///call, the previous snapshot gets lost. |
|
503 ///\param _g The graph we make the snapshot of. |
|
504 void save(ListGraph &_g) |
|
505 { |
|
506 if(g!=&_g) { |
|
507 if(g) deregist(); |
|
508 regist(_g); |
|
509 } |
|
510 added_nodes.clear(); |
|
511 added_edges.clear(); |
|
512 } |
|
513 |
|
514 ///Undo the changes until the last snapshot. |
|
515 |
|
516 ///Undo the changes until last snapshot created by save(). |
|
517 /// |
|
518 ///\todo This function might be called undo(). |
|
519 void restore() { |
|
520 deregist(); |
|
521 while(!added_edges.empty()) { |
|
522 g->erase(added_edges.front()); |
|
523 added_edges.pop_front(); |
|
524 } |
|
525 while(!added_nodes.empty()) { |
|
526 g->erase(added_nodes.front()); |
|
527 added_nodes.pop_front(); |
|
528 } |
|
529 } |
|
530 }; |
|
531 |
|
532 }; |
|
533 |
|
534 |
|
535 /**************** Undirected List Graph ****************/ |
|
536 |
|
537 typedef ErasableUndirGraphExtender< |
|
538 ClearableUndirGraphExtender< |
|
539 ExtendableUndirGraphExtender< |
|
540 MappableUndirGraphExtender< |
|
541 IterableUndirGraphExtender< |
|
542 AlterableUndirGraphExtender< |
|
543 UndirGraphExtender<ListGraphBase> > > > > > > ErasableUndirListGraphBase; |
|
544 |
|
545 ///An undirected list graph class. |
|
546 |
|
547 ///This is a simple and fast erasable undirected graph implementation. |
|
548 /// |
|
549 ///It conforms to the |
|
550 ///\ref concept::UndirGraph "UndirGraph" concept. |
|
551 /// |
|
552 ///\sa concept::UndirGraph. |
|
553 /// |
|
554 ///\todo SnapShot, reverseEdge(), moveTarget(), moveSource(), contract() |
|
555 ///haven't been implemented yet. |
|
556 /// |
|
557 class UndirListGraph : public ErasableUndirListGraphBase { |
|
558 }; |
|
559 |
|
560 |
|
561 /// @} |
|
562 } //namespace lemon |
|
563 |
|
564 |
|
565 #endif |
|