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