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