1.1 --- a/lemon/concepts/maps.h Fri Feb 08 13:42:11 2008 +0100
1.2 +++ b/lemon/concepts/maps.h Tue Feb 12 21:03:19 2008 +0000
1.3 @@ -55,7 +55,6 @@
1.4
1.5 template<typename _ReadMap>
1.6 struct Constraints {
1.7 -
1.8 void constraints() {
1.9 Value val = m[key];
1.10 val = m[key];
1.11 @@ -175,10 +174,9 @@
1.12 void set(const Key &k,const Value &t) { operator[](k)=t; }
1.13
1.14 template<typename _ReferenceMap>
1.15 - struct ReferenceMapConcept {
1.16 -
1.17 + struct Constraints {
1.18 void constraints() {
1.19 - checkConcept<ReadWriteMap, _ReferenceMap >();
1.20 + checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
1.21 m[key] = val;
1.22 val = m[key];
1.23 m[key] = ref;
1.24 @@ -191,10 +189,10 @@
1.25
1.26 typename _ReferenceMap::Key& own_key;
1.27 typename _ReferenceMap::Value& own_val;
1.28 - typename _ReferenceMap::Reference& own_ref;
1.29 + typename _ReferenceMap::Reference own_ref;
1.30 Key& key;
1.31 Value& val;
1.32 - Reference& ref;
1.33 + Reference ref;
1.34 _ReferenceMap& m;
1.35 };
1.36 };
2.1 --- a/lemon/list_graph.h Fri Feb 08 13:42:11 2008 +0100
2.2 +++ b/lemon/list_graph.h Tue Feb 12 21:03:19 2008 +0000
2.3 @@ -111,12 +111,12 @@
2.4 }
2.5
2.6
2.7 - void first(Arc& e) const {
2.8 + void first(Arc& arc) const {
2.9 int n;
2.10 for(n = first_node;
2.11 n!=-1 && nodes[n].first_in == -1;
2.12 n = nodes[n].next);
2.13 - e.id = (n == -1) ? -1 : nodes[n].first_in;
2.14 + arc.id = (n == -1) ? -1 : nodes[n].first_in;
2.15 }
2.16
2.17 void next(Arc& arc) const {
2.18 @@ -293,35 +293,37 @@
2.19
2.20 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
2.21
2.22 - /// \addtogroup digraphs
2.23 + /// \addtogroup graphs
2.24 /// @{
2.25
2.26 - ///A list digraph class.
2.27 + ///A general directed graph structure.
2.28
2.29 - ///This is a simple and fast digraph implementation.
2.30 + ///\ref ListDigraph is a simple and fast <em>directed graph</em>
2.31 + ///implementation based on static linked lists that are stored in
2.32 + ///\c std::vector structures.
2.33 ///
2.34 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
2.35 - ///also provides several additional useful extra functionalities.
2.36 - ///The most of the member functions and nested classes are
2.37 - ///documented only in the concept class.
2.38 + ///also provides several useful additional functionalities.
2.39 + ///Most of the member functions and nested classes are documented
2.40 + ///only in the concept class.
2.41 ///
2.42 ///An important extra feature of this digraph implementation is that
2.43 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
2.44 ///
2.45 - ///\sa concepts::Digraph.
2.46 + ///\sa concepts::Digraph
2.47
2.48 class ListDigraph : public ExtendedListDigraphBase {
2.49 private:
2.50 - ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
2.51 + ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
2.52
2.53 - ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
2.54 + ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
2.55 ///
2.56 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
2.57 ///\brief Assignment of ListDigraph to another one is \e not allowed.
2.58 - ///Use DigraphCopy() instead.
2.59 + ///Use copyDigraph() instead.
2.60
2.61 ///Assignment of ListDigraph to another one is \e not allowed.
2.62 - ///Use DigraphCopy() instead.
2.63 + ///Use copyDigraph() instead.
2.64 void operator=(const ListDigraph &) {}
2.65 public:
2.66
2.67 @@ -335,8 +337,8 @@
2.68
2.69 ///Add a new node to the digraph.
2.70
2.71 - /// \return the new node.
2.72 - ///
2.73 + ///Add a new node to the digraph.
2.74 + ///\return the new node.
2.75 Node addNode() { return Parent::addNode(); }
2.76
2.77 ///Add a new arc to the digraph.
2.78 @@ -348,25 +350,27 @@
2.79 return Parent::addArc(s, t);
2.80 }
2.81
2.82 - /// Changes the target of \c e to \c n
2.83 + /// Change the target of \c e to \c n
2.84
2.85 - /// Changes the target of \c e to \c n
2.86 + /// Change the target of \c e to \c n
2.87 ///
2.88 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
2.89 ///the changed arc remain valid. However <tt>InArcIt</tt>s are
2.90 ///invalidated.
2.91 + ///
2.92 ///\warning This functionality cannot be used together with the Snapshot
2.93 ///feature.
2.94 void changeTarget(Arc e, Node n) {
2.95 Parent::changeTarget(e,n);
2.96 }
2.97 - /// Changes the source of \c e to \c n
2.98 + /// Change the source of \c e to \c n
2.99
2.100 - /// Changes the source of \c e to \c n
2.101 + /// Change the source of \c e to \c n
2.102 ///
2.103 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
2.104 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
2.105 ///invalidated.
2.106 + ///
2.107 ///\warning This functionality cannot be used together with the Snapshot
2.108 ///feature.
2.109 void changeSource(Arc e, Node n) {
2.110 @@ -378,6 +382,7 @@
2.111 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
2.112 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
2.113 ///invalidated.
2.114 + ///
2.115 ///\warning This functionality cannot be used together with the Snapshot
2.116 ///feature.
2.117 void reverseArc(Arc e) {
2.118 @@ -386,7 +391,9 @@
2.119 changeSource(e,t);
2.120 }
2.121
2.122 - /// Using this it is possible to avoid the superfluous memory
2.123 + /// Reserve memory for nodes.
2.124 +
2.125 + /// Using this function it is possible to avoid the superfluous memory
2.126 /// allocation: if you know that the digraph you want to build will
2.127 /// be very large (e.g. it will contain millions of nodes and/or arcs)
2.128 /// then it is worth reserving space for this amount before starting
2.129 @@ -394,10 +401,9 @@
2.130 /// \sa reserveArc
2.131 void reserveNode(int n) { nodes.reserve(n); };
2.132
2.133 - /// \brief Using this it is possible to avoid the superfluous memory
2.134 - /// allocation.
2.135 + /// Reserve memory for arcs.
2.136
2.137 - /// Using this it is possible to avoid the superfluous memory
2.138 + /// Using this function it is possible to avoid the superfluous memory
2.139 /// allocation: if you know that the digraph you want to build will
2.140 /// be very large (e.g. it will contain millions of nodes and/or arcs)
2.141 /// then it is worth reserving space for this amount before starting
2.142 @@ -408,16 +414,15 @@
2.143 ///Contract two nodes.
2.144
2.145 ///This function contracts two nodes.
2.146 - ///
2.147 ///Node \p b will be removed but instead of deleting
2.148 ///incident arcs, they will be joined to \p a.
2.149 ///The last parameter \p r controls whether to remove loops. \c true
2.150 ///means that loops will be removed.
2.151 ///
2.152 - ///\note The <tt>ArcIt</tt>s
2.153 - ///referencing a moved arc remain
2.154 + ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
2.155 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
2.156 ///may be invalidated.
2.157 + ///
2.158 ///\warning This functionality cannot be used together with the Snapshot
2.159 ///feature.
2.160 void contract(Node a, Node b, bool r = true)
2.161 @@ -452,8 +457,9 @@
2.162 ///be invalidated.
2.163 ///
2.164 ///\warning This functionality cannot be used together with the
2.165 - ///Snapshot feature. \todo It could be implemented in a bit
2.166 - ///faster way.
2.167 + ///Snapshot feature.
2.168 + ///
2.169 + ///\todo It could be implemented in a bit faster way.
2.170 Node split(Node n, bool connect = true) {
2.171 Node b = addNode();
2.172 for(OutArcIt e(*this,n);e!=INVALID;) {
2.173 @@ -471,9 +477,11 @@
2.174 ///This function splits an arc. First a new node \c b is added to
2.175 ///the digraph, then the original arc is re-targeted to \c
2.176 ///b. Finally an arc from \c b to the original target is added.
2.177 - ///\return The newly created node.
2.178 - ///\warning This functionality
2.179 - ///cannot be used together with the Snapshot feature.
2.180 + ///
2.181 + ///\return The newly created node.
2.182 + ///
2.183 + ///\warning This functionality cannot be used together with the
2.184 + ///Snapshot feature.
2.185 Node split(Arc e) {
2.186 Node b = addNode();
2.187 addArc(b,target(e));
2.188 @@ -482,16 +490,16 @@
2.189 }
2.190
2.191 /// \brief Class to make a snapshot of the digraph and restore
2.192 - /// to it later.
2.193 + /// it later.
2.194 ///
2.195 - /// Class to make a snapshot of the digraph and to restore it
2.196 - /// later.
2.197 + /// Class to make a snapshot of the digraph and restore it later.
2.198 ///
2.199 /// The newly added nodes and arcs can be removed using the
2.200 /// restore() function.
2.201 ///
2.202 - /// \warning Arc and node deletions cannot be restored. This
2.203 - /// events invalidate the snapshot.
2.204 + /// \warning Arc and node deletions and other modifications (e.g.
2.205 + /// contracting, splitting, reversing arcs or nodes) cannot be
2.206 + /// restored. These events invalidate the snapshot.
2.207 class Snapshot {
2.208 protected:
2.209
2.210 @@ -776,9 +784,9 @@
2.211 public:
2.212 Edge() {}
2.213 Edge (Invalid) { id = -1; }
2.214 - bool operator==(const Edge& arc) const {return id == arc.id;}
2.215 - bool operator!=(const Edge& arc) const {return id != arc.id;}
2.216 - bool operator<(const Edge& arc) const {return id < arc.id;}
2.217 + bool operator==(const Edge& edge) const {return id == edge.id;}
2.218 + bool operator!=(const Edge& edge) const {return id != edge.id;}
2.219 + bool operator<(const Edge& edge) const {return id < edge.id;}
2.220 };
2.221
2.222 class Arc {
2.223 @@ -909,20 +917,20 @@
2.224 }
2.225
2.226 void firstInc(Edge &e, bool& d, const Node& v) const {
2.227 - int de = nodes[v.id].first_out;
2.228 - if (de != -1 ) {
2.229 - e.id = de / 2;
2.230 - d = ((de & 1) == 1);
2.231 + int a = nodes[v.id].first_out;
2.232 + if (a != -1 ) {
2.233 + e.id = a / 2;
2.234 + d = ((a & 1) == 1);
2.235 } else {
2.236 e.id = -1;
2.237 d = true;
2.238 }
2.239 }
2.240 void nextInc(Edge &e, bool& d) const {
2.241 - int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
2.242 - if (de != -1 ) {
2.243 - e.id = de / 2;
2.244 - d = ((de & 1) == 1);
2.245 + int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
2.246 + if (a != -1 ) {
2.247 + e.id = a / 2;
2.248 + d = ((a & 1) == 1);
2.249 } else {
2.250 e.id = -1;
2.251 d = true;
2.252 @@ -1008,8 +1016,8 @@
2.253
2.254 }
2.255
2.256 - void erase(const Edge& arc) {
2.257 - int n = arc.id * 2;
2.258 + void erase(const Edge& edge) {
2.259 + int n = edge.id * 2;
2.260
2.261 if (arcs[n].next_out != -1) {
2.262 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
2.263 @@ -1089,40 +1097,40 @@
2.264
2.265 };
2.266
2.267 -// typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >
2.268 -// ExtendedListGraphBase;
2.269 -
2.270 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
2.271
2.272
2.273 -
2.274 - /// \addtogroup digraphs
2.275 + /// \addtogroup graphs
2.276 /// @{
2.277
2.278 - ///An undirected list digraph class.
2.279 + ///A general undirected graph structure.
2.280
2.281 - ///This is a simple and fast undirected digraph implementation.
2.282 + ///\ref ListGraph is a simple and fast <em>undirected graph</em>
2.283 + ///implementation based on static linked lists that are stored in
2.284 + ///\c std::vector structures.
2.285 ///
2.286 - ///An important extra feature of this digraph implementation is that
2.287 + ///It conforms to the \ref concepts::Graph "Graph concept" and it
2.288 + ///also provides several useful additional functionalities.
2.289 + ///Most of the member functions and nested classes are documented
2.290 + ///only in the concept class.
2.291 + ///
2.292 + ///An important extra feature of this graph implementation is that
2.293 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
2.294 ///
2.295 - ///It conforms to the
2.296 - ///\ref concepts::Graph "Graph concept".
2.297 - ///
2.298 - ///\sa concepts::Graph.
2.299 - ///
2.300 + ///\sa concepts::Graph
2.301 +
2.302 class ListGraph : public ExtendedListGraphBase {
2.303 private:
2.304 - ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
2.305 + ///ListGraph is \e not copy constructible. Use copyGraph() instead.
2.306
2.307 - ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
2.308 + ///ListGraph is \e not copy constructible. Use copyGraph() instead.
2.309 ///
2.310 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
2.311 ///\brief Assignment of ListGraph to another one is \e not allowed.
2.312 - ///Use GraphCopy() instead.
2.313 + ///Use copyGraph() instead.
2.314
2.315 ///Assignment of ListGraph to another one is \e not allowed.
2.316 - ///Use GraphCopy() instead.
2.317 + ///Use copyGraph() instead.
2.318 void operator=(const ListGraph &) {}
2.319 public:
2.320 /// Constructor
2.321 @@ -1133,49 +1141,58 @@
2.322
2.323 typedef ExtendedListGraphBase Parent;
2.324
2.325 - typedef Parent::OutArcIt IncArcIt;
2.326 + typedef Parent::OutArcIt IncEdgeIt;
2.327
2.328 - /// \brief Add a new node to the digraph.
2.329 + /// \brief Add a new node to the graph.
2.330 ///
2.331 + /// Add a new node to the graph.
2.332 /// \return the new node.
2.333 - ///
2.334 Node addNode() { return Parent::addNode(); }
2.335
2.336 - /// \brief Add a new edge to the digraph.
2.337 + /// \brief Add a new edge to the graph.
2.338 ///
2.339 - /// Add a new arc to the digraph with source node \c s
2.340 + /// Add a new edge to the graph with source node \c s
2.341 /// and target node \c t.
2.342 /// \return the new edge.
2.343 Edge addEdge(const Node& s, const Node& t) {
2.344 return Parent::addEdge(s, t);
2.345 }
2.346 - /// \brief Changes the source of \c e to \c n
2.347 + /// \brief Change the source of \c e to \c n
2.348 ///
2.349 - /// Changes the source of \c e to \c n
2.350 + /// This function changes the source of \c e to \c n.
2.351 ///
2.352 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
2.353 ///referencing the changed arc remain
2.354 ///valid. However <tt>OutArcIt</tt>s are invalidated.
2.355 + ///
2.356 + ///\warning This functionality cannot be used together with the
2.357 + ///Snapshot feature.
2.358 void changeSource(Edge e, Node n) {
2.359 Parent::changeSource(e,n);
2.360 }
2.361 - /// \brief Changes the target of \c e to \c n
2.362 + /// \brief Change the target of \c e to \c n
2.363 ///
2.364 - /// Changes the target of \c e to \c n
2.365 + /// This function changes the target of \c e to \c n.
2.366 ///
2.367 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
2.368 /// valid. However the other iterators may be invalidated.
2.369 + ///
2.370 + ///\warning This functionality cannot be used together with the
2.371 + ///Snapshot feature.
2.372 void changeTarget(Edge e, Node n) {
2.373 Parent::changeTarget(e,n);
2.374 }
2.375 - /// \brief Changes the source of \c e to \c n
2.376 + /// \brief Change the source of \c e to \c n
2.377 ///
2.378 - /// Changes the source of \c e to \c n. It changes the proper
2.379 - /// node of the represented edge.
2.380 + /// This function changes the source of \c e to \c n.
2.381 + /// It also changes the proper node of the represented edge.
2.382 ///
2.383 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
2.384 ///referencing the changed arc remain
2.385 ///valid. However <tt>OutArcIt</tt>s are invalidated.
2.386 + ///
2.387 + ///\warning This functionality cannot be used together with the
2.388 + ///Snapshot feature.
2.389 void changeSource(Arc e, Node n) {
2.390 if (Parent::direction(e)) {
2.391 Parent::changeSource(e,n);
2.392 @@ -1183,14 +1200,17 @@
2.393 Parent::changeTarget(e,n);
2.394 }
2.395 }
2.396 - /// \brief Changes the target of \c e to \c n
2.397 + /// \brief Change the target of \c e to \c n
2.398 ///
2.399 - /// Changes the target of \c e to \c n. It changes the proper
2.400 - /// node of the represented edge.
2.401 + /// This function changes the target of \c e to \c n.
2.402 + /// It also changes the proper node of the represented edge.
2.403 ///
2.404 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
2.405 ///referencing the changed arc remain
2.406 ///valid. However <tt>InArcIt</tt>s are invalidated.
2.407 + ///
2.408 + ///\warning This functionality cannot be used together with the
2.409 + ///Snapshot feature.
2.410 void changeTarget(Arc e, Node n) {
2.411 if (Parent::direction(e)) {
2.412 Parent::changeTarget(e,n);
2.413 @@ -1201,7 +1221,6 @@
2.414 /// \brief Contract two nodes.
2.415 ///
2.416 /// This function contracts two nodes.
2.417 - ///
2.418 /// Node \p b will be removed but instead of deleting
2.419 /// its neighboring arcs, they will be joined to \p a.
2.420 /// The last parameter \p r controls whether to remove loops. \c true
2.421 @@ -1209,9 +1228,12 @@
2.422 ///
2.423 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
2.424 /// valid.
2.425 + ///
2.426 + ///\warning This functionality cannot be used together with the
2.427 + ///Snapshot feature.
2.428 void contract(Node a, Node b, bool r = true) {
2.429 - for(IncArcIt e(*this, b); e!=INVALID;) {
2.430 - IncArcIt f = e; ++f;
2.431 + for(IncEdgeIt e(*this, b); e!=INVALID;) {
2.432 + IncEdgeIt f = e; ++f;
2.433 if (r && runningNode(e) == a) {
2.434 erase(e);
2.435 } else if (source(e) == b) {
2.436 @@ -1225,17 +1247,17 @@
2.437 }
2.438
2.439
2.440 - /// \brief Class to make a snapshot of the digraph and restore
2.441 - /// to it later.
2.442 + /// \brief Class to make a snapshot of the graph and restore
2.443 + /// it later.
2.444 ///
2.445 - /// Class to make a snapshot of the digraph and to restore it
2.446 - /// later.
2.447 + /// Class to make a snapshot of the graph and restore it later.
2.448 ///
2.449 /// The newly added nodes and edges can be removed
2.450 /// using the restore() function.
2.451 ///
2.452 - /// \warning Arc and node deletions cannot be restored. This
2.453 - /// events invalidate the snapshot.
2.454 + /// \warning Edge and node deletions and other modifications
2.455 + /// (e.g. changing nodes of edges, contracting nodes) cannot be
2.456 + /// restored. These events invalidate the snapshot.
2.457 class Snapshot {
2.458 protected:
2.459
2.460 @@ -1303,51 +1325,51 @@
2.461
2.462 protected:
2.463
2.464 - virtual void add(const Edge& arc) {
2.465 - snapshot.addEdge(arc);
2.466 + virtual void add(const Edge& edge) {
2.467 + snapshot.addEdge(edge);
2.468 }
2.469 - virtual void add(const std::vector<Edge>& arcs) {
2.470 - for (int i = arcs.size() - 1; i >= 0; ++i) {
2.471 - snapshot.addEdge(arcs[i]);
2.472 + virtual void add(const std::vector<Edge>& edges) {
2.473 + for (int i = edges.size() - 1; i >= 0; ++i) {
2.474 + snapshot.addEdge(edges[i]);
2.475 }
2.476 }
2.477 - virtual void erase(const Edge& arc) {
2.478 - snapshot.eraseEdge(arc);
2.479 + virtual void erase(const Edge& edge) {
2.480 + snapshot.eraseEdge(edge);
2.481 }
2.482 - virtual void erase(const std::vector<Edge>& arcs) {
2.483 - for (int i = 0; i < int(arcs.size()); ++i) {
2.484 - snapshot.eraseEdge(arcs[i]);
2.485 + virtual void erase(const std::vector<Edge>& edges) {
2.486 + for (int i = 0; i < int(edges.size()); ++i) {
2.487 + snapshot.eraseEdge(edges[i]);
2.488 }
2.489 }
2.490 virtual void build() {
2.491 - Edge arc;
2.492 - std::vector<Edge> arcs;
2.493 - for (notifier()->first(arc); arc != INVALID;
2.494 - notifier()->next(arc)) {
2.495 - arcs.push_back(arc);
2.496 + Edge edge;
2.497 + std::vector<Edge> edges;
2.498 + for (notifier()->first(edge); edge != INVALID;
2.499 + notifier()->next(edge)) {
2.500 + edges.push_back(edge);
2.501 }
2.502 - for (int i = arcs.size() - 1; i >= 0; --i) {
2.503 - snapshot.addEdge(arcs[i]);
2.504 + for (int i = edges.size() - 1; i >= 0; --i) {
2.505 + snapshot.addEdge(edges[i]);
2.506 }
2.507 }
2.508 virtual void clear() {
2.509 - Edge arc;
2.510 - for (notifier()->first(arc); arc != INVALID;
2.511 - notifier()->next(arc)) {
2.512 - snapshot.eraseEdge(arc);
2.513 + Edge edge;
2.514 + for (notifier()->first(edge); edge != INVALID;
2.515 + notifier()->next(edge)) {
2.516 + snapshot.eraseEdge(edge);
2.517 }
2.518 }
2.519
2.520 Snapshot& snapshot;
2.521 };
2.522 -
2.523 - ListGraph *digraph;
2.524 +
2.525 + ListGraph *graph;
2.526
2.527 NodeObserverProxy node_observer_proxy;
2.528 - EdgeObserverProxy arc_observer_proxy;
2.529 + EdgeObserverProxy edge_observer_proxy;
2.530
2.531 std::list<Node> added_nodes;
2.532 - std::list<Edge> added_arcs;
2.533 + std::list<Edge> added_edges;
2.534
2.535
2.536 void addNode(const Node& node) {
2.537 @@ -1358,37 +1380,37 @@
2.538 std::find(added_nodes.begin(), added_nodes.end(), node);
2.539 if (it == added_nodes.end()) {
2.540 clear();
2.541 - arc_observer_proxy.detach();
2.542 + edge_observer_proxy.detach();
2.543 throw NodeNotifier::ImmediateDetach();
2.544 } else {
2.545 added_nodes.erase(it);
2.546 }
2.547 }
2.548
2.549 - void addEdge(const Edge& arc) {
2.550 - added_arcs.push_front(arc);
2.551 + void addEdge(const Edge& edge) {
2.552 + added_edges.push_front(edge);
2.553 }
2.554 - void eraseEdge(const Edge& arc) {
2.555 + void eraseEdge(const Edge& edge) {
2.556 std::list<Edge>::iterator it =
2.557 - std::find(added_arcs.begin(), added_arcs.end(), arc);
2.558 - if (it == added_arcs.end()) {
2.559 + std::find(added_edges.begin(), added_edges.end(), edge);
2.560 + if (it == added_edges.end()) {
2.561 clear();
2.562 node_observer_proxy.detach();
2.563 throw EdgeNotifier::ImmediateDetach();
2.564 } else {
2.565 - added_arcs.erase(it);
2.566 - }
2.567 + added_edges.erase(it);
2.568 + }
2.569 }
2.570
2.571 - void attach(ListGraph &_digraph) {
2.572 - digraph = &_digraph;
2.573 - node_observer_proxy.attach(digraph->notifier(Node()));
2.574 - arc_observer_proxy.attach(digraph->notifier(Edge()));
2.575 + void attach(ListGraph &_graph) {
2.576 + graph = &_graph;
2.577 + node_observer_proxy.attach(graph->notifier(Node()));
2.578 + edge_observer_proxy.attach(graph->notifier(Edge()));
2.579 }
2.580
2.581 void detach() {
2.582 node_observer_proxy.detach();
2.583 - arc_observer_proxy.detach();
2.584 + edge_observer_proxy.detach();
2.585 }
2.586
2.587 bool attached() const {
2.588 @@ -1397,7 +1419,7 @@
2.589
2.590 void clear() {
2.591 added_nodes.clear();
2.592 - added_arcs.clear();
2.593 + added_edges.clear();
2.594 }
2.595
2.596 public:
2.597 @@ -1407,32 +1429,32 @@
2.598 /// Default constructor.
2.599 /// To actually make a snapshot you must call save().
2.600 Snapshot()
2.601 - : digraph(0), node_observer_proxy(*this),
2.602 - arc_observer_proxy(*this) {}
2.603 + : graph(0), node_observer_proxy(*this),
2.604 + edge_observer_proxy(*this) {}
2.605
2.606 /// \brief Constructor that immediately makes a snapshot.
2.607 ///
2.608 - /// This constructor immediately makes a snapshot of the digraph.
2.609 - /// \param _digraph The digraph we make a snapshot of.
2.610 - Snapshot(ListGraph &_digraph)
2.611 + /// This constructor immediately makes a snapshot of the graph.
2.612 + /// \param _graph The graph we make a snapshot of.
2.613 + Snapshot(ListGraph &_graph)
2.614 : node_observer_proxy(*this),
2.615 - arc_observer_proxy(*this) {
2.616 - attach(_digraph);
2.617 + edge_observer_proxy(*this) {
2.618 + attach(_graph);
2.619 }
2.620
2.621 /// \brief Make a snapshot.
2.622 ///
2.623 - /// Make a snapshot of the digraph.
2.624 + /// Make a snapshot of the graph.
2.625 ///
2.626 /// This function can be called more than once. In case of a repeated
2.627 /// call, the previous snapshot gets lost.
2.628 - /// \param _digraph The digraph we make the snapshot of.
2.629 - void save(ListGraph &_digraph) {
2.630 + /// \param _graph The graph we make the snapshot of.
2.631 + void save(ListGraph &_graph) {
2.632 if (attached()) {
2.633 detach();
2.634 clear();
2.635 }
2.636 - attach(_digraph);
2.637 + attach(_graph);
2.638 }
2.639
2.640 /// \brief Undo the changes until the last snapshot.
2.641 @@ -1440,13 +1462,13 @@
2.642 /// Undo the changes until the last snapshot created by save().
2.643 void restore() {
2.644 detach();
2.645 - for(std::list<Edge>::iterator it = added_arcs.begin();
2.646 - it != added_arcs.end(); ++it) {
2.647 - digraph->erase(*it);
2.648 + for(std::list<Edge>::iterator it = added_edges.begin();
2.649 + it != added_edges.end(); ++it) {
2.650 + graph->erase(*it);
2.651 }
2.652 for(std::list<Node>::iterator it = added_nodes.begin();
2.653 it != added_nodes.end(); ++it) {
2.654 - digraph->erase(*it);
2.655 + graph->erase(*it);
2.656 }
2.657 clear();
2.658 }