1.1 --- a/src/lemon/list_graph.h Fri Nov 19 18:17:25 2004 +0000
1.2 +++ b/src/lemon/list_graph.h Sat Nov 20 10:19:06 2004 +0000
1.3 @@ -31,6 +31,7 @@
1.4
1.5 #include <lemon/default_map.h>
1.6
1.7 +#include <list>
1.8
1.9 namespace lemon {
1.10
1.11 @@ -386,6 +387,119 @@
1.12 }
1.13 erase(b);
1.14 }
1.15 +
1.16 +
1.17 + ///Class to make a snapshot of the graph and to restrore to it later.
1.18 +
1.19 + ///Class to make a snapshot of the graph and to restrore to it later.
1.20 + ///
1.21 + ///The newly added nodes and edges can be removed using the
1.22 + ///restore() function.
1.23 + ///
1.24 + ///\warning Edge and node deletions cannot be restored.
1.25 + ///\warning SnapShots cannot be nested.
1.26 + ///\ingroup graphs
1.27 + class SnapShot : public AlterationObserverRegistry<Node>::ObserverBase,
1.28 + public AlterationObserverRegistry<Edge>::ObserverBase
1.29 + {
1.30 + protected:
1.31 +
1.32 + ListGraph *g;
1.33 + std::list<Node> added_nodes;
1.34 + std::list<Edge> added_edges;
1.35 +
1.36 + bool active;
1.37 + virtual void add(const Node& n) {
1.38 + added_nodes.push_back(n);
1.39 + };
1.40 + ///\bug Exception...
1.41 + ///
1.42 + virtual void erase(const Node&)
1.43 + {
1.44 + exit(1);
1.45 + }
1.46 + virtual void add(const Edge& n) {
1.47 + added_edges.push_back(n);
1.48 + };
1.49 + ///\bug Exception...
1.50 + ///
1.51 + virtual void erase(const Edge&)
1.52 + {
1.53 + exit(1);
1.54 + }
1.55 +
1.56 + void regist(ListGraph &_g) {
1.57 + g=&_g;
1.58 + AlterationObserverRegistry<Node>::ObserverBase::
1.59 + attach(g->node_observers);
1.60 + AlterationObserverRegistry<Edge>::ObserverBase::
1.61 + attach(g->edge_observers);
1.62 + }
1.63 +
1.64 + void deregist() {
1.65 + AlterationObserverRegistry<Node>::ObserverBase::
1.66 + detach();
1.67 + AlterationObserverRegistry<Edge>::ObserverBase::
1.68 + detach();
1.69 + g=0;
1.70 + }
1.71 +
1.72 + public:
1.73 + ///Default constructur.
1.74 +
1.75 + ///Default constructur.
1.76 + ///To actually make a snapshot you must call save().
1.77 + ///
1.78 + SnapShot() : g(0) {}
1.79 + ///Constructor that immediately makes a snapshot.
1.80 +
1.81 + ///This constructor immediately makes a snapshot of the graph.
1.82 + ///\param _g The graph we make a snapshot of.
1.83 + SnapShot(ListGraph &_g) {
1.84 + regist(_g);
1.85 + }
1.86 + ///\bug Is it necessary?
1.87 + ///
1.88 + ~SnapShot()
1.89 + {
1.90 + if(g) deregist();
1.91 + }
1.92 +
1.93 + ///Make a snapshot.
1.94 +
1.95 + ///Make a snapshot of the graph.
1.96 + ///
1.97 + ///This function can be called more than once. In case of a repeated
1.98 + ///call, the previous snapshot gets lost.
1.99 + ///\param _g The graph we make the snapshot of.
1.100 + void save(ListGraph &_g)
1.101 + {
1.102 + if(g!=&_g) {
1.103 + if(g) deregist();
1.104 + regist(_g);
1.105 + }
1.106 + added_nodes.clear();
1.107 + added_edges.clear();
1.108 + }
1.109 +
1.110 + ///Undo the changes until the last snapshot.
1.111 +
1.112 + ///Undo the changes until last snapshot created by save().
1.113 + ///
1.114 + ///\todo This function might be called undo().
1.115 + void restore() {
1.116 + deregist();
1.117 + while(!added_edges.empty()) {
1.118 + g->erase(added_edges.front());
1.119 + added_edges.pop_front();
1.120 + }
1.121 + while(!added_nodes.empty()) {
1.122 + g->erase(added_nodes.front());
1.123 + added_nodes.pop_front();
1.124 + }
1.125 + }
1.126 + };
1.127 +
1.128 };
1.129
1.130 /// @}
2.1 --- a/src/lemon/smart_graph.h Fri Nov 19 18:17:25 2004 +0000
2.2 +++ b/src/lemon/smart_graph.h Sat Nov 20 10:19:06 2004 +0000
2.3 @@ -260,50 +260,11 @@
2.4 return _findEdge(u,v,prev);
2.5 }
2.6
2.7 - ///Internal data structure to store snapshots
2.8 -
2.9 - ///\ingroup graphs
2.10 - ///\sa makeSnapShot()
2.11 - ///\sa rollBack()
2.12 - struct SnapShot
2.13 - {
2.14 - unsigned int node_num;
2.15 - unsigned int edge_num;
2.16 - };
2.17 -
2.18 - ///Make a snapshot of the graph.
2.19 + class SnapShot;
2.20 + friend class SnapShot;
2.21
2.22 - ///Make a snapshot of the graph.
2.23 - ///
2.24 - ///The newly added nodes and edges can be removed using the
2.25 - ///rollBack() function.
2.26 - ///
2.27 - ///\return An stucture SnapShot describing the pesent state of the
2.28 - ///graph.
2.29 - ///\note After you rolled back to a state, you cannot roll "back" to
2.30 - ///a later state, in other word you cannot add again the edges deleted
2.31 - ///by rollBack().
2.32 - ///\todo This function might be called saveState() or getState().
2.33 - SnapShot makeSnapShot()
2.34 - {
2.35 - SnapShot s;
2.36 - s.node_num=nodes.size();
2.37 - s.edge_num=edges.size();
2.38 - return s;
2.39 - }
2.40 -
2.41 - ///Undo the changes until a snapshot.
2.42 -
2.43 - ///Undo the changes until a snapshot created by makeSnapShot().
2.44 - ///
2.45 - ///\param s an internal stucture given back by makeSnapShot()
2.46 - ///\note After you rolled back to a state, you cannot "roll forward" to
2.47 - ///a later state, in other word you cannot add again the edges deleted
2.48 - ///by rollBack().
2.49 - ///
2.50 - ///\todo This function might be called undo().
2.51 -
2.52 - void rollBack(const SnapShot &s)
2.53 + protected:
2.54 + void restoreSnapShot(const SnapShot &s)
2.55 {
2.56 while(s.edge_num>edges.size()) {
2.57 edge_observers.erase(Edge(edges.size()-1));
2.58 @@ -316,7 +277,73 @@
2.59 node_observers.erase(Node(nodes.size()-1));
2.60 nodes.pop_back();
2.61 }
2.62 - }
2.63 + }
2.64 +
2.65 + public:
2.66 + ///Class to make a snapshot of the graph and to restrore to it later.
2.67 +
2.68 + ///Class to make a snapshot of the graph and to restrore to it later.
2.69 + ///
2.70 + ///The newly added nodes and edges can be removed using the
2.71 + ///restore() function.
2.72 + ///\note After you restore a state, you cannot restore
2.73 + ///a later state, in other word you cannot add again the edges deleted
2.74 + ///by restore() using another SnapShot instance.
2.75 + ///
2.76 + ///\ingroup graphs
2.77 + class SnapShot
2.78 + {
2.79 + SmartGraph *g;
2.80 + protected:
2.81 + friend class SmartGraph;
2.82 + unsigned int node_num;
2.83 + unsigned int edge_num;
2.84 + public:
2.85 + ///Default constructur.
2.86 +
2.87 + ///Default constructur.
2.88 + ///To actually make a snapshot you must call save().
2.89 + ///
2.90 + SnapShot() : g(0) {}
2.91 + ///Constructor that immediately makes a snapshot
2.92 +
2.93 + ///This constructor immediately makes a snapshot of the graph.
2.94 + ///\param _g The graph we make a snapshot of.
2.95 + SnapShot(SmartGraph &_g) :g(&_g) {
2.96 + node_num=g->nodes.size();
2.97 + edge_num=g->edges.size();
2.98 + }
2.99 +
2.100 + ///Make a snapshot.
2.101 +
2.102 + ///Make a snapshot of the graph.
2.103 + ///
2.104 + ///This function can be called more than once. In case of a repeated
2.105 + ///call, the previous snapshot gets lost.
2.106 + ///\param _g The graph we make the snapshot of.
2.107 + void save(SmartGraph &_g)
2.108 + {
2.109 + g=&_g;
2.110 + node_num=g->nodes.size();
2.111 + edge_num=g->edges.size();
2.112 + }
2.113 +
2.114 + ///Undo the changes until a snapshot.
2.115 +
2.116 + ///Undo the changes until a snapshot created by save().
2.117 + ///
2.118 + ///\param s an internal stucture given back by save()
2.119 + ///\note After you restored a state, you cannot restore
2.120 + ///a later state, in other word you cannot add again the edges deleted
2.121 + ///by restore().
2.122 + ///
2.123 + ///\todo This function might be called undo().
2.124 +
2.125 + void restore()
2.126 + {
2.127 + g->restoreSnapShot(*this);
2.128 + }
2.129 + };
2.130 };
2.131
2.132 /// @}