1 /* -*- C++ -*- |
|
2 * src/lemon/smart_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_SMART_GRAPH_H |
|
18 #define LEMON_SMART_GRAPH_H |
|
19 |
|
20 ///\ingroup graphs |
|
21 ///\file |
|
22 ///\brief SmartGraph and SymSmartGraph classes. |
|
23 |
|
24 #include <vector> |
|
25 |
|
26 #include <lemon/invalid.h> |
|
27 |
|
28 #include <lemon/bits/clearable_graph_extender.h> |
|
29 #include <lemon/bits/extendable_graph_extender.h> |
|
30 #include <lemon/bits/iterable_graph_extender.h> |
|
31 #include <lemon/bits/alteration_notifier.h> |
|
32 #include <lemon/bits/default_map.h> |
|
33 |
|
34 #include <lemon/bits/undir_graph_extender.h> |
|
35 |
|
36 #include <lemon/utility.h> |
|
37 |
|
38 namespace lemon { |
|
39 |
|
40 class SmartGraph; |
|
41 ///Base of SmartGraph |
|
42 |
|
43 ///Base of SmartGraph |
|
44 /// |
|
45 class SmartGraphBase { |
|
46 |
|
47 friend class SmatGraph; |
|
48 |
|
49 protected: |
|
50 struct NodeT |
|
51 { |
|
52 int first_in,first_out; |
|
53 NodeT() : first_in(-1), first_out(-1) {} |
|
54 }; |
|
55 struct EdgeT |
|
56 { |
|
57 int target, source, next_in, next_out; |
|
58 //FIXME: is this necessary? |
|
59 EdgeT() : next_in(-1), next_out(-1) {} |
|
60 }; |
|
61 |
|
62 std::vector<NodeT> nodes; |
|
63 |
|
64 std::vector<EdgeT> edges; |
|
65 |
|
66 |
|
67 public: |
|
68 |
|
69 typedef SmartGraphBase Graph; |
|
70 |
|
71 class Node; |
|
72 class Edge; |
|
73 |
|
74 |
|
75 public: |
|
76 |
|
77 SmartGraphBase() : nodes(), edges() { } |
|
78 SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { } |
|
79 |
|
80 typedef True NodeNumTag; |
|
81 typedef True EdgeNumTag; |
|
82 |
|
83 ///Number of nodes. |
|
84 int nodeNum() const { return nodes.size(); } |
|
85 ///Number of edges. |
|
86 int edgeNum() const { return edges.size(); } |
|
87 |
|
88 /// Maximum node ID. |
|
89 |
|
90 /// Maximum node ID. |
|
91 ///\sa id(Node) |
|
92 int maxId(Node = INVALID) const { return nodes.size()-1; } |
|
93 /// Maximum edge ID. |
|
94 |
|
95 /// Maximum edge ID. |
|
96 ///\sa id(Edge) |
|
97 int maxId(Edge = INVALID) const { return edges.size()-1; } |
|
98 |
|
99 Node source(Edge e) const { return edges[e.n].source; } |
|
100 Node target(Edge e) const { return edges[e.n].target; } |
|
101 |
|
102 /// Node ID. |
|
103 |
|
104 /// The ID of a valid Node is a nonnegative integer not greater than |
|
105 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
106 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
107 /// |
|
108 /// The ID of the \ref INVALID node is -1. |
|
109 ///\return The ID of the node \c v. |
|
110 static int id(Node v) { return v.n; } |
|
111 /// Edge ID. |
|
112 |
|
113 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
114 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
115 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
116 /// |
|
117 /// The ID of the \ref INVALID edge is -1. |
|
118 ///\return The ID of the edge \c e. |
|
119 static int id(Edge e) { return e.n; } |
|
120 |
|
121 static Node fromId(int id, Node) { return Node(id);} |
|
122 |
|
123 static Edge fromId(int id, Edge) { return Edge(id);} |
|
124 |
|
125 Node addNode() { |
|
126 Node n; n.n=nodes.size(); |
|
127 nodes.push_back(NodeT()); //FIXME: Hmmm... |
|
128 return n; |
|
129 } |
|
130 |
|
131 Edge addEdge(Node u, Node v) { |
|
132 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... |
|
133 edges[e.n].source=u.n; edges[e.n].target=v.n; |
|
134 edges[e.n].next_out=nodes[u.n].first_out; |
|
135 edges[e.n].next_in=nodes[v.n].first_in; |
|
136 nodes[u.n].first_out=nodes[v.n].first_in=e.n; |
|
137 |
|
138 return e; |
|
139 } |
|
140 |
|
141 void clear() { |
|
142 edges.clear(); |
|
143 nodes.clear(); |
|
144 } |
|
145 |
|
146 |
|
147 class Node { |
|
148 friend class SmartGraphBase; |
|
149 friend class SmartGraph; |
|
150 |
|
151 protected: |
|
152 int n; |
|
153 ///\todo It should be removed (or at least define a setToId() instead). |
|
154 /// |
|
155 Node(int nn) {n=nn;} |
|
156 public: |
|
157 Node() {} |
|
158 Node (Invalid) { n=-1; } |
|
159 bool operator==(const Node i) const {return n==i.n;} |
|
160 bool operator!=(const Node i) const {return n!=i.n;} |
|
161 bool operator<(const Node i) const {return n<i.n;} |
|
162 }; |
|
163 |
|
164 |
|
165 class Edge { |
|
166 friend class SmartGraphBase; |
|
167 friend class SmartGraph; |
|
168 |
|
169 protected: |
|
170 int n; |
|
171 ///\todo It should be removed (or at least define a setToId() instead). |
|
172 /// |
|
173 Edge(int nn) {n=nn;} |
|
174 public: |
|
175 Edge() { } |
|
176 Edge (Invalid) { n=-1; } |
|
177 bool operator==(const Edge i) const {return n==i.n;} |
|
178 bool operator!=(const Edge i) const {return n!=i.n;} |
|
179 bool operator<(const Edge i) const {return n<i.n;} |
|
180 }; |
|
181 |
|
182 void first(Node& node) const { |
|
183 node.n = nodes.size() - 1; |
|
184 } |
|
185 |
|
186 static void next(Node& node) { |
|
187 --node.n; |
|
188 } |
|
189 |
|
190 void first(Edge& edge) const { |
|
191 edge.n = edges.size() - 1; |
|
192 } |
|
193 |
|
194 static void next(Edge& edge) { |
|
195 --edge.n; |
|
196 } |
|
197 |
|
198 void firstOut(Edge& edge, const Node& node) const { |
|
199 edge.n = nodes[node.n].first_out; |
|
200 } |
|
201 |
|
202 void nextOut(Edge& edge) const { |
|
203 edge.n = edges[edge.n].next_out; |
|
204 } |
|
205 |
|
206 void firstIn(Edge& edge, const Node& node) const { |
|
207 edge.n = nodes[node.n].first_in; |
|
208 } |
|
209 |
|
210 void nextIn(Edge& edge) const { |
|
211 edge.n = edges[edge.n].next_in; |
|
212 } |
|
213 |
|
214 Edge _findEdge(Node u,Node v, Edge prev = INVALID) |
|
215 { |
|
216 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; |
|
217 while(e!=-1 && edges[e].target!=v.n) e = edges[e].next_out; |
|
218 prev.n=e; |
|
219 return prev; |
|
220 } |
|
221 |
|
222 Node _split(Node n, bool connect = true) |
|
223 { |
|
224 Node b = addNode(); |
|
225 nodes[b.n].first_out=nodes[n.n].first_out; |
|
226 nodes[n.n].first_out=-1; |
|
227 for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n; |
|
228 if(connect) addEdge(n,b); |
|
229 return b; |
|
230 } |
|
231 |
|
232 }; |
|
233 |
|
234 typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase; |
|
235 typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase; |
|
236 typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase; |
|
237 typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase; |
|
238 typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase; |
|
239 |
|
240 /// \addtogroup graphs |
|
241 /// @{ |
|
242 |
|
243 ///A smart graph class. |
|
244 |
|
245 ///This is a simple and fast graph implementation. |
|
246 ///It is also quite memory efficient, but at the price |
|
247 ///that <b> it does support only limited (only stack-like) |
|
248 ///node and edge deletions</b>. |
|
249 ///It conforms to |
|
250 ///the \ref concept::ExtendableGraph "ExtendableGraph" concept. |
|
251 ///\sa concept::ExtendableGraph. |
|
252 /// |
|
253 ///\author Alpar Juttner |
|
254 class SmartGraph : public ClearableSmartGraphBase { |
|
255 public: |
|
256 /// Finds an edge between two nodes. |
|
257 |
|
258 /// Finds an edge from node \c u to node \c v. |
|
259 /// |
|
260 /// If \c prev is \ref INVALID (this is the default value), then |
|
261 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
|
262 /// the next edge from \c u to \c v after \c prev. |
|
263 /// \return The found edge or \ref INVALID if there is no such an edge. |
|
264 /// |
|
265 /// Thus you can iterate through each edge from \c u to \c v as it follows. |
|
266 /// \code |
|
267 /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) { |
|
268 /// ... |
|
269 /// } |
|
270 /// \endcode |
|
271 /// \todo Possibly it should be a global function. |
|
272 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
273 { |
|
274 return _findEdge(u,v,prev); |
|
275 } |
|
276 |
|
277 class SnapShot; |
|
278 friend class SnapShot; |
|
279 |
|
280 protected: |
|
281 void restoreSnapShot(const SnapShot &s) |
|
282 { |
|
283 while(s.edge_num>edges.size()) { |
|
284 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1)); |
|
285 nodes[edges.back().target].first_in=edges.back().next_in; |
|
286 nodes[edges.back().source].first_out=edges.back().next_out; |
|
287 edges.pop_back(); |
|
288 } |
|
289 //nodes.resize(s.nodes_num); |
|
290 while(s.node_num>nodes.size()) { |
|
291 Parent::getNotifier(Node()).erase(Node(nodes.size()-1)); |
|
292 nodes.pop_back(); |
|
293 } |
|
294 } |
|
295 |
|
296 public: |
|
297 |
|
298 ///Split a node. |
|
299 |
|
300 ///This function splits a node. First a new node is added to the graph, |
|
301 ///then the source of each outgoing edge of \c n is moved to this new node. |
|
302 ///If \c connect is \c true (this is the default value), then a new edge |
|
303 ///from \c n to the newly created node is also added. |
|
304 ///\return The newly created node. |
|
305 /// |
|
306 ///\note The <tt>Edge</tt>s |
|
307 ///referencing a moved edge remain |
|
308 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
|
309 ///may be invalidated. |
|
310 ///\warning This functionality cannot be used together with the SnapShot |
|
311 ///feature. |
|
312 ///\todo It could be implemented in a bit faster way. |
|
313 Node split(Node n, bool connect = true) |
|
314 { |
|
315 return _split(n,connect); |
|
316 } |
|
317 |
|
318 |
|
319 ///Class to make a snapshot of the graph and to restrore to it later. |
|
320 |
|
321 ///Class to make a snapshot of the graph and to restrore to it later. |
|
322 /// |
|
323 ///The newly added nodes and edges can be removed using the |
|
324 ///restore() function. |
|
325 ///\note After you restore a state, you cannot restore |
|
326 ///a later state, in other word you cannot add again the edges deleted |
|
327 ///by restore() using another SnapShot instance. |
|
328 /// |
|
329 class SnapShot |
|
330 { |
|
331 SmartGraph *g; |
|
332 protected: |
|
333 friend class SmartGraph; |
|
334 unsigned int node_num; |
|
335 unsigned int edge_num; |
|
336 public: |
|
337 ///Default constructor. |
|
338 |
|
339 ///Default constructor. |
|
340 ///To actually make a snapshot you must call save(). |
|
341 /// |
|
342 SnapShot() : g(0) {} |
|
343 ///Constructor that immediately makes a snapshot |
|
344 |
|
345 ///This constructor immediately makes a snapshot of the graph. |
|
346 ///\param _g The graph we make a snapshot of. |
|
347 SnapShot(SmartGraph &_g) :g(&_g) { |
|
348 node_num=g->nodes.size(); |
|
349 edge_num=g->edges.size(); |
|
350 } |
|
351 |
|
352 ///Make a snapshot. |
|
353 |
|
354 ///Make a snapshot of the graph. |
|
355 /// |
|
356 ///This function can be called more than once. In case of a repeated |
|
357 ///call, the previous snapshot gets lost. |
|
358 ///\param _g The graph we make the snapshot of. |
|
359 void save(SmartGraph &_g) |
|
360 { |
|
361 g=&_g; |
|
362 node_num=g->nodes.size(); |
|
363 edge_num=g->edges.size(); |
|
364 } |
|
365 |
|
366 ///Undo the changes until a snapshot. |
|
367 |
|
368 ///Undo the changes until a snapshot created by save(). |
|
369 /// |
|
370 ///\param s an internal stucture given back by save() |
|
371 ///\note After you restored a state, you cannot restore |
|
372 ///a later state, in other word you cannot add again the edges deleted |
|
373 ///by restore(). |
|
374 /// |
|
375 ///\todo This function might be called undo(). |
|
376 |
|
377 void restore() |
|
378 { |
|
379 g->restoreSnapShot(*this); |
|
380 } |
|
381 }; |
|
382 }; |
|
383 |
|
384 |
|
385 /**************** Undirected List Graph ****************/ |
|
386 |
|
387 typedef ClearableUndirGraphExtender< |
|
388 ExtendableUndirGraphExtender< |
|
389 MappableUndirGraphExtender< |
|
390 IterableUndirGraphExtender< |
|
391 AlterableUndirGraphExtender< |
|
392 UndirGraphExtender<SmartGraphBase> > > > > > UndirSmartGraphBase; |
|
393 |
|
394 ///A smart undirected graph class. |
|
395 |
|
396 ///This is a simple and fast undirected graph implementation. |
|
397 ///It is also quite memory efficient, but at the price |
|
398 ///that <b> it does support only limited (only stack-like) |
|
399 ///node and edge deletions</b>. |
|
400 ///Except from this it conforms to |
|
401 ///the \ref concept::UndirGraph "UndirGraph" concept. |
|
402 ///\sa concept::UndirGraph. |
|
403 /// |
|
404 ///\todo SnapShot hasn't been implemented yet. |
|
405 /// |
|
406 class UndirSmartGraph : public UndirSmartGraphBase { |
|
407 }; |
|
408 |
|
409 |
|
410 /// @} |
|
411 } //namespace lemon |
|
412 |
|
413 |
|
414 #endif //LEMON_SMART_GRAPH_H |
|