1.1 --- a/lemon/Makefile.am Tue Mar 25 16:36:44 2008 +0100
1.2 +++ b/lemon/Makefile.am Wed Mar 26 17:28:28 2008 +0100
1.3 @@ -31,6 +31,7 @@
1.4 lemon/math.h \
1.5 lemon/path.h \
1.6 lemon/random.h \
1.7 + lemon/smart_graph.h \
1.8 lemon/tolerance.h \
1.9 lemon/unionfind.h
1.10
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/smart_graph.h Wed Mar 26 17:28:28 2008 +0100
2.3 @@ -0,0 +1,757 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_SMART_GRAPH_H
2.23 +#define LEMON_SMART_GRAPH_H
2.24 +
2.25 +///\ingroup graphs
2.26 +///\file
2.27 +///\brief SmartDigraph and SmartGraph classes.
2.28 +
2.29 +#include <vector>
2.30 +
2.31 +#include <lemon/bits/invalid.h>
2.32 +
2.33 +#include <lemon/bits/base_extender.h>
2.34 +#include <lemon/bits/graph_extender.h>
2.35 +
2.36 +#include <lemon/bits/utility.h>
2.37 +#include <lemon/error.h>
2.38 +
2.39 +#include <lemon/bits/graph_extender.h>
2.40 +
2.41 +namespace lemon {
2.42 +
2.43 + class SmartDigraph;
2.44 + ///Base of SmartDigraph
2.45 +
2.46 + ///Base of SmartDigraph
2.47 + ///
2.48 + class SmartDigraphBase {
2.49 + protected:
2.50 +
2.51 + struct NodeT
2.52 + {
2.53 + int first_in, first_out;
2.54 + NodeT() {}
2.55 + };
2.56 + struct ArcT
2.57 + {
2.58 + int target, source, next_in, next_out;
2.59 + ArcT() {}
2.60 + };
2.61 +
2.62 + std::vector<NodeT> nodes;
2.63 + std::vector<ArcT> arcs;
2.64 +
2.65 + public:
2.66 +
2.67 + typedef SmartDigraphBase Graph;
2.68 +
2.69 + class Node;
2.70 + class Arc;
2.71 +
2.72 + public:
2.73 +
2.74 + SmartDigraphBase() : nodes(), arcs() { }
2.75 + SmartDigraphBase(const SmartDigraphBase &_g)
2.76 + : nodes(_g.nodes), arcs(_g.arcs) { }
2.77 +
2.78 + typedef True NodeNumTag;
2.79 + typedef True ArcNumTag;
2.80 +
2.81 + int nodeNum() const { return nodes.size(); }
2.82 + int arcNum() const { return arcs.size(); }
2.83 +
2.84 + int maxNodeId() const { return nodes.size()-1; }
2.85 + int maxArcId() const { return arcs.size()-1; }
2.86 +
2.87 + Node addNode() {
2.88 + int n = nodes.size();
2.89 + nodes.push_back(NodeT());
2.90 + nodes[n].first_in = -1;
2.91 + nodes[n].first_out = -1;
2.92 + return Node(n);
2.93 + }
2.94 +
2.95 + Arc addArc(Node u, Node v) {
2.96 + int n = arcs.size();
2.97 + arcs.push_back(ArcT());
2.98 + arcs[n].source = u._id;
2.99 + arcs[n].target = v._id;
2.100 + arcs[n].next_out = nodes[u._id].first_out;
2.101 + arcs[n].next_in = nodes[v._id].first_in;
2.102 + nodes[u._id].first_out = nodes[v._id].first_in = n;
2.103 +
2.104 + return Arc(n);
2.105 + }
2.106 +
2.107 + void clear() {
2.108 + arcs.clear();
2.109 + nodes.clear();
2.110 + }
2.111 +
2.112 + Node source(Arc a) const { return Node(arcs[a._id].source); }
2.113 + Node target(Arc a) const { return Node(arcs[a._id].target); }
2.114 +
2.115 + static int id(Node v) { return v._id; }
2.116 + static int id(Arc a) { return a._id; }
2.117 +
2.118 + static Node nodeFromId(int id) { return Node(id);}
2.119 + static Arc arcFromId(int id) { return Arc(id);}
2.120 +
2.121 + class Node {
2.122 + friend class SmartDigraphBase;
2.123 + friend class SmartDigraph;
2.124 +
2.125 + protected:
2.126 + int _id;
2.127 + explicit Node(int id) : _id(id) {}
2.128 + public:
2.129 + Node() {}
2.130 + Node (Invalid) : _id(-1) {}
2.131 + bool operator==(const Node i) const {return _id == i._id;}
2.132 + bool operator!=(const Node i) const {return _id != i._id;}
2.133 + bool operator<(const Node i) const {return _id < i._id;}
2.134 + };
2.135 +
2.136 +
2.137 + class Arc {
2.138 + friend class SmartDigraphBase;
2.139 + friend class SmartDigraph;
2.140 +
2.141 + protected:
2.142 + int _id;
2.143 + explicit Arc(int id) : _id(id) {}
2.144 + public:
2.145 + Arc() { }
2.146 + Arc (Invalid) : _id(-1) {}
2.147 + bool operator==(const Arc i) const {return _id == i._id;}
2.148 + bool operator!=(const Arc i) const {return _id != i._id;}
2.149 + bool operator<(const Arc i) const {return _id < i._id;}
2.150 + };
2.151 +
2.152 + void first(Node& node) const {
2.153 + node._id = nodes.size() - 1;
2.154 + }
2.155 +
2.156 + static void next(Node& node) {
2.157 + --node._id;
2.158 + }
2.159 +
2.160 + void first(Arc& arc) const {
2.161 + arc._id = arcs.size() - 1;
2.162 + }
2.163 +
2.164 + static void next(Arc& arc) {
2.165 + --arc._id;
2.166 + }
2.167 +
2.168 + void firstOut(Arc& arc, const Node& node) const {
2.169 + arc._id = nodes[node._id].first_out;
2.170 + }
2.171 +
2.172 + void nextOut(Arc& arc) const {
2.173 + arc._id = arcs[arc._id].next_out;
2.174 + }
2.175 +
2.176 + void firstIn(Arc& arc, const Node& node) const {
2.177 + arc._id = nodes[node._id].first_in;
2.178 + }
2.179 +
2.180 + void nextIn(Arc& arc) const {
2.181 + arc._id = arcs[arc._id].next_in;
2.182 + }
2.183 +
2.184 + };
2.185 +
2.186 + typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
2.187 +
2.188 + ///\ingroup graphs
2.189 + ///
2.190 + ///\brief A smart directed graph class.
2.191 + ///
2.192 + ///This is a simple and fast digraph implementation.
2.193 + ///It is also quite memory efficient, but at the price
2.194 + ///that <b> it does support only limited (only stack-like)
2.195 + ///node and arc deletions</b>.
2.196 + ///It conforms to the \ref concepts::Digraph "Digraph concept" with
2.197 + ///an important extra feature that its maps are real \ref
2.198 + ///concepts::ReferenceMap "reference map"s.
2.199 + ///
2.200 + ///\sa concepts::Digraph.
2.201 + ///
2.202 + ///\author Alpar Juttner
2.203 + class SmartDigraph : public ExtendedSmartDigraphBase {
2.204 + public:
2.205 +
2.206 + typedef ExtendedSmartDigraphBase Parent;
2.207 +
2.208 + private:
2.209 +
2.210 + ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
2.211 +
2.212 + ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
2.213 + ///
2.214 + SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
2.215 + ///\brief Assignment of SmartDigraph to another one is \e not allowed.
2.216 + ///Use DigraphCopy() instead.
2.217 +
2.218 + ///Assignment of SmartDigraph to another one is \e not allowed.
2.219 + ///Use DigraphCopy() instead.
2.220 + void operator=(const SmartDigraph &) {}
2.221 +
2.222 + public:
2.223 +
2.224 + /// Constructor
2.225 +
2.226 + /// Constructor.
2.227 + ///
2.228 + SmartDigraph() {};
2.229 +
2.230 + ///Add a new node to the digraph.
2.231 +
2.232 + /// \return the new node.
2.233 + ///
2.234 + Node addNode() { return Parent::addNode(); }
2.235 +
2.236 + ///Add a new arc to the digraph.
2.237 +
2.238 + ///Add a new arc to the digraph with source node \c s
2.239 + ///and target node \c t.
2.240 + ///\return the new arc.
2.241 + Arc addArc(const Node& s, const Node& t) {
2.242 + return Parent::addArc(s, t);
2.243 + }
2.244 +
2.245 + /// \brief Using this it is possible to avoid the superfluous memory
2.246 + /// allocation.
2.247 +
2.248 + /// Using this it is possible to avoid the superfluous memory
2.249 + /// allocation: if you know that the digraph you want to build will
2.250 + /// be very large (e.g. it will contain millions of nodes and/or arcs)
2.251 + /// then it is worth reserving space for this amount before starting
2.252 + /// to build the digraph.
2.253 + /// \sa reserveArc
2.254 + void reserveNode(int n) { nodes.reserve(n); };
2.255 +
2.256 + /// \brief Using this it is possible to avoid the superfluous memory
2.257 + /// allocation.
2.258 +
2.259 + /// Using this it is possible to avoid the superfluous memory
2.260 + /// allocation: if you know that the digraph you want to build will
2.261 + /// be very large (e.g. it will contain millions of nodes and/or arcs)
2.262 + /// then it is worth reserving space for this amount before starting
2.263 + /// to build the digraph.
2.264 + /// \sa reserveNode
2.265 + void reserveArc(int m) { arcs.reserve(m); };
2.266 +
2.267 + ///Clear the digraph.
2.268 +
2.269 + ///Erase all the nodes and arcs from the digraph.
2.270 + ///
2.271 + void clear() {
2.272 + Parent::clear();
2.273 + }
2.274 +
2.275 + ///Split a node.
2.276 +
2.277 + ///This function splits a node. First a new node is added to the digraph,
2.278 + ///then the source of each outgoing arc of \c n is moved to this new node.
2.279 + ///If \c connect is \c true (this is the default value), then a new arc
2.280 + ///from \c n to the newly created node is also added.
2.281 + ///\return The newly created node.
2.282 + ///
2.283 + ///\note The <tt>Arc</tt>s
2.284 + ///referencing a moved arc remain
2.285 + ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
2.286 + ///may be invalidated.
2.287 + ///\warning This functionality cannot be used together with the Snapshot
2.288 + ///feature.
2.289 + ///\todo It could be implemented in a bit faster way.
2.290 + Node split(Node n, bool connect = true)
2.291 + {
2.292 + Node b = addNode();
2.293 + nodes[b._id].first_out=nodes[n._id].first_out;
2.294 + nodes[n._id].first_out=-1;
2.295 + for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
2.296 + if(connect) addArc(n,b);
2.297 + return b;
2.298 + }
2.299 +
2.300 + public:
2.301 +
2.302 + class Snapshot;
2.303 +
2.304 + protected:
2.305 +
2.306 + void restoreSnapshot(const Snapshot &s)
2.307 + {
2.308 + while(s.arc_num<arcs.size()) {
2.309 + Arc arc = arcFromId(arcs.size()-1);
2.310 + Parent::notifier(Arc()).erase(arc);
2.311 + nodes[arcs.back().source].first_out=arcs.back().next_out;
2.312 + nodes[arcs.back().target].first_in=arcs.back().next_in;
2.313 + arcs.pop_back();
2.314 + }
2.315 + while(s.node_num<nodes.size()) {
2.316 + Node node = nodeFromId(nodes.size()-1);
2.317 + Parent::notifier(Node()).erase(node);
2.318 + nodes.pop_back();
2.319 + }
2.320 + }
2.321 +
2.322 + public:
2.323 +
2.324 + ///Class to make a snapshot of the digraph and to restrore to it later.
2.325 +
2.326 + ///Class to make a snapshot of the digraph and to restrore to it later.
2.327 + ///
2.328 + ///The newly added nodes and arcs can be removed using the
2.329 + ///restore() function.
2.330 + ///\note After you restore a state, you cannot restore
2.331 + ///a later state, in other word you cannot add again the arcs deleted
2.332 + ///by restore() using another one Snapshot instance.
2.333 + ///
2.334 + ///\warning If you do not use correctly the snapshot that can cause
2.335 + ///either broken program, invalid state of the digraph, valid but
2.336 + ///not the restored digraph or no change. Because the runtime performance
2.337 + ///the validity of the snapshot is not stored.
2.338 + class Snapshot
2.339 + {
2.340 + SmartDigraph *_graph;
2.341 + protected:
2.342 + friend class SmartDigraph;
2.343 + unsigned int node_num;
2.344 + unsigned int arc_num;
2.345 + public:
2.346 + ///Default constructor.
2.347 +
2.348 + ///Default constructor.
2.349 + ///To actually make a snapshot you must call save().
2.350 + ///
2.351 + Snapshot() : _graph(0) {}
2.352 + ///Constructor that immediately makes a snapshot
2.353 +
2.354 + ///This constructor immediately makes a snapshot of the digraph.
2.355 + ///\param _g The digraph we make a snapshot of.
2.356 + Snapshot(SmartDigraph &graph) : _graph(&graph) {
2.357 + node_num=_graph->nodes.size();
2.358 + arc_num=_graph->arcs.size();
2.359 + }
2.360 +
2.361 + ///Make a snapshot.
2.362 +
2.363 + ///Make a snapshot of the digraph.
2.364 + ///
2.365 + ///This function can be called more than once. In case of a repeated
2.366 + ///call, the previous snapshot gets lost.
2.367 + ///\param _g The digraph we make the snapshot of.
2.368 + void save(SmartDigraph &graph)
2.369 + {
2.370 + _graph=&graph;
2.371 + node_num=_graph->nodes.size();
2.372 + arc_num=_graph->arcs.size();
2.373 + }
2.374 +
2.375 + ///Undo the changes until a snapshot.
2.376 +
2.377 + ///Undo the changes until a snapshot created by save().
2.378 + ///
2.379 + ///\note After you restored a state, you cannot restore
2.380 + ///a later state, in other word you cannot add again the arcs deleted
2.381 + ///by restore().
2.382 + void restore()
2.383 + {
2.384 + _graph->restoreSnapshot(*this);
2.385 + }
2.386 + };
2.387 + };
2.388 +
2.389 +
2.390 + class SmartGraphBase {
2.391 +
2.392 + protected:
2.393 +
2.394 + struct NodeT {
2.395 + int first_out;
2.396 + };
2.397 +
2.398 + struct ArcT {
2.399 + int target;
2.400 + int next_out;
2.401 + };
2.402 +
2.403 + std::vector<NodeT> nodes;
2.404 + std::vector<ArcT> arcs;
2.405 +
2.406 + int first_free_arc;
2.407 +
2.408 + public:
2.409 +
2.410 + typedef SmartGraphBase Digraph;
2.411 +
2.412 + class Node;
2.413 + class Arc;
2.414 + class Edge;
2.415 +
2.416 + class Node {
2.417 + friend class SmartGraphBase;
2.418 + protected:
2.419 +
2.420 + int _id;
2.421 + explicit Node(int id) { _id = id;}
2.422 +
2.423 + public:
2.424 + Node() {}
2.425 + Node (Invalid) { _id = -1; }
2.426 + bool operator==(const Node& node) const {return _id == node._id;}
2.427 + bool operator!=(const Node& node) const {return _id != node._id;}
2.428 + bool operator<(const Node& node) const {return _id < node._id;}
2.429 + };
2.430 +
2.431 + class Edge {
2.432 + friend class SmartGraphBase;
2.433 + protected:
2.434 +
2.435 + int _id;
2.436 + explicit Edge(int id) { _id = id;}
2.437 +
2.438 + public:
2.439 + Edge() {}
2.440 + Edge (Invalid) { _id = -1; }
2.441 + bool operator==(const Edge& arc) const {return _id == arc._id;}
2.442 + bool operator!=(const Edge& arc) const {return _id != arc._id;}
2.443 + bool operator<(const Edge& arc) const {return _id < arc._id;}
2.444 + };
2.445 +
2.446 + class Arc {
2.447 + friend class SmartGraphBase;
2.448 + protected:
2.449 +
2.450 + int _id;
2.451 + explicit Arc(int id) { _id = id;}
2.452 +
2.453 + public:
2.454 + operator Edge() const { return edgeFromId(_id / 2); }
2.455 +
2.456 + Arc() {}
2.457 + Arc (Invalid) { _id = -1; }
2.458 + bool operator==(const Arc& arc) const {return _id == arc._id;}
2.459 + bool operator!=(const Arc& arc) const {return _id != arc._id;}
2.460 + bool operator<(const Arc& arc) const {return _id < arc._id;}
2.461 + };
2.462 +
2.463 +
2.464 +
2.465 + SmartGraphBase()
2.466 + : nodes(), arcs() {}
2.467 +
2.468 +
2.469 + int maxNodeId() const { return nodes.size()-1; }
2.470 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
2.471 + int maxArcId() const { return arcs.size()-1; }
2.472 +
2.473 + Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
2.474 + Node target(Arc e) const { return Node(arcs[e._id].target); }
2.475 +
2.476 + Node source(Edge e) const { return Node(arcs[2 * e._id].target); }
2.477 + Node target(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
2.478 +
2.479 + static bool direction(Arc e) {
2.480 + return (e._id & 1) == 1;
2.481 + }
2.482 +
2.483 + static Arc direct(Edge e, bool d) {
2.484 + return Arc(e._id * 2 + (d ? 1 : 0));
2.485 + }
2.486 +
2.487 + void first(Node& node) const {
2.488 + node._id = nodes.size() - 1;
2.489 + }
2.490 +
2.491 + void next(Node& node) const {
2.492 + --node._id;
2.493 + }
2.494 +
2.495 + void first(Arc& arc) const {
2.496 + arc._id = arcs.size() - 1;
2.497 + }
2.498 +
2.499 + void next(Arc& arc) const {
2.500 + --arc._id;
2.501 + }
2.502 +
2.503 + void first(Edge& arc) const {
2.504 + arc._id = arcs.size() / 2 - 1;
2.505 + }
2.506 +
2.507 + void next(Edge& arc) const {
2.508 + --arc._id;
2.509 + }
2.510 +
2.511 + void firstOut(Arc &arc, const Node& v) const {
2.512 + arc._id = nodes[v._id].first_out;
2.513 + }
2.514 + void nextOut(Arc &arc) const {
2.515 + arc._id = arcs[arc._id].next_out;
2.516 + }
2.517 +
2.518 + void firstIn(Arc &arc, const Node& v) const {
2.519 + arc._id = ((nodes[v._id].first_out) ^ 1);
2.520 + if (arc._id == -2) arc._id = -1;
2.521 + }
2.522 + void nextIn(Arc &arc) const {
2.523 + arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
2.524 + if (arc._id == -2) arc._id = -1;
2.525 + }
2.526 +
2.527 + void firstInc(Edge &arc, bool& d, const Node& v) const {
2.528 + int de = nodes[v._id].first_out;
2.529 + if (de != -1) {
2.530 + arc._id = de / 2;
2.531 + d = ((de & 1) == 1);
2.532 + } else {
2.533 + arc._id = -1;
2.534 + d = true;
2.535 + }
2.536 + }
2.537 + void nextInc(Edge &arc, bool& d) const {
2.538 + int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
2.539 + if (de != -1) {
2.540 + arc._id = de / 2;
2.541 + d = ((de & 1) == 1);
2.542 + } else {
2.543 + arc._id = -1;
2.544 + d = true;
2.545 + }
2.546 + }
2.547 +
2.548 + static int id(Node v) { return v._id; }
2.549 + static int id(Arc e) { return e._id; }
2.550 + static int id(Edge e) { return e._id; }
2.551 +
2.552 + static Node nodeFromId(int id) { return Node(id);}
2.553 + static Arc arcFromId(int id) { return Arc(id);}
2.554 + static Edge edgeFromId(int id) { return Edge(id);}
2.555 +
2.556 + Node addNode() {
2.557 + int n = nodes.size();
2.558 + nodes.push_back(NodeT());
2.559 + nodes[n].first_out = -1;
2.560 +
2.561 + return Node(n);
2.562 + }
2.563 +
2.564 + Edge addArc(Node u, Node v) {
2.565 + int n = arcs.size();
2.566 + arcs.push_back(ArcT());
2.567 + arcs.push_back(ArcT());
2.568 +
2.569 + arcs[n].target = u._id;
2.570 + arcs[n | 1].target = v._id;
2.571 +
2.572 + arcs[n].next_out = nodes[v._id].first_out;
2.573 + nodes[v._id].first_out = n;
2.574 +
2.575 + arcs[n | 1].next_out = nodes[u._id].first_out;
2.576 + nodes[u._id].first_out = (n | 1);
2.577 +
2.578 + return Edge(n / 2);
2.579 + }
2.580 +
2.581 + void clear() {
2.582 + arcs.clear();
2.583 + nodes.clear();
2.584 + }
2.585 +
2.586 + };
2.587 +
2.588 + typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
2.589 +
2.590 + /// \ingroup graphs
2.591 + ///
2.592 + /// \brief A smart undirected graph class.
2.593 + ///
2.594 + /// This is a simple and fast graph implementation.
2.595 + /// It is also quite memory efficient, but at the price
2.596 + /// that <b> it does support only limited (only stack-like)
2.597 + /// node and arc deletions</b>.
2.598 + /// Except from this it conforms to
2.599 + /// the \ref concepts::Graph "Graph concept".
2.600 + ///
2.601 + /// It also has an
2.602 + /// important extra feature that
2.603 + /// its maps are real \ref concepts::ReferenceMap "reference map"s.
2.604 + ///
2.605 + /// \sa concepts::Graph.
2.606 + ///
2.607 + class SmartGraph : public ExtendedSmartGraphBase {
2.608 + private:
2.609 +
2.610 + ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
2.611 +
2.612 + ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
2.613 + ///
2.614 + SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
2.615 +
2.616 + ///\brief Assignment of SmartGraph to another one is \e not allowed.
2.617 + ///Use GraphCopy() instead.
2.618 +
2.619 + ///Assignment of SmartGraph to another one is \e not allowed.
2.620 + ///Use GraphCopy() instead.
2.621 + void operator=(const SmartGraph &) {}
2.622 +
2.623 + public:
2.624 +
2.625 + typedef ExtendedSmartGraphBase Parent;
2.626 +
2.627 + /// Constructor
2.628 +
2.629 + /// Constructor.
2.630 + ///
2.631 + SmartGraph() {}
2.632 +
2.633 + ///Add a new node to the graph.
2.634 +
2.635 + /// \return the new node.
2.636 + ///
2.637 + Node addNode() { return Parent::addNode(); }
2.638 +
2.639 + ///Add a new edge to the graph.
2.640 +
2.641 + ///Add a new edge to the graph with node \c s
2.642 + ///and \c t.
2.643 + ///\return the new edge.
2.644 + Edge addEdge(const Node& s, const Node& t) {
2.645 + return Parent::addArc(s, t);
2.646 + }
2.647 +
2.648 + ///Clear the graph.
2.649 +
2.650 + ///Erase all the nodes and edges from the graph.
2.651 + ///
2.652 + void clear() {
2.653 + Parent::clear();
2.654 + }
2.655 +
2.656 + public:
2.657 +
2.658 + class Snapshot;
2.659 +
2.660 + protected:
2.661 +
2.662 + void saveSnapshot(Snapshot &s)
2.663 + {
2.664 + s._graph = this;
2.665 + s.node_num = nodes.size();
2.666 + s.arc_num = arcs.size();
2.667 + }
2.668 +
2.669 + void restoreSnapshot(const Snapshot &s)
2.670 + {
2.671 + while(s.arc_num<arcs.size()) {
2.672 + int n=arcs.size()-1;
2.673 + Edge arc=edgeFromId(n/2);
2.674 + Parent::notifier(Edge()).erase(arc);
2.675 + std::vector<Arc> dir;
2.676 + dir.push_back(arcFromId(n));
2.677 + dir.push_back(arcFromId(n-1));
2.678 + Parent::notifier(Arc()).erase(dir);
2.679 + nodes[arcs[n].target].first_out=arcs[n].next_out;
2.680 + nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
2.681 + arcs.pop_back();
2.682 + arcs.pop_back();
2.683 + }
2.684 + while(s.node_num<nodes.size()) {
2.685 + int n=nodes.size()-1;
2.686 + Node node = nodeFromId(n);
2.687 + Parent::notifier(Node()).erase(node);
2.688 + nodes.pop_back();
2.689 + }
2.690 + }
2.691 +
2.692 + public:
2.693 +
2.694 + ///Class to make a snapshot of the digraph and to restrore to it later.
2.695 +
2.696 + ///Class to make a snapshot of the digraph and to restrore to it later.
2.697 + ///
2.698 + ///The newly added nodes and arcs can be removed using the
2.699 + ///restore() function.
2.700 + ///
2.701 + ///\note After you restore a state, you cannot restore
2.702 + ///a later state, in other word you cannot add again the arcs deleted
2.703 + ///by restore() using another one Snapshot instance.
2.704 + ///
2.705 + ///\warning If you do not use correctly the snapshot that can cause
2.706 + ///either broken program, invalid state of the digraph, valid but
2.707 + ///not the restored digraph or no change. Because the runtime performance
2.708 + ///the validity of the snapshot is not stored.
2.709 + class Snapshot
2.710 + {
2.711 + SmartGraph *_graph;
2.712 + protected:
2.713 + friend class SmartGraph;
2.714 + unsigned int node_num;
2.715 + unsigned int arc_num;
2.716 + public:
2.717 + ///Default constructor.
2.718 +
2.719 + ///Default constructor.
2.720 + ///To actually make a snapshot you must call save().
2.721 + ///
2.722 + Snapshot() : _graph(0) {}
2.723 + ///Constructor that immediately makes a snapshot
2.724 +
2.725 + ///This constructor immediately makes a snapshot of the digraph.
2.726 + ///\param g The digraph we make a snapshot of.
2.727 + Snapshot(SmartGraph &graph) {
2.728 + graph.saveSnapshot(*this);
2.729 + }
2.730 +
2.731 + ///Make a snapshot.
2.732 +
2.733 + ///Make a snapshot of the graph.
2.734 + ///
2.735 + ///This function can be called more than once. In case of a repeated
2.736 + ///call, the previous snapshot gets lost.
2.737 + ///\param g The digraph we make the snapshot of.
2.738 + void save(SmartGraph &graph)
2.739 + {
2.740 + graph.saveSnapshot(*this);
2.741 + }
2.742 +
2.743 + ///Undo the changes until a snapshot.
2.744 +
2.745 + ///Undo the changes until a snapshot created by save().
2.746 + ///
2.747 + ///\note After you restored a state, you cannot restore
2.748 + ///a later state, in other word you cannot add again the arcs deleted
2.749 + ///by restore().
2.750 + void restore()
2.751 + {
2.752 + _graph->restoreSnapshot(*this);
2.753 + }
2.754 + };
2.755 + };
2.756 +
2.757 +} //namespace lemon
2.758 +
2.759 +
2.760 +#endif //LEMON_SMART_GRAPH_H
3.1 --- a/test/graph_test.cc Tue Mar 25 16:36:44 2008 +0100
3.2 +++ b/test/graph_test.cc Wed Mar 26 17:28:28 2008 +0100
3.3 @@ -18,7 +18,7 @@
3.4
3.5 #include <lemon/concepts/graph.h>
3.6 #include <lemon/list_graph.h>
3.7 -// #include <lemon/smart_graph.h>
3.8 +#include <lemon/smart_graph.h>
3.9 // #include <lemon/full_graph.h>
3.10 // #include <lemon/grid_graph.h>
3.11
3.12 @@ -47,7 +47,7 @@
3.13 }
3.14 {
3.15 checkConcept<Graph, ListGraph>();
3.16 -// checkConcept<Graph, SmartGraph>();
3.17 + checkConcept<Graph, SmartGraph>();
3.18 // checkConcept<Graph, FullGraph>();
3.19 // checkConcept<Graph, Graph>();
3.20 // checkConcept<Graph, GridGraph>();
3.21 @@ -188,7 +188,7 @@
3.22 check_concepts();
3.23
3.24 check_graph<ListGraph>();
3.25 -// check_graph<SmartGraph>();
3.26 + check_graph<SmartGraph>();
3.27
3.28 // {
3.29 // FullGraph g(5);