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