1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/smart_graph.h Wed Mar 26 17:28:28 2008 +0100
1.3 @@ -0,0 +1,757 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_SMART_GRAPH_H
1.23 +#define LEMON_SMART_GRAPH_H
1.24 +
1.25 +///\ingroup graphs
1.26 +///\file
1.27 +///\brief SmartDigraph and SmartGraph classes.
1.28 +
1.29 +#include <vector>
1.30 +
1.31 +#include <lemon/bits/invalid.h>
1.32 +
1.33 +#include <lemon/bits/base_extender.h>
1.34 +#include <lemon/bits/graph_extender.h>
1.35 +
1.36 +#include <lemon/bits/utility.h>
1.37 +#include <lemon/error.h>
1.38 +
1.39 +#include <lemon/bits/graph_extender.h>
1.40 +
1.41 +namespace lemon {
1.42 +
1.43 + class SmartDigraph;
1.44 + ///Base of SmartDigraph
1.45 +
1.46 + ///Base of SmartDigraph
1.47 + ///
1.48 + class SmartDigraphBase {
1.49 + protected:
1.50 +
1.51 + struct NodeT
1.52 + {
1.53 + int first_in, first_out;
1.54 + NodeT() {}
1.55 + };
1.56 + struct ArcT
1.57 + {
1.58 + int target, source, next_in, next_out;
1.59 + ArcT() {}
1.60 + };
1.61 +
1.62 + std::vector<NodeT> nodes;
1.63 + std::vector<ArcT> arcs;
1.64 +
1.65 + public:
1.66 +
1.67 + typedef SmartDigraphBase Graph;
1.68 +
1.69 + class Node;
1.70 + class Arc;
1.71 +
1.72 + public:
1.73 +
1.74 + SmartDigraphBase() : nodes(), arcs() { }
1.75 + SmartDigraphBase(const SmartDigraphBase &_g)
1.76 + : nodes(_g.nodes), arcs(_g.arcs) { }
1.77 +
1.78 + typedef True NodeNumTag;
1.79 + typedef True ArcNumTag;
1.80 +
1.81 + int nodeNum() const { return nodes.size(); }
1.82 + int arcNum() const { return arcs.size(); }
1.83 +
1.84 + int maxNodeId() const { return nodes.size()-1; }
1.85 + int maxArcId() const { return arcs.size()-1; }
1.86 +
1.87 + Node addNode() {
1.88 + int n = nodes.size();
1.89 + nodes.push_back(NodeT());
1.90 + nodes[n].first_in = -1;
1.91 + nodes[n].first_out = -1;
1.92 + return Node(n);
1.93 + }
1.94 +
1.95 + Arc addArc(Node u, Node v) {
1.96 + int n = arcs.size();
1.97 + arcs.push_back(ArcT());
1.98 + arcs[n].source = u._id;
1.99 + arcs[n].target = v._id;
1.100 + arcs[n].next_out = nodes[u._id].first_out;
1.101 + arcs[n].next_in = nodes[v._id].first_in;
1.102 + nodes[u._id].first_out = nodes[v._id].first_in = n;
1.103 +
1.104 + return Arc(n);
1.105 + }
1.106 +
1.107 + void clear() {
1.108 + arcs.clear();
1.109 + nodes.clear();
1.110 + }
1.111 +
1.112 + Node source(Arc a) const { return Node(arcs[a._id].source); }
1.113 + Node target(Arc a) const { return Node(arcs[a._id].target); }
1.114 +
1.115 + static int id(Node v) { return v._id; }
1.116 + static int id(Arc a) { return a._id; }
1.117 +
1.118 + static Node nodeFromId(int id) { return Node(id);}
1.119 + static Arc arcFromId(int id) { return Arc(id);}
1.120 +
1.121 + class Node {
1.122 + friend class SmartDigraphBase;
1.123 + friend class SmartDigraph;
1.124 +
1.125 + protected:
1.126 + int _id;
1.127 + explicit Node(int id) : _id(id) {}
1.128 + public:
1.129 + Node() {}
1.130 + Node (Invalid) : _id(-1) {}
1.131 + bool operator==(const Node i) const {return _id == i._id;}
1.132 + bool operator!=(const Node i) const {return _id != i._id;}
1.133 + bool operator<(const Node i) const {return _id < i._id;}
1.134 + };
1.135 +
1.136 +
1.137 + class Arc {
1.138 + friend class SmartDigraphBase;
1.139 + friend class SmartDigraph;
1.140 +
1.141 + protected:
1.142 + int _id;
1.143 + explicit Arc(int id) : _id(id) {}
1.144 + public:
1.145 + Arc() { }
1.146 + Arc (Invalid) : _id(-1) {}
1.147 + bool operator==(const Arc i) const {return _id == i._id;}
1.148 + bool operator!=(const Arc i) const {return _id != i._id;}
1.149 + bool operator<(const Arc i) const {return _id < i._id;}
1.150 + };
1.151 +
1.152 + void first(Node& node) const {
1.153 + node._id = nodes.size() - 1;
1.154 + }
1.155 +
1.156 + static void next(Node& node) {
1.157 + --node._id;
1.158 + }
1.159 +
1.160 + void first(Arc& arc) const {
1.161 + arc._id = arcs.size() - 1;
1.162 + }
1.163 +
1.164 + static void next(Arc& arc) {
1.165 + --arc._id;
1.166 + }
1.167 +
1.168 + void firstOut(Arc& arc, const Node& node) const {
1.169 + arc._id = nodes[node._id].first_out;
1.170 + }
1.171 +
1.172 + void nextOut(Arc& arc) const {
1.173 + arc._id = arcs[arc._id].next_out;
1.174 + }
1.175 +
1.176 + void firstIn(Arc& arc, const Node& node) const {
1.177 + arc._id = nodes[node._id].first_in;
1.178 + }
1.179 +
1.180 + void nextIn(Arc& arc) const {
1.181 + arc._id = arcs[arc._id].next_in;
1.182 + }
1.183 +
1.184 + };
1.185 +
1.186 + typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
1.187 +
1.188 + ///\ingroup graphs
1.189 + ///
1.190 + ///\brief A smart directed graph class.
1.191 + ///
1.192 + ///This is a simple and fast digraph implementation.
1.193 + ///It is also quite memory efficient, but at the price
1.194 + ///that <b> it does support only limited (only stack-like)
1.195 + ///node and arc deletions</b>.
1.196 + ///It conforms to the \ref concepts::Digraph "Digraph concept" with
1.197 + ///an important extra feature that its maps are real \ref
1.198 + ///concepts::ReferenceMap "reference map"s.
1.199 + ///
1.200 + ///\sa concepts::Digraph.
1.201 + ///
1.202 + ///\author Alpar Juttner
1.203 + class SmartDigraph : public ExtendedSmartDigraphBase {
1.204 + public:
1.205 +
1.206 + typedef ExtendedSmartDigraphBase Parent;
1.207 +
1.208 + private:
1.209 +
1.210 + ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.211 +
1.212 + ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.213 + ///
1.214 + SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
1.215 + ///\brief Assignment of SmartDigraph to another one is \e not allowed.
1.216 + ///Use DigraphCopy() instead.
1.217 +
1.218 + ///Assignment of SmartDigraph to another one is \e not allowed.
1.219 + ///Use DigraphCopy() instead.
1.220 + void operator=(const SmartDigraph &) {}
1.221 +
1.222 + public:
1.223 +
1.224 + /// Constructor
1.225 +
1.226 + /// Constructor.
1.227 + ///
1.228 + SmartDigraph() {};
1.229 +
1.230 + ///Add a new node to the digraph.
1.231 +
1.232 + /// \return the new node.
1.233 + ///
1.234 + Node addNode() { return Parent::addNode(); }
1.235 +
1.236 + ///Add a new arc to the digraph.
1.237 +
1.238 + ///Add a new arc to the digraph with source node \c s
1.239 + ///and target node \c t.
1.240 + ///\return the new arc.
1.241 + Arc addArc(const Node& s, const Node& t) {
1.242 + return Parent::addArc(s, t);
1.243 + }
1.244 +
1.245 + /// \brief Using this it is possible to avoid the superfluous memory
1.246 + /// allocation.
1.247 +
1.248 + /// Using this it is possible to avoid the superfluous memory
1.249 + /// allocation: if you know that the digraph you want to build will
1.250 + /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.251 + /// then it is worth reserving space for this amount before starting
1.252 + /// to build the digraph.
1.253 + /// \sa reserveArc
1.254 + void reserveNode(int n) { nodes.reserve(n); };
1.255 +
1.256 + /// \brief Using this it is possible to avoid the superfluous memory
1.257 + /// allocation.
1.258 +
1.259 + /// Using this it is possible to avoid the superfluous memory
1.260 + /// allocation: if you know that the digraph you want to build will
1.261 + /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.262 + /// then it is worth reserving space for this amount before starting
1.263 + /// to build the digraph.
1.264 + /// \sa reserveNode
1.265 + void reserveArc(int m) { arcs.reserve(m); };
1.266 +
1.267 + ///Clear the digraph.
1.268 +
1.269 + ///Erase all the nodes and arcs from the digraph.
1.270 + ///
1.271 + void clear() {
1.272 + Parent::clear();
1.273 + }
1.274 +
1.275 + ///Split a node.
1.276 +
1.277 + ///This function splits a node. First a new node is added to the digraph,
1.278 + ///then the source of each outgoing arc of \c n is moved to this new node.
1.279 + ///If \c connect is \c true (this is the default value), then a new arc
1.280 + ///from \c n to the newly created node is also added.
1.281 + ///\return The newly created node.
1.282 + ///
1.283 + ///\note The <tt>Arc</tt>s
1.284 + ///referencing a moved arc remain
1.285 + ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
1.286 + ///may be invalidated.
1.287 + ///\warning This functionality cannot be used together with the Snapshot
1.288 + ///feature.
1.289 + ///\todo It could be implemented in a bit faster way.
1.290 + Node split(Node n, bool connect = true)
1.291 + {
1.292 + Node b = addNode();
1.293 + nodes[b._id].first_out=nodes[n._id].first_out;
1.294 + nodes[n._id].first_out=-1;
1.295 + for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
1.296 + if(connect) addArc(n,b);
1.297 + return b;
1.298 + }
1.299 +
1.300 + public:
1.301 +
1.302 + class Snapshot;
1.303 +
1.304 + protected:
1.305 +
1.306 + void restoreSnapshot(const Snapshot &s)
1.307 + {
1.308 + while(s.arc_num<arcs.size()) {
1.309 + Arc arc = arcFromId(arcs.size()-1);
1.310 + Parent::notifier(Arc()).erase(arc);
1.311 + nodes[arcs.back().source].first_out=arcs.back().next_out;
1.312 + nodes[arcs.back().target].first_in=arcs.back().next_in;
1.313 + arcs.pop_back();
1.314 + }
1.315 + while(s.node_num<nodes.size()) {
1.316 + Node node = nodeFromId(nodes.size()-1);
1.317 + Parent::notifier(Node()).erase(node);
1.318 + nodes.pop_back();
1.319 + }
1.320 + }
1.321 +
1.322 + public:
1.323 +
1.324 + ///Class to make a snapshot of the digraph and to restrore to it later.
1.325 +
1.326 + ///Class to make a snapshot of the digraph and to restrore to it later.
1.327 + ///
1.328 + ///The newly added nodes and arcs can be removed using the
1.329 + ///restore() function.
1.330 + ///\note After you restore a state, you cannot restore
1.331 + ///a later state, in other word you cannot add again the arcs deleted
1.332 + ///by restore() using another one Snapshot instance.
1.333 + ///
1.334 + ///\warning If you do not use correctly the snapshot that can cause
1.335 + ///either broken program, invalid state of the digraph, valid but
1.336 + ///not the restored digraph or no change. Because the runtime performance
1.337 + ///the validity of the snapshot is not stored.
1.338 + class Snapshot
1.339 + {
1.340 + SmartDigraph *_graph;
1.341 + protected:
1.342 + friend class SmartDigraph;
1.343 + unsigned int node_num;
1.344 + unsigned int arc_num;
1.345 + public:
1.346 + ///Default constructor.
1.347 +
1.348 + ///Default constructor.
1.349 + ///To actually make a snapshot you must call save().
1.350 + ///
1.351 + Snapshot() : _graph(0) {}
1.352 + ///Constructor that immediately makes a snapshot
1.353 +
1.354 + ///This constructor immediately makes a snapshot of the digraph.
1.355 + ///\param _g The digraph we make a snapshot of.
1.356 + Snapshot(SmartDigraph &graph) : _graph(&graph) {
1.357 + node_num=_graph->nodes.size();
1.358 + arc_num=_graph->arcs.size();
1.359 + }
1.360 +
1.361 + ///Make a snapshot.
1.362 +
1.363 + ///Make a snapshot of the digraph.
1.364 + ///
1.365 + ///This function can be called more than once. In case of a repeated
1.366 + ///call, the previous snapshot gets lost.
1.367 + ///\param _g The digraph we make the snapshot of.
1.368 + void save(SmartDigraph &graph)
1.369 + {
1.370 + _graph=&graph;
1.371 + node_num=_graph->nodes.size();
1.372 + arc_num=_graph->arcs.size();
1.373 + }
1.374 +
1.375 + ///Undo the changes until a snapshot.
1.376 +
1.377 + ///Undo the changes until a snapshot created by save().
1.378 + ///
1.379 + ///\note After you restored a state, you cannot restore
1.380 + ///a later state, in other word you cannot add again the arcs deleted
1.381 + ///by restore().
1.382 + void restore()
1.383 + {
1.384 + _graph->restoreSnapshot(*this);
1.385 + }
1.386 + };
1.387 + };
1.388 +
1.389 +
1.390 + class SmartGraphBase {
1.391 +
1.392 + protected:
1.393 +
1.394 + struct NodeT {
1.395 + int first_out;
1.396 + };
1.397 +
1.398 + struct ArcT {
1.399 + int target;
1.400 + int next_out;
1.401 + };
1.402 +
1.403 + std::vector<NodeT> nodes;
1.404 + std::vector<ArcT> arcs;
1.405 +
1.406 + int first_free_arc;
1.407 +
1.408 + public:
1.409 +
1.410 + typedef SmartGraphBase Digraph;
1.411 +
1.412 + class Node;
1.413 + class Arc;
1.414 + class Edge;
1.415 +
1.416 + class Node {
1.417 + friend class SmartGraphBase;
1.418 + protected:
1.419 +
1.420 + int _id;
1.421 + explicit Node(int id) { _id = id;}
1.422 +
1.423 + public:
1.424 + Node() {}
1.425 + Node (Invalid) { _id = -1; }
1.426 + bool operator==(const Node& node) const {return _id == node._id;}
1.427 + bool operator!=(const Node& node) const {return _id != node._id;}
1.428 + bool operator<(const Node& node) const {return _id < node._id;}
1.429 + };
1.430 +
1.431 + class Edge {
1.432 + friend class SmartGraphBase;
1.433 + protected:
1.434 +
1.435 + int _id;
1.436 + explicit Edge(int id) { _id = id;}
1.437 +
1.438 + public:
1.439 + Edge() {}
1.440 + Edge (Invalid) { _id = -1; }
1.441 + bool operator==(const Edge& arc) const {return _id == arc._id;}
1.442 + bool operator!=(const Edge& arc) const {return _id != arc._id;}
1.443 + bool operator<(const Edge& arc) const {return _id < arc._id;}
1.444 + };
1.445 +
1.446 + class Arc {
1.447 + friend class SmartGraphBase;
1.448 + protected:
1.449 +
1.450 + int _id;
1.451 + explicit Arc(int id) { _id = id;}
1.452 +
1.453 + public:
1.454 + operator Edge() const { return edgeFromId(_id / 2); }
1.455 +
1.456 + Arc() {}
1.457 + Arc (Invalid) { _id = -1; }
1.458 + bool operator==(const Arc& arc) const {return _id == arc._id;}
1.459 + bool operator!=(const Arc& arc) const {return _id != arc._id;}
1.460 + bool operator<(const Arc& arc) const {return _id < arc._id;}
1.461 + };
1.462 +
1.463 +
1.464 +
1.465 + SmartGraphBase()
1.466 + : nodes(), arcs() {}
1.467 +
1.468 +
1.469 + int maxNodeId() const { return nodes.size()-1; }
1.470 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.471 + int maxArcId() const { return arcs.size()-1; }
1.472 +
1.473 + Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
1.474 + Node target(Arc e) const { return Node(arcs[e._id].target); }
1.475 +
1.476 + Node source(Edge e) const { return Node(arcs[2 * e._id].target); }
1.477 + Node target(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
1.478 +
1.479 + static bool direction(Arc e) {
1.480 + return (e._id & 1) == 1;
1.481 + }
1.482 +
1.483 + static Arc direct(Edge e, bool d) {
1.484 + return Arc(e._id * 2 + (d ? 1 : 0));
1.485 + }
1.486 +
1.487 + void first(Node& node) const {
1.488 + node._id = nodes.size() - 1;
1.489 + }
1.490 +
1.491 + void next(Node& node) const {
1.492 + --node._id;
1.493 + }
1.494 +
1.495 + void first(Arc& arc) const {
1.496 + arc._id = arcs.size() - 1;
1.497 + }
1.498 +
1.499 + void next(Arc& arc) const {
1.500 + --arc._id;
1.501 + }
1.502 +
1.503 + void first(Edge& arc) const {
1.504 + arc._id = arcs.size() / 2 - 1;
1.505 + }
1.506 +
1.507 + void next(Edge& arc) const {
1.508 + --arc._id;
1.509 + }
1.510 +
1.511 + void firstOut(Arc &arc, const Node& v) const {
1.512 + arc._id = nodes[v._id].first_out;
1.513 + }
1.514 + void nextOut(Arc &arc) const {
1.515 + arc._id = arcs[arc._id].next_out;
1.516 + }
1.517 +
1.518 + void firstIn(Arc &arc, const Node& v) const {
1.519 + arc._id = ((nodes[v._id].first_out) ^ 1);
1.520 + if (arc._id == -2) arc._id = -1;
1.521 + }
1.522 + void nextIn(Arc &arc) const {
1.523 + arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
1.524 + if (arc._id == -2) arc._id = -1;
1.525 + }
1.526 +
1.527 + void firstInc(Edge &arc, bool& d, const Node& v) const {
1.528 + int de = nodes[v._id].first_out;
1.529 + if (de != -1) {
1.530 + arc._id = de / 2;
1.531 + d = ((de & 1) == 1);
1.532 + } else {
1.533 + arc._id = -1;
1.534 + d = true;
1.535 + }
1.536 + }
1.537 + void nextInc(Edge &arc, bool& d) const {
1.538 + int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
1.539 + if (de != -1) {
1.540 + arc._id = de / 2;
1.541 + d = ((de & 1) == 1);
1.542 + } else {
1.543 + arc._id = -1;
1.544 + d = true;
1.545 + }
1.546 + }
1.547 +
1.548 + static int id(Node v) { return v._id; }
1.549 + static int id(Arc e) { return e._id; }
1.550 + static int id(Edge e) { return e._id; }
1.551 +
1.552 + static Node nodeFromId(int id) { return Node(id);}
1.553 + static Arc arcFromId(int id) { return Arc(id);}
1.554 + static Edge edgeFromId(int id) { return Edge(id);}
1.555 +
1.556 + Node addNode() {
1.557 + int n = nodes.size();
1.558 + nodes.push_back(NodeT());
1.559 + nodes[n].first_out = -1;
1.560 +
1.561 + return Node(n);
1.562 + }
1.563 +
1.564 + Edge addArc(Node u, Node v) {
1.565 + int n = arcs.size();
1.566 + arcs.push_back(ArcT());
1.567 + arcs.push_back(ArcT());
1.568 +
1.569 + arcs[n].target = u._id;
1.570 + arcs[n | 1].target = v._id;
1.571 +
1.572 + arcs[n].next_out = nodes[v._id].first_out;
1.573 + nodes[v._id].first_out = n;
1.574 +
1.575 + arcs[n | 1].next_out = nodes[u._id].first_out;
1.576 + nodes[u._id].first_out = (n | 1);
1.577 +
1.578 + return Edge(n / 2);
1.579 + }
1.580 +
1.581 + void clear() {
1.582 + arcs.clear();
1.583 + nodes.clear();
1.584 + }
1.585 +
1.586 + };
1.587 +
1.588 + typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
1.589 +
1.590 + /// \ingroup graphs
1.591 + ///
1.592 + /// \brief A smart undirected graph class.
1.593 + ///
1.594 + /// This is a simple and fast graph implementation.
1.595 + /// It is also quite memory efficient, but at the price
1.596 + /// that <b> it does support only limited (only stack-like)
1.597 + /// node and arc deletions</b>.
1.598 + /// Except from this it conforms to
1.599 + /// the \ref concepts::Graph "Graph concept".
1.600 + ///
1.601 + /// It also has an
1.602 + /// important extra feature that
1.603 + /// its maps are real \ref concepts::ReferenceMap "reference map"s.
1.604 + ///
1.605 + /// \sa concepts::Graph.
1.606 + ///
1.607 + class SmartGraph : public ExtendedSmartGraphBase {
1.608 + private:
1.609 +
1.610 + ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
1.611 +
1.612 + ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
1.613 + ///
1.614 + SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
1.615 +
1.616 + ///\brief Assignment of SmartGraph to another one is \e not allowed.
1.617 + ///Use GraphCopy() instead.
1.618 +
1.619 + ///Assignment of SmartGraph to another one is \e not allowed.
1.620 + ///Use GraphCopy() instead.
1.621 + void operator=(const SmartGraph &) {}
1.622 +
1.623 + public:
1.624 +
1.625 + typedef ExtendedSmartGraphBase Parent;
1.626 +
1.627 + /// Constructor
1.628 +
1.629 + /// Constructor.
1.630 + ///
1.631 + SmartGraph() {}
1.632 +
1.633 + ///Add a new node to the graph.
1.634 +
1.635 + /// \return the new node.
1.636 + ///
1.637 + Node addNode() { return Parent::addNode(); }
1.638 +
1.639 + ///Add a new edge to the graph.
1.640 +
1.641 + ///Add a new edge to the graph with node \c s
1.642 + ///and \c t.
1.643 + ///\return the new edge.
1.644 + Edge addEdge(const Node& s, const Node& t) {
1.645 + return Parent::addArc(s, t);
1.646 + }
1.647 +
1.648 + ///Clear the graph.
1.649 +
1.650 + ///Erase all the nodes and edges from the graph.
1.651 + ///
1.652 + void clear() {
1.653 + Parent::clear();
1.654 + }
1.655 +
1.656 + public:
1.657 +
1.658 + class Snapshot;
1.659 +
1.660 + protected:
1.661 +
1.662 + void saveSnapshot(Snapshot &s)
1.663 + {
1.664 + s._graph = this;
1.665 + s.node_num = nodes.size();
1.666 + s.arc_num = arcs.size();
1.667 + }
1.668 +
1.669 + void restoreSnapshot(const Snapshot &s)
1.670 + {
1.671 + while(s.arc_num<arcs.size()) {
1.672 + int n=arcs.size()-1;
1.673 + Edge arc=edgeFromId(n/2);
1.674 + Parent::notifier(Edge()).erase(arc);
1.675 + std::vector<Arc> dir;
1.676 + dir.push_back(arcFromId(n));
1.677 + dir.push_back(arcFromId(n-1));
1.678 + Parent::notifier(Arc()).erase(dir);
1.679 + nodes[arcs[n].target].first_out=arcs[n].next_out;
1.680 + nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
1.681 + arcs.pop_back();
1.682 + arcs.pop_back();
1.683 + }
1.684 + while(s.node_num<nodes.size()) {
1.685 + int n=nodes.size()-1;
1.686 + Node node = nodeFromId(n);
1.687 + Parent::notifier(Node()).erase(node);
1.688 + nodes.pop_back();
1.689 + }
1.690 + }
1.691 +
1.692 + public:
1.693 +
1.694 + ///Class to make a snapshot of the digraph and to restrore to it later.
1.695 +
1.696 + ///Class to make a snapshot of the digraph and to restrore to it later.
1.697 + ///
1.698 + ///The newly added nodes and arcs can be removed using the
1.699 + ///restore() function.
1.700 + ///
1.701 + ///\note After you restore a state, you cannot restore
1.702 + ///a later state, in other word you cannot add again the arcs deleted
1.703 + ///by restore() using another one Snapshot instance.
1.704 + ///
1.705 + ///\warning If you do not use correctly the snapshot that can cause
1.706 + ///either broken program, invalid state of the digraph, valid but
1.707 + ///not the restored digraph or no change. Because the runtime performance
1.708 + ///the validity of the snapshot is not stored.
1.709 + class Snapshot
1.710 + {
1.711 + SmartGraph *_graph;
1.712 + protected:
1.713 + friend class SmartGraph;
1.714 + unsigned int node_num;
1.715 + unsigned int arc_num;
1.716 + public:
1.717 + ///Default constructor.
1.718 +
1.719 + ///Default constructor.
1.720 + ///To actually make a snapshot you must call save().
1.721 + ///
1.722 + Snapshot() : _graph(0) {}
1.723 + ///Constructor that immediately makes a snapshot
1.724 +
1.725 + ///This constructor immediately makes a snapshot of the digraph.
1.726 + ///\param g The digraph we make a snapshot of.
1.727 + Snapshot(SmartGraph &graph) {
1.728 + graph.saveSnapshot(*this);
1.729 + }
1.730 +
1.731 + ///Make a snapshot.
1.732 +
1.733 + ///Make a snapshot of the graph.
1.734 + ///
1.735 + ///This function can be called more than once. In case of a repeated
1.736 + ///call, the previous snapshot gets lost.
1.737 + ///\param g The digraph we make the snapshot of.
1.738 + void save(SmartGraph &graph)
1.739 + {
1.740 + graph.saveSnapshot(*this);
1.741 + }
1.742 +
1.743 + ///Undo the changes until a snapshot.
1.744 +
1.745 + ///Undo the changes until a snapshot created by save().
1.746 + ///
1.747 + ///\note After you restored a state, you cannot restore
1.748 + ///a later state, in other word you cannot add again the arcs deleted
1.749 + ///by restore().
1.750 + void restore()
1.751 + {
1.752 + _graph->restoreSnapshot(*this);
1.753 + }
1.754 + };
1.755 + };
1.756 +
1.757 +} //namespace lemon
1.758 +
1.759 +
1.760 +#endif //LEMON_SMART_GRAPH_H