1.1 --- a/lemon/list_graph.h Sat Jan 12 23:30:44 2008 +0000
1.2 +++ b/lemon/list_graph.h Sun Jan 20 20:43:48 2008 +0100
1.3 @@ -16,3 +16,1452 @@
1.4 *
1.5 */
1.6
1.7 +#ifndef LEMON_LIST_GRAPH_H
1.8 +#define LEMON_LIST_GRAPH_H
1.9 +
1.10 +///\ingroup graphs
1.11 +///\file
1.12 +///\brief ListDigraph, ListGraph classes.
1.13 +
1.14 +#include <lemon/bits/graph_extender.h>
1.15 +
1.16 +#include <vector>
1.17 +#include <list>
1.18 +
1.19 +namespace lemon {
1.20 +
1.21 + class ListDigraphBase {
1.22 +
1.23 + protected:
1.24 + struct NodeT {
1.25 + int first_in, first_out;
1.26 + int prev, next;
1.27 + };
1.28 +
1.29 + struct ArcT {
1.30 + int target, source;
1.31 + int prev_in, prev_out;
1.32 + int next_in, next_out;
1.33 + };
1.34 +
1.35 + std::vector<NodeT> nodes;
1.36 +
1.37 + int first_node;
1.38 +
1.39 + int first_free_node;
1.40 +
1.41 + std::vector<ArcT> arcs;
1.42 +
1.43 + int first_free_arc;
1.44 +
1.45 + public:
1.46 +
1.47 + typedef ListDigraphBase Digraph;
1.48 +
1.49 + class Node {
1.50 + friend class ListDigraphBase;
1.51 + protected:
1.52 +
1.53 + int id;
1.54 + explicit Node(int pid) { id = pid;}
1.55 +
1.56 + public:
1.57 + Node() {}
1.58 + Node (Invalid) { id = -1; }
1.59 + bool operator==(const Node& node) const {return id == node.id;}
1.60 + bool operator!=(const Node& node) const {return id != node.id;}
1.61 + bool operator<(const Node& node) const {return id < node.id;}
1.62 + };
1.63 +
1.64 + class Arc {
1.65 + friend class ListDigraphBase;
1.66 + protected:
1.67 +
1.68 + int id;
1.69 + explicit Arc(int pid) { id = pid;}
1.70 +
1.71 + public:
1.72 + Arc() {}
1.73 + Arc (Invalid) { id = -1; }
1.74 + bool operator==(const Arc& arc) const {return id == arc.id;}
1.75 + bool operator!=(const Arc& arc) const {return id != arc.id;}
1.76 + bool operator<(const Arc& arc) const {return id < arc.id;}
1.77 + };
1.78 +
1.79 +
1.80 +
1.81 + ListDigraphBase()
1.82 + : nodes(), first_node(-1),
1.83 + first_free_node(-1), arcs(), first_free_arc(-1) {}
1.84 +
1.85 +
1.86 + int maxNodeId() const { return nodes.size()-1; }
1.87 + int maxArcId() const { return arcs.size()-1; }
1.88 +
1.89 + Node source(Arc e) const { return Node(arcs[e.id].source); }
1.90 + Node target(Arc e) const { return Node(arcs[e.id].target); }
1.91 +
1.92 +
1.93 + void first(Node& node) const {
1.94 + node.id = first_node;
1.95 + }
1.96 +
1.97 + void next(Node& node) const {
1.98 + node.id = nodes[node.id].next;
1.99 + }
1.100 +
1.101 +
1.102 + void first(Arc& e) const {
1.103 + int n;
1.104 + for(n = first_node;
1.105 + n!=-1 && nodes[n].first_in == -1;
1.106 + n = nodes[n].next);
1.107 + e.id = (n == -1) ? -1 : nodes[n].first_in;
1.108 + }
1.109 +
1.110 + void next(Arc& arc) const {
1.111 + if (arcs[arc.id].next_in != -1) {
1.112 + arc.id = arcs[arc.id].next_in;
1.113 + } else {
1.114 + int n;
1.115 + for(n = nodes[arcs[arc.id].target].next;
1.116 + n!=-1 && nodes[n].first_in == -1;
1.117 + n = nodes[n].next);
1.118 + arc.id = (n == -1) ? -1 : nodes[n].first_in;
1.119 + }
1.120 + }
1.121 +
1.122 + void firstOut(Arc &e, const Node& v) const {
1.123 + e.id = nodes[v.id].first_out;
1.124 + }
1.125 + void nextOut(Arc &e) const {
1.126 + e.id=arcs[e.id].next_out;
1.127 + }
1.128 +
1.129 + void firstIn(Arc &e, const Node& v) const {
1.130 + e.id = nodes[v.id].first_in;
1.131 + }
1.132 + void nextIn(Arc &e) const {
1.133 + e.id=arcs[e.id].next_in;
1.134 + }
1.135 +
1.136 +
1.137 + static int id(Node v) { return v.id; }
1.138 + static int id(Arc e) { return e.id; }
1.139 +
1.140 + static Node nodeFromId(int id) { return Node(id);}
1.141 + static Arc arcFromId(int id) { return Arc(id);}
1.142 +
1.143 + Node addNode() {
1.144 + int n;
1.145 +
1.146 + if(first_free_node==-1) {
1.147 + n = nodes.size();
1.148 + nodes.push_back(NodeT());
1.149 + } else {
1.150 + n = first_free_node;
1.151 + first_free_node = nodes[n].next;
1.152 + }
1.153 +
1.154 + nodes[n].next = first_node;
1.155 + if(first_node != -1) nodes[first_node].prev = n;
1.156 + first_node = n;
1.157 + nodes[n].prev = -1;
1.158 +
1.159 + nodes[n].first_in = nodes[n].first_out = -1;
1.160 +
1.161 + return Node(n);
1.162 + }
1.163 +
1.164 + Arc addArc(Node u, Node v) {
1.165 + int n;
1.166 +
1.167 + if (first_free_arc == -1) {
1.168 + n = arcs.size();
1.169 + arcs.push_back(ArcT());
1.170 + } else {
1.171 + n = first_free_arc;
1.172 + first_free_arc = arcs[n].next_in;
1.173 + }
1.174 +
1.175 + arcs[n].source = u.id;
1.176 + arcs[n].target = v.id;
1.177 +
1.178 + arcs[n].next_out = nodes[u.id].first_out;
1.179 + if(nodes[u.id].first_out != -1) {
1.180 + arcs[nodes[u.id].first_out].prev_out = n;
1.181 + }
1.182 +
1.183 + arcs[n].next_in = nodes[v.id].first_in;
1.184 + if(nodes[v.id].first_in != -1) {
1.185 + arcs[nodes[v.id].first_in].prev_in = n;
1.186 + }
1.187 +
1.188 + arcs[n].prev_in = arcs[n].prev_out = -1;
1.189 +
1.190 + nodes[u.id].first_out = nodes[v.id].first_in = n;
1.191 +
1.192 + return Arc(n);
1.193 + }
1.194 +
1.195 + void erase(const Node& node) {
1.196 + int n = node.id;
1.197 +
1.198 + if(nodes[n].next != -1) {
1.199 + nodes[nodes[n].next].prev = nodes[n].prev;
1.200 + }
1.201 +
1.202 + if(nodes[n].prev != -1) {
1.203 + nodes[nodes[n].prev].next = nodes[n].next;
1.204 + } else {
1.205 + first_node = nodes[n].next;
1.206 + }
1.207 +
1.208 + nodes[n].next = first_free_node;
1.209 + first_free_node = n;
1.210 +
1.211 + }
1.212 +
1.213 + void erase(const Arc& arc) {
1.214 + int n = arc.id;
1.215 +
1.216 + if(arcs[n].next_in!=-1) {
1.217 + arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
1.218 + }
1.219 +
1.220 + if(arcs[n].prev_in!=-1) {
1.221 + arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
1.222 + } else {
1.223 + nodes[arcs[n].target].first_in = arcs[n].next_in;
1.224 + }
1.225 +
1.226 +
1.227 + if(arcs[n].next_out!=-1) {
1.228 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.229 + }
1.230 +
1.231 + if(arcs[n].prev_out!=-1) {
1.232 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.233 + } else {
1.234 + nodes[arcs[n].source].first_out = arcs[n].next_out;
1.235 + }
1.236 +
1.237 + arcs[n].next_in = first_free_arc;
1.238 + first_free_arc = n;
1.239 +
1.240 + }
1.241 +
1.242 + void clear() {
1.243 + arcs.clear();
1.244 + nodes.clear();
1.245 + first_node = first_free_node = first_free_arc = -1;
1.246 + }
1.247 +
1.248 + protected:
1.249 + void changeTarget(Arc e, Node n)
1.250 + {
1.251 + if(arcs[e.id].next_in != -1)
1.252 + arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
1.253 + if(arcs[e.id].prev_in != -1)
1.254 + arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
1.255 + else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
1.256 + if (nodes[n.id].first_in != -1) {
1.257 + arcs[nodes[n.id].first_in].prev_in = e.id;
1.258 + }
1.259 + arcs[e.id].target = n.id;
1.260 + arcs[e.id].prev_in = -1;
1.261 + arcs[e.id].next_in = nodes[n.id].first_in;
1.262 + nodes[n.id].first_in = e.id;
1.263 + }
1.264 + void changeSource(Arc e, Node n)
1.265 + {
1.266 + if(arcs[e.id].next_out != -1)
1.267 + arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
1.268 + if(arcs[e.id].prev_out != -1)
1.269 + arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
1.270 + else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
1.271 + if (nodes[n.id].first_out != -1) {
1.272 + arcs[nodes[n.id].first_out].prev_out = e.id;
1.273 + }
1.274 + arcs[e.id].source = n.id;
1.275 + arcs[e.id].prev_out = -1;
1.276 + arcs[e.id].next_out = nodes[n.id].first_out;
1.277 + nodes[n.id].first_out = e.id;
1.278 + }
1.279 +
1.280 + };
1.281 +
1.282 + typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
1.283 +
1.284 + /// \addtogroup digraphs
1.285 + /// @{
1.286 +
1.287 + ///A list digraph class.
1.288 +
1.289 + ///This is a simple and fast digraph implementation.
1.290 + ///
1.291 + ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
1.292 + ///also provides several additional useful extra functionalities.
1.293 + ///The most of the member functions and nested classes are
1.294 + ///documented only in the concept class.
1.295 + ///
1.296 + ///An important extra feature of this digraph implementation is that
1.297 + ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1.298 + ///
1.299 + ///\sa concepts::Digraph.
1.300 +
1.301 + class ListDigraph : public ExtendedListDigraphBase {
1.302 + private:
1.303 + ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.304 +
1.305 + ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.306 + ///
1.307 + ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
1.308 + ///\brief Assignment of ListDigraph to another one is \e not allowed.
1.309 + ///Use DigraphCopy() instead.
1.310 +
1.311 + ///Assignment of ListDigraph to another one is \e not allowed.
1.312 + ///Use DigraphCopy() instead.
1.313 + void operator=(const ListDigraph &) {}
1.314 + public:
1.315 +
1.316 + typedef ExtendedListDigraphBase Parent;
1.317 +
1.318 + /// Constructor
1.319 +
1.320 + /// Constructor.
1.321 + ///
1.322 + ListDigraph() {}
1.323 +
1.324 + ///Add a new node to the digraph.
1.325 +
1.326 + /// \return the new node.
1.327 + ///
1.328 + Node addNode() { return Parent::addNode(); }
1.329 +
1.330 + ///Add a new arc to the digraph.
1.331 +
1.332 + ///Add a new arc to the digraph with source node \c s
1.333 + ///and target node \c t.
1.334 + ///\return the new arc.
1.335 + Arc addArc(const Node& s, const Node& t) {
1.336 + return Parent::addArc(s, t);
1.337 + }
1.338 +
1.339 + /// Changes the target of \c e to \c n
1.340 +
1.341 + /// Changes the target of \c e to \c n
1.342 + ///
1.343 + ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
1.344 + ///the changed arc remain valid. However <tt>InArcIt</tt>s are
1.345 + ///invalidated.
1.346 + ///\warning This functionality cannot be used together with the Snapshot
1.347 + ///feature.
1.348 + void changeTarget(Arc e, Node n) {
1.349 + Parent::changeTarget(e,n);
1.350 + }
1.351 + /// Changes the source of \c e to \c n
1.352 +
1.353 + /// Changes the source of \c e to \c n
1.354 + ///
1.355 + ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
1.356 + ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
1.357 + ///invalidated.
1.358 + ///\warning This functionality cannot be used together with the Snapshot
1.359 + ///feature.
1.360 + void changeSource(Arc e, Node n) {
1.361 + Parent::changeSource(e,n);
1.362 + }
1.363 +
1.364 + /// Invert the direction of an arc.
1.365 +
1.366 + ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
1.367 + ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
1.368 + ///invalidated.
1.369 + ///\warning This functionality cannot be used together with the Snapshot
1.370 + ///feature.
1.371 + void reverseArc(Arc e) {
1.372 + Node t=target(e);
1.373 + changeTarget(e,source(e));
1.374 + changeSource(e,t);
1.375 + }
1.376 +
1.377 + /// Using this it is possible to avoid the superfluous memory
1.378 + /// allocation: if you know that the digraph you want to build will
1.379 + /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.380 + /// then it is worth reserving space for this amount before starting
1.381 + /// to build the digraph.
1.382 + /// \sa reserveArc
1.383 + void reserveNode(int n) { nodes.reserve(n); };
1.384 +
1.385 + /// \brief Using this it is possible to avoid the superfluous memory
1.386 + /// allocation.
1.387 +
1.388 + /// Using this it is possible to avoid the superfluous memory
1.389 + /// allocation: if you know that the digraph you want to build will
1.390 + /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.391 + /// then it is worth reserving space for this amount before starting
1.392 + /// to build the digraph.
1.393 + /// \sa reserveNode
1.394 + void reserveArc(int m) { arcs.reserve(m); };
1.395 +
1.396 + ///Contract two nodes.
1.397 +
1.398 + ///This function contracts two nodes.
1.399 + ///
1.400 + ///Node \p b will be removed but instead of deleting
1.401 + ///incident arcs, they will be joined to \p a.
1.402 + ///The last parameter \p r controls whether to remove loops. \c true
1.403 + ///means that loops will be removed.
1.404 + ///
1.405 + ///\note The <tt>ArcIt</tt>s
1.406 + ///referencing a moved arc remain
1.407 + ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
1.408 + ///may be invalidated.
1.409 + ///\warning This functionality cannot be used together with the Snapshot
1.410 + ///feature.
1.411 + void contract(Node a, Node b, bool r = true)
1.412 + {
1.413 + for(OutArcIt e(*this,b);e!=INVALID;) {
1.414 + OutArcIt f=e;
1.415 + ++f;
1.416 + if(r && target(e)==a) erase(e);
1.417 + else changeSource(e,a);
1.418 + e=f;
1.419 + }
1.420 + for(InArcIt e(*this,b);e!=INVALID;) {
1.421 + InArcIt f=e;
1.422 + ++f;
1.423 + if(r && source(e)==a) erase(e);
1.424 + else changeTarget(e,a);
1.425 + e=f;
1.426 + }
1.427 + erase(b);
1.428 + }
1.429 +
1.430 + ///Split a node.
1.431 +
1.432 + ///This function splits a node. First a new node is added to the digraph,
1.433 + ///then the source of each outgoing arc of \c n is moved to this new node.
1.434 + ///If \c connect is \c true (this is the default value), then a new arc
1.435 + ///from \c n to the newly created node is also added.
1.436 + ///\return The newly created node.
1.437 + ///
1.438 + ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
1.439 + ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
1.440 + ///be invalidated.
1.441 + ///
1.442 + ///\warning This functionality cannot be used together with the
1.443 + ///Snapshot feature. \todo It could be implemented in a bit
1.444 + ///faster way.
1.445 + Node split(Node n, bool connect = true) {
1.446 + Node b = addNode();
1.447 + for(OutArcIt e(*this,n);e!=INVALID;) {
1.448 + OutArcIt f=e;
1.449 + ++f;
1.450 + changeSource(e,b);
1.451 + e=f;
1.452 + }
1.453 + if (connect) addArc(n,b);
1.454 + return b;
1.455 + }
1.456 +
1.457 + ///Split an arc.
1.458 +
1.459 + ///This function splits an arc. First a new node \c b is added to
1.460 + ///the digraph, then the original arc is re-targeted to \c
1.461 + ///b. Finally an arc from \c b to the original target is added.
1.462 + ///\return The newly created node.
1.463 + ///\warning This functionality
1.464 + ///cannot be used together with the Snapshot feature.
1.465 + Node split(Arc e) {
1.466 + Node b = addNode();
1.467 + addArc(b,target(e));
1.468 + changeTarget(e,b);
1.469 + return b;
1.470 + }
1.471 +
1.472 + /// \brief Class to make a snapshot of the digraph and restore
1.473 + /// to it later.
1.474 + ///
1.475 + /// Class to make a snapshot of the digraph and to restore it
1.476 + /// later.
1.477 + ///
1.478 + /// The newly added nodes and arcs can be removed using the
1.479 + /// restore() function.
1.480 + ///
1.481 + /// \warning Arc and node deletions cannot be restored. This
1.482 + /// events invalidate the snapshot.
1.483 + class Snapshot {
1.484 + protected:
1.485 +
1.486 + typedef Parent::NodeNotifier NodeNotifier;
1.487 +
1.488 + class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.489 + public:
1.490 +
1.491 + NodeObserverProxy(Snapshot& _snapshot)
1.492 + : snapshot(_snapshot) {}
1.493 +
1.494 + using NodeNotifier::ObserverBase::attach;
1.495 + using NodeNotifier::ObserverBase::detach;
1.496 + using NodeNotifier::ObserverBase::attached;
1.497 +
1.498 + protected:
1.499 +
1.500 + virtual void add(const Node& node) {
1.501 + snapshot.addNode(node);
1.502 + }
1.503 + virtual void add(const std::vector<Node>& nodes) {
1.504 + for (int i = nodes.size() - 1; i >= 0; ++i) {
1.505 + snapshot.addNode(nodes[i]);
1.506 + }
1.507 + }
1.508 + virtual void erase(const Node& node) {
1.509 + snapshot.eraseNode(node);
1.510 + }
1.511 + virtual void erase(const std::vector<Node>& nodes) {
1.512 + for (int i = 0; i < int(nodes.size()); ++i) {
1.513 + snapshot.eraseNode(nodes[i]);
1.514 + }
1.515 + }
1.516 + virtual void build() {
1.517 + Node node;
1.518 + std::vector<Node> nodes;
1.519 + for (notifier()->first(node); node != INVALID;
1.520 + notifier()->next(node)) {
1.521 + nodes.push_back(node);
1.522 + }
1.523 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.524 + snapshot.addNode(nodes[i]);
1.525 + }
1.526 + }
1.527 + virtual void clear() {
1.528 + Node node;
1.529 + for (notifier()->first(node); node != INVALID;
1.530 + notifier()->next(node)) {
1.531 + snapshot.eraseNode(node);
1.532 + }
1.533 + }
1.534 +
1.535 + Snapshot& snapshot;
1.536 + };
1.537 +
1.538 + class ArcObserverProxy : public ArcNotifier::ObserverBase {
1.539 + public:
1.540 +
1.541 + ArcObserverProxy(Snapshot& _snapshot)
1.542 + : snapshot(_snapshot) {}
1.543 +
1.544 + using ArcNotifier::ObserverBase::attach;
1.545 + using ArcNotifier::ObserverBase::detach;
1.546 + using ArcNotifier::ObserverBase::attached;
1.547 +
1.548 + protected:
1.549 +
1.550 + virtual void add(const Arc& arc) {
1.551 + snapshot.addArc(arc);
1.552 + }
1.553 + virtual void add(const std::vector<Arc>& arcs) {
1.554 + for (int i = arcs.size() - 1; i >= 0; ++i) {
1.555 + snapshot.addArc(arcs[i]);
1.556 + }
1.557 + }
1.558 + virtual void erase(const Arc& arc) {
1.559 + snapshot.eraseArc(arc);
1.560 + }
1.561 + virtual void erase(const std::vector<Arc>& arcs) {
1.562 + for (int i = 0; i < int(arcs.size()); ++i) {
1.563 + snapshot.eraseArc(arcs[i]);
1.564 + }
1.565 + }
1.566 + virtual void build() {
1.567 + Arc arc;
1.568 + std::vector<Arc> arcs;
1.569 + for (notifier()->first(arc); arc != INVALID;
1.570 + notifier()->next(arc)) {
1.571 + arcs.push_back(arc);
1.572 + }
1.573 + for (int i = arcs.size() - 1; i >= 0; --i) {
1.574 + snapshot.addArc(arcs[i]);
1.575 + }
1.576 + }
1.577 + virtual void clear() {
1.578 + Arc arc;
1.579 + for (notifier()->first(arc); arc != INVALID;
1.580 + notifier()->next(arc)) {
1.581 + snapshot.eraseArc(arc);
1.582 + }
1.583 + }
1.584 +
1.585 + Snapshot& snapshot;
1.586 + };
1.587 +
1.588 + ListDigraph *digraph;
1.589 +
1.590 + NodeObserverProxy node_observer_proxy;
1.591 + ArcObserverProxy arc_observer_proxy;
1.592 +
1.593 + std::list<Node> added_nodes;
1.594 + std::list<Arc> added_arcs;
1.595 +
1.596 +
1.597 + void addNode(const Node& node) {
1.598 + added_nodes.push_front(node);
1.599 + }
1.600 + void eraseNode(const Node& node) {
1.601 + std::list<Node>::iterator it =
1.602 + std::find(added_nodes.begin(), added_nodes.end(), node);
1.603 + if (it == added_nodes.end()) {
1.604 + clear();
1.605 + arc_observer_proxy.detach();
1.606 + throw NodeNotifier::ImmediateDetach();
1.607 + } else {
1.608 + added_nodes.erase(it);
1.609 + }
1.610 + }
1.611 +
1.612 + void addArc(const Arc& arc) {
1.613 + added_arcs.push_front(arc);
1.614 + }
1.615 + void eraseArc(const Arc& arc) {
1.616 + std::list<Arc>::iterator it =
1.617 + std::find(added_arcs.begin(), added_arcs.end(), arc);
1.618 + if (it == added_arcs.end()) {
1.619 + clear();
1.620 + node_observer_proxy.detach();
1.621 + throw ArcNotifier::ImmediateDetach();
1.622 + } else {
1.623 + added_arcs.erase(it);
1.624 + }
1.625 + }
1.626 +
1.627 + void attach(ListDigraph &_digraph) {
1.628 + digraph = &_digraph;
1.629 + node_observer_proxy.attach(digraph->notifier(Node()));
1.630 + arc_observer_proxy.attach(digraph->notifier(Arc()));
1.631 + }
1.632 +
1.633 + void detach() {
1.634 + node_observer_proxy.detach();
1.635 + arc_observer_proxy.detach();
1.636 + }
1.637 +
1.638 + bool attached() const {
1.639 + return node_observer_proxy.attached();
1.640 + }
1.641 +
1.642 + void clear() {
1.643 + added_nodes.clear();
1.644 + added_arcs.clear();
1.645 + }
1.646 +
1.647 + public:
1.648 +
1.649 + /// \brief Default constructor.
1.650 + ///
1.651 + /// Default constructor.
1.652 + /// To actually make a snapshot you must call save().
1.653 + Snapshot()
1.654 + : digraph(0), node_observer_proxy(*this),
1.655 + arc_observer_proxy(*this) {}
1.656 +
1.657 + /// \brief Constructor that immediately makes a snapshot.
1.658 + ///
1.659 + /// This constructor immediately makes a snapshot of the digraph.
1.660 + /// \param _digraph The digraph we make a snapshot of.
1.661 + Snapshot(ListDigraph &_digraph)
1.662 + : node_observer_proxy(*this),
1.663 + arc_observer_proxy(*this) {
1.664 + attach(_digraph);
1.665 + }
1.666 +
1.667 + /// \brief Make a snapshot.
1.668 + ///
1.669 + /// Make a snapshot of the digraph.
1.670 + ///
1.671 + /// This function can be called more than once. In case of a repeated
1.672 + /// call, the previous snapshot gets lost.
1.673 + /// \param _digraph The digraph we make the snapshot of.
1.674 + void save(ListDigraph &_digraph) {
1.675 + if (attached()) {
1.676 + detach();
1.677 + clear();
1.678 + }
1.679 + attach(_digraph);
1.680 + }
1.681 +
1.682 + /// \brief Undo the changes until the last snapshot.
1.683 + //
1.684 + /// Undo the changes until the last snapshot created by save().
1.685 + void restore() {
1.686 + detach();
1.687 + for(std::list<Arc>::iterator it = added_arcs.begin();
1.688 + it != added_arcs.end(); ++it) {
1.689 + digraph->erase(*it);
1.690 + }
1.691 + for(std::list<Node>::iterator it = added_nodes.begin();
1.692 + it != added_nodes.end(); ++it) {
1.693 + digraph->erase(*it);
1.694 + }
1.695 + clear();
1.696 + }
1.697 +
1.698 + /// \brief Gives back true when the snapshot is valid.
1.699 + ///
1.700 + /// Gives back true when the snapshot is valid.
1.701 + bool valid() const {
1.702 + return attached();
1.703 + }
1.704 + };
1.705 +
1.706 + };
1.707 +
1.708 + ///@}
1.709 +
1.710 + class ListGraphBase {
1.711 +
1.712 + protected:
1.713 +
1.714 + struct NodeT {
1.715 + int first_out;
1.716 + int prev, next;
1.717 + };
1.718 +
1.719 + struct ArcT {
1.720 + int target;
1.721 + int prev_out, next_out;
1.722 + };
1.723 +
1.724 + std::vector<NodeT> nodes;
1.725 +
1.726 + int first_node;
1.727 +
1.728 + int first_free_node;
1.729 +
1.730 + std::vector<ArcT> arcs;
1.731 +
1.732 + int first_free_arc;
1.733 +
1.734 + public:
1.735 +
1.736 + typedef ListGraphBase Digraph;
1.737 +
1.738 + class Node;
1.739 + class Arc;
1.740 + class Edge;
1.741 +
1.742 + class Node {
1.743 + friend class ListGraphBase;
1.744 + protected:
1.745 +
1.746 + int id;
1.747 + explicit Node(int pid) { id = pid;}
1.748 +
1.749 + public:
1.750 + Node() {}
1.751 + Node (Invalid) { id = -1; }
1.752 + bool operator==(const Node& node) const {return id == node.id;}
1.753 + bool operator!=(const Node& node) const {return id != node.id;}
1.754 + bool operator<(const Node& node) const {return id < node.id;}
1.755 + };
1.756 +
1.757 + class Edge {
1.758 + friend class ListGraphBase;
1.759 + protected:
1.760 +
1.761 + int id;
1.762 + explicit Edge(int pid) { id = pid;}
1.763 +
1.764 + public:
1.765 + Edge() {}
1.766 + Edge (Invalid) { id = -1; }
1.767 + bool operator==(const Edge& arc) const {return id == arc.id;}
1.768 + bool operator!=(const Edge& arc) const {return id != arc.id;}
1.769 + bool operator<(const Edge& arc) const {return id < arc.id;}
1.770 + };
1.771 +
1.772 + class Arc {
1.773 + friend class ListGraphBase;
1.774 + protected:
1.775 +
1.776 + int id;
1.777 + explicit Arc(int pid) { id = pid;}
1.778 +
1.779 + public:
1.780 + operator Edge() const { return edgeFromId(id / 2); }
1.781 +
1.782 + Arc() {}
1.783 + Arc (Invalid) { id = -1; }
1.784 + bool operator==(const Arc& arc) const {return id == arc.id;}
1.785 + bool operator!=(const Arc& arc) const {return id != arc.id;}
1.786 + bool operator<(const Arc& arc) const {return id < arc.id;}
1.787 + };
1.788 +
1.789 +
1.790 +
1.791 + ListGraphBase()
1.792 + : nodes(), first_node(-1),
1.793 + first_free_node(-1), arcs(), first_free_arc(-1) {}
1.794 +
1.795 +
1.796 + int maxNodeId() const { return nodes.size()-1; }
1.797 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.798 + int maxArcId() const { return arcs.size()-1; }
1.799 +
1.800 + Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.801 + Node target(Arc e) const { return Node(arcs[e.id].target); }
1.802 +
1.803 + Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
1.804 + Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
1.805 +
1.806 + static bool direction(Arc e) {
1.807 + return (e.id & 1) == 1;
1.808 + }
1.809 +
1.810 + static Arc direct(Edge e, bool d) {
1.811 + return Arc(e.id * 2 + (d ? 1 : 0));
1.812 + }
1.813 +
1.814 + void first(Node& node) const {
1.815 + node.id = first_node;
1.816 + }
1.817 +
1.818 + void next(Node& node) const {
1.819 + node.id = nodes[node.id].next;
1.820 + }
1.821 +
1.822 + void first(Arc& e) const {
1.823 + int n = first_node;
1.824 + while (n != -1 && nodes[n].first_out == -1) {
1.825 + n = nodes[n].next;
1.826 + }
1.827 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.828 + }
1.829 +
1.830 + void next(Arc& e) const {
1.831 + if (arcs[e.id].next_out != -1) {
1.832 + e.id = arcs[e.id].next_out;
1.833 + } else {
1.834 + int n = nodes[arcs[e.id ^ 1].target].next;
1.835 + while(n != -1 && nodes[n].first_out == -1) {
1.836 + n = nodes[n].next;
1.837 + }
1.838 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.839 + }
1.840 + }
1.841 +
1.842 + void first(Edge& e) const {
1.843 + int n = first_node;
1.844 + while (n != -1) {
1.845 + e.id = nodes[n].first_out;
1.846 + while ((e.id & 1) != 1) {
1.847 + e.id = arcs[e.id].next_out;
1.848 + }
1.849 + if (e.id != -1) {
1.850 + e.id /= 2;
1.851 + return;
1.852 + }
1.853 + n = nodes[n].next;
1.854 + }
1.855 + e.id = -1;
1.856 + }
1.857 +
1.858 + void next(Edge& e) const {
1.859 + int n = arcs[e.id * 2].target;
1.860 + e.id = arcs[(e.id * 2) | 1].next_out;
1.861 + while ((e.id & 1) != 1) {
1.862 + e.id = arcs[e.id].next_out;
1.863 + }
1.864 + if (e.id != -1) {
1.865 + e.id /= 2;
1.866 + return;
1.867 + }
1.868 + n = nodes[n].next;
1.869 + while (n != -1) {
1.870 + e.id = nodes[n].first_out;
1.871 + while ((e.id & 1) != 1) {
1.872 + e.id = arcs[e.id].next_out;
1.873 + }
1.874 + if (e.id != -1) {
1.875 + e.id /= 2;
1.876 + return;
1.877 + }
1.878 + n = nodes[n].next;
1.879 + }
1.880 + e.id = -1;
1.881 + }
1.882 +
1.883 + void firstOut(Arc &e, const Node& v) const {
1.884 + e.id = nodes[v.id].first_out;
1.885 + }
1.886 + void nextOut(Arc &e) const {
1.887 + e.id = arcs[e.id].next_out;
1.888 + }
1.889 +
1.890 + void firstIn(Arc &e, const Node& v) const {
1.891 + e.id = ((nodes[v.id].first_out) ^ 1);
1.892 + if (e.id == -2) e.id = -1;
1.893 + }
1.894 + void nextIn(Arc &e) const {
1.895 + e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
1.896 + if (e.id == -2) e.id = -1;
1.897 + }
1.898 +
1.899 + void firstInc(Edge &e, bool& d, const Node& v) const {
1.900 + int de = nodes[v.id].first_out;
1.901 + if (de != -1 ) {
1.902 + e.id = de / 2;
1.903 + d = ((de & 1) == 1);
1.904 + } else {
1.905 + e.id = -1;
1.906 + d = true;
1.907 + }
1.908 + }
1.909 + void nextInc(Edge &e, bool& d) const {
1.910 + int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.911 + if (de != -1 ) {
1.912 + e.id = de / 2;
1.913 + d = ((de & 1) == 1);
1.914 + } else {
1.915 + e.id = -1;
1.916 + d = true;
1.917 + }
1.918 + }
1.919 +
1.920 + static int id(Node v) { return v.id; }
1.921 + static int id(Arc e) { return e.id; }
1.922 + static int id(Edge e) { return e.id; }
1.923 +
1.924 + static Node nodeFromId(int id) { return Node(id);}
1.925 + static Arc arcFromId(int id) { return Arc(id);}
1.926 + static Edge edgeFromId(int id) { return Edge(id);}
1.927 +
1.928 + Node addNode() {
1.929 + int n;
1.930 +
1.931 + if(first_free_node==-1) {
1.932 + n = nodes.size();
1.933 + nodes.push_back(NodeT());
1.934 + } else {
1.935 + n = first_free_node;
1.936 + first_free_node = nodes[n].next;
1.937 + }
1.938 +
1.939 + nodes[n].next = first_node;
1.940 + if (first_node != -1) nodes[first_node].prev = n;
1.941 + first_node = n;
1.942 + nodes[n].prev = -1;
1.943 +
1.944 + nodes[n].first_out = -1;
1.945 +
1.946 + return Node(n);
1.947 + }
1.948 +
1.949 + Edge addEdge(Node u, Node v) {
1.950 + int n;
1.951 +
1.952 + if (first_free_arc == -1) {
1.953 + n = arcs.size();
1.954 + arcs.push_back(ArcT());
1.955 + arcs.push_back(ArcT());
1.956 + } else {
1.957 + n = first_free_arc;
1.958 + first_free_arc = arcs[n].next_out;
1.959 + }
1.960 +
1.961 + arcs[n].target = u.id;
1.962 + arcs[n | 1].target = v.id;
1.963 +
1.964 + arcs[n].next_out = nodes[v.id].first_out;
1.965 + if (nodes[v.id].first_out != -1) {
1.966 + arcs[nodes[v.id].first_out].prev_out = n;
1.967 + }
1.968 + arcs[n].prev_out = -1;
1.969 + nodes[v.id].first_out = n;
1.970 +
1.971 + arcs[n | 1].next_out = nodes[u.id].first_out;
1.972 + if (nodes[u.id].first_out != -1) {
1.973 + arcs[nodes[u.id].first_out].prev_out = (n | 1);
1.974 + }
1.975 + arcs[n | 1].prev_out = -1;
1.976 + nodes[u.id].first_out = (n | 1);
1.977 +
1.978 + return Edge(n / 2);
1.979 + }
1.980 +
1.981 + void erase(const Node& node) {
1.982 + int n = node.id;
1.983 +
1.984 + if(nodes[n].next != -1) {
1.985 + nodes[nodes[n].next].prev = nodes[n].prev;
1.986 + }
1.987 +
1.988 + if(nodes[n].prev != -1) {
1.989 + nodes[nodes[n].prev].next = nodes[n].next;
1.990 + } else {
1.991 + first_node = nodes[n].next;
1.992 + }
1.993 +
1.994 + nodes[n].next = first_free_node;
1.995 + first_free_node = n;
1.996 +
1.997 + }
1.998 +
1.999 + void erase(const Edge& arc) {
1.1000 + int n = arc.id * 2;
1.1001 +
1.1002 + if (arcs[n].next_out != -1) {
1.1003 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.1004 + }
1.1005 +
1.1006 + if (arcs[n].prev_out != -1) {
1.1007 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.1008 + } else {
1.1009 + nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1.1010 + }
1.1011 +
1.1012 + if (arcs[n | 1].next_out != -1) {
1.1013 + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.1014 + }
1.1015 +
1.1016 + if (arcs[n | 1].prev_out != -1) {
1.1017 + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.1018 + } else {
1.1019 + nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1.1020 + }
1.1021 +
1.1022 + arcs[n].next_out = first_free_arc;
1.1023 + first_free_arc = n;
1.1024 +
1.1025 + }
1.1026 +
1.1027 + void clear() {
1.1028 + arcs.clear();
1.1029 + nodes.clear();
1.1030 + first_node = first_free_node = first_free_arc = -1;
1.1031 + }
1.1032 +
1.1033 + protected:
1.1034 +
1.1035 + void changeTarget(Edge e, Node n) {
1.1036 + if(arcs[2 * e.id].next_out != -1) {
1.1037 + arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.1038 + }
1.1039 + if(arcs[2 * e.id].prev_out != -1) {
1.1040 + arcs[arcs[2 * e.id].prev_out].next_out =
1.1041 + arcs[2 * e.id].next_out;
1.1042 + } else {
1.1043 + nodes[arcs[(2 * e.id) | 1].target].first_out =
1.1044 + arcs[2 * e.id].next_out;
1.1045 + }
1.1046 +
1.1047 + if (nodes[n.id].first_out != -1) {
1.1048 + arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1.1049 + }
1.1050 + arcs[(2 * e.id) | 1].target = n.id;
1.1051 + arcs[2 * e.id].prev_out = -1;
1.1052 + arcs[2 * e.id].next_out = nodes[n.id].first_out;
1.1053 + nodes[n.id].first_out = 2 * e.id;
1.1054 + }
1.1055 +
1.1056 + void changeSource(Edge e, Node n) {
1.1057 + if(arcs[(2 * e.id) | 1].next_out != -1) {
1.1058 + arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.1059 + arcs[(2 * e.id) | 1].prev_out;
1.1060 + }
1.1061 + if(arcs[(2 * e.id) | 1].prev_out != -1) {
1.1062 + arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1.1063 + arcs[(2 * e.id) | 1].next_out;
1.1064 + } else {
1.1065 + nodes[arcs[2 * e.id].target].first_out =
1.1066 + arcs[(2 * e.id) | 1].next_out;
1.1067 + }
1.1068 +
1.1069 + if (nodes[n.id].first_out != -1) {
1.1070 + arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.1071 + }
1.1072 + arcs[2 * e.id].target = n.id;
1.1073 + arcs[(2 * e.id) | 1].prev_out = -1;
1.1074 + arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.1075 + nodes[n.id].first_out = ((2 * e.id) | 1);
1.1076 + }
1.1077 +
1.1078 + };
1.1079 +
1.1080 +// typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >
1.1081 +// ExtendedListGraphBase;
1.1082 +
1.1083 + typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1.1084 +
1.1085 +
1.1086 +
1.1087 + /// \addtogroup digraphs
1.1088 + /// @{
1.1089 +
1.1090 + ///An undirected list digraph class.
1.1091 +
1.1092 + ///This is a simple and fast undirected digraph implementation.
1.1093 + ///
1.1094 + ///An important extra feature of this digraph implementation is that
1.1095 + ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1.1096 + ///
1.1097 + ///It conforms to the
1.1098 + ///\ref concepts::Graph "Graph concept".
1.1099 + ///
1.1100 + ///\sa concepts::Graph.
1.1101 + ///
1.1102 + class ListGraph : public ExtendedListGraphBase {
1.1103 + private:
1.1104 + ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
1.1105 +
1.1106 + ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
1.1107 + ///
1.1108 + ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
1.1109 + ///\brief Assignment of ListGraph to another one is \e not allowed.
1.1110 + ///Use GraphCopy() instead.
1.1111 +
1.1112 + ///Assignment of ListGraph to another one is \e not allowed.
1.1113 + ///Use GraphCopy() instead.
1.1114 + void operator=(const ListGraph &) {}
1.1115 + public:
1.1116 + /// Constructor
1.1117 +
1.1118 + /// Constructor.
1.1119 + ///
1.1120 + ListGraph() {}
1.1121 +
1.1122 + typedef ExtendedListGraphBase Parent;
1.1123 +
1.1124 + typedef Parent::OutArcIt IncArcIt;
1.1125 +
1.1126 + /// \brief Add a new node to the digraph.
1.1127 + ///
1.1128 + /// \return the new node.
1.1129 + ///
1.1130 + Node addNode() { return Parent::addNode(); }
1.1131 +
1.1132 + /// \brief Add a new edge to the digraph.
1.1133 + ///
1.1134 + /// Add a new arc to the digraph with source node \c s
1.1135 + /// and target node \c t.
1.1136 + /// \return the new edge.
1.1137 + Edge addEdge(const Node& s, const Node& t) {
1.1138 + return Parent::addEdge(s, t);
1.1139 + }
1.1140 + /// \brief Changes the source of \c e to \c n
1.1141 + ///
1.1142 + /// Changes the source of \c e to \c n
1.1143 + ///
1.1144 + ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1.1145 + ///referencing the changed arc remain
1.1146 + ///valid. However <tt>OutArcIt</tt>s are invalidated.
1.1147 + void changeSource(Edge e, Node n) {
1.1148 + Parent::changeSource(e,n);
1.1149 + }
1.1150 + /// \brief Changes the target of \c e to \c n
1.1151 + ///
1.1152 + /// Changes the target of \c e to \c n
1.1153 + ///
1.1154 + /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
1.1155 + /// valid. However the other iterators may be invalidated.
1.1156 + void changeTarget(Edge e, Node n) {
1.1157 + Parent::changeTarget(e,n);
1.1158 + }
1.1159 + /// \brief Changes the source of \c e to \c n
1.1160 + ///
1.1161 + /// Changes the source of \c e to \c n. It changes the proper
1.1162 + /// node of the represented edge.
1.1163 + ///
1.1164 + ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1.1165 + ///referencing the changed arc remain
1.1166 + ///valid. However <tt>OutArcIt</tt>s are invalidated.
1.1167 + void changeSource(Arc e, Node n) {
1.1168 + if (Parent::direction(e)) {
1.1169 + Parent::changeSource(e,n);
1.1170 + } else {
1.1171 + Parent::changeTarget(e,n);
1.1172 + }
1.1173 + }
1.1174 + /// \brief Changes the target of \c e to \c n
1.1175 + ///
1.1176 + /// Changes the target of \c e to \c n. It changes the proper
1.1177 + /// node of the represented edge.
1.1178 + ///
1.1179 + ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
1.1180 + ///referencing the changed arc remain
1.1181 + ///valid. However <tt>InArcIt</tt>s are invalidated.
1.1182 + void changeTarget(Arc e, Node n) {
1.1183 + if (Parent::direction(e)) {
1.1184 + Parent::changeTarget(e,n);
1.1185 + } else {
1.1186 + Parent::changeSource(e,n);
1.1187 + }
1.1188 + }
1.1189 + /// \brief Contract two nodes.
1.1190 + ///
1.1191 + /// This function contracts two nodes.
1.1192 + ///
1.1193 + /// Node \p b will be removed but instead of deleting
1.1194 + /// its neighboring arcs, they will be joined to \p a.
1.1195 + /// The last parameter \p r controls whether to remove loops. \c true
1.1196 + /// means that loops will be removed.
1.1197 + ///
1.1198 + /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
1.1199 + /// valid.
1.1200 + void contract(Node a, Node b, bool r = true) {
1.1201 + for(IncArcIt e(*this, b); e!=INVALID;) {
1.1202 + IncArcIt f = e; ++f;
1.1203 + if (r && runningNode(e) == a) {
1.1204 + erase(e);
1.1205 + } else if (source(e) == b) {
1.1206 + changeSource(e, a);
1.1207 + } else {
1.1208 + changeTarget(e, a);
1.1209 + }
1.1210 + e = f;
1.1211 + }
1.1212 + erase(b);
1.1213 + }
1.1214 +
1.1215 +
1.1216 + /// \brief Class to make a snapshot of the digraph and restore
1.1217 + /// to it later.
1.1218 + ///
1.1219 + /// Class to make a snapshot of the digraph and to restore it
1.1220 + /// later.
1.1221 + ///
1.1222 + /// The newly added nodes and edges can be removed
1.1223 + /// using the restore() function.
1.1224 + ///
1.1225 + /// \warning Arc and node deletions cannot be restored. This
1.1226 + /// events invalidate the snapshot.
1.1227 + class Snapshot {
1.1228 + protected:
1.1229 +
1.1230 + typedef Parent::NodeNotifier NodeNotifier;
1.1231 +
1.1232 + class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.1233 + public:
1.1234 +
1.1235 + NodeObserverProxy(Snapshot& _snapshot)
1.1236 + : snapshot(_snapshot) {}
1.1237 +
1.1238 + using NodeNotifier::ObserverBase::attach;
1.1239 + using NodeNotifier::ObserverBase::detach;
1.1240 + using NodeNotifier::ObserverBase::attached;
1.1241 +
1.1242 + protected:
1.1243 +
1.1244 + virtual void add(const Node& node) {
1.1245 + snapshot.addNode(node);
1.1246 + }
1.1247 + virtual void add(const std::vector<Node>& nodes) {
1.1248 + for (int i = nodes.size() - 1; i >= 0; ++i) {
1.1249 + snapshot.addNode(nodes[i]);
1.1250 + }
1.1251 + }
1.1252 + virtual void erase(const Node& node) {
1.1253 + snapshot.eraseNode(node);
1.1254 + }
1.1255 + virtual void erase(const std::vector<Node>& nodes) {
1.1256 + for (int i = 0; i < int(nodes.size()); ++i) {
1.1257 + snapshot.eraseNode(nodes[i]);
1.1258 + }
1.1259 + }
1.1260 + virtual void build() {
1.1261 + Node node;
1.1262 + std::vector<Node> nodes;
1.1263 + for (notifier()->first(node); node != INVALID;
1.1264 + notifier()->next(node)) {
1.1265 + nodes.push_back(node);
1.1266 + }
1.1267 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.1268 + snapshot.addNode(nodes[i]);
1.1269 + }
1.1270 + }
1.1271 + virtual void clear() {
1.1272 + Node node;
1.1273 + for (notifier()->first(node); node != INVALID;
1.1274 + notifier()->next(node)) {
1.1275 + snapshot.eraseNode(node);
1.1276 + }
1.1277 + }
1.1278 +
1.1279 + Snapshot& snapshot;
1.1280 + };
1.1281 +
1.1282 + class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1.1283 + public:
1.1284 +
1.1285 + EdgeObserverProxy(Snapshot& _snapshot)
1.1286 + : snapshot(_snapshot) {}
1.1287 +
1.1288 + using EdgeNotifier::ObserverBase::attach;
1.1289 + using EdgeNotifier::ObserverBase::detach;
1.1290 + using EdgeNotifier::ObserverBase::attached;
1.1291 +
1.1292 + protected:
1.1293 +
1.1294 + virtual void add(const Edge& arc) {
1.1295 + snapshot.addEdge(arc);
1.1296 + }
1.1297 + virtual void add(const std::vector<Edge>& arcs) {
1.1298 + for (int i = arcs.size() - 1; i >= 0; ++i) {
1.1299 + snapshot.addEdge(arcs[i]);
1.1300 + }
1.1301 + }
1.1302 + virtual void erase(const Edge& arc) {
1.1303 + snapshot.eraseEdge(arc);
1.1304 + }
1.1305 + virtual void erase(const std::vector<Edge>& arcs) {
1.1306 + for (int i = 0; i < int(arcs.size()); ++i) {
1.1307 + snapshot.eraseEdge(arcs[i]);
1.1308 + }
1.1309 + }
1.1310 + virtual void build() {
1.1311 + Edge arc;
1.1312 + std::vector<Edge> arcs;
1.1313 + for (notifier()->first(arc); arc != INVALID;
1.1314 + notifier()->next(arc)) {
1.1315 + arcs.push_back(arc);
1.1316 + }
1.1317 + for (int i = arcs.size() - 1; i >= 0; --i) {
1.1318 + snapshot.addEdge(arcs[i]);
1.1319 + }
1.1320 + }
1.1321 + virtual void clear() {
1.1322 + Edge arc;
1.1323 + for (notifier()->first(arc); arc != INVALID;
1.1324 + notifier()->next(arc)) {
1.1325 + snapshot.eraseEdge(arc);
1.1326 + }
1.1327 + }
1.1328 +
1.1329 + Snapshot& snapshot;
1.1330 + };
1.1331 +
1.1332 + ListGraph *digraph;
1.1333 +
1.1334 + NodeObserverProxy node_observer_proxy;
1.1335 + EdgeObserverProxy arc_observer_proxy;
1.1336 +
1.1337 + std::list<Node> added_nodes;
1.1338 + std::list<Edge> added_arcs;
1.1339 +
1.1340 +
1.1341 + void addNode(const Node& node) {
1.1342 + added_nodes.push_front(node);
1.1343 + }
1.1344 + void eraseNode(const Node& node) {
1.1345 + std::list<Node>::iterator it =
1.1346 + std::find(added_nodes.begin(), added_nodes.end(), node);
1.1347 + if (it == added_nodes.end()) {
1.1348 + clear();
1.1349 + arc_observer_proxy.detach();
1.1350 + throw NodeNotifier::ImmediateDetach();
1.1351 + } else {
1.1352 + added_nodes.erase(it);
1.1353 + }
1.1354 + }
1.1355 +
1.1356 + void addEdge(const Edge& arc) {
1.1357 + added_arcs.push_front(arc);
1.1358 + }
1.1359 + void eraseEdge(const Edge& arc) {
1.1360 + std::list<Edge>::iterator it =
1.1361 + std::find(added_arcs.begin(), added_arcs.end(), arc);
1.1362 + if (it == added_arcs.end()) {
1.1363 + clear();
1.1364 + node_observer_proxy.detach();
1.1365 + throw EdgeNotifier::ImmediateDetach();
1.1366 + } else {
1.1367 + added_arcs.erase(it);
1.1368 + }
1.1369 + }
1.1370 +
1.1371 + void attach(ListGraph &_digraph) {
1.1372 + digraph = &_digraph;
1.1373 + node_observer_proxy.attach(digraph->notifier(Node()));
1.1374 + arc_observer_proxy.attach(digraph->notifier(Edge()));
1.1375 + }
1.1376 +
1.1377 + void detach() {
1.1378 + node_observer_proxy.detach();
1.1379 + arc_observer_proxy.detach();
1.1380 + }
1.1381 +
1.1382 + bool attached() const {
1.1383 + return node_observer_proxy.attached();
1.1384 + }
1.1385 +
1.1386 + void clear() {
1.1387 + added_nodes.clear();
1.1388 + added_arcs.clear();
1.1389 + }
1.1390 +
1.1391 + public:
1.1392 +
1.1393 + /// \brief Default constructor.
1.1394 + ///
1.1395 + /// Default constructor.
1.1396 + /// To actually make a snapshot you must call save().
1.1397 + Snapshot()
1.1398 + : digraph(0), node_observer_proxy(*this),
1.1399 + arc_observer_proxy(*this) {}
1.1400 +
1.1401 + /// \brief Constructor that immediately makes a snapshot.
1.1402 + ///
1.1403 + /// This constructor immediately makes a snapshot of the digraph.
1.1404 + /// \param _digraph The digraph we make a snapshot of.
1.1405 + Snapshot(ListGraph &_digraph)
1.1406 + : node_observer_proxy(*this),
1.1407 + arc_observer_proxy(*this) {
1.1408 + attach(_digraph);
1.1409 + }
1.1410 +
1.1411 + /// \brief Make a snapshot.
1.1412 + ///
1.1413 + /// Make a snapshot of the digraph.
1.1414 + ///
1.1415 + /// This function can be called more than once. In case of a repeated
1.1416 + /// call, the previous snapshot gets lost.
1.1417 + /// \param _digraph The digraph we make the snapshot of.
1.1418 + void save(ListGraph &_digraph) {
1.1419 + if (attached()) {
1.1420 + detach();
1.1421 + clear();
1.1422 + }
1.1423 + attach(_digraph);
1.1424 + }
1.1425 +
1.1426 + /// \brief Undo the changes until the last snapshot.
1.1427 + //
1.1428 + /// Undo the changes until the last snapshot created by save().
1.1429 + void restore() {
1.1430 + detach();
1.1431 + for(std::list<Edge>::iterator it = added_arcs.begin();
1.1432 + it != added_arcs.end(); ++it) {
1.1433 + digraph->erase(*it);
1.1434 + }
1.1435 + for(std::list<Node>::iterator it = added_nodes.begin();
1.1436 + it != added_nodes.end(); ++it) {
1.1437 + digraph->erase(*it);
1.1438 + }
1.1439 + clear();
1.1440 + }
1.1441 +
1.1442 + /// \brief Gives back true when the snapshot is valid.
1.1443 + ///
1.1444 + /// Gives back true when the snapshot is valid.
1.1445 + bool valid() const {
1.1446 + return attached();
1.1447 + }
1.1448 + };
1.1449 + };
1.1450 +
1.1451 + /// @}
1.1452 +} //namespace lemon
1.1453 +
1.1454 +
1.1455 +#endif