1.1 --- a/lemon/smart_graph.h Mon Sep 28 15:53:20 2009 +0200
1.2 +++ b/lemon/smart_graph.h Thu Nov 05 10:27:17 2009 +0100
1.3 @@ -32,10 +32,7 @@
1.4 namespace lemon {
1.5
1.6 class SmartDigraph;
1.7 - ///Base of SmartDigraph
1.8
1.9 - ///Base of SmartDigraph
1.10 - ///
1.11 class SmartDigraphBase {
1.12 protected:
1.13
1.14 @@ -187,28 +184,26 @@
1.15 ///
1.16 ///\brief A smart directed graph class.
1.17 ///
1.18 - ///This is a simple and fast digraph implementation.
1.19 - ///It is also quite memory efficient, but at the price
1.20 - ///that <b> it does support only limited (only stack-like)
1.21 - ///node and arc deletions</b>.
1.22 - ///It fully conforms to the \ref concepts::Digraph "Digraph concept".
1.23 + ///\ref SmartDigraph is a simple and fast digraph implementation.
1.24 + ///It is also quite memory efficient but at the price
1.25 + ///that it does not support node and arc deletion
1.26 + ///(except for the Snapshot feature).
1.27 ///
1.28 - ///\sa concepts::Digraph.
1.29 + ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
1.30 + ///and it also provides some additional functionalities.
1.31 + ///Most of its member functions and nested classes are documented
1.32 + ///only in the concept class.
1.33 + ///
1.34 + ///\sa concepts::Digraph
1.35 + ///\sa SmartGraph
1.36 class SmartDigraph : public ExtendedSmartDigraphBase {
1.37 typedef ExtendedSmartDigraphBase Parent;
1.38
1.39 private:
1.40 -
1.41 - ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.42 -
1.43 - ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
1.44 - ///
1.45 + /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
1.46 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
1.47 - ///\brief Assignment of SmartDigraph to another one is \e not allowed.
1.48 - ///Use DigraphCopy() instead.
1.49 -
1.50 - ///Assignment of SmartDigraph to another one is \e not allowed.
1.51 - ///Use DigraphCopy() instead.
1.52 + /// \brief Assignment of a digraph to another one is \e not allowed.
1.53 + /// Use DigraphCopy instead.
1.54 void operator=(const SmartDigraph &) {}
1.55
1.56 public:
1.57 @@ -221,79 +216,49 @@
1.58
1.59 ///Add a new node to the digraph.
1.60
1.61 - /// Add a new node to the digraph.
1.62 - /// \return The new node.
1.63 + ///This function adds a new node to the digraph.
1.64 + ///\return The new node.
1.65 Node addNode() { return Parent::addNode(); }
1.66
1.67 ///Add a new arc to the digraph.
1.68
1.69 - ///Add a new arc to the digraph with source node \c s
1.70 + ///This function adds a new arc to the digraph with source node \c s
1.71 ///and target node \c t.
1.72 ///\return The new arc.
1.73 - Arc addArc(const Node& s, const Node& t) {
1.74 + Arc addArc(Node s, Node t) {
1.75 return Parent::addArc(s, t);
1.76 }
1.77
1.78 - /// \brief Using this it is possible to avoid the superfluous memory
1.79 - /// allocation.
1.80 -
1.81 - /// Using this it is possible to avoid the superfluous memory
1.82 - /// allocation: if you know that the digraph you want to build will
1.83 - /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.84 - /// then it is worth reserving space for this amount before starting
1.85 - /// to build the digraph.
1.86 - /// \sa reserveArc
1.87 - void reserveNode(int n) { nodes.reserve(n); };
1.88 -
1.89 - /// \brief Using this it is possible to avoid the superfluous memory
1.90 - /// allocation.
1.91 -
1.92 - /// Using this it is possible to avoid the superfluous memory
1.93 - /// allocation: if you know that the digraph you want to build will
1.94 - /// be very large (e.g. it will contain millions of nodes and/or arcs)
1.95 - /// then it is worth reserving space for this amount before starting
1.96 - /// to build the digraph.
1.97 - /// \sa reserveNode
1.98 - void reserveArc(int m) { arcs.reserve(m); };
1.99 -
1.100 /// \brief Node validity check
1.101 ///
1.102 - /// This function gives back true if the given node is valid,
1.103 - /// ie. it is a real node of the graph.
1.104 + /// This function gives back \c true if the given node is valid,
1.105 + /// i.e. it is a real node of the digraph.
1.106 ///
1.107 /// \warning A removed node (using Snapshot) could become valid again
1.108 - /// when new nodes are added to the graph.
1.109 + /// if new nodes are added to the digraph.
1.110 bool valid(Node n) const { return Parent::valid(n); }
1.111
1.112 /// \brief Arc validity check
1.113 ///
1.114 - /// This function gives back true if the given arc is valid,
1.115 - /// ie. it is a real arc of the graph.
1.116 + /// This function gives back \c true if the given arc is valid,
1.117 + /// i.e. it is a real arc of the digraph.
1.118 ///
1.119 /// \warning A removed arc (using Snapshot) could become valid again
1.120 - /// when new arcs are added to the graph.
1.121 + /// if new arcs are added to the graph.
1.122 bool valid(Arc a) const { return Parent::valid(a); }
1.123
1.124 - ///Clear the digraph.
1.125 -
1.126 - ///Erase all the nodes and arcs from the digraph.
1.127 - ///
1.128 - void clear() {
1.129 - Parent::clear();
1.130 - }
1.131 -
1.132 ///Split a node.
1.133
1.134 - ///This function splits a node. First a new node is added to the digraph,
1.135 - ///then the source of each outgoing arc of \c n is moved to this new node.
1.136 - ///If \c connect is \c true (this is the default value), then a new arc
1.137 - ///from \c n to the newly created node is also added.
1.138 + ///This function splits the given node. First, a new node is added
1.139 + ///to the digraph, then the source of each outgoing arc of node \c n
1.140 + ///is moved to this new node.
1.141 + ///If the second parameter \c connect is \c true (this is the default
1.142 + ///value), then a new arc from node \c n to the newly created node
1.143 + ///is also added.
1.144 ///\return The newly created node.
1.145 ///
1.146 - ///\note The <tt>Arc</tt>s
1.147 - ///referencing a moved arc remain
1.148 - ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
1.149 - ///may be invalidated.
1.150 + ///\note All iterators remain valid.
1.151 + ///
1.152 ///\warning This functionality cannot be used together with the Snapshot
1.153 ///feature.
1.154 Node split(Node n, bool connect = true)
1.155 @@ -308,6 +273,34 @@
1.156 return b;
1.157 }
1.158
1.159 + ///Clear the digraph.
1.160 +
1.161 + ///This function erases all nodes and arcs from the digraph.
1.162 + ///
1.163 + void clear() {
1.164 + Parent::clear();
1.165 + }
1.166 +
1.167 + /// Reserve memory for nodes.
1.168 +
1.169 + /// Using this function, it is possible to avoid superfluous memory
1.170 + /// allocation: if you know that the digraph you want to build will
1.171 + /// be large (e.g. it will contain millions of nodes and/or arcs),
1.172 + /// then it is worth reserving space for this amount before starting
1.173 + /// to build the digraph.
1.174 + /// \sa reserveArc()
1.175 + void reserveNode(int n) { nodes.reserve(n); };
1.176 +
1.177 + /// Reserve memory for arcs.
1.178 +
1.179 + /// Using this function, it is possible to avoid superfluous memory
1.180 + /// allocation: if you know that the digraph you want to build will
1.181 + /// be large (e.g. it will contain millions of nodes and/or arcs),
1.182 + /// then it is worth reserving space for this amount before starting
1.183 + /// to build the digraph.
1.184 + /// \sa reserveNode()
1.185 + void reserveArc(int m) { arcs.reserve(m); };
1.186 +
1.187 public:
1.188
1.189 class Snapshot;
1.190 @@ -332,20 +325,23 @@
1.191
1.192 public:
1.193
1.194 - ///Class to make a snapshot of the digraph and to restrore to it later.
1.195 + ///Class to make a snapshot of the digraph and to restore it later.
1.196
1.197 - ///Class to make a snapshot of the digraph and to restrore to it later.
1.198 + ///Class to make a snapshot of the digraph and to restore it later.
1.199 ///
1.200 ///The newly added nodes and arcs can be removed using the
1.201 - ///restore() function.
1.202 - ///\note After you restore a state, you cannot restore
1.203 - ///a later state, in other word you cannot add again the arcs deleted
1.204 - ///by restore() using another one Snapshot instance.
1.205 + ///restore() function. This is the only way for deleting nodes and/or
1.206 + ///arcs from a SmartDigraph structure.
1.207 ///
1.208 - ///\warning If you do not use correctly the snapshot that can cause
1.209 - ///either broken program, invalid state of the digraph, valid but
1.210 - ///not the restored digraph or no change. Because the runtime performance
1.211 - ///the validity of the snapshot is not stored.
1.212 + ///\note After a state is restored, you cannot restore a later state,
1.213 + ///i.e. you cannot add the removed nodes and arcs again using
1.214 + ///another Snapshot instance.
1.215 + ///
1.216 + ///\warning Node splitting cannot be restored.
1.217 + ///\warning The validity of the snapshot is not stored due to
1.218 + ///performance reasons. If you do not use the snapshot correctly,
1.219 + ///it can cause broken program, invalid or not restored state of
1.220 + ///the digraph or no change.
1.221 class Snapshot
1.222 {
1.223 SmartDigraph *_graph;
1.224 @@ -357,39 +353,32 @@
1.225 ///Default constructor.
1.226
1.227 ///Default constructor.
1.228 - ///To actually make a snapshot you must call save().
1.229 - ///
1.230 + ///You have to call save() to actually make a snapshot.
1.231 Snapshot() : _graph(0) {}
1.232 ///Constructor that immediately makes a snapshot
1.233
1.234 - ///This constructor immediately makes a snapshot of the digraph.
1.235 - ///\param graph The digraph we make a snapshot of.
1.236 - Snapshot(SmartDigraph &graph) : _graph(&graph) {
1.237 + ///This constructor immediately makes a snapshot of the given digraph.
1.238 + ///
1.239 + Snapshot(SmartDigraph &gr) : _graph(&gr) {
1.240 node_num=_graph->nodes.size();
1.241 arc_num=_graph->arcs.size();
1.242 }
1.243
1.244 ///Make a snapshot.
1.245
1.246 - ///Make a snapshot of the digraph.
1.247 - ///
1.248 - ///This function can be called more than once. In case of a repeated
1.249 + ///This function makes a snapshot of the given digraph.
1.250 + ///It can be called more than once. In case of a repeated
1.251 ///call, the previous snapshot gets lost.
1.252 - ///\param graph The digraph we make the snapshot of.
1.253 - void save(SmartDigraph &graph)
1.254 - {
1.255 - _graph=&graph;
1.256 + void save(SmartDigraph &gr) {
1.257 + _graph=&gr;
1.258 node_num=_graph->nodes.size();
1.259 arc_num=_graph->arcs.size();
1.260 }
1.261
1.262 ///Undo the changes until a snapshot.
1.263
1.264 - ///Undo the changes until a snapshot created by save().
1.265 - ///
1.266 - ///\note After you restored a state, you cannot restore
1.267 - ///a later state, in other word you cannot add again the arcs deleted
1.268 - ///by restore().
1.269 + ///This function undos the changes until the last snapshot
1.270 + ///created by save() or Snapshot(SmartDigraph&).
1.271 void restore()
1.272 {
1.273 _graph->restoreSnapshot(*this);
1.274 @@ -508,7 +497,7 @@
1.275 node._id = nodes.size() - 1;
1.276 }
1.277
1.278 - void next(Node& node) const {
1.279 + static void next(Node& node) {
1.280 --node._id;
1.281 }
1.282
1.283 @@ -516,7 +505,7 @@
1.284 arc._id = arcs.size() - 1;
1.285 }
1.286
1.287 - void next(Arc& arc) const {
1.288 + static void next(Arc& arc) {
1.289 --arc._id;
1.290 }
1.291
1.292 @@ -524,7 +513,7 @@
1.293 arc._id = arcs.size() / 2 - 1;
1.294 }
1.295
1.296 - void next(Edge& arc) const {
1.297 + static void next(Edge& arc) {
1.298 --arc._id;
1.299 }
1.300
1.301 @@ -621,29 +610,26 @@
1.302 ///
1.303 /// \brief A smart undirected graph class.
1.304 ///
1.305 - /// This is a simple and fast graph implementation.
1.306 - /// It is also quite memory efficient, but at the price
1.307 - /// that <b> it does support only limited (only stack-like)
1.308 - /// node and arc deletions</b>.
1.309 - /// It fully conforms to the \ref concepts::Graph "Graph concept".
1.310 + /// \ref SmartGraph is a simple and fast graph implementation.
1.311 + /// It is also quite memory efficient but at the price
1.312 + /// that it does not support node and edge deletion
1.313 + /// (except for the Snapshot feature).
1.314 ///
1.315 - /// \sa concepts::Graph.
1.316 + /// This type fully conforms to the \ref concepts::Graph "Graph concept"
1.317 + /// and it also provides some additional functionalities.
1.318 + /// Most of its member functions and nested classes are documented
1.319 + /// only in the concept class.
1.320 + ///
1.321 + /// \sa concepts::Graph
1.322 + /// \sa SmartDigraph
1.323 class SmartGraph : public ExtendedSmartGraphBase {
1.324 typedef ExtendedSmartGraphBase Parent;
1.325
1.326 private:
1.327 -
1.328 - ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
1.329 -
1.330 - ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
1.331 - ///
1.332 + /// Graphs are \e not copy constructible. Use GraphCopy instead.
1.333 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
1.334 -
1.335 - ///\brief Assignment of SmartGraph to another one is \e not allowed.
1.336 - ///Use GraphCopy() instead.
1.337 -
1.338 - ///Assignment of SmartGraph to another one is \e not allowed.
1.339 - ///Use GraphCopy() instead.
1.340 + /// \brief Assignment of a graph to another one is \e not allowed.
1.341 + /// Use GraphCopy instead.
1.342 void operator=(const SmartGraph &) {}
1.343
1.344 public:
1.345 @@ -654,56 +640,77 @@
1.346 ///
1.347 SmartGraph() {}
1.348
1.349 - ///Add a new node to the graph.
1.350 -
1.351 - /// Add a new node to the graph.
1.352 + /// \brief Add a new node to the graph.
1.353 + ///
1.354 + /// This function adds a new node to the graph.
1.355 /// \return The new node.
1.356 Node addNode() { return Parent::addNode(); }
1.357
1.358 - ///Add a new edge to the graph.
1.359 -
1.360 - ///Add a new edge to the graph with node \c s
1.361 - ///and \c t.
1.362 - ///\return The new edge.
1.363 - Edge addEdge(const Node& s, const Node& t) {
1.364 - return Parent::addEdge(s, t);
1.365 + /// \brief Add a new edge to the graph.
1.366 + ///
1.367 + /// This function adds a new edge to the graph between nodes
1.368 + /// \c u and \c v with inherent orientation from node \c u to
1.369 + /// node \c v.
1.370 + /// \return The new edge.
1.371 + Edge addEdge(Node u, Node v) {
1.372 + return Parent::addEdge(u, v);
1.373 }
1.374
1.375 /// \brief Node validity check
1.376 ///
1.377 - /// This function gives back true if the given node is valid,
1.378 - /// ie. it is a real node of the graph.
1.379 + /// This function gives back \c true if the given node is valid,
1.380 + /// i.e. it is a real node of the graph.
1.381 ///
1.382 /// \warning A removed node (using Snapshot) could become valid again
1.383 - /// when new nodes are added to the graph.
1.384 + /// if new nodes are added to the graph.
1.385 bool valid(Node n) const { return Parent::valid(n); }
1.386
1.387 + /// \brief Edge validity check
1.388 + ///
1.389 + /// This function gives back \c true if the given edge is valid,
1.390 + /// i.e. it is a real edge of the graph.
1.391 + ///
1.392 + /// \warning A removed edge (using Snapshot) could become valid again
1.393 + /// if new edges are added to the graph.
1.394 + bool valid(Edge e) const { return Parent::valid(e); }
1.395 +
1.396 /// \brief Arc validity check
1.397 ///
1.398 - /// This function gives back true if the given arc is valid,
1.399 - /// ie. it is a real arc of the graph.
1.400 + /// This function gives back \c true if the given arc is valid,
1.401 + /// i.e. it is a real arc of the graph.
1.402 ///
1.403 /// \warning A removed arc (using Snapshot) could become valid again
1.404 - /// when new edges are added to the graph.
1.405 + /// if new edges are added to the graph.
1.406 bool valid(Arc a) const { return Parent::valid(a); }
1.407
1.408 - /// \brief Edge validity check
1.409 - ///
1.410 - /// This function gives back true if the given edge is valid,
1.411 - /// ie. it is a real edge of the graph.
1.412 - ///
1.413 - /// \warning A removed edge (using Snapshot) could become valid again
1.414 - /// when new edges are added to the graph.
1.415 - bool valid(Edge e) const { return Parent::valid(e); }
1.416 -
1.417 ///Clear the graph.
1.418
1.419 - ///Erase all the nodes and edges from the graph.
1.420 + ///This function erases all nodes and arcs from the graph.
1.421 ///
1.422 void clear() {
1.423 Parent::clear();
1.424 }
1.425
1.426 + /// Reserve memory for nodes.
1.427 +
1.428 + /// Using this function, it is possible to avoid superfluous memory
1.429 + /// allocation: if you know that the graph you want to build will
1.430 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.431 + /// then it is worth reserving space for this amount before starting
1.432 + /// to build the graph.
1.433 + /// \sa reserveEdge()
1.434 + void reserveNode(int n) { nodes.reserve(n); };
1.435 +
1.436 + /// Reserve memory for edges.
1.437 +
1.438 + /// Using this function, it is possible to avoid superfluous memory
1.439 + /// allocation: if you know that the graph you want to build will
1.440 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.441 + /// then it is worth reserving space for this amount before starting
1.442 + /// to build the graph.
1.443 + /// \sa reserveNode()
1.444 + void reserveEdge(int m) { arcs.reserve(2 * m); };
1.445 +
1.446 public:
1.447
1.448 class Snapshot;
1.449 @@ -742,21 +749,22 @@
1.450
1.451 public:
1.452
1.453 - ///Class to make a snapshot of the digraph and to restrore to it later.
1.454 + ///Class to make a snapshot of the graph and to restore it later.
1.455
1.456 - ///Class to make a snapshot of the digraph and to restrore to it later.
1.457 + ///Class to make a snapshot of the graph and to restore it later.
1.458 ///
1.459 - ///The newly added nodes and arcs can be removed using the
1.460 - ///restore() function.
1.461 + ///The newly added nodes and edges can be removed using the
1.462 + ///restore() function. This is the only way for deleting nodes and/or
1.463 + ///edges from a SmartGraph structure.
1.464 ///
1.465 - ///\note After you restore a state, you cannot restore
1.466 - ///a later state, in other word you cannot add again the arcs deleted
1.467 - ///by restore() using another one Snapshot instance.
1.468 + ///\note After a state is restored, you cannot restore a later state,
1.469 + ///i.e. you cannot add the removed nodes and edges again using
1.470 + ///another Snapshot instance.
1.471 ///
1.472 - ///\warning If you do not use correctly the snapshot that can cause
1.473 - ///either broken program, invalid state of the digraph, valid but
1.474 - ///not the restored digraph or no change. Because the runtime performance
1.475 - ///the validity of the snapshot is not stored.
1.476 + ///\warning The validity of the snapshot is not stored due to
1.477 + ///performance reasons. If you do not use the snapshot correctly,
1.478 + ///it can cause broken program, invalid or not restored state of
1.479 + ///the graph or no change.
1.480 class Snapshot
1.481 {
1.482 SmartGraph *_graph;
1.483 @@ -768,36 +776,30 @@
1.484 ///Default constructor.
1.485
1.486 ///Default constructor.
1.487 - ///To actually make a snapshot you must call save().
1.488 - ///
1.489 + ///You have to call save() to actually make a snapshot.
1.490 Snapshot() : _graph(0) {}
1.491 ///Constructor that immediately makes a snapshot
1.492
1.493 - ///This constructor immediately makes a snapshot of the digraph.
1.494 - ///\param graph The digraph we make a snapshot of.
1.495 - Snapshot(SmartGraph &graph) {
1.496 - graph.saveSnapshot(*this);
1.497 + /// This constructor immediately makes a snapshot of the given graph.
1.498 + ///
1.499 + Snapshot(SmartGraph &gr) {
1.500 + gr.saveSnapshot(*this);
1.501 }
1.502
1.503 ///Make a snapshot.
1.504
1.505 - ///Make a snapshot of the graph.
1.506 - ///
1.507 - ///This function can be called more than once. In case of a repeated
1.508 + ///This function makes a snapshot of the given graph.
1.509 + ///It can be called more than once. In case of a repeated
1.510 ///call, the previous snapshot gets lost.
1.511 - ///\param graph The digraph we make the snapshot of.
1.512 - void save(SmartGraph &graph)
1.513 + void save(SmartGraph &gr)
1.514 {
1.515 - graph.saveSnapshot(*this);
1.516 + gr.saveSnapshot(*this);
1.517 }
1.518
1.519 - ///Undo the changes until a snapshot.
1.520 + ///Undo the changes until the last snapshot.
1.521
1.522 - ///Undo the changes until a snapshot created by save().
1.523 - ///
1.524 - ///\note After you restored a state, you cannot restore
1.525 - ///a later state, in other word you cannot add again the arcs deleted
1.526 - ///by restore().
1.527 + ///This function undos the changes until the last snapshot
1.528 + ///created by save() or Snapshot(SmartGraph&).
1.529 void restore()
1.530 {
1.531 _graph->restoreSnapshot(*this);