Changeset 780:580af8cf2f6a in lemon-1.2 for lemon
- Timestamp:
- 11/05/09 10:23:16 (15 years ago)
- Branch:
- default
- Parents:
- 779:c160bf9f18ef (diff), 772:f964a00b9068 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Location:
- lemon
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r770 r780 114 114 lemon/smart_graph.h \ 115 115 lemon/soplex.h \ 116 lemon/static_graph.h \ 116 117 lemon/suurballe.h \ 117 118 lemon/time_measure.h \ -
lemon/Makefile.am
r773 r780 58 58 lemon/arg_parser.h \ 59 59 lemon/assert.h \ 60 lemon/bellman_ford.h \ 60 61 lemon/bfs.h \ 61 62 lemon/bin_heap.h \ 63 lemon/binom_heap.h \ 62 64 lemon/bucket_heap.h \ 63 65 lemon/cbc.h \ … … 79 81 lemon/euler.h \ 80 82 lemon/fib_heap.h \ 83 lemon/fourary_heap.h \ 81 84 lemon/full_graph.h \ 82 85 lemon/glpk.h \ … … 84 87 lemon/graph_to_eps.h \ 85 88 lemon/grid_graph.h \ 89 lemon/hartmann_orlin.h \ 90 lemon/howard.h \ 86 91 lemon/hypercube_graph.h \ 92 lemon/karp.h \ 93 lemon/kary_heap.h \ 87 94 lemon/kruskal.h \ 88 95 lemon/hao_orlin.h \ … … 99 106 lemon/nauty_reader.h \ 100 107 lemon/network_simplex.h \ 108 lemon/pairing_heap.h \ 101 109 lemon/path.h \ 102 110 lemon/preflow.h \ -
lemon/full_graph.h
r735 r780 52 52 53 53 Node operator()(int ix) const { return Node(ix); } 54 int index(const Node& node) const{ return node._id; }54 static int index(const Node& node) { return node._id; } 55 55 56 56 Arc arc(const Node& s, const Node& t) const { … … 214 214 /// the range <tt>[0..nodeNum()-1]</tt>. 215 215 /// \sa operator()() 216 int index(Node node) const{ return Parent::index(node); }216 static int index(const Node& node) { return Parent::index(node); } 217 217 218 218 /// \brief Returns the arc connecting the given nodes. … … 288 288 289 289 Node operator()(int ix) const { return Node(ix); } 290 int index(const Node& node) const{ return node._id; }290 static int index(const Node& node) { return node._id; } 291 291 292 292 Edge edge(const Node& u, const Node& v) const { … … 589 589 /// the range <tt>[0..nodeNum()-1]</tt>. 590 590 /// \sa operator()() 591 int index(Node node) const{ return Parent::index(node); }591 static int index(const Node& node) { return Parent::index(node); } 592 592 593 593 /// \brief Returns the arc connecting the given nodes. -
lemon/full_graph.h
r778 r780 25 25 ///\ingroup graphs 26 26 ///\file 27 ///\brief Full Graph and FullDigraph classes.27 ///\brief FullDigraph and FullGraph classes. 28 28 29 29 namespace lemon { … … 149 149 /// \ingroup graphs 150 150 /// 151 /// \brief A full digraph class. 152 /// 153 /// This is a simple and fast directed full graph implementation. 154 /// From each node go arcs to each node (including the source node), 155 /// therefore the number of the arcs in the digraph is the square of 156 /// the node number. This digraph type is completely static, so you 157 /// can neither add nor delete either arcs or nodes, and it needs 158 /// constant space in memory. 159 /// 160 /// This class fully conforms to the \ref concepts::Digraph 161 /// "Digraph concept". 162 /// 163 /// The \c FullDigraph and \c FullGraph classes are very similar, 151 /// \brief A directed full graph class. 152 /// 153 /// FullDigraph is a simple and fast implmenetation of directed full 154 /// (complete) graphs. It contains an arc from each node to each node 155 /// (including a loop for each node), therefore the number of arcs 156 /// is the square of the number of nodes. 157 /// This class is completely static and it needs constant memory space. 158 /// Thus you can neither add nor delete nodes or arcs, however 159 /// the structure can be resized using resize(). 160 /// 161 /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". 162 /// Most of its member functions and nested classes are documented 163 /// only in the concept class. 164 /// 165 /// \note FullDigraph and FullGraph classes are very similar, 164 166 /// but there are two differences. While this class conforms only 165 /// to the \ref concepts::Digraph "Digraph" concept, the \cFullGraph166 /// c lass conforms to the \ref concepts::Graph "Graph" concept,167 /// moreover \c FullGraph does not contain a loop arcfor each168 /// node as \c FullDigraphdoes.167 /// to the \ref concepts::Digraph "Digraph" concept, FullGraph 168 /// conforms to the \ref concepts::Graph "Graph" concept, 169 /// moreover FullGraph does not contain a loop for each 170 /// node as this class does. 169 171 /// 170 172 /// \sa FullGraph … … 174 176 public: 175 177 176 /// \brief Constructor 178 /// \brief Default constructor. 179 /// 180 /// Default constructor. The number of nodes and arcs will be zero. 177 181 FullDigraph() { construct(0); } 178 182 … … 185 189 /// \brief Resizes the digraph 186 190 /// 187 /// Resizes the digraph. The function will fully destroyand188 /// rebuild the digraph. This cause that the maps of the digraph will191 /// This function resizes the digraph. It fully destroys and 192 /// rebuilds the structure, therefore the maps of the digraph will be 189 193 /// reallocated automatically and the previous values will be lost. 190 194 void resize(int n) { … … 198 202 /// \brief Returns the node with the given index. 199 203 /// 200 /// Returns the node with the given index. Since it is a static201 /// digraph its nodes can be indexed with integers from the range202 /// <tt>[0..nodeNum()-1]</tt>.204 /// Returns the node with the given index. Since this structure is 205 /// completely static, the nodes can be indexed with integers from 206 /// the range <tt>[0..nodeNum()-1]</tt>. 203 207 /// \sa index() 204 208 Node operator()(int ix) const { return Parent::operator()(ix); } … … 206 210 /// \brief Returns the index of the given node. 207 211 /// 208 /// Returns the index of the given node. Since it is a static209 /// digraph its nodes can be indexed with integers from the range210 /// <tt>[0..nodeNum()-1]</tt>.211 /// \sa operator() 212 /// Returns the index of the given node. Since this structure is 213 /// completely static, the nodes can be indexed with integers from 214 /// the range <tt>[0..nodeNum()-1]</tt>. 215 /// \sa operator()() 212 216 static int index(const Node& node) { return Parent::index(node); } 213 217 … … 215 219 /// 216 220 /// Returns the arc connecting the given nodes. 217 Arc arc( const Node& u, const Node&v) const {221 Arc arc(Node u, Node v) const { 218 222 return Parent::arc(u, v); 219 223 } … … 521 525 /// \brief An undirected full graph class. 522 526 /// 523 /// This is a simple and fast undirected full graph 524 /// implementation. From each node go edge to each other node, 525 /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. 526 /// This graph type is completely static, so you can neither 527 /// add nor delete either edges or nodes, and it needs constant 528 /// space in memory. 529 /// 530 /// This class fully conforms to the \ref concepts::Graph "Graph concept". 531 /// 532 /// The \c FullGraph and \c FullDigraph classes are very similar, 533 /// but there are two differences. While the \c FullDigraph class 527 /// FullGraph is a simple and fast implmenetation of undirected full 528 /// (complete) graphs. It contains an edge between every distinct pair 529 /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>. 530 /// This class is completely static and it needs constant memory space. 531 /// Thus you can neither add nor delete nodes or edges, however 532 /// the structure can be resized using resize(). 533 /// 534 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 535 /// Most of its member functions and nested classes are documented 536 /// only in the concept class. 537 /// 538 /// \note FullDigraph and FullGraph classes are very similar, 539 /// but there are two differences. While FullDigraph 534 540 /// conforms only to the \ref concepts::Digraph "Digraph" concept, 535 541 /// this class conforms to the \ref concepts::Graph "Graph" concept, 536 /// moreover \c FullGraph does not contain a loop arcfor each537 /// node as \cFullDigraph does.542 /// moreover this class does not contain a loop for each 543 /// node as FullDigraph does. 538 544 /// 539 545 /// \sa FullDigraph … … 543 549 public: 544 550 545 /// \brief Constructor 551 /// \brief Default constructor. 552 /// 553 /// Default constructor. The number of nodes and edges will be zero. 546 554 FullGraph() { construct(0); } 547 555 … … 554 562 /// \brief Resizes the graph 555 563 /// 556 /// Resizes the graph. The function will fully destroyand557 /// rebuild the graph. This cause that the maps of the graph will564 /// This function resizes the graph. It fully destroys and 565 /// rebuilds the structure, therefore the maps of the graph will be 558 566 /// reallocated automatically and the previous values will be lost. 559 567 void resize(int n) { … … 569 577 /// \brief Returns the node with the given index. 570 578 /// 571 /// Returns the node with the given index. Since it is a static572 /// graph its nodes can be indexed with integers from the range573 /// <tt>[0..nodeNum()-1]</tt>.579 /// Returns the node with the given index. Since this structure is 580 /// completely static, the nodes can be indexed with integers from 581 /// the range <tt>[0..nodeNum()-1]</tt>. 574 582 /// \sa index() 575 583 Node operator()(int ix) const { return Parent::operator()(ix); } … … 577 585 /// \brief Returns the index of the given node. 578 586 /// 579 /// Returns the index of the given node. Since it is a static580 /// graph its nodes can be indexed with integers from the range581 /// <tt>[0..nodeNum()-1]</tt>.582 /// \sa operator() 587 /// Returns the index of the given node. Since this structure is 588 /// completely static, the nodes can be indexed with integers from 589 /// the range <tt>[0..nodeNum()-1]</tt>. 590 /// \sa operator()() 583 591 static int index(const Node& node) { return Parent::index(node); } 584 592 … … 586 594 /// 587 595 /// Returns the arc connecting the given nodes. 588 Arc arc( const Node& s, const Node&t) const {596 Arc arc(Node s, Node t) const { 589 597 return Parent::arc(s, t); 590 598 } 591 599 592 /// \brief Returns the edge connect sthe given nodes.593 /// 594 /// Returns the edge connect sthe given nodes.595 Edge edge( const Node& u, const Node&v) const {600 /// \brief Returns the edge connecting the given nodes. 601 /// 602 /// Returns the edge connecting the given nodes. 603 Edge edge(Node u, Node v) const { 596 604 return Parent::edge(u, v); 597 605 } -
lemon/hypercube_graph.h
r737 r780 263 263 } 264 264 265 int index(Node node) const{265 static int index(Node node) { 266 266 return node._id; 267 267 } … … 357 357 /// Gives back the index of the given node. 358 358 /// The lower bits of the integer describes the node. 359 int index(Node node) const{359 static int index(Node node) { 360 360 return Parent::index(node); 361 361 } -
lemon/hypercube_graph.h
r778 r780 283 283 /// \brief Hypercube graph class 284 284 /// 285 /// This class implements a special graph type. The nodes of the graph286 /// are indiced with integers withat most \c dim binary digits.285 /// HypercubeGraph implements a special graph type. The nodes of the 286 /// graph are indexed with integers having at most \c dim binary digits. 287 287 /// Two nodes are connected in the graph if and only if their indices 288 288 /// differ only on one position in the binary form. 289 /// This class is completely static and it needs constant memory space. 290 /// Thus you can neither add nor delete nodes or edges, however 291 /// the structure can be resized using resize(). 292 /// 293 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 294 /// Most of its member functions and nested classes are documented 295 /// only in the concept class. 289 296 /// 290 297 /// \note The type of the indices is chosen to \c int for efficiency 291 298 /// reasons. Thus the maximum dimension of this implementation is 26 292 299 /// (assuming that the size of \c int is 32 bit). 293 ///294 /// This graph type fully conforms to the \ref concepts::Graph295 /// "Graph concept".296 300 class HypercubeGraph : public ExtendedHypercubeGraphBase { 297 301 typedef ExtendedHypercubeGraphBase Parent; … … 303 307 /// Constructs a hypercube graph with \c dim dimensions. 304 308 HypercubeGraph(int dim) { construct(dim); } 309 310 /// \brief Resizes the graph 311 /// 312 /// This function resizes the graph. It fully destroys and 313 /// rebuilds the structure, therefore the maps of the graph will be 314 /// reallocated automatically and the previous values will be lost. 315 void resize(int dim) { 316 Parent::notifier(Arc()).clear(); 317 Parent::notifier(Edge()).clear(); 318 Parent::notifier(Node()).clear(); 319 construct(dim); 320 Parent::notifier(Node()).build(); 321 Parent::notifier(Edge()).build(); 322 Parent::notifier(Arc()).build(); 323 } 305 324 306 325 /// \brief The number of dimensions. … … 321 340 /// 322 341 /// Gives back the dimension id of the given edge. 323 /// It is in the [0..dim-1] range.342 /// It is in the range <tt>[0..dim-1]</tt>. 324 343 int dimension(Edge edge) const { 325 344 return Parent::dimension(edge); … … 329 348 /// 330 349 /// Gives back the dimension id of the given arc. 331 /// It is in the [0..dim-1] range.350 /// It is in the range <tt>[0..dim-1]</tt>. 332 351 int dimension(Arc arc) const { 333 352 return Parent::dimension(arc); -
lemon/smart_graph.h
r736 r780 498 498 } 499 499 500 void next(Node& node) const{500 static void next(Node& node) { 501 501 --node._id; 502 502 } … … 506 506 } 507 507 508 void next(Arc& arc) const{508 static void next(Arc& arc) { 509 509 --arc._id; 510 510 } … … 514 514 } 515 515 516 void next(Edge& arc) const{516 static void next(Edge& arc) { 517 517 --arc._id; 518 518 } -
lemon/smart_graph.h
r778 r780 33 33 34 34 class SmartDigraph; 35 ///Base of SmartDigraph 36 37 ///Base of SmartDigraph 38 /// 35 39 36 class SmartDigraphBase { 40 37 protected: … … 188 185 ///\brief A smart directed graph class. 189 186 /// 190 ///This is a simple and fast digraph implementation. 191 ///It is also quite memory efficient, but at the price 192 ///that <b> it does support only limited (only stack-like) 193 ///node and arc deletions</b>. 194 ///It fully conforms to the \ref concepts::Digraph "Digraph concept". 187 ///\ref SmartDigraph is a simple and fast digraph implementation. 188 ///It is also quite memory efficient but at the price 189 ///that it does not support node and arc deletion 190 ///(except for the Snapshot feature). 195 191 /// 196 ///\sa concepts::Digraph. 192 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 193 ///and it also provides some additional functionalities. 194 ///Most of its member functions and nested classes are documented 195 ///only in the concept class. 196 /// 197 ///\sa concepts::Digraph 198 ///\sa SmartGraph 197 199 class SmartDigraph : public ExtendedSmartDigraphBase { 198 200 typedef ExtendedSmartDigraphBase Parent; 199 201 200 202 private: 201 202 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 203 204 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 205 /// 203 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 206 204 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; 207 ///\brief Assignment of SmartDigraph to another one is \e not allowed. 208 ///Use DigraphCopy() instead. 209 210 ///Assignment of SmartDigraph to another one is \e not allowed. 211 ///Use DigraphCopy() instead. 205 /// \brief Assignment of a digraph to another one is \e not allowed. 206 /// Use DigraphCopy instead. 212 207 void operator=(const SmartDigraph &) {} 213 208 … … 222 217 ///Add a new node to the digraph. 223 218 224 /// Adda new node to the digraph.225 /// 219 ///This function adds a new node to the digraph. 220 ///\return The new node. 226 221 Node addNode() { return Parent::addNode(); } 227 222 228 223 ///Add a new arc to the digraph. 229 224 230 /// Adda new arc to the digraph with source node \c s225 ///This function adds a new arc to the digraph with source node \c s 231 226 ///and target node \c t. 232 227 ///\return The new arc. 233 Arc addArc( const Node& s, const Node&t) {228 Arc addArc(Node s, Node t) { 234 229 return Parent::addArc(s, t); 235 230 } 236 231 237 /// \brief Using this it is possible to avoid the superfluous memory238 /// allocation.239 240 /// Using this it is possible to avoid the superfluous memory241 /// allocation: if you know that the digraph you want to build will242 /// be very large (e.g. it will contain millions of nodes and/or arcs)243 /// then it is worth reserving space for this amount before starting244 /// to build the digraph.245 /// \sa reserveArc246 void reserveNode(int n) { nodes.reserve(n); };247 248 /// \brief Using this it is possible to avoid the superfluous memory249 /// allocation.250 251 /// Using this it is possible to avoid the superfluous memory252 /// allocation: if you know that the digraph you want to build will253 /// be very large (e.g. it will contain millions of nodes and/or arcs)254 /// then it is worth reserving space for this amount before starting255 /// to build the digraph.256 /// \sa reserveNode257 void reserveArc(int m) { arcs.reserve(m); };258 259 232 /// \brief Node validity check 260 233 /// 261 /// This function gives back true if the given node is valid,262 /// i e. it is a real node of thegraph.234 /// This function gives back \c true if the given node is valid, 235 /// i.e. it is a real node of the digraph. 263 236 /// 264 237 /// \warning A removed node (using Snapshot) could become valid again 265 /// when new nodes are added to thegraph.238 /// if new nodes are added to the digraph. 266 239 bool valid(Node n) const { return Parent::valid(n); } 267 240 268 241 /// \brief Arc validity check 269 242 /// 270 /// This function gives back true if the given arc is valid,271 /// i e. it is a real arc of thegraph.243 /// This function gives back \c true if the given arc is valid, 244 /// i.e. it is a real arc of the digraph. 272 245 /// 273 246 /// \warning A removed arc (using Snapshot) could become valid again 274 /// whennew arcs are added to the graph.247 /// if new arcs are added to the graph. 275 248 bool valid(Arc a) const { return Parent::valid(a); } 276 249 277 ///Clear the digraph.278 279 ///Erase all the nodes and arcs from the digraph.280 ///281 void clear() {282 Parent::clear();283 }284 285 250 ///Split a node. 286 251 287 ///This function splits a node. First a new node is added to the digraph, 288 ///then the source of each outgoing arc of \c n is moved to this new node. 289 ///If \c connect is \c true (this is the default value), then a new arc 290 ///from \c n to the newly created node is also added. 252 ///This function splits the given node. First, a new node is added 253 ///to the digraph, then the source of each outgoing arc of node \c n 254 ///is moved to this new node. 255 ///If the second parameter \c connect is \c true (this is the default 256 ///value), then a new arc from node \c n to the newly created node 257 ///is also added. 291 258 ///\return The newly created node. 292 259 /// 293 ///\note The <tt>Arc</tt>s 294 ///referencing a moved arc remain 295 ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s 296 ///may be invalidated. 260 ///\note All iterators remain valid. 261 /// 297 262 ///\warning This functionality cannot be used together with the Snapshot 298 263 ///feature. … … 309 274 } 310 275 276 ///Clear the digraph. 277 278 ///This function erases all nodes and arcs from the digraph. 279 /// 280 void clear() { 281 Parent::clear(); 282 } 283 284 /// Reserve memory for nodes. 285 286 /// Using this function, it is possible to avoid superfluous memory 287 /// allocation: if you know that the digraph you want to build will 288 /// be large (e.g. it will contain millions of nodes and/or arcs), 289 /// then it is worth reserving space for this amount before starting 290 /// to build the digraph. 291 /// \sa reserveArc() 292 void reserveNode(int n) { nodes.reserve(n); }; 293 294 /// Reserve memory for arcs. 295 296 /// Using this function, it is possible to avoid superfluous memory 297 /// allocation: if you know that the digraph you want to build will 298 /// be large (e.g. it will contain millions of nodes and/or arcs), 299 /// then it is worth reserving space for this amount before starting 300 /// to build the digraph. 301 /// \sa reserveNode() 302 void reserveArc(int m) { arcs.reserve(m); }; 303 311 304 public: 312 305 … … 333 326 public: 334 327 335 ///Class to make a snapshot of the digraph and to rest rore toit later.336 337 ///Class to make a snapshot of the digraph and to rest rore toit later.328 ///Class to make a snapshot of the digraph and to restore it later. 329 330 ///Class to make a snapshot of the digraph and to restore it later. 338 331 /// 339 332 ///The newly added nodes and arcs can be removed using the 340 ///restore() function. 341 ///\note After you restore a state, you cannot restore 342 ///a later state, in other word you cannot add again the arcs deleted 343 ///by restore() using another one Snapshot instance. 344 /// 345 ///\warning If you do not use correctly the snapshot that can cause 346 ///either broken program, invalid state of the digraph, valid but 347 ///not the restored digraph or no change. Because the runtime performance 348 ///the validity of the snapshot is not stored. 333 ///restore() function. This is the only way for deleting nodes and/or 334 ///arcs from a SmartDigraph structure. 335 /// 336 ///\note After a state is restored, you cannot restore a later state, 337 ///i.e. you cannot add the removed nodes and arcs again using 338 ///another Snapshot instance. 339 /// 340 ///\warning Node splitting cannot be restored. 341 ///\warning The validity of the snapshot is not stored due to 342 ///performance reasons. If you do not use the snapshot correctly, 343 ///it can cause broken program, invalid or not restored state of 344 ///the digraph or no change. 349 345 class Snapshot 350 346 { … … 358 354 359 355 ///Default constructor. 360 ///To actually make a snapshot you must call save(). 361 /// 356 ///You have to call save() to actually make a snapshot. 362 357 Snapshot() : _graph(0) {} 363 358 ///Constructor that immediately makes a snapshot 364 359 365 ///This constructor immediately makes a snapshot of the digraph.366 /// \param graph The digraph we make a snapshot of.367 Snapshot(SmartDigraph &gr aph) : _graph(&graph) {360 ///This constructor immediately makes a snapshot of the given digraph. 361 /// 362 Snapshot(SmartDigraph &gr) : _graph(&gr) { 368 363 node_num=_graph->nodes.size(); 369 364 arc_num=_graph->arcs.size(); … … 372 367 ///Make a snapshot. 373 368 374 ///Make a snapshot of the digraph. 375 /// 376 ///This function can be called more than once. In case of a repeated 369 ///This function makes a snapshot of the given digraph. 370 ///It can be called more than once. In case of a repeated 377 371 ///call, the previous snapshot gets lost. 378 ///\param graph The digraph we make the snapshot of. 379 void save(SmartDigraph &graph) 380 { 381 _graph=&graph; 372 void save(SmartDigraph &gr) { 373 _graph=&gr; 382 374 node_num=_graph->nodes.size(); 383 375 arc_num=_graph->arcs.size(); … … 386 378 ///Undo the changes until a snapshot. 387 379 388 ///Undo the changes until a snapshot created by save(). 389 /// 390 ///\note After you restored a state, you cannot restore 391 ///a later state, in other word you cannot add again the arcs deleted 392 ///by restore(). 380 ///This function undos the changes until the last snapshot 381 ///created by save() or Snapshot(SmartDigraph&). 393 382 void restore() 394 383 { … … 622 611 /// \brief A smart undirected graph class. 623 612 /// 624 /// This is a simple and fast graph implementation. 625 /// It is also quite memory efficient, but at the price 626 /// that <b> it does support only limited (only stack-like) 627 /// node and arc deletions</b>. 628 /// It fully conforms to the \ref concepts::Graph "Graph concept". 613 /// \ref SmartGraph is a simple and fast graph implementation. 614 /// It is also quite memory efficient but at the price 615 /// that it does not support node and edge deletion 616 /// (except for the Snapshot feature). 629 617 /// 630 /// \sa concepts::Graph. 618 /// This type fully conforms to the \ref concepts::Graph "Graph concept" 619 /// and it also provides some additional functionalities. 620 /// Most of its member functions and nested classes are documented 621 /// only in the concept class. 622 /// 623 /// \sa concepts::Graph 624 /// \sa SmartDigraph 631 625 class SmartGraph : public ExtendedSmartGraphBase { 632 626 typedef ExtendedSmartGraphBase Parent; 633 627 634 628 private: 635 636 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 637 638 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 639 /// 629 /// Graphs are \e not copy constructible. Use GraphCopy instead. 640 630 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; 641 642 ///\brief Assignment of SmartGraph to another one is \e not allowed. 643 ///Use GraphCopy() instead. 644 645 ///Assignment of SmartGraph to another one is \e not allowed. 646 ///Use GraphCopy() instead. 631 /// \brief Assignment of a graph to another one is \e not allowed. 632 /// Use GraphCopy instead. 647 633 void operator=(const SmartGraph &) {} 648 634 … … 655 641 SmartGraph() {} 656 642 657 /// Add a new node to the graph.658 659 /// Adda new node to the graph.643 /// \brief Add a new node to the graph. 644 /// 645 /// This function adds a new node to the graph. 660 646 /// \return The new node. 661 647 Node addNode() { return Parent::addNode(); } 662 648 663 ///Add a new edge to the graph. 664 665 ///Add a new edge to the graph with node \c s 666 ///and \c t. 667 ///\return The new edge. 668 Edge addEdge(const Node& s, const Node& t) { 669 return Parent::addEdge(s, t); 649 /// \brief Add a new edge to the graph. 650 /// 651 /// This function adds a new edge to the graph between nodes 652 /// \c u and \c v with inherent orientation from node \c u to 653 /// node \c v. 654 /// \return The new edge. 655 Edge addEdge(Node u, Node v) { 656 return Parent::addEdge(u, v); 670 657 } 671 658 672 659 /// \brief Node validity check 673 660 /// 674 /// This function gives back true if the given node is valid,675 /// i e. it is a real node of the graph.661 /// This function gives back \c true if the given node is valid, 662 /// i.e. it is a real node of the graph. 676 663 /// 677 664 /// \warning A removed node (using Snapshot) could become valid again 678 /// whennew nodes are added to the graph.665 /// if new nodes are added to the graph. 679 666 bool valid(Node n) const { return Parent::valid(n); } 680 667 668 /// \brief Edge validity check 669 /// 670 /// This function gives back \c true if the given edge is valid, 671 /// i.e. it is a real edge of the graph. 672 /// 673 /// \warning A removed edge (using Snapshot) could become valid again 674 /// if new edges are added to the graph. 675 bool valid(Edge e) const { return Parent::valid(e); } 676 681 677 /// \brief Arc validity check 682 678 /// 683 /// This function gives back true if the given arc is valid,684 /// i e. it is a real arc of the graph.679 /// This function gives back \c true if the given arc is valid, 680 /// i.e. it is a real arc of the graph. 685 681 /// 686 682 /// \warning A removed arc (using Snapshot) could become valid again 687 /// whennew edges are added to the graph.683 /// if new edges are added to the graph. 688 684 bool valid(Arc a) const { return Parent::valid(a); } 689 685 690 /// \brief Edge validity check691 ///692 /// This function gives back true if the given edge is valid,693 /// ie. it is a real edge of the graph.694 ///695 /// \warning A removed edge (using Snapshot) could become valid again696 /// when new edges are added to the graph.697 bool valid(Edge e) const { return Parent::valid(e); }698 699 686 ///Clear the graph. 700 687 701 /// Erase all the nodes and edges from the graph.688 ///This function erases all nodes and arcs from the graph. 702 689 /// 703 690 void clear() { 704 691 Parent::clear(); 705 692 } 693 694 /// Reserve memory for nodes. 695 696 /// Using this function, it is possible to avoid superfluous memory 697 /// allocation: if you know that the graph you want to build will 698 /// be large (e.g. it will contain millions of nodes and/or edges), 699 /// then it is worth reserving space for this amount before starting 700 /// to build the graph. 701 /// \sa reserveEdge() 702 void reserveNode(int n) { nodes.reserve(n); }; 703 704 /// Reserve memory for edges. 705 706 /// Using this function, it is possible to avoid superfluous memory 707 /// allocation: if you know that the graph you want to build will 708 /// be large (e.g. it will contain millions of nodes and/or edges), 709 /// then it is worth reserving space for this amount before starting 710 /// to build the graph. 711 /// \sa reserveNode() 712 void reserveEdge(int m) { arcs.reserve(2 * m); }; 706 713 707 714 public: … … 743 750 public: 744 751 745 ///Class to make a snapshot of the digraph and to restrore to it later. 746 747 ///Class to make a snapshot of the digraph and to restrore to it later. 748 /// 749 ///The newly added nodes and arcs can be removed using the 750 ///restore() function. 751 /// 752 ///\note After you restore a state, you cannot restore 753 ///a later state, in other word you cannot add again the arcs deleted 754 ///by restore() using another one Snapshot instance. 755 /// 756 ///\warning If you do not use correctly the snapshot that can cause 757 ///either broken program, invalid state of the digraph, valid but 758 ///not the restored digraph or no change. Because the runtime performance 759 ///the validity of the snapshot is not stored. 752 ///Class to make a snapshot of the graph and to restore it later. 753 754 ///Class to make a snapshot of the graph and to restore it later. 755 /// 756 ///The newly added nodes and edges can be removed using the 757 ///restore() function. This is the only way for deleting nodes and/or 758 ///edges from a SmartGraph structure. 759 /// 760 ///\note After a state is restored, you cannot restore a later state, 761 ///i.e. you cannot add the removed nodes and edges again using 762 ///another Snapshot instance. 763 /// 764 ///\warning The validity of the snapshot is not stored due to 765 ///performance reasons. If you do not use the snapshot correctly, 766 ///it can cause broken program, invalid or not restored state of 767 ///the graph or no change. 760 768 class Snapshot 761 769 { … … 769 777 770 778 ///Default constructor. 771 ///To actually make a snapshot you must call save(). 772 /// 779 ///You have to call save() to actually make a snapshot. 773 780 Snapshot() : _graph(0) {} 774 781 ///Constructor that immediately makes a snapshot 775 782 776 /// This constructor immediately makes a snapshot of the digraph.777 /// \param graph The digraph we make a snapshot of.778 Snapshot(SmartGraph &gr aph) {779 gr aph.saveSnapshot(*this);783 /// This constructor immediately makes a snapshot of the given graph. 784 /// 785 Snapshot(SmartGraph &gr) { 786 gr.saveSnapshot(*this); 780 787 } 781 788 782 789 ///Make a snapshot. 783 790 784 ///Make a snapshot of the graph. 785 /// 786 ///This function can be called more than once. In case of a repeated 791 ///This function makes a snapshot of the given graph. 792 ///It can be called more than once. In case of a repeated 787 793 ///call, the previous snapshot gets lost. 788 ///\param graph The digraph we make the snapshot of. 789 void save(SmartGraph &graph) 794 void save(SmartGraph &gr) 790 795 { 791 graph.saveSnapshot(*this); 792 } 793 794 ///Undo the changes until a snapshot. 795 796 ///Undo the changes until a snapshot created by save(). 797 /// 798 ///\note After you restored a state, you cannot restore 799 ///a later state, in other word you cannot add again the arcs deleted 800 ///by restore(). 796 gr.saveSnapshot(*this); 797 } 798 799 ///Undo the changes until the last snapshot. 800 801 ///This function undos the changes until the last snapshot 802 ///created by save() or Snapshot(SmartGraph&). 801 803 void restore() 802 804 {
Note: See TracChangeset
for help on using the changeset viewer.