1.1 --- a/lemon/list_graph.h Thu Jan 11 21:05:00 2007 +0000
1.2 +++ b/lemon/list_graph.h Thu Jan 11 21:06:47 2007 +0000
1.3 @@ -98,16 +98,7 @@
1.4 first_free_node(-1), edges(), first_free_edge(-1) {}
1.5
1.6
1.7 - /// Maximum node ID.
1.8 -
1.9 - /// Maximum node ID.
1.10 - ///\sa id(Node)
1.11 int maxNodeId() const { return nodes.size()-1; }
1.12 -
1.13 - /// Maximum edge ID.
1.14 -
1.15 - /// Maximum edge ID.
1.16 - ///\sa id(Edge)
1.17 int maxEdgeId() const { return edges.size()-1; }
1.18
1.19 Node source(Edge e) const { return Node(edges[e.id].source); }
1.20 @@ -164,12 +155,6 @@
1.21 static Node nodeFromId(int id) { return Node(id);}
1.22 static Edge edgeFromId(int id) { return Edge(id);}
1.23
1.24 - /// Adds a new node to the graph.
1.25 -
1.26 - /// Adds a new node to the graph.
1.27 - ///
1.28 - /// \warning It adds the new node to the front of the list.
1.29 - /// (i.e. the lastly added node becomes the first.)
1.30 Node addNode() {
1.31 int n;
1.32
1.33 @@ -735,10 +720,368 @@
1.34
1.35 ///@}
1.36
1.37 - /**************** Undirected List Graph ****************/
1.38 + class ListUGraphBase {
1.39
1.40 - typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1.41 - ExtendedListUGraphBase;
1.42 + protected:
1.43 +
1.44 + struct NodeT {
1.45 + int first_out;
1.46 + int prev, next;
1.47 + };
1.48 +
1.49 + struct EdgeT {
1.50 + int target;
1.51 + int prev_out, next_out;
1.52 + };
1.53 +
1.54 + std::vector<NodeT> nodes;
1.55 +
1.56 + int first_node;
1.57 +
1.58 + int first_free_node;
1.59 +
1.60 + std::vector<EdgeT> edges;
1.61 +
1.62 + int first_free_edge;
1.63 +
1.64 + public:
1.65 +
1.66 + typedef ListUGraphBase Graph;
1.67 +
1.68 + class Node {
1.69 + friend class ListUGraphBase;
1.70 + protected:
1.71 +
1.72 + int id;
1.73 + explicit Node(int pid) { id = pid;}
1.74 +
1.75 + public:
1.76 + Node() {}
1.77 + Node (Invalid) { id = -1; }
1.78 + bool operator==(const Node& node) const {return id == node.id;}
1.79 + bool operator!=(const Node& node) const {return id != node.id;}
1.80 + bool operator<(const Node& node) const {return id < node.id;}
1.81 + };
1.82 +
1.83 + class UEdge {
1.84 + friend class ListUGraphBase;
1.85 + protected:
1.86 +
1.87 + int id;
1.88 + explicit UEdge(int pid) { id = pid;}
1.89 +
1.90 + public:
1.91 + UEdge() {}
1.92 + UEdge (Invalid) { id = -1; }
1.93 + bool operator==(const UEdge& edge) const {return id == edge.id;}
1.94 + bool operator!=(const UEdge& edge) const {return id != edge.id;}
1.95 + bool operator<(const UEdge& edge) const {return id < edge.id;}
1.96 + };
1.97 +
1.98 + class Edge {
1.99 + friend class ListUGraphBase;
1.100 + protected:
1.101 +
1.102 + int id;
1.103 + explicit Edge(int pid) { id = pid;}
1.104 +
1.105 + public:
1.106 + operator UEdge() const { return UEdge(id / 2); }
1.107 +
1.108 + Edge() {}
1.109 + Edge (Invalid) { id = -1; }
1.110 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.111 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.112 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.113 + };
1.114 +
1.115 +
1.116 +
1.117 + ListUGraphBase()
1.118 + : nodes(), first_node(-1),
1.119 + first_free_node(-1), edges(), first_free_edge(-1) {}
1.120 +
1.121 +
1.122 + int maxNodeId() const { return nodes.size()-1; }
1.123 + int maxUEdgeId() const { return edges.size() / 2 - 1; }
1.124 + int maxEdgeId() const { return edges.size()-1; }
1.125 +
1.126 + Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
1.127 + Node target(Edge e) const { return Node(edges[e.id].target); }
1.128 +
1.129 + Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
1.130 + Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
1.131 +
1.132 + static bool direction(Edge e) {
1.133 + return (e.id & 1) == 1;
1.134 + }
1.135 +
1.136 + static Edge direct(UEdge e, bool d) {
1.137 + return Edge(e.id * 2 + (d ? 1 : 0));
1.138 + }
1.139 +
1.140 + void first(Node& node) const {
1.141 + node.id = first_node;
1.142 + }
1.143 +
1.144 + void next(Node& node) const {
1.145 + node.id = nodes[node.id].next;
1.146 + }
1.147 +
1.148 + void first(Edge& e) const {
1.149 + int n = first_node;
1.150 + while (n != -1 && nodes[n].first_out == -1) {
1.151 + n = nodes[n].next;
1.152 + }
1.153 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.154 + }
1.155 +
1.156 + void next(Edge& e) const {
1.157 + if (edges[e.id].next_out != -1) {
1.158 + e.id = edges[e.id].next_out;
1.159 + } else {
1.160 + int n = nodes[edges[e.id ^ 1].target].next;
1.161 + while(n != -1 && nodes[n].first_out == -1) {
1.162 + n = nodes[n].next;
1.163 + }
1.164 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.165 + }
1.166 + }
1.167 +
1.168 + void first(UEdge& e) const {
1.169 + int n = first_node;
1.170 + while (n != -1) {
1.171 + e.id = nodes[n].first_out;
1.172 + while ((e.id & 1) != 1) {
1.173 + e.id = edges[e.id].next_out;
1.174 + }
1.175 + if (e.id != -1) {
1.176 + e.id /= 2;
1.177 + return;
1.178 + }
1.179 + n = nodes[n].next;
1.180 + }
1.181 + e.id = -1;
1.182 + }
1.183 +
1.184 + void next(UEdge& e) const {
1.185 + int n = edges[e.id * 2].target;
1.186 + e.id = edges[(e.id * 2) | 1].next_out;
1.187 + while ((e.id & 1) != 1) {
1.188 + e.id = edges[e.id].next_out;
1.189 + }
1.190 + if (e.id != -1) {
1.191 + e.id /= 2;
1.192 + return;
1.193 + }
1.194 + n = nodes[n].next;
1.195 + while (n != -1) {
1.196 + e.id = nodes[n].first_out;
1.197 + while ((e.id & 1) != 1) {
1.198 + e.id = edges[e.id].next_out;
1.199 + }
1.200 + if (e.id != -1) {
1.201 + e.id /= 2;
1.202 + return;
1.203 + }
1.204 + n = nodes[n].next;
1.205 + }
1.206 + e.id = -1;
1.207 + }
1.208 +
1.209 + void firstOut(Edge &e, const Node& v) const {
1.210 + e.id = nodes[v.id].first_out;
1.211 + }
1.212 + void nextOut(Edge &e) const {
1.213 + e.id = edges[e.id].next_out;
1.214 + }
1.215 +
1.216 + void firstIn(Edge &e, const Node& v) const {
1.217 + e.id = ((nodes[v.id].first_out) ^ 1);
1.218 + if (e.id == -2) e.id = -1;
1.219 + }
1.220 + void nextIn(Edge &e) const {
1.221 + e.id = ((edges[e.id ^ 1].next_out) ^ 1);
1.222 + if (e.id == -2) e.id = -1;
1.223 + }
1.224 +
1.225 + void firstInc(UEdge &e, bool& d, const Node& v) const {
1.226 + int de = nodes[v.id].first_out;
1.227 + e.id = de / 2;
1.228 + d = ((de & 1) == 1);
1.229 + }
1.230 + void nextInc(UEdge &e, bool& d) const {
1.231 + int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
1.232 + e.id = de / 2;
1.233 + d = ((de & 1) == 1);
1.234 + }
1.235 +
1.236 + static int id(Node v) { return v.id; }
1.237 + static int id(Edge e) { return e.id; }
1.238 + static int id(UEdge e) { return e.id; }
1.239 +
1.240 + static Node nodeFromId(int id) { return Node(id);}
1.241 + static Edge edgeFromId(int id) { return Edge(id);}
1.242 + static UEdge uEdgeFromId(int id) { return UEdge(id);}
1.243 +
1.244 + Node addNode() {
1.245 + int n;
1.246 +
1.247 + if(first_free_node==-1) {
1.248 + n = nodes.size();
1.249 + nodes.push_back(NodeT());
1.250 + } else {
1.251 + n = first_free_node;
1.252 + first_free_node = nodes[n].next;
1.253 + }
1.254 +
1.255 + nodes[n].next = first_node;
1.256 + if (first_node != -1) nodes[first_node].prev = n;
1.257 + first_node = n;
1.258 + nodes[n].prev = -1;
1.259 +
1.260 + nodes[n].first_out = -1;
1.261 +
1.262 + return Node(n);
1.263 + }
1.264 +
1.265 + UEdge addEdge(Node u, Node v) {
1.266 + int n;
1.267 +
1.268 + if (first_free_edge == -1) {
1.269 + n = edges.size();
1.270 + edges.push_back(EdgeT());
1.271 + edges.push_back(EdgeT());
1.272 + } else {
1.273 + n = first_free_edge;
1.274 + first_free_edge = edges[n].next_out;
1.275 + }
1.276 +
1.277 + edges[n].target = u.id;
1.278 + edges[n | 1].target = v.id;
1.279 +
1.280 + edges[n].next_out = nodes[v.id].first_out;
1.281 + edges[n | 1].next_out = nodes[u.id].first_out;
1.282 + if (nodes[v.id].first_out != -1) {
1.283 + edges[nodes[v.id].first_out].prev_out = n;
1.284 + }
1.285 + if (nodes[u.id].first_out != -1) {
1.286 + edges[nodes[u.id].first_out].prev_out = (n | 1);
1.287 + }
1.288 +
1.289 + edges[n].prev_out = edges[n | 1].prev_out = -1;
1.290 +
1.291 + nodes[v.id].first_out = n;
1.292 + nodes[u.id].first_out = (n | 1);
1.293 +
1.294 + return UEdge(n / 2);
1.295 + }
1.296 +
1.297 + void erase(const Node& node) {
1.298 + int n = node.id;
1.299 +
1.300 + if(nodes[n].next != -1) {
1.301 + nodes[nodes[n].next].prev = nodes[n].prev;
1.302 + }
1.303 +
1.304 + if(nodes[n].prev != -1) {
1.305 + nodes[nodes[n].prev].next = nodes[n].next;
1.306 + } else {
1.307 + first_node = nodes[n].next;
1.308 + }
1.309 +
1.310 + nodes[n].next = first_free_node;
1.311 + first_free_node = n;
1.312 +
1.313 + }
1.314 +
1.315 + void erase(const UEdge& edge) {
1.316 + int n = edge.id * 2;
1.317 +
1.318 + if (edges[n].next_out != -1) {
1.319 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.320 + }
1.321 +
1.322 + if (edges[n].prev_out != -1) {
1.323 + edges[edges[n].prev_out].next_out = edges[n].next_out;
1.324 + } else {
1.325 + nodes[edges[n | 1].target].first_out = edges[n].next_out;
1.326 + }
1.327 +
1.328 + if (edges[n | 1].next_out != -1) {
1.329 + edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
1.330 + }
1.331 +
1.332 + if (edges[n | 1].prev_out != -1) {
1.333 + edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
1.334 + } else {
1.335 + nodes[edges[n].target].first_out = edges[n | 1].next_out;
1.336 + }
1.337 +
1.338 + edges[n].next_out = first_free_edge;
1.339 + first_free_edge = n;
1.340 +
1.341 + }
1.342 +
1.343 + void clear() {
1.344 + edges.clear();
1.345 + nodes.clear();
1.346 + first_node = first_free_node = first_free_edge = -1;
1.347 + }
1.348 +
1.349 + protected:
1.350 +
1.351 + void changeTarget(UEdge e, Node n) {
1.352 + if(edges[2 * e.id].next_out != -1) {
1.353 + edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
1.354 + }
1.355 + if(edges[2 * e.id].prev_out != -1) {
1.356 + edges[edges[2 * e.id].prev_out].next_out =
1.357 + edges[2 * e.id].next_out;
1.358 + } else {
1.359 + nodes[edges[(2 * e.id) | 1].target].first_out =
1.360 + edges[2 * e.id].next_out;
1.361 + }
1.362 +
1.363 + if (nodes[n.id].first_out != -1) {
1.364 + edges[nodes[n.id].first_out].prev_out = 2 * e.id;
1.365 + }
1.366 + edges[(2 * e.id) | 1].target = n.id;
1.367 + edges[2 * e.id].prev_out = -1;
1.368 + edges[2 * e.id].next_out = nodes[n.id].first_out;
1.369 + nodes[n.id].first_out = 2 * e.id;
1.370 + }
1.371 +
1.372 + void changeSource(UEdge e, Node n) {
1.373 + if(edges[(2 * e.id) | 1].next_out != -1) {
1.374 + edges[edges[(2 * e.id) | 1].next_out].prev_out =
1.375 + edges[(2 * e.id) | 1].prev_out;
1.376 + }
1.377 + if(edges[(2 * e.id) | 1].prev_out != -1) {
1.378 + edges[edges[(2 * e.id) | 1].prev_out].next_out =
1.379 + edges[(2 * e.id) | 1].next_out;
1.380 + } else {
1.381 + nodes[edges[2 * e.id].target].first_out =
1.382 + edges[(2 * e.id) | 1].next_out;
1.383 + }
1.384 +
1.385 + if (nodes[n.id].first_out != -1) {
1.386 + edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.387 + }
1.388 + edges[2 * e.id].target = n.id;
1.389 + edges[(2 * e.id) | 1].prev_out = -1;
1.390 + edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.391 + nodes[n.id].first_out = ((2 * e.id) | 1);
1.392 + }
1.393 +
1.394 + };
1.395 +
1.396 +// typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1.397 +// ExtendedListUGraphBase;
1.398 +
1.399 + typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
1.400 +
1.401 +
1.402
1.403 /// \addtogroup graphs
1.404 /// @{
1.405 @@ -776,6 +1119,9 @@
1.406 ListUGraph() {}
1.407
1.408 typedef ExtendedListUGraphBase Parent;
1.409 +
1.410 + typedef Parent::OutEdgeIt IncEdgeIt;
1.411 +
1.412 /// \brief Add a new node to the graph.
1.413 ///
1.414 /// \return the new node.
2.1 --- a/lemon/smart_graph.h Thu Jan 11 21:05:00 2007 +0000
2.2 +++ b/lemon/smart_graph.h Thu Jan 11 21:06:47 2007 +0000
2.3 @@ -366,10 +366,191 @@
2.4 };
2.5
2.6
2.7 - /**************** Undirected List Graph ****************/
2.8 + class SmartUGraphBase {
2.9
2.10 - typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
2.11 - ExtendedSmartUGraphBase;
2.12 + protected:
2.13 +
2.14 + struct NodeT {
2.15 + int first_out;
2.16 + };
2.17 +
2.18 + struct EdgeT {
2.19 + int target;
2.20 + int next_out;
2.21 + };
2.22 +
2.23 + std::vector<NodeT> nodes;
2.24 + std::vector<EdgeT> edges;
2.25 +
2.26 + int first_free_edge;
2.27 +
2.28 + public:
2.29 +
2.30 + typedef SmartUGraphBase Graph;
2.31 +
2.32 + class Node {
2.33 + friend class SmartUGraphBase;
2.34 + protected:
2.35 +
2.36 + int id;
2.37 + explicit Node(int pid) { id = pid;}
2.38 +
2.39 + public:
2.40 + Node() {}
2.41 + Node (Invalid) { id = -1; }
2.42 + bool operator==(const Node& node) const {return id == node.id;}
2.43 + bool operator!=(const Node& node) const {return id != node.id;}
2.44 + bool operator<(const Node& node) const {return id < node.id;}
2.45 + };
2.46 +
2.47 + class UEdge {
2.48 + friend class SmartUGraphBase;
2.49 + protected:
2.50 +
2.51 + int id;
2.52 + explicit UEdge(int pid) { id = pid;}
2.53 +
2.54 + public:
2.55 + UEdge() {}
2.56 + UEdge (Invalid) { id = -1; }
2.57 + bool operator==(const UEdge& edge) const {return id == edge.id;}
2.58 + bool operator!=(const UEdge& edge) const {return id != edge.id;}
2.59 + bool operator<(const UEdge& edge) const {return id < edge.id;}
2.60 + };
2.61 +
2.62 + class Edge {
2.63 + friend class SmartUGraphBase;
2.64 + protected:
2.65 +
2.66 + int id;
2.67 + explicit Edge(int pid) { id = pid;}
2.68 +
2.69 + public:
2.70 + operator UEdge() const { return UEdge(id / 2); }
2.71 +
2.72 + Edge() {}
2.73 + Edge (Invalid) { id = -1; }
2.74 + bool operator==(const Edge& edge) const {return id == edge.id;}
2.75 + bool operator!=(const Edge& edge) const {return id != edge.id;}
2.76 + bool operator<(const Edge& edge) const {return id < edge.id;}
2.77 + };
2.78 +
2.79 +
2.80 +
2.81 + SmartUGraphBase()
2.82 + : nodes(), edges() {}
2.83 +
2.84 +
2.85 + int maxNodeId() const { return nodes.size()-1; }
2.86 + int maxUEdgeId() const { return edges.size() / 2 - 1; }
2.87 + int maxEdgeId() const { return edges.size()-1; }
2.88 +
2.89 + Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
2.90 + Node target(Edge e) const { return Node(edges[e.id].target); }
2.91 +
2.92 + Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
2.93 + Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
2.94 +
2.95 + static bool direction(Edge e) {
2.96 + return (e.id & 1) == 1;
2.97 + }
2.98 +
2.99 + static Edge direct(UEdge e, bool d) {
2.100 + return Edge(e.id * 2 + (d ? 1 : 0));
2.101 + }
2.102 +
2.103 + void first(Node& node) const {
2.104 + node.id = nodes.size() - 1;
2.105 + }
2.106 +
2.107 + void next(Node& node) const {
2.108 + --node.id;
2.109 + }
2.110 +
2.111 + void first(Edge& edge) const {
2.112 + edge.id = edges.size() - 1;
2.113 + }
2.114 +
2.115 + void next(Edge& edge) const {
2.116 + --edge.id;
2.117 + }
2.118 +
2.119 + void first(UEdge& edge) const {
2.120 + edge.id = edges.size() / 2 - 1;
2.121 + }
2.122 +
2.123 + void next(UEdge& edge) const {
2.124 + --edge.id;
2.125 + }
2.126 +
2.127 + void firstOut(Edge &edge, const Node& v) const {
2.128 + edge.id = nodes[v.id].first_out;
2.129 + }
2.130 + void nextOut(Edge &edge) const {
2.131 + edge.id = edges[edge.id].next_out;
2.132 + }
2.133 +
2.134 + void firstIn(Edge &edge, const Node& v) const {
2.135 + edge.id = ((nodes[v.id].first_out) ^ 1);
2.136 + if (e.id == -2) e.id = -1;
2.137 + }
2.138 + void nextIn(Edge &edge) const {
2.139 + edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
2.140 + if (e.id == -2) e.id = -1;
2.141 + }
2.142 +
2.143 + void firstInc(UEdge &edge, bool& d, const Node& v) const {
2.144 + int de = nodes[v.id].first_out;
2.145 + edge.id = de / 2;
2.146 + d = ((de & 1) == 1);
2.147 + }
2.148 + void nextInc(UEdge &edge, bool& d) const {
2.149 + int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
2.150 + edge.id = de / 2;
2.151 + d = ((de & 1) == 1);
2.152 + }
2.153 +
2.154 + static int id(Node v) { return v.id; }
2.155 + static int id(Edge e) { return e.id; }
2.156 + static int id(UEdge e) { return e.id; }
2.157 +
2.158 + static Node nodeFromId(int id) { return Node(id);}
2.159 + static Edge edgeFromId(int id) { return Edge(id);}
2.160 + static UEdge uEdgeFromId(int id) { return UEdge(id);}
2.161 +
2.162 + Node addNode() {
2.163 + int n = nodes.size();
2.164 + nodes.push_back(NodeT());
2.165 + nodes[n].first_out = -1;
2.166 +
2.167 + return Node(n);
2.168 + }
2.169 +
2.170 + UEdge addEdge(Node u, Node v) {
2.171 + int n = edges.size();
2.172 + edges.push_back(EdgeT());
2.173 + edges.push_back(EdgeT());
2.174 +
2.175 + edges[n].target = u.id;
2.176 + edges[n | 1].target = v.id;
2.177 +
2.178 + edges[n].next_out = nodes[v.id].first_out;
2.179 + edges[n | 1].next_out = nodes[u.id].first_out;
2.180 +
2.181 + nodes[v.id].first_out = n;
2.182 + nodes[u.id].first_out = (n | 1);
2.183 +
2.184 + return UEdge(n / 2);
2.185 + }
2.186 +
2.187 + void clear() {
2.188 + edges.clear();
2.189 + nodes.clear();
2.190 + }
2.191 +
2.192 + };
2.193 +
2.194 + typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
2.195
2.196 /// \ingroup graphs
2.197 ///
2.198 @@ -407,6 +588,7 @@
2.199 public:
2.200
2.201 typedef ExtendedSmartUGraphBase Parent;
2.202 + typedef Parent::OutEdgeIt IncEdgeIt;
2.203
2.204 /// Constructor
2.205
2.206 @@ -443,22 +625,31 @@
2.207
2.208 protected:
2.209
2.210 + void saveSnapshot(Snapshot &s)
2.211 + {
2.212 + s.g = this;
2.213 + s.node_num = nodes.size();
2.214 + s.edge_num = edges.size();
2.215 + }
2.216
2.217 void restoreSnapshot(const Snapshot &s)
2.218 {
2.219 while(s.edge_num<edges.size()) {
2.220 - UEdge edge = uEdgeFromId(edges.size()-1);
2.221 + int n=edges.size()-1;
2.222 + UEdge edge=uEdgeFromId(n/2);
2.223 Parent::getNotifier(UEdge()).erase(edge);
2.224 std::vector<Edge> dir;
2.225 - dir.push_back(Parent::direct(edge, true));
2.226 - dir.push_back(Parent::direct(edge, false));
2.227 + dir.push_back(edgeFromId(n));
2.228 + dir.push_back(edgeFromId(n-1));
2.229 Parent::getNotifier(Edge()).erase(dir);
2.230 - nodes[edges.back().source].first_out=edges.back().next_out;
2.231 - nodes[edges.back().target].first_in=edges.back().next_in;
2.232 + nodes[edges[n].target].first_out=edges[n].next_out;
2.233 + nodes[edges[n-1].target].first_out=edges[n-1].next_out;
2.234 + edges.pop_back();
2.235 edges.pop_back();
2.236 }
2.237 while(s.node_num<nodes.size()) {
2.238 - Node node = nodeFromId(nodes.size()-1);
2.239 + int n=nodes.size()-1;
2.240 + Node node = nodeFromId(n);
2.241 Parent::getNotifier(Node()).erase(node);
2.242 nodes.pop_back();
2.243 }
2.244 @@ -499,9 +690,8 @@
2.245
2.246 ///This constructor immediately makes a snapshot of the graph.
2.247 ///\param _g The graph we make a snapshot of.
2.248 - Snapshot(SmartUGraph &_g) :g(&_g) {
2.249 - node_num=g->nodes.size();
2.250 - edge_num=g->edges.size();
2.251 + Snapshot(SmartUGraph &g) {
2.252 + g.saveSnapshot(*this);
2.253 }
2.254
2.255 ///Make a snapshot.
2.256 @@ -511,11 +701,9 @@
2.257 ///This function can be called more than once. In case of a repeated
2.258 ///call, the previous snapshot gets lost.
2.259 ///\param _g The graph we make the snapshot of.
2.260 - void save(SmartUGraph &_g)
2.261 + void save(SmartUGraph &g)
2.262 {
2.263 - g=&_g;
2.264 - node_num=g->nodes.size();
2.265 - edge_num=g->edges.size();
2.266 + g.saveSnapshot(*this);
2.267 }
2.268
2.269 ///Undo the changes until a snapshot.
2.270 @@ -527,7 +715,7 @@
2.271 ///by restore().
2.272 void restore()
2.273 {
2.274 - g->restoreSnapshot(*this);
2.275 + g->restoreSnapshot(*this);
2.276 }
2.277 };
2.278 };