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