1.1 --- a/lemon/list_graph.h Fri Jan 25 14:52:50 2008 +0000
1.2 +++ b/lemon/list_graph.h Tue Feb 05 11:24:57 2008 +0100
1.3 @@ -111,12 +111,12 @@
1.4 }
1.5
1.6
1.7 - void first(Arc& e) const {
1.8 + void first(Arc& arc) const {
1.9 int n;
1.10 for(n = first_node;
1.11 n!=-1 && nodes[n].first_in == -1;
1.12 n = nodes[n].next);
1.13 - e.id = (n == -1) ? -1 : nodes[n].first_in;
1.14 + arc.id = (n == -1) ? -1 : nodes[n].first_in;
1.15 }
1.16
1.17 void next(Arc& arc) const {
1.18 @@ -293,35 +293,37 @@
1.19
1.20 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
1.21
1.22 - /// \addtogroup digraphs
1.23 + /// \addtogroup graphs
1.24 /// @{
1.25
1.26 - ///A list digraph class.
1.27 + ///A general directed graph structure.
1.28
1.29 - ///This is a simple and fast digraph implementation.
1.30 + ///\ref ListDigraph is a simple and fast <em>directed graph</em>
1.31 + ///implementation based on static linked lists that are stored in
1.32 + ///\c std::vector structures.
1.33 ///
1.34 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
1.35 - ///also provides several additional useful extra functionalities.
1.36 - ///The most of the member functions and nested classes are
1.37 - ///documented only in the concept class.
1.38 + ///also provides several useful additional functionalities.
1.39 + ///Most of the member functions and nested classes are documented
1.40 + ///only in the concept class.
1.41 ///
1.42 ///An important extra feature of this digraph implementation is that
1.43 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1.44 ///
1.45 - ///\sa concepts::Digraph.
1.46 + ///\sa concepts::Digraph
1.47
1.48 class ListDigraph : public ExtendedListDigraphBase {
1.49 private:
1.50 - ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.51 + ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
1.52
1.53 - ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.54 + ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
1.55 ///
1.56 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
1.57 ///\brief Assignment of ListDigraph to another one is \e not allowed.
1.58 - ///Use DigraphCopy() instead.
1.59 + ///Use copyDigraph() instead.
1.60
1.61 ///Assignment of ListDigraph to another one is \e not allowed.
1.62 - ///Use DigraphCopy() instead.
1.63 + ///Use copyDigraph() instead.
1.64 void operator=(const ListDigraph &) {}
1.65 public:
1.66
1.67 @@ -335,8 +337,8 @@
1.68
1.69 ///Add a new node to the digraph.
1.70
1.71 - /// \return the new node.
1.72 - ///
1.73 + ///Add a new node to the digraph.
1.74 + ///\return the new node.
1.75 Node addNode() { return Parent::addNode(); }
1.76
1.77 ///Add a new arc to the digraph.
1.78 @@ -348,25 +350,27 @@
1.79 return Parent::addArc(s, t);
1.80 }
1.81
1.82 - /// Changes the target of \c e to \c n
1.83 + /// Change the target of \c e to \c n
1.84
1.85 - /// Changes the target of \c e to \c n
1.86 + /// Change the target of \c e to \c n
1.87 ///
1.88 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
1.89 ///the changed arc remain valid. However <tt>InArcIt</tt>s are
1.90 ///invalidated.
1.91 + ///
1.92 ///\warning This functionality cannot be used together with the Snapshot
1.93 ///feature.
1.94 void changeTarget(Arc e, Node n) {
1.95 Parent::changeTarget(e,n);
1.96 }
1.97 - /// Changes the source of \c e to \c n
1.98 + /// Change the source of \c e to \c n
1.99
1.100 - /// Changes the source of \c e to \c n
1.101 + /// Change the source of \c e to \c n
1.102 ///
1.103 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
1.104 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
1.105 ///invalidated.
1.106 + ///
1.107 ///\warning This functionality cannot be used together with the Snapshot
1.108 ///feature.
1.109 void changeSource(Arc e, Node n) {
1.110 @@ -378,6 +382,7 @@
1.111 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
1.112 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
1.113 ///invalidated.
1.114 + ///
1.115 ///\warning This functionality cannot be used together with the Snapshot
1.116 ///feature.
1.117 void reverseArc(Arc e) {
1.118 @@ -386,7 +391,9 @@
1.119 changeSource(e,t);
1.120 }
1.121
1.122 - /// Using this it is possible to avoid the superfluous memory
1.123 + /// Reserve memory for nodes.
1.124 +
1.125 + /// Using this function it is possible to avoid the superfluous memory
1.126 /// allocation: if you know that the digraph you want to build will
1.127 /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.128 /// then it is worth reserving space for this amount before starting
1.129 @@ -394,10 +401,9 @@
1.130 /// \sa reserveArc
1.131 void reserveNode(int n) { nodes.reserve(n); };
1.132
1.133 - /// \brief Using this it is possible to avoid the superfluous memory
1.134 - /// allocation.
1.135 + /// Reserve memory for arcs.
1.136
1.137 - /// Using this it is possible to avoid the superfluous memory
1.138 + /// Using this function it is possible to avoid the superfluous memory
1.139 /// allocation: if you know that the digraph you want to build will
1.140 /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.141 /// then it is worth reserving space for this amount before starting
1.142 @@ -408,16 +414,15 @@
1.143 ///Contract two nodes.
1.144
1.145 ///This function contracts two nodes.
1.146 - ///
1.147 ///Node \p b will be removed but instead of deleting
1.148 ///incident arcs, they will be joined to \p a.
1.149 ///The last parameter \p r controls whether to remove loops. \c true
1.150 ///means that loops will be removed.
1.151 ///
1.152 - ///\note The <tt>ArcIt</tt>s
1.153 - ///referencing a moved arc remain
1.154 + ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
1.155 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
1.156 ///may be invalidated.
1.157 + ///
1.158 ///\warning This functionality cannot be used together with the Snapshot
1.159 ///feature.
1.160 void contract(Node a, Node b, bool r = true)
1.161 @@ -452,8 +457,9 @@
1.162 ///be invalidated.
1.163 ///
1.164 ///\warning This functionality cannot be used together with the
1.165 - ///Snapshot feature. \todo It could be implemented in a bit
1.166 - ///faster way.
1.167 + ///Snapshot feature.
1.168 + ///
1.169 + ///\todo It could be implemented in a bit faster way.
1.170 Node split(Node n, bool connect = true) {
1.171 Node b = addNode();
1.172 for(OutArcIt e(*this,n);e!=INVALID;) {
1.173 @@ -471,9 +477,11 @@
1.174 ///This function splits an arc. First a new node \c b is added to
1.175 ///the digraph, then the original arc is re-targeted to \c
1.176 ///b. Finally an arc from \c b to the original target is added.
1.177 - ///\return The newly created node.
1.178 - ///\warning This functionality
1.179 - ///cannot be used together with the Snapshot feature.
1.180 + ///
1.181 + ///\return The newly created node.
1.182 + ///
1.183 + ///\warning This functionality cannot be used together with the
1.184 + ///Snapshot feature.
1.185 Node split(Arc e) {
1.186 Node b = addNode();
1.187 addArc(b,target(e));
1.188 @@ -482,16 +490,16 @@
1.189 }
1.190
1.191 /// \brief Class to make a snapshot of the digraph and restore
1.192 - /// to it later.
1.193 + /// it later.
1.194 ///
1.195 - /// Class to make a snapshot of the digraph and to restore it
1.196 - /// later.
1.197 + /// Class to make a snapshot of the digraph and restore it later.
1.198 ///
1.199 /// The newly added nodes and arcs can be removed using the
1.200 /// restore() function.
1.201 ///
1.202 - /// \warning Arc and node deletions cannot be restored. This
1.203 - /// events invalidate the snapshot.
1.204 + /// \warning Arc and node deletions and other modifications (e.g.
1.205 + /// contracting, splitting, reversing arcs or nodes) cannot be
1.206 + /// restored. These events invalidate the snapshot.
1.207 class Snapshot {
1.208 protected:
1.209
1.210 @@ -776,9 +784,9 @@
1.211 public:
1.212 Edge() {}
1.213 Edge (Invalid) { id = -1; }
1.214 - bool operator==(const Edge& arc) const {return id == arc.id;}
1.215 - bool operator!=(const Edge& arc) const {return id != arc.id;}
1.216 - bool operator<(const Edge& arc) const {return id < arc.id;}
1.217 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.218 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.219 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.220 };
1.221
1.222 class Arc {
1.223 @@ -909,20 +917,20 @@
1.224 }
1.225
1.226 void firstInc(Edge &e, bool& d, const Node& v) const {
1.227 - int de = nodes[v.id].first_out;
1.228 - if (de != -1 ) {
1.229 - e.id = de / 2;
1.230 - d = ((de & 1) == 1);
1.231 + int a = nodes[v.id].first_out;
1.232 + if (a != -1 ) {
1.233 + e.id = a / 2;
1.234 + d = ((a & 1) == 1);
1.235 } else {
1.236 e.id = -1;
1.237 d = true;
1.238 }
1.239 }
1.240 void nextInc(Edge &e, bool& d) const {
1.241 - int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.242 - if (de != -1 ) {
1.243 - e.id = de / 2;
1.244 - d = ((de & 1) == 1);
1.245 + int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.246 + if (a != -1 ) {
1.247 + e.id = a / 2;
1.248 + d = ((a & 1) == 1);
1.249 } else {
1.250 e.id = -1;
1.251 d = true;
1.252 @@ -1008,8 +1016,8 @@
1.253
1.254 }
1.255
1.256 - void erase(const Edge& arc) {
1.257 - int n = arc.id * 2;
1.258 + void erase(const Edge& edge) {
1.259 + int n = edge.id * 2;
1.260
1.261 if (arcs[n].next_out != -1) {
1.262 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.263 @@ -1089,40 +1097,40 @@
1.264
1.265 };
1.266
1.267 -// typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >
1.268 -// ExtendedListGraphBase;
1.269 -
1.270 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1.271
1.272
1.273 -
1.274 - /// \addtogroup digraphs
1.275 + /// \addtogroup graphs
1.276 /// @{
1.277
1.278 - ///An undirected list digraph class.
1.279 + ///A general undirected graph structure.
1.280
1.281 - ///This is a simple and fast undirected digraph implementation.
1.282 + ///\ref ListGraph is a simple and fast <em>undirected graph</em>
1.283 + ///implementation based on static linked lists that are stored in
1.284 + ///\c std::vector structures.
1.285 ///
1.286 - ///An important extra feature of this digraph implementation is that
1.287 + ///It conforms to the \ref concepts::Graph "Graph concept" and it
1.288 + ///also provides several useful additional functionalities.
1.289 + ///Most of the member functions and nested classes are documented
1.290 + ///only in the concept class.
1.291 + ///
1.292 + ///An important extra feature of this graph implementation is that
1.293 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1.294 ///
1.295 - ///It conforms to the
1.296 - ///\ref concepts::Graph "Graph concept".
1.297 - ///
1.298 - ///\sa concepts::Graph.
1.299 - ///
1.300 + ///\sa concepts::Graph
1.301 +
1.302 class ListGraph : public ExtendedListGraphBase {
1.303 private:
1.304 - ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
1.305 + ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1.306
1.307 - ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
1.308 + ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1.309 ///
1.310 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
1.311 ///\brief Assignment of ListGraph to another one is \e not allowed.
1.312 - ///Use GraphCopy() instead.
1.313 + ///Use copyGraph() instead.
1.314
1.315 ///Assignment of ListGraph to another one is \e not allowed.
1.316 - ///Use GraphCopy() instead.
1.317 + ///Use copyGraph() instead.
1.318 void operator=(const ListGraph &) {}
1.319 public:
1.320 /// Constructor
1.321 @@ -1133,49 +1141,58 @@
1.322
1.323 typedef ExtendedListGraphBase Parent;
1.324
1.325 - typedef Parent::OutArcIt IncArcIt;
1.326 + typedef Parent::OutArcIt IncEdgeIt;
1.327
1.328 - /// \brief Add a new node to the digraph.
1.329 + /// \brief Add a new node to the graph.
1.330 ///
1.331 + /// Add a new node to the graph.
1.332 /// \return the new node.
1.333 - ///
1.334 Node addNode() { return Parent::addNode(); }
1.335
1.336 - /// \brief Add a new edge to the digraph.
1.337 + /// \brief Add a new edge to the graph.
1.338 ///
1.339 - /// Add a new arc to the digraph with source node \c s
1.340 + /// Add a new edge to the graph with source node \c s
1.341 /// and target node \c t.
1.342 /// \return the new edge.
1.343 Edge addEdge(const Node& s, const Node& t) {
1.344 return Parent::addEdge(s, t);
1.345 }
1.346 - /// \brief Changes the source of \c e to \c n
1.347 + /// \brief Change the source of \c e to \c n
1.348 ///
1.349 - /// Changes the source of \c e to \c n
1.350 + /// This function changes the source of \c e to \c n.
1.351 ///
1.352 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1.353 ///referencing the changed arc remain
1.354 ///valid. However <tt>OutArcIt</tt>s are invalidated.
1.355 + ///
1.356 + ///\warning This functionality cannot be used together with the
1.357 + ///Snapshot feature.
1.358 void changeSource(Edge e, Node n) {
1.359 Parent::changeSource(e,n);
1.360 }
1.361 - /// \brief Changes the target of \c e to \c n
1.362 + /// \brief Change the target of \c e to \c n
1.363 ///
1.364 - /// Changes the target of \c e to \c n
1.365 + /// This function changes the target of \c e to \c n.
1.366 ///
1.367 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
1.368 /// valid. However the other iterators may be invalidated.
1.369 + ///
1.370 + ///\warning This functionality cannot be used together with the
1.371 + ///Snapshot feature.
1.372 void changeTarget(Edge e, Node n) {
1.373 Parent::changeTarget(e,n);
1.374 }
1.375 - /// \brief Changes the source of \c e to \c n
1.376 + /// \brief Change the source of \c e to \c n
1.377 ///
1.378 - /// Changes the source of \c e to \c n. It changes the proper
1.379 - /// node of the represented edge.
1.380 + /// This function changes the source of \c e to \c n.
1.381 + /// It also changes the proper node of the represented edge.
1.382 ///
1.383 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1.384 ///referencing the changed arc remain
1.385 ///valid. However <tt>OutArcIt</tt>s are invalidated.
1.386 + ///
1.387 + ///\warning This functionality cannot be used together with the
1.388 + ///Snapshot feature.
1.389 void changeSource(Arc e, Node n) {
1.390 if (Parent::direction(e)) {
1.391 Parent::changeSource(e,n);
1.392 @@ -1183,14 +1200,17 @@
1.393 Parent::changeTarget(e,n);
1.394 }
1.395 }
1.396 - /// \brief Changes the target of \c e to \c n
1.397 + /// \brief Change the target of \c e to \c n
1.398 ///
1.399 - /// Changes the target of \c e to \c n. It changes the proper
1.400 - /// node of the represented edge.
1.401 + /// This function changes the target of \c e to \c n.
1.402 + /// It also changes the proper node of the represented edge.
1.403 ///
1.404 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
1.405 ///referencing the changed arc remain
1.406 ///valid. However <tt>InArcIt</tt>s are invalidated.
1.407 + ///
1.408 + ///\warning This functionality cannot be used together with the
1.409 + ///Snapshot feature.
1.410 void changeTarget(Arc e, Node n) {
1.411 if (Parent::direction(e)) {
1.412 Parent::changeTarget(e,n);
1.413 @@ -1201,7 +1221,6 @@
1.414 /// \brief Contract two nodes.
1.415 ///
1.416 /// This function contracts two nodes.
1.417 - ///
1.418 /// Node \p b will be removed but instead of deleting
1.419 /// its neighboring arcs, they will be joined to \p a.
1.420 /// The last parameter \p r controls whether to remove loops. \c true
1.421 @@ -1209,9 +1228,12 @@
1.422 ///
1.423 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
1.424 /// valid.
1.425 + ///
1.426 + ///\warning This functionality cannot be used together with the
1.427 + ///Snapshot feature.
1.428 void contract(Node a, Node b, bool r = true) {
1.429 - for(IncArcIt e(*this, b); e!=INVALID;) {
1.430 - IncArcIt f = e; ++f;
1.431 + for(IncEdgeIt e(*this, b); e!=INVALID;) {
1.432 + IncEdgeIt f = e; ++f;
1.433 if (r && runningNode(e) == a) {
1.434 erase(e);
1.435 } else if (source(e) == b) {
1.436 @@ -1225,17 +1247,17 @@
1.437 }
1.438
1.439
1.440 - /// \brief Class to make a snapshot of the digraph and restore
1.441 - /// to it later.
1.442 + /// \brief Class to make a snapshot of the graph and restore
1.443 + /// it later.
1.444 ///
1.445 - /// Class to make a snapshot of the digraph and to restore it
1.446 - /// later.
1.447 + /// Class to make a snapshot of the graph and restore it later.
1.448 ///
1.449 /// The newly added nodes and edges can be removed
1.450 /// using the restore() function.
1.451 ///
1.452 - /// \warning Arc and node deletions cannot be restored. This
1.453 - /// events invalidate the snapshot.
1.454 + /// \warning Edge and node deletions and other modifications
1.455 + /// (e.g. changing nodes of edges, contracting nodes) cannot be
1.456 + /// restored. These events invalidate the snapshot.
1.457 class Snapshot {
1.458 protected:
1.459
1.460 @@ -1303,51 +1325,51 @@
1.461
1.462 protected:
1.463
1.464 - virtual void add(const Edge& arc) {
1.465 - snapshot.addEdge(arc);
1.466 + virtual void add(const Edge& edge) {
1.467 + snapshot.addEdge(edge);
1.468 }
1.469 - virtual void add(const std::vector<Edge>& arcs) {
1.470 - for (int i = arcs.size() - 1; i >= 0; ++i) {
1.471 - snapshot.addEdge(arcs[i]);
1.472 + virtual void add(const std::vector<Edge>& edges) {
1.473 + for (int i = edges.size() - 1; i >= 0; ++i) {
1.474 + snapshot.addEdge(edges[i]);
1.475 }
1.476 }
1.477 - virtual void erase(const Edge& arc) {
1.478 - snapshot.eraseEdge(arc);
1.479 + virtual void erase(const Edge& edge) {
1.480 + snapshot.eraseEdge(edge);
1.481 }
1.482 - virtual void erase(const std::vector<Edge>& arcs) {
1.483 - for (int i = 0; i < int(arcs.size()); ++i) {
1.484 - snapshot.eraseEdge(arcs[i]);
1.485 + virtual void erase(const std::vector<Edge>& edges) {
1.486 + for (int i = 0; i < int(edges.size()); ++i) {
1.487 + snapshot.eraseEdge(edges[i]);
1.488 }
1.489 }
1.490 virtual void build() {
1.491 - Edge arc;
1.492 - std::vector<Edge> arcs;
1.493 - for (notifier()->first(arc); arc != INVALID;
1.494 - notifier()->next(arc)) {
1.495 - arcs.push_back(arc);
1.496 + Edge edge;
1.497 + std::vector<Edge> edges;
1.498 + for (notifier()->first(edge); edge != INVALID;
1.499 + notifier()->next(edge)) {
1.500 + edges.push_back(edge);
1.501 }
1.502 - for (int i = arcs.size() - 1; i >= 0; --i) {
1.503 - snapshot.addEdge(arcs[i]);
1.504 + for (int i = edges.size() - 1; i >= 0; --i) {
1.505 + snapshot.addEdge(edges[i]);
1.506 }
1.507 }
1.508 virtual void clear() {
1.509 - Edge arc;
1.510 - for (notifier()->first(arc); arc != INVALID;
1.511 - notifier()->next(arc)) {
1.512 - snapshot.eraseEdge(arc);
1.513 + Edge edge;
1.514 + for (notifier()->first(edge); edge != INVALID;
1.515 + notifier()->next(edge)) {
1.516 + snapshot.eraseEdge(edge);
1.517 }
1.518 }
1.519
1.520 Snapshot& snapshot;
1.521 };
1.522 -
1.523 - ListGraph *digraph;
1.524 +
1.525 + ListGraph *graph;
1.526
1.527 NodeObserverProxy node_observer_proxy;
1.528 - EdgeObserverProxy arc_observer_proxy;
1.529 + EdgeObserverProxy edge_observer_proxy;
1.530
1.531 std::list<Node> added_nodes;
1.532 - std::list<Edge> added_arcs;
1.533 + std::list<Edge> added_edges;
1.534
1.535
1.536 void addNode(const Node& node) {
1.537 @@ -1358,37 +1380,37 @@
1.538 std::find(added_nodes.begin(), added_nodes.end(), node);
1.539 if (it == added_nodes.end()) {
1.540 clear();
1.541 - arc_observer_proxy.detach();
1.542 + edge_observer_proxy.detach();
1.543 throw NodeNotifier::ImmediateDetach();
1.544 } else {
1.545 added_nodes.erase(it);
1.546 }
1.547 }
1.548
1.549 - void addEdge(const Edge& arc) {
1.550 - added_arcs.push_front(arc);
1.551 + void addEdge(const Edge& edge) {
1.552 + added_edges.push_front(edge);
1.553 }
1.554 - void eraseEdge(const Edge& arc) {
1.555 + void eraseEdge(const Edge& edge) {
1.556 std::list<Edge>::iterator it =
1.557 - std::find(added_arcs.begin(), added_arcs.end(), arc);
1.558 - if (it == added_arcs.end()) {
1.559 + std::find(added_edges.begin(), added_edges.end(), edge);
1.560 + if (it == added_edges.end()) {
1.561 clear();
1.562 node_observer_proxy.detach();
1.563 throw EdgeNotifier::ImmediateDetach();
1.564 } else {
1.565 - added_arcs.erase(it);
1.566 - }
1.567 + added_edges.erase(it);
1.568 + }
1.569 }
1.570
1.571 - void attach(ListGraph &_digraph) {
1.572 - digraph = &_digraph;
1.573 - node_observer_proxy.attach(digraph->notifier(Node()));
1.574 - arc_observer_proxy.attach(digraph->notifier(Edge()));
1.575 + void attach(ListGraph &_graph) {
1.576 + graph = &_graph;
1.577 + node_observer_proxy.attach(graph->notifier(Node()));
1.578 + edge_observer_proxy.attach(graph->notifier(Edge()));
1.579 }
1.580
1.581 void detach() {
1.582 node_observer_proxy.detach();
1.583 - arc_observer_proxy.detach();
1.584 + edge_observer_proxy.detach();
1.585 }
1.586
1.587 bool attached() const {
1.588 @@ -1397,7 +1419,7 @@
1.589
1.590 void clear() {
1.591 added_nodes.clear();
1.592 - added_arcs.clear();
1.593 + added_edges.clear();
1.594 }
1.595
1.596 public:
1.597 @@ -1407,32 +1429,32 @@
1.598 /// Default constructor.
1.599 /// To actually make a snapshot you must call save().
1.600 Snapshot()
1.601 - : digraph(0), node_observer_proxy(*this),
1.602 - arc_observer_proxy(*this) {}
1.603 + : graph(0), node_observer_proxy(*this),
1.604 + edge_observer_proxy(*this) {}
1.605
1.606 /// \brief Constructor that immediately makes a snapshot.
1.607 ///
1.608 - /// This constructor immediately makes a snapshot of the digraph.
1.609 - /// \param _digraph The digraph we make a snapshot of.
1.610 - Snapshot(ListGraph &_digraph)
1.611 + /// This constructor immediately makes a snapshot of the graph.
1.612 + /// \param _graph The graph we make a snapshot of.
1.613 + Snapshot(ListGraph &_graph)
1.614 : node_observer_proxy(*this),
1.615 - arc_observer_proxy(*this) {
1.616 - attach(_digraph);
1.617 + edge_observer_proxy(*this) {
1.618 + attach(_graph);
1.619 }
1.620
1.621 /// \brief Make a snapshot.
1.622 ///
1.623 - /// Make a snapshot of the digraph.
1.624 + /// Make a snapshot of the graph.
1.625 ///
1.626 /// This function can be called more than once. In case of a repeated
1.627 /// call, the previous snapshot gets lost.
1.628 - /// \param _digraph The digraph we make the snapshot of.
1.629 - void save(ListGraph &_digraph) {
1.630 + /// \param _graph The graph we make the snapshot of.
1.631 + void save(ListGraph &_graph) {
1.632 if (attached()) {
1.633 detach();
1.634 clear();
1.635 }
1.636 - attach(_digraph);
1.637 + attach(_graph);
1.638 }
1.639
1.640 /// \brief Undo the changes until the last snapshot.
1.641 @@ -1440,13 +1462,13 @@
1.642 /// Undo the changes until the last snapshot created by save().
1.643 void restore() {
1.644 detach();
1.645 - for(std::list<Edge>::iterator it = added_arcs.begin();
1.646 - it != added_arcs.end(); ++it) {
1.647 - digraph->erase(*it);
1.648 + for(std::list<Edge>::iterator it = added_edges.begin();
1.649 + it != added_edges.end(); ++it) {
1.650 + graph->erase(*it);
1.651 }
1.652 for(std::list<Node>::iterator it = added_nodes.begin();
1.653 it != added_nodes.end(); ++it) {
1.654 - digraph->erase(*it);
1.655 + graph->erase(*it);
1.656 }
1.657 clear();
1.658 }