258 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
258 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
259 { |
259 { |
260 return _findEdge(u,v,prev); |
260 return _findEdge(u,v,prev); |
261 } |
261 } |
262 |
262 |
263 ///Internal data structure to store snapshots |
263 class SnapShot; |
264 |
264 friend class SnapShot; |
265 ///\ingroup graphs |
265 |
266 ///\sa makeSnapShot() |
266 protected: |
267 ///\sa rollBack() |
267 void restoreSnapShot(const SnapShot &s) |
268 struct SnapShot |
|
269 { |
|
270 unsigned int node_num; |
|
271 unsigned int edge_num; |
|
272 }; |
|
273 |
|
274 ///Make a snapshot of the graph. |
|
275 |
|
276 ///Make a snapshot of the graph. |
|
277 /// |
|
278 ///The newly added nodes and edges can be removed using the |
|
279 ///rollBack() function. |
|
280 /// |
|
281 ///\return An stucture SnapShot describing the pesent state of the |
|
282 ///graph. |
|
283 ///\note After you rolled back to a state, you cannot roll "back" to |
|
284 ///a later state, in other word you cannot add again the edges deleted |
|
285 ///by rollBack(). |
|
286 ///\todo This function might be called saveState() or getState(). |
|
287 SnapShot makeSnapShot() |
|
288 { |
|
289 SnapShot s; |
|
290 s.node_num=nodes.size(); |
|
291 s.edge_num=edges.size(); |
|
292 return s; |
|
293 } |
|
294 |
|
295 ///Undo the changes until a snapshot. |
|
296 |
|
297 ///Undo the changes until a snapshot created by makeSnapShot(). |
|
298 /// |
|
299 ///\param s an internal stucture given back by makeSnapShot() |
|
300 ///\note After you rolled back to a state, you cannot "roll forward" to |
|
301 ///a later state, in other word you cannot add again the edges deleted |
|
302 ///by rollBack(). |
|
303 /// |
|
304 ///\todo This function might be called undo(). |
|
305 |
|
306 void rollBack(const SnapShot &s) |
|
307 { |
268 { |
308 while(s.edge_num>edges.size()) { |
269 while(s.edge_num>edges.size()) { |
309 edge_observers.erase(Edge(edges.size()-1)); |
270 edge_observers.erase(Edge(edges.size()-1)); |
310 nodes[edges.back().target].first_in=edges.back().next_in; |
271 nodes[edges.back().target].first_in=edges.back().next_in; |
311 nodes[edges.back().source].first_out=edges.back().next_out; |
272 nodes[edges.back().source].first_out=edges.back().next_out; |
314 //nodes.resize(s.nodes_num); |
275 //nodes.resize(s.nodes_num); |
315 while(s.node_num>nodes.size()) { |
276 while(s.node_num>nodes.size()) { |
316 node_observers.erase(Node(nodes.size()-1)); |
277 node_observers.erase(Node(nodes.size()-1)); |
317 nodes.pop_back(); |
278 nodes.pop_back(); |
318 } |
279 } |
319 } |
280 } |
|
281 |
|
282 public: |
|
283 ///Class to make a snapshot of the graph and to restrore to it later. |
|
284 |
|
285 ///Class to make a snapshot of the graph and to restrore to it later. |
|
286 /// |
|
287 ///The newly added nodes and edges can be removed using the |
|
288 ///restore() function. |
|
289 ///\note After you restore a state, you cannot restore |
|
290 ///a later state, in other word you cannot add again the edges deleted |
|
291 ///by restore() using another SnapShot instance. |
|
292 /// |
|
293 ///\ingroup graphs |
|
294 class SnapShot |
|
295 { |
|
296 SmartGraph *g; |
|
297 protected: |
|
298 friend class SmartGraph; |
|
299 unsigned int node_num; |
|
300 unsigned int edge_num; |
|
301 public: |
|
302 ///Default constructur. |
|
303 |
|
304 ///Default constructur. |
|
305 ///To actually make a snapshot you must call save(). |
|
306 /// |
|
307 SnapShot() : g(0) {} |
|
308 ///Constructor that immediately makes a snapshot |
|
309 |
|
310 ///This constructor immediately makes a snapshot of the graph. |
|
311 ///\param _g The graph we make a snapshot of. |
|
312 SnapShot(SmartGraph &_g) :g(&_g) { |
|
313 node_num=g->nodes.size(); |
|
314 edge_num=g->edges.size(); |
|
315 } |
|
316 |
|
317 ///Make a snapshot. |
|
318 |
|
319 ///Make a snapshot of the graph. |
|
320 /// |
|
321 ///This function can be called more than once. In case of a repeated |
|
322 ///call, the previous snapshot gets lost. |
|
323 ///\param _g The graph we make the snapshot of. |
|
324 void save(SmartGraph &_g) |
|
325 { |
|
326 g=&_g; |
|
327 node_num=g->nodes.size(); |
|
328 edge_num=g->edges.size(); |
|
329 } |
|
330 |
|
331 ///Undo the changes until a snapshot. |
|
332 |
|
333 ///Undo the changes until a snapshot created by save(). |
|
334 /// |
|
335 ///\param s an internal stucture given back by save() |
|
336 ///\note After you restored a state, you cannot restore |
|
337 ///a later state, in other word you cannot add again the edges deleted |
|
338 ///by restore(). |
|
339 /// |
|
340 ///\todo This function might be called undo(). |
|
341 |
|
342 void restore() |
|
343 { |
|
344 g->restoreSnapShot(*this); |
|
345 } |
|
346 }; |
320 }; |
347 }; |
321 |
348 |
322 /// @} |
349 /// @} |
323 } //namespace lemon |
350 } //namespace lemon |
324 |
351 |