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