1.1 --- a/lemon/list_graph.h Sun Aug 23 11:07:50 2009 +0200
1.2 +++ b/lemon/list_graph.h Sun Aug 23 11:09:22 2009 +0200
1.3 @@ -21,7 +21,7 @@
1.4
1.5 ///\ingroup graphs
1.6 ///\file
1.7 -///\brief ListDigraph, ListGraph classes.
1.8 +///\brief ListDigraph and ListGraph classes.
1.9
1.10 #include <lemon/core.h>
1.11 #include <lemon/error.h>
1.12 @@ -311,31 +311,25 @@
1.13
1.14 ///A general directed graph structure.
1.15
1.16 - ///\ref ListDigraph is a simple and fast <em>directed graph</em>
1.17 - ///implementation based on static linked lists that are stored in
1.18 + ///\ref ListDigraph is a versatile and fast directed graph
1.19 + ///implementation based on linked lists that are stored in
1.20 ///\c std::vector structures.
1.21 ///
1.22 - ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
1.23 - ///also provides several useful additional functionalities.
1.24 - ///Most of the member functions and nested classes are documented
1.25 + ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
1.26 + ///and it also provides several useful additional functionalities.
1.27 + ///Most of its member functions and nested classes are documented
1.28 ///only in the concept class.
1.29 ///
1.30 ///\sa concepts::Digraph
1.31 -
1.32 + ///\sa ListGraph
1.33 class ListDigraph : public ExtendedListDigraphBase {
1.34 typedef ExtendedListDigraphBase Parent;
1.35
1.36 private:
1.37 - ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
1.38 -
1.39 - ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
1.40 - ///
1.41 + /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
1.42 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
1.43 - ///\brief Assignment of ListDigraph to another one is \e not allowed.
1.44 - ///Use copyDigraph() instead.
1.45 -
1.46 - ///Assignment of ListDigraph to another one is \e not allowed.
1.47 - ///Use copyDigraph() instead.
1.48 + /// \brief Assignment of a digraph to another one is \e not allowed.
1.49 + /// Use DigraphCopy instead.
1.50 void operator=(const ListDigraph &) {}
1.51 public:
1.52
1.53 @@ -347,71 +341,65 @@
1.54
1.55 ///Add a new node to the digraph.
1.56
1.57 - ///Add a new node to the digraph.
1.58 + ///This function adds a new node to the digraph.
1.59 ///\return The new node.
1.60 Node addNode() { return Parent::addNode(); }
1.61
1.62 ///Add a new arc to the digraph.
1.63
1.64 - ///Add a new arc to the digraph with source node \c s
1.65 + ///This function adds a new arc to the digraph with source node \c s
1.66 ///and target node \c t.
1.67 ///\return The new arc.
1.68 - Arc addArc(const Node& s, const Node& t) {
1.69 + Arc addArc(Node s, Node t) {
1.70 return Parent::addArc(s, t);
1.71 }
1.72
1.73 ///\brief Erase a node from the digraph.
1.74 ///
1.75 - ///Erase a node from the digraph.
1.76 - ///
1.77 - void erase(const Node& n) { Parent::erase(n); }
1.78 + ///This function erases the given node from the digraph.
1.79 + void erase(Node n) { Parent::erase(n); }
1.80
1.81 ///\brief Erase an arc from the digraph.
1.82 ///
1.83 - ///Erase an arc from the digraph.
1.84 - ///
1.85 - void erase(const Arc& a) { Parent::erase(a); }
1.86 + ///This function erases the given arc from the digraph.
1.87 + void erase(Arc a) { Parent::erase(a); }
1.88
1.89 /// Node validity check
1.90
1.91 - /// This function gives back true if the given node is valid,
1.92 - /// ie. it is a real node of the graph.
1.93 + /// This function gives back \c true if the given node is valid,
1.94 + /// i.e. it is a real node of the digraph.
1.95 ///
1.96 - /// \warning A Node pointing to a removed item
1.97 - /// could become valid again later if new nodes are
1.98 - /// added to the graph.
1.99 + /// \warning A removed node could become valid again if new nodes are
1.100 + /// added to the digraph.
1.101 bool valid(Node n) const { return Parent::valid(n); }
1.102
1.103 /// Arc validity check
1.104
1.105 - /// This function gives back true if the given arc is valid,
1.106 - /// ie. it is a real arc of the graph.
1.107 + /// This function gives back \c true if the given arc is valid,
1.108 + /// i.e. it is a real arc of the digraph.
1.109 ///
1.110 - /// \warning An Arc pointing to a removed item
1.111 - /// could become valid again later if new nodes are
1.112 - /// added to the graph.
1.113 + /// \warning A removed arc could become valid again if new arcs are
1.114 + /// added to the digraph.
1.115 bool valid(Arc a) const { return Parent::valid(a); }
1.116
1.117 - /// Change the target of \c a to \c n
1.118 + /// Change the target node of an arc
1.119
1.120 - /// Change the target of \c a to \c n
1.121 + /// This function changes the target node of the given arc \c a to \c n.
1.122 ///
1.123 - ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
1.124 - ///the changed arc remain valid. However <tt>InArcIt</tt>s are
1.125 - ///invalidated.
1.126 + ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
1.127 + ///arc remain valid, however \c InArcIt iterators are invalidated.
1.128 ///
1.129 ///\warning This functionality cannot be used together with the Snapshot
1.130 ///feature.
1.131 void changeTarget(Arc a, Node n) {
1.132 Parent::changeTarget(a,n);
1.133 }
1.134 - /// Change the source of \c a to \c n
1.135 + /// Change the source node of an arc
1.136
1.137 - /// Change the source of \c a to \c n
1.138 + /// This function changes the source node of the given arc \c a to \c n.
1.139 ///
1.140 - ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
1.141 - ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
1.142 - ///invalidated.
1.143 + ///\note \c InArcIt iterators referencing the changed arc remain
1.144 + ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
1.145 ///
1.146 ///\warning This functionality cannot be used together with the Snapshot
1.147 ///feature.
1.148 @@ -419,86 +407,70 @@
1.149 Parent::changeSource(a,n);
1.150 }
1.151
1.152 - /// Invert the direction of an arc.
1.153 + /// Reverse the direction of an arc.
1.154
1.155 - ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
1.156 - ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
1.157 - ///invalidated.
1.158 + /// This function reverses the direction of the given arc.
1.159 + ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
1.160 + ///the changed arc are invalidated.
1.161 ///
1.162 ///\warning This functionality cannot be used together with the Snapshot
1.163 ///feature.
1.164 - void reverseArc(Arc e) {
1.165 - Node t=target(e);
1.166 - changeTarget(e,source(e));
1.167 - changeSource(e,t);
1.168 + void reverseArc(Arc a) {
1.169 + Node t=target(a);
1.170 + changeTarget(a,source(a));
1.171 + changeSource(a,t);
1.172 }
1.173
1.174 - /// Reserve memory for nodes.
1.175 -
1.176 - /// Using this function it is possible to avoid the superfluous memory
1.177 - /// allocation: if you know that the digraph you want to build will
1.178 - /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.179 - /// then it is worth reserving space for this amount before starting
1.180 - /// to build the digraph.
1.181 - /// \sa reserveArc
1.182 - void reserveNode(int n) { nodes.reserve(n); };
1.183 -
1.184 - /// Reserve memory for arcs.
1.185 -
1.186 - /// Using this function it is possible to avoid the superfluous memory
1.187 - /// allocation: if you know that the digraph you want to build will
1.188 - /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.189 - /// then it is worth reserving space for this amount before starting
1.190 - /// to build the digraph.
1.191 - /// \sa reserveNode
1.192 - void reserveArc(int m) { arcs.reserve(m); };
1.193 -
1.194 ///Contract two nodes.
1.195
1.196 - ///This function contracts two nodes.
1.197 - ///Node \p b will be removed but instead of deleting
1.198 - ///incident arcs, they will be joined to \p a.
1.199 - ///The last parameter \p r controls whether to remove loops. \c true
1.200 - ///means that loops will be removed.
1.201 + ///This function contracts the given two nodes.
1.202 + ///Node \c v is removed, but instead of deleting its
1.203 + ///incident arcs, they are joined to node \c u.
1.204 + ///If the last parameter \c r is \c true (this is the default value),
1.205 + ///then the newly created loops are removed.
1.206 ///
1.207 - ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
1.208 - ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
1.209 - ///may be invalidated.
1.210 + ///\note The moved arcs are joined to node \c u using changeSource()
1.211 + ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
1.212 + ///invalidated for the outgoing arcs of node \c v and \c InArcIt
1.213 + ///iterators are invalidated for the incomming arcs of \c v.
1.214 + ///Moreover all iterators referencing node \c v or the removed
1.215 + ///loops are also invalidated. Other iterators remain valid.
1.216 ///
1.217 ///\warning This functionality cannot be used together with the Snapshot
1.218 ///feature.
1.219 - void contract(Node a, Node b, bool r = true)
1.220 + void contract(Node u, Node v, bool r = true)
1.221 {
1.222 - for(OutArcIt e(*this,b);e!=INVALID;) {
1.223 + for(OutArcIt e(*this,v);e!=INVALID;) {
1.224 OutArcIt f=e;
1.225 ++f;
1.226 - if(r && target(e)==a) erase(e);
1.227 - else changeSource(e,a);
1.228 + if(r && target(e)==u) erase(e);
1.229 + else changeSource(e,u);
1.230 e=f;
1.231 }
1.232 - for(InArcIt e(*this,b);e!=INVALID;) {
1.233 + for(InArcIt e(*this,v);e!=INVALID;) {
1.234 InArcIt f=e;
1.235 ++f;
1.236 - if(r && source(e)==a) erase(e);
1.237 - else changeTarget(e,a);
1.238 + if(r && source(e)==u) erase(e);
1.239 + else changeTarget(e,u);
1.240 e=f;
1.241 }
1.242 - erase(b);
1.243 + erase(v);
1.244 }
1.245
1.246 ///Split a node.
1.247
1.248 - ///This function splits a node. First a new node is added to the digraph,
1.249 - ///then the source of each outgoing arc of \c n is moved to this new node.
1.250 - ///If \c connect is \c true (this is the default value), then a new arc
1.251 - ///from \c n to the newly created node is also added.
1.252 + ///This function splits the given node. First, a new node is added
1.253 + ///to the digraph, then the source of each outgoing arc of node \c n
1.254 + ///is moved to this new node.
1.255 + ///If the second parameter \c connect is \c true (this is the default
1.256 + ///value), then a new arc from node \c n to the newly created node
1.257 + ///is also added.
1.258 ///\return The newly created node.
1.259 ///
1.260 - ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
1.261 - ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
1.262 - ///be invalidated.
1.263 + ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing
1.264 + ///arcs of node \c n are invalidated. Other iterators remain valid.
1.265 ///
1.266 - ///\warning This functionality cannot be used in conjunction with the
1.267 + ///\warning This functionality cannot be used together with the
1.268 ///Snapshot feature.
1.269 Node split(Node n, bool connect = true) {
1.270 Node b = addNode();
1.271 @@ -514,21 +486,52 @@
1.272
1.273 ///Split an arc.
1.274
1.275 - ///This function splits an arc. First a new node \c b is added to
1.276 - ///the digraph, then the original arc is re-targeted to \c
1.277 - ///b. Finally an arc from \c b to the original target is added.
1.278 + ///This function splits the given arc. First, a new node \c v is
1.279 + ///added to the digraph, then the target node of the original arc
1.280 + ///is set to \c v. Finally, an arc from \c v to the original target
1.281 + ///is added.
1.282 + ///\return The newly created node.
1.283 ///
1.284 - ///\return The newly created node.
1.285 + ///\note \c InArcIt iterators referencing the original arc are
1.286 + ///invalidated. Other iterators remain valid.
1.287 ///
1.288 ///\warning This functionality cannot be used together with the
1.289 ///Snapshot feature.
1.290 - Node split(Arc e) {
1.291 - Node b = addNode();
1.292 - addArc(b,target(e));
1.293 - changeTarget(e,b);
1.294 - return b;
1.295 + Node split(Arc a) {
1.296 + Node v = addNode();
1.297 + addArc(v,target(a));
1.298 + changeTarget(a,v);
1.299 + return v;
1.300 }
1.301
1.302 + ///Clear the digraph.
1.303 +
1.304 + ///This function erases all nodes and arcs from the digraph.
1.305 + ///
1.306 + void clear() {
1.307 + Parent::clear();
1.308 + }
1.309 +
1.310 + /// Reserve memory for nodes.
1.311 +
1.312 + /// Using this function, it is possible to avoid superfluous memory
1.313 + /// allocation: if you know that the digraph you want to build will
1.314 + /// be large (e.g. it will contain millions of nodes and/or arcs),
1.315 + /// then it is worth reserving space for this amount before starting
1.316 + /// to build the digraph.
1.317 + /// \sa reserveArc()
1.318 + void reserveNode(int n) { nodes.reserve(n); };
1.319 +
1.320 + /// Reserve memory for arcs.
1.321 +
1.322 + /// Using this function, it is possible to avoid superfluous memory
1.323 + /// allocation: if you know that the digraph you want to build will
1.324 + /// be large (e.g. it will contain millions of nodes and/or arcs),
1.325 + /// then it is worth reserving space for this amount before starting
1.326 + /// to build the digraph.
1.327 + /// \sa reserveNode()
1.328 + void reserveArc(int m) { arcs.reserve(m); };
1.329 +
1.330 /// \brief Class to make a snapshot of the digraph and restore
1.331 /// it later.
1.332 ///
1.333 @@ -537,9 +540,15 @@
1.334 /// The newly added nodes and arcs can be removed using the
1.335 /// restore() function.
1.336 ///
1.337 - /// \warning Arc and node deletions and other modifications (e.g.
1.338 - /// contracting, splitting, reversing arcs or nodes) cannot be
1.339 + /// \note After a state is restored, you cannot restore a later state,
1.340 + /// i.e. you cannot add the removed nodes and arcs again using
1.341 + /// another Snapshot instance.
1.342 + ///
1.343 + /// \warning Node and arc deletions and other modifications (e.g.
1.344 + /// reversing, contracting, splitting arcs or nodes) cannot be
1.345 /// restored. These events invalidate the snapshot.
1.346 + /// However the arcs and nodes that were added to the digraph after
1.347 + /// making the current snapshot can be removed without invalidating it.
1.348 class Snapshot {
1.349 protected:
1.350
1.351 @@ -709,39 +718,37 @@
1.352 /// \brief Default constructor.
1.353 ///
1.354 /// Default constructor.
1.355 - /// To actually make a snapshot you must call save().
1.356 + /// You have to call save() to actually make a snapshot.
1.357 Snapshot()
1.358 : digraph(0), node_observer_proxy(*this),
1.359 arc_observer_proxy(*this) {}
1.360
1.361 /// \brief Constructor that immediately makes a snapshot.
1.362 ///
1.363 - /// This constructor immediately makes a snapshot of the digraph.
1.364 - /// \param _digraph The digraph we make a snapshot of.
1.365 - Snapshot(ListDigraph &_digraph)
1.366 + /// This constructor immediately makes a snapshot of the given digraph.
1.367 + Snapshot(ListDigraph &gr)
1.368 : node_observer_proxy(*this),
1.369 arc_observer_proxy(*this) {
1.370 - attach(_digraph);
1.371 + attach(gr);
1.372 }
1.373
1.374 /// \brief Make a snapshot.
1.375 ///
1.376 - /// Make a snapshot of the digraph.
1.377 - ///
1.378 - /// This function can be called more than once. In case of a repeated
1.379 + /// This function makes a snapshot of the given digraph.
1.380 + /// It can be called more than once. In case of a repeated
1.381 /// call, the previous snapshot gets lost.
1.382 - /// \param _digraph The digraph we make the snapshot of.
1.383 - void save(ListDigraph &_digraph) {
1.384 + void save(ListDigraph &gr) {
1.385 if (attached()) {
1.386 detach();
1.387 clear();
1.388 }
1.389 - attach(_digraph);
1.390 + attach(gr);
1.391 }
1.392
1.393 /// \brief Undo the changes until the last snapshot.
1.394 - //
1.395 - /// Undo the changes until the last snapshot created by save().
1.396 + ///
1.397 + /// This function undos the changes until the last snapshot
1.398 + /// created by save() or Snapshot(ListDigraph&).
1.399 void restore() {
1.400 detach();
1.401 for(std::list<Arc>::iterator it = added_arcs.begin();
1.402 @@ -755,9 +762,9 @@
1.403 clear();
1.404 }
1.405
1.406 - /// \brief Gives back true when the snapshot is valid.
1.407 + /// \brief Returns \c true if the snapshot is valid.
1.408 ///
1.409 - /// Gives back true when the snapshot is valid.
1.410 + /// This function returns \c true if the snapshot is valid.
1.411 bool valid() const {
1.412 return attached();
1.413 }
1.414 @@ -795,10 +802,6 @@
1.415
1.416 typedef ListGraphBase Graph;
1.417
1.418 - class Node;
1.419 - class Arc;
1.420 - class Edge;
1.421 -
1.422 class Node {
1.423 friend class ListGraphBase;
1.424 protected:
1.425 @@ -848,8 +851,6 @@
1.426 bool operator<(const Arc& arc) const {return id < arc.id;}
1.427 };
1.428
1.429 -
1.430 -
1.431 ListGraphBase()
1.432 : nodes(), first_node(-1),
1.433 first_free_node(-1), arcs(), first_free_arc(-1) {}
1.434 @@ -1164,31 +1165,25 @@
1.435
1.436 ///A general undirected graph structure.
1.437
1.438 - ///\ref ListGraph is a simple and fast <em>undirected graph</em>
1.439 - ///implementation based on static linked lists that are stored in
1.440 + ///\ref ListGraph is a versatile and fast undirected graph
1.441 + ///implementation based on linked lists that are stored in
1.442 ///\c std::vector structures.
1.443 ///
1.444 - ///It conforms to the \ref concepts::Graph "Graph concept" and it
1.445 - ///also provides several useful additional functionalities.
1.446 - ///Most of the member functions and nested classes are documented
1.447 + ///This type fully conforms to the \ref concepts::Graph "Graph concept"
1.448 + ///and it also provides several useful additional functionalities.
1.449 + ///Most of its member functions and nested classes are documented
1.450 ///only in the concept class.
1.451 ///
1.452 ///\sa concepts::Graph
1.453 -
1.454 + ///\sa ListDigraph
1.455 class ListGraph : public ExtendedListGraphBase {
1.456 typedef ExtendedListGraphBase Parent;
1.457
1.458 private:
1.459 - ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1.460 -
1.461 - ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1.462 - ///
1.463 + /// Graphs are \e not copy constructible. Use GraphCopy instead.
1.464 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
1.465 - ///\brief Assignment of ListGraph to another one is \e not allowed.
1.466 - ///Use copyGraph() instead.
1.467 -
1.468 - ///Assignment of ListGraph to another one is \e not allowed.
1.469 - ///Use copyGraph() instead.
1.470 + /// \brief Assignment of a graph to another one is \e not allowed.
1.471 + /// Use GraphCopy instead.
1.472 void operator=(const ListGraph &) {}
1.473 public:
1.474 /// Constructor
1.475 @@ -1201,94 +1196,95 @@
1.476
1.477 /// \brief Add a new node to the graph.
1.478 ///
1.479 - /// Add a new node to the graph.
1.480 + /// This function adds a new node to the graph.
1.481 /// \return The new node.
1.482 Node addNode() { return Parent::addNode(); }
1.483
1.484 /// \brief Add a new edge to the graph.
1.485 ///
1.486 - /// Add a new edge to the graph with source node \c s
1.487 - /// and target node \c t.
1.488 + /// This function adds a new edge to the graph between nodes
1.489 + /// \c u and \c v with inherent orientation from node \c u to
1.490 + /// node \c v.
1.491 /// \return The new edge.
1.492 - Edge addEdge(const Node& s, const Node& t) {
1.493 - return Parent::addEdge(s, t);
1.494 + Edge addEdge(Node u, Node v) {
1.495 + return Parent::addEdge(u, v);
1.496 }
1.497
1.498 - /// \brief Erase a node from the graph.
1.499 + ///\brief Erase a node from the graph.
1.500 ///
1.501 - /// Erase a node from the graph.
1.502 + /// This function erases the given node from the graph.
1.503 + void erase(Node n) { Parent::erase(n); }
1.504 +
1.505 + ///\brief Erase an edge from the graph.
1.506 ///
1.507 - void erase(const Node& n) { Parent::erase(n); }
1.508 -
1.509 - /// \brief Erase an edge from the graph.
1.510 - ///
1.511 - /// Erase an edge from the graph.
1.512 - ///
1.513 - void erase(const Edge& e) { Parent::erase(e); }
1.514 + /// This function erases the given edge from the graph.
1.515 + void erase(Edge e) { Parent::erase(e); }
1.516 /// Node validity check
1.517
1.518 - /// This function gives back true if the given node is valid,
1.519 - /// ie. it is a real node of the graph.
1.520 + /// This function gives back \c true if the given node is valid,
1.521 + /// i.e. it is a real node of the graph.
1.522 ///
1.523 - /// \warning A Node pointing to a removed item
1.524 - /// could become valid again later if new nodes are
1.525 + /// \warning A removed node could become valid again if new nodes are
1.526 /// added to the graph.
1.527 bool valid(Node n) const { return Parent::valid(n); }
1.528 + /// Edge validity check
1.529 +
1.530 + /// This function gives back \c true if the given edge is valid,
1.531 + /// i.e. it is a real edge of the graph.
1.532 + ///
1.533 + /// \warning A removed edge could become valid again if new edges are
1.534 + /// added to the graph.
1.535 + bool valid(Edge e) const { return Parent::valid(e); }
1.536 /// Arc validity check
1.537
1.538 - /// This function gives back true if the given arc is valid,
1.539 - /// ie. it is a real arc of the graph.
1.540 + /// This function gives back \c true if the given arc is valid,
1.541 + /// i.e. it is a real arc of the graph.
1.542 ///
1.543 - /// \warning An Arc pointing to a removed item
1.544 - /// could become valid again later if new edges are
1.545 + /// \warning A removed arc could become valid again if new edges are
1.546 /// added to the graph.
1.547 bool valid(Arc a) const { return Parent::valid(a); }
1.548 - /// Edge validity check
1.549
1.550 - /// This function gives back true if the given edge is valid,
1.551 - /// ie. it is a real arc of the graph.
1.552 + /// \brief Change the first node of an edge.
1.553 ///
1.554 - /// \warning A Edge pointing to a removed item
1.555 - /// could become valid again later if new edges are
1.556 - /// added to the graph.
1.557 - bool valid(Edge e) const { return Parent::valid(e); }
1.558 - /// \brief Change the end \c u of \c e to \c n
1.559 + /// This function changes the first node of the given edge \c e to \c n.
1.560 ///
1.561 - /// This function changes the end \c u of \c e to node \c n.
1.562 - ///
1.563 - ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
1.564 - ///changed edge are invalidated and if the changed node is the
1.565 - ///base node of an iterator then this iterator is also
1.566 - ///invalidated.
1.567 + ///\note \c EdgeIt and \c ArcIt iterators referencing the
1.568 + ///changed edge are invalidated and all other iterators whose
1.569 + ///base node is the changed node are also invalidated.
1.570 ///
1.571 ///\warning This functionality cannot be used together with the
1.572 ///Snapshot feature.
1.573 void changeU(Edge e, Node n) {
1.574 Parent::changeU(e,n);
1.575 }
1.576 - /// \brief Change the end \c v of \c e to \c n
1.577 + /// \brief Change the second node of an edge.
1.578 ///
1.579 - /// This function changes the end \c v of \c e to \c n.
1.580 + /// This function changes the second node of the given edge \c e to \c n.
1.581 ///
1.582 - ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
1.583 - ///valid, however <tt>ArcIt</tt>s and if the changed node is the
1.584 - ///base node of an iterator then this iterator is invalidated.
1.585 + ///\note \c EdgeIt iterators referencing the changed edge remain
1.586 + ///valid, however \c ArcIt iterators referencing the changed edge and
1.587 + ///all other iterators whose base node is the changed node are also
1.588 + ///invalidated.
1.589 ///
1.590 ///\warning This functionality cannot be used together with the
1.591 ///Snapshot feature.
1.592 void changeV(Edge e, Node n) {
1.593 Parent::changeV(e,n);
1.594 }
1.595 +
1.596 /// \brief Contract two nodes.
1.597 ///
1.598 - /// This function contracts two nodes.
1.599 - /// Node \p b will be removed but instead of deleting
1.600 - /// its neighboring arcs, they will be joined to \p a.
1.601 - /// The last parameter \p r controls whether to remove loops. \c true
1.602 - /// means that loops will be removed.
1.603 + /// This function contracts the given two nodes.
1.604 + /// Node \c b is removed, but instead of deleting
1.605 + /// its incident edges, they are joined to node \c a.
1.606 + /// If the last parameter \c r is \c true (this is the default value),
1.607 + /// then the newly created loops are removed.
1.608 ///
1.609 - /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
1.610 - /// valid.
1.611 + /// \note The moved edges are joined to node \c a using changeU()
1.612 + /// or changeV(), thus all edge and arc iterators whose base node is
1.613 + /// \c b are invalidated.
1.614 + /// Moreover all iterators referencing node \c b or the removed
1.615 + /// loops are also invalidated. Other iterators remain valid.
1.616 ///
1.617 ///\warning This functionality cannot be used together with the
1.618 ///Snapshot feature.
1.619 @@ -1307,6 +1303,13 @@
1.620 erase(b);
1.621 }
1.622
1.623 + ///Clear the graph.
1.624 +
1.625 + ///This function erases all nodes and arcs from the graph.
1.626 + ///
1.627 + void clear() {
1.628 + Parent::clear();
1.629 + }
1.630
1.631 /// \brief Class to make a snapshot of the graph and restore
1.632 /// it later.
1.633 @@ -1316,9 +1319,15 @@
1.634 /// The newly added nodes and edges can be removed
1.635 /// using the restore() function.
1.636 ///
1.637 - /// \warning Edge and node deletions and other modifications
1.638 - /// (e.g. changing nodes of edges, contracting nodes) cannot be
1.639 - /// restored. These events invalidate the snapshot.
1.640 + /// \note After a state is restored, you cannot restore a later state,
1.641 + /// i.e. you cannot add the removed nodes and edges again using
1.642 + /// another Snapshot instance.
1.643 + ///
1.644 + /// \warning Node and edge deletions and other modifications
1.645 + /// (e.g. changing the end-nodes of edges or contracting nodes)
1.646 + /// cannot be restored. These events invalidate the snapshot.
1.647 + /// However the edges and nodes that were added to the graph after
1.648 + /// making the current snapshot can be removed without invalidating it.
1.649 class Snapshot {
1.650 protected:
1.651
1.652 @@ -1488,39 +1497,37 @@
1.653 /// \brief Default constructor.
1.654 ///
1.655 /// Default constructor.
1.656 - /// To actually make a snapshot you must call save().
1.657 + /// You have to call save() to actually make a snapshot.
1.658 Snapshot()
1.659 : graph(0), node_observer_proxy(*this),
1.660 edge_observer_proxy(*this) {}
1.661
1.662 /// \brief Constructor that immediately makes a snapshot.
1.663 ///
1.664 - /// This constructor immediately makes a snapshot of the graph.
1.665 - /// \param _graph The graph we make a snapshot of.
1.666 - Snapshot(ListGraph &_graph)
1.667 + /// This constructor immediately makes a snapshot of the given graph.
1.668 + Snapshot(ListGraph &gr)
1.669 : node_observer_proxy(*this),
1.670 edge_observer_proxy(*this) {
1.671 - attach(_graph);
1.672 + attach(gr);
1.673 }
1.674
1.675 /// \brief Make a snapshot.
1.676 ///
1.677 - /// Make a snapshot of the graph.
1.678 - ///
1.679 - /// This function can be called more than once. In case of a repeated
1.680 + /// This function makes a snapshot of the given graph.
1.681 + /// It can be called more than once. In case of a repeated
1.682 /// call, the previous snapshot gets lost.
1.683 - /// \param _graph The graph we make the snapshot of.
1.684 - void save(ListGraph &_graph) {
1.685 + void save(ListGraph &gr) {
1.686 if (attached()) {
1.687 detach();
1.688 clear();
1.689 }
1.690 - attach(_graph);
1.691 + attach(gr);
1.692 }
1.693
1.694 /// \brief Undo the changes until the last snapshot.
1.695 - //
1.696 - /// Undo the changes until the last snapshot created by save().
1.697 + ///
1.698 + /// This function undos the changes until the last snapshot
1.699 + /// created by save() or Snapshot(ListGraph&).
1.700 void restore() {
1.701 detach();
1.702 for(std::list<Edge>::iterator it = added_edges.begin();
1.703 @@ -1534,9 +1541,9 @@
1.704 clear();
1.705 }
1.706
1.707 - /// \brief Gives back true when the snapshot is valid.
1.708 + /// \brief Returns \c true if the snapshot is valid.
1.709 ///
1.710 - /// Gives back true when the snapshot is valid.
1.711 + /// This function returns \c true if the snapshot is valid.
1.712 bool valid() const {
1.713 return attached();
1.714 }