Changes in / [741:10c9c3a35b83:739:32baeb8e5c8f] in lemon-main
- Files:
-
- 11 edited
-
doc/groups.dox (modified) (1 diff)
-
lemon/concepts/digraph.h (modified) (15 diffs)
-
lemon/concepts/graph.h (modified) (26 diffs)
-
lemon/concepts/graph_components.h (modified) (1 diff)
-
lemon/full_graph.h (modified) (11 diffs)
-
lemon/grid_graph.h (modified) (16 diffs)
-
lemon/hypercube_graph.h (modified) (4 diffs)
-
lemon/list_graph.h (modified) (27 diffs)
-
lemon/smart_graph.h (modified) (12 diffs)
-
test/digraph_test.cc (modified) (3 diffs)
-
test/graph_test.cc (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r735 r663 637 637 \brief Skeleton and concept checking classes for graph structures 638 638 639 This group contains the skeletons and concept checking classes of 640 graph structures .639 This group contains the skeletons and concept checking classes of LEMON's 640 graph structures and helper classes used to implement these. 641 641 */ 642 642 -
lemon/concepts/digraph.h
r734 r580 36 36 /// \brief Class describing the concept of directed graphs. 37 37 /// 38 /// This class describes the common interface of all directed39 /// graphs (digraphs).38 /// This class describes the \ref concept "concept" of the 39 /// immutable directed digraphs. 40 40 /// 41 /// Like all concept classes, it only provides an interface 42 /// without any sensible implementation. So any general algorithm for 43 /// directed graphs should compile with this class, but it will not 44 /// run properly, of course. 45 /// An actual digraph implementation like \ref ListDigraph or 46 /// \ref SmartDigraph may have additional functionality. 41 /// Note that actual digraph implementation like @ref ListDigraph or 42 /// @ref SmartDigraph may have several additional functionality. 47 43 /// 48 /// \sa Graph44 /// \sa concept 49 45 class Digraph { 50 46 private: 51 /// Diraphs are \e not copy constructible. Use DigraphCopy instead. 52 Digraph(const Digraph &) {} 53 /// \brief Assignment of a digraph to another one is \e not allowed. 54 /// Use DigraphCopy instead. 47 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 48 49 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 50 /// 51 Digraph(const Digraph &) {}; 52 ///\brief Assignment of \ref Digraph "Digraph"s to another ones are 53 ///\e not allowed. Use DigraphCopy() instead. 54 55 ///Assignment of \ref Digraph "Digraph"s to another ones are 56 ///\e not allowed. Use DigraphCopy() instead. 57 55 58 void operator=(const Digraph &) {} 56 57 59 public: 58 /// Default constructor. 60 ///\e 61 62 /// Defalult constructor. 63 64 /// Defalult constructor. 65 /// 59 66 Digraph() { } 60 61 /// The node type of the digraph 67 /// Class for identifying a node of the digraph 62 68 63 69 /// This class identifies a node of the digraph. It also serves 64 70 /// as a base class of the node iterators, 65 /// thus they convert to this type.71 /// thus they will convert to this type. 66 72 class Node { 67 73 public: 68 74 /// Default constructor 69 75 70 /// Default constructor.71 /// \warning It sets the objectto an undefined value.76 /// @warning The default constructor sets the iterator 77 /// to an undefined value. 72 78 Node() { } 73 79 /// Copy constructor. … … 77 83 Node(const Node&) { } 78 84 79 /// %Invalid constructor \& conversion.80 81 /// Initializes the objectto be invalid.85 /// Invalid constructor \& conversion. 86 87 /// This constructor initializes the iterator to be invalid. 82 88 /// \sa Invalid for more details. 83 89 Node(Invalid) { } 84 90 /// Equality operator 85 91 86 /// Equality operator.87 ///88 92 /// Two iterators are equal if and only if they point to the 89 /// same object or both are \c INVALID.93 /// same object or both are invalid. 90 94 bool operator==(Node) const { return true; } 91 95 92 96 /// Inequality operator 93 97 94 /// Inequality operator. 98 /// \sa operator==(Node n) 99 /// 95 100 bool operator!=(Node) const { return true; } 96 101 97 102 /// Artificial ordering operator. 98 103 99 /// Artificial ordering operator. 100 /// 101 /// \note This operator only has to define some strict ordering of 102 /// the nodes; this order has nothing to do with the iteration 103 /// ordering of the nodes. 104 /// To allow the use of digraph descriptors as key type in std::map or 105 /// similar associative container we require this. 106 /// 107 /// \note This operator only have to define some strict ordering of 108 /// the items; this order has nothing to do with the iteration 109 /// ordering of the items. 104 110 bool operator<(Node) const { return false; } 105 }; 106 107 /// Iterator class for the nodes. 108 109 /// This iterator goes through each node of the digraph. 111 112 }; 113 114 /// This iterator goes through each node. 115 116 /// This iterator goes through each node. 110 117 /// Its usage is quite simple, for example you can count the number 111 /// of nodes in a digraph \c g of type \c %Digraph like this:118 /// of nodes in digraph \c g of type \c Digraph like this: 112 119 ///\code 113 120 /// int count=0; … … 118 125 /// Default constructor 119 126 120 /// Default constructor.121 /// \warning It sets the iteratorto an undefined value.127 /// @warning The default constructor sets the iterator 128 /// to an undefined value. 122 129 NodeIt() { } 123 130 /// Copy constructor. … … 126 133 /// 127 134 NodeIt(const NodeIt& n) : Node(n) { } 128 /// %Invalid constructor \& conversion.129 130 /// Initialize sthe iterator to be invalid.135 /// Invalid constructor \& conversion. 136 137 /// Initialize the iterator to be invalid. 131 138 /// \sa Invalid for more details. 132 139 NodeIt(Invalid) { } 133 140 /// Sets the iterator to the first node. 134 141 135 /// Sets the iterator to the first node of the given digraph. 136 /// 137 explicit NodeIt(const Digraph&) { } 138 /// Sets the iterator to the given node. 139 140 /// Sets the iterator to the given node of the given digraph. 141 /// 142 /// Sets the iterator to the first node of \c g. 143 /// 144 NodeIt(const Digraph&) { } 145 /// Node -> NodeIt conversion. 146 147 /// Sets the iterator to the node of \c the digraph pointed by 148 /// the trivial iterator. 149 /// This feature necessitates that each time we 150 /// iterate the arc-set, the iteration order is the same. 142 151 NodeIt(const Digraph&, const Node&) { } 143 152 /// Next node. … … 149 158 150 159 151 /// The arc typeof the digraph160 /// Class for identifying an arc of the digraph 152 161 153 162 /// This class identifies an arc of the digraph. It also serves … … 158 167 /// Default constructor 159 168 160 /// Default constructor.161 /// \warning It sets the objectto an undefined value.169 /// @warning The default constructor sets the iterator 170 /// to an undefined value. 162 171 Arc() { } 163 172 /// Copy constructor. … … 166 175 /// 167 176 Arc(const Arc&) { } 168 /// %Invalid constructor \& conversion.169 170 /// Initialize s the objectto be invalid.171 /// \sa Invalid for more details.177 /// Initialize the iterator to be invalid. 178 179 /// Initialize the iterator to be invalid. 180 /// 172 181 Arc(Invalid) { } 173 182 /// Equality operator 174 183 175 /// Equality operator.176 ///177 184 /// Two iterators are equal if and only if they point to the 178 /// same object or both are \c INVALID.185 /// same object or both are invalid. 179 186 bool operator==(Arc) const { return true; } 180 187 /// Inequality operator 181 188 182 /// Inequality operator. 189 /// \sa operator==(Arc n) 190 /// 183 191 bool operator!=(Arc) const { return true; } 184 192 185 193 /// Artificial ordering operator. 186 194 187 /// Artificial ordering operator. 188 /// 189 /// \note This operator only has to define some strict ordering of 190 /// the arcs; this order has nothing to do with the iteration 191 /// ordering of the arcs. 195 /// To allow the use of digraph descriptors as key type in std::map or 196 /// similar associative container we require this. 197 /// 198 /// \note This operator only have to define some strict ordering of 199 /// the items; this order has nothing to do with the iteration 200 /// ordering of the items. 192 201 bool operator<(Arc) const { return false; } 193 202 }; 194 203 195 /// Iterator class forthe outgoing arcs of a node.204 /// This iterator goes trough the outgoing arcs of a node. 196 205 197 206 /// This iterator goes trough the \e outgoing arcs of a certain node … … 199 208 /// Its usage is quite simple, for example you can count the number 200 209 /// of outgoing arcs of a node \c n 201 /// in a digraph \c g of type \c %Digraph as follows.210 /// in digraph \c g of type \c Digraph as follows. 202 211 ///\code 203 212 /// int count=0; 204 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;213 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; 205 214 ///\endcode 215 206 216 class OutArcIt : public Arc { 207 217 public: 208 218 /// Default constructor 209 219 210 /// Default constructor.211 /// \warning It sets the iteratorto an undefined value.220 /// @warning The default constructor sets the iterator 221 /// to an undefined value. 212 222 OutArcIt() { } 213 223 /// Copy constructor. … … 216 226 /// 217 227 OutArcIt(const OutArcIt& e) : Arc(e) { } 218 /// %Invalid constructor \& conversion.219 220 /// Initialize sthe iterator to be invalid.221 /// \sa Invalid for more details.228 /// Initialize the iterator to be invalid. 229 230 /// Initialize the iterator to be invalid. 231 /// 222 232 OutArcIt(Invalid) { } 223 /// Sets the iterator to the first outgoing arc.224 225 /// Sets the iterator to the first outgoing arc of the given node.226 /// 233 /// This constructor sets the iterator to the first outgoing arc. 234 235 /// This constructor sets the iterator to the first outgoing arc of 236 /// the node. 227 237 OutArcIt(const Digraph&, const Node&) { } 228 /// Sets the iterator to the given arc. 229 230 /// Sets the iterator to the given arc of the given digraph. 231 /// 238 /// Arc -> OutArcIt conversion 239 240 /// Sets the iterator to the value of the trivial iterator. 241 /// This feature necessitates that each time we 242 /// iterate the arc-set, the iteration order is the same. 232 243 OutArcIt(const Digraph&, const Arc&) { } 233 /// 244 ///Next outgoing arc 234 245 235 246 /// Assign the iterator to the next … … 238 249 }; 239 250 240 /// Iterator class forthe incoming arcs of a node.251 /// This iterator goes trough the incoming arcs of a node. 241 252 242 253 /// This iterator goes trough the \e incoming arcs of a certain node 243 254 /// of a digraph. 244 255 /// Its usage is quite simple, for example you can count the number 245 /// of incoming arcs of a node \c n246 /// in a digraph \c g of type \c %Digraph as follows.256 /// of outgoing arcs of a node \c n 257 /// in digraph \c g of type \c Digraph as follows. 247 258 ///\code 248 259 /// int count=0; 249 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;260 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count; 250 261 ///\endcode 262 251 263 class InArcIt : public Arc { 252 264 public: 253 265 /// Default constructor 254 266 255 /// Default constructor.256 /// \warning It sets the iteratorto an undefined value.267 /// @warning The default constructor sets the iterator 268 /// to an undefined value. 257 269 InArcIt() { } 258 270 /// Copy constructor. … … 261 273 /// 262 274 InArcIt(const InArcIt& e) : Arc(e) { } 263 /// %Invalid constructor \& conversion.264 265 /// Initialize sthe iterator to be invalid.266 /// \sa Invalid for more details.275 /// Initialize the iterator to be invalid. 276 277 /// Initialize the iterator to be invalid. 278 /// 267 279 InArcIt(Invalid) { } 268 /// Sets the iterator to thefirst incoming arc.269 270 /// Sets the iterator to the first incoming arc of the given node.271 /// 280 /// This constructor sets the iterator to first incoming arc. 281 282 /// This constructor set the iterator to the first incoming arc of 283 /// the node. 272 284 InArcIt(const Digraph&, const Node&) { } 273 /// Sets the iterator to the given arc. 274 275 /// Sets the iterator to the given arc of the given digraph. 276 /// 285 /// Arc -> InArcIt conversion 286 287 /// Sets the iterator to the value of the trivial iterator \c e. 288 /// This feature necessitates that each time we 289 /// iterate the arc-set, the iteration order is the same. 277 290 InArcIt(const Digraph&, const Arc&) { } 278 291 /// Next incoming arc 279 292 280 /// Assign the iterator to the next 281 /// incoming arc of the corresponding node.293 /// Assign the iterator to the next inarc of the corresponding node. 294 /// 282 295 InArcIt& operator++() { return *this; } 283 296 }; 284 285 /// Iterator class for the arcs. 286 287 /// This iterator goes through each arc of the digraph. 297 /// This iterator goes through each arc. 298 299 /// This iterator goes through each arc of a digraph. 288 300 /// Its usage is quite simple, for example you can count the number 289 /// of arcs in a digraph \c g of type \c %Digraph as follows:301 /// of arcs in a digraph \c g of type \c Digraph as follows: 290 302 ///\code 291 303 /// int count=0; 292 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;304 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count; 293 305 ///\endcode 294 306 class ArcIt : public Arc { … … 296 308 /// Default constructor 297 309 298 /// Default constructor.299 /// \warning It sets the iteratorto an undefined value.310 /// @warning The default constructor sets the iterator 311 /// to an undefined value. 300 312 ArcIt() { } 301 313 /// Copy constructor. … … 304 316 /// 305 317 ArcIt(const ArcIt& e) : Arc(e) { } 306 /// %Invalid constructor \& conversion.307 308 /// Initialize sthe iterator to be invalid.309 /// \sa Invalid for more details.318 /// Initialize the iterator to be invalid. 319 320 /// Initialize the iterator to be invalid. 321 /// 310 322 ArcIt(Invalid) { } 311 /// Sets the iterator to the first arc. 312 313 /// Sets the iterator to the first arc of the given digraph. 314 /// 315 explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } 316 /// Sets the iterator to the given arc. 317 318 /// Sets the iterator to the given arc of the given digraph. 319 /// 323 /// This constructor sets the iterator to the first arc. 324 325 /// This constructor sets the iterator to the first arc of \c g. 326 ///@param g the digraph 327 ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } 328 /// Arc -> ArcIt conversion 329 330 /// Sets the iterator to the value of the trivial iterator \c e. 331 /// This feature necessitates that each time we 332 /// iterate the arc-set, the iteration order is the same. 320 333 ArcIt(const Digraph&, const Arc&) { } 321 /// 334 ///Next arc 322 335 323 336 /// Assign the iterator to the next arc. 324 ///325 337 ArcIt& operator++() { return *this; } 326 338 }; 327 328 /// \brief The source node of the arc. 329 /// 330 /// Returns the source node of the given arc. 339 ///Gives back the target node of an arc. 340 341 ///Gives back the target node of an arc. 342 /// 343 Node target(Arc) const { return INVALID; } 344 ///Gives back the source node of an arc. 345 346 ///Gives back the source node of an arc. 347 /// 331 348 Node source(Arc) const { return INVALID; } 332 349 333 /// \brief The target node of the arc. 334 /// 335 /// Returns the target node of the given arc. 336 Node target(Arc) const { return INVALID; } 337 338 /// \brief The ID of the node. 339 /// 340 /// Returns the ID of the given node. 350 /// \brief Returns the ID of the node. 341 351 int id(Node) const { return -1; } 342 352 343 /// \brief The ID of the arc. 344 /// 345 /// Returns the ID of the given arc. 353 /// \brief Returns the ID of the arc. 346 354 int id(Arc) const { return -1; } 347 355 348 /// \brief The node with the given ID. 349 /// 350 /// Returns the node with the given ID. 351 /// \pre The argument should be a valid node ID in the digraph. 356 /// \brief Returns the node with the given ID. 357 /// 358 /// \pre The argument should be a valid node ID in the graph. 352 359 Node nodeFromId(int) const { return INVALID; } 353 360 354 /// \brief The arc with the given ID. 355 /// 356 /// Returns the arc with the given ID. 357 /// \pre The argument should be a valid arc ID in the digraph. 361 /// \brief Returns the arc with the given ID. 362 /// 363 /// \pre The argument should be a valid arc ID in the graph. 358 364 Arc arcFromId(int) const { return INVALID; } 359 365 360 /// \brief An upper bound on the node IDs. 361 /// 362 /// Returns an upper bound on the node IDs. 366 /// \brief Returns an upper bound on the node IDs. 363 367 int maxNodeId() const { return -1; } 364 368 365 /// \brief An upper bound on the arc IDs. 366 /// 367 /// Returns an upper bound on the arc IDs. 369 /// \brief Returns an upper bound on the arc IDs. 368 370 int maxArcId() const { return -1; } 369 371 … … 391 393 int maxId(Arc) const { return -1; } 392 394 393 /// \brief The opposite node on the arc.394 ///395 /// Returns the opposite node on the given arc.396 Node oppositeNode(Node, Arc) const { return INVALID; }397 398 395 /// \brief The base node of the iterator. 399 396 /// 400 /// Returns the base node of the given outgoing arc iterator401 /// (i.e. the source node of the corresponding arc).402 Node baseNode( OutArcIt) const { return INVALID; }397 /// Gives back the base node of the iterator. 398 /// It is always the target of the pointed arc. 399 Node baseNode(const InArcIt&) const { return INVALID; } 403 400 404 401 /// \brief The running node of the iterator. 405 402 /// 406 /// Returns the running node of the given outgoing arc iterator407 /// (i.e. the target node of the corresponding arc).408 Node runningNode( OutArcIt) const { return INVALID; }403 /// Gives back the running node of the iterator. 404 /// It is always the source of the pointed arc. 405 Node runningNode(const InArcIt&) const { return INVALID; } 409 406 410 407 /// \brief The base node of the iterator. 411 408 /// 412 /// Returns the base node of the given incomming arc iterator413 /// (i.e. the target node of the corresponding arc).414 Node baseNode( InArcIt) const { return INVALID; }409 /// Gives back the base node of the iterator. 410 /// It is always the source of the pointed arc. 411 Node baseNode(const OutArcIt&) const { return INVALID; } 415 412 416 413 /// \brief The running node of the iterator. 417 414 /// 418 /// Returns the running node of the given incomming arc iterator 419 /// (i.e. the source node of the corresponding arc). 420 Node runningNode(InArcIt) const { return INVALID; } 421 422 /// \brief Standard graph map type for the nodes. 423 /// 424 /// Standard graph map type for the nodes. 425 /// It conforms to the ReferenceMap concept. 415 /// Gives back the running node of the iterator. 416 /// It is always the target of the pointed arc. 417 Node runningNode(const OutArcIt&) const { return INVALID; } 418 419 /// \brief The opposite node on the given arc. 420 /// 421 /// Gives back the opposite node on the given arc. 422 Node oppositeNode(const Node&, const Arc&) const { return INVALID; } 423 424 /// \brief Reference map of the nodes to type \c T. 425 /// 426 /// Reference map of the nodes to type \c T. 426 427 template<class T> 427 428 class NodeMap : public ReferenceMap<Node, T, T&, const T&> { 428 429 public: 429 430 430 /// Constructor431 explicitNodeMap(const Digraph&) { }432 /// Constructor with given initial value431 ///\e 432 NodeMap(const Digraph&) { } 433 ///\e 433 434 NodeMap(const Digraph&, T) { } 434 435 … … 445 446 }; 446 447 447 /// \brief Standard graph map type for the arcs. 448 /// 449 /// Standard graph map type for the arcs. 450 /// It conforms to the ReferenceMap concept. 448 /// \brief Reference map of the arcs to type \c T. 449 /// 450 /// Reference map of the arcs to type \c T. 451 451 template<class T> 452 452 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> { 453 453 public: 454 454 455 /// Constructor456 explicitArcMap(const Digraph&) { }457 /// Constructor with given initial value455 ///\e 456 ArcMap(const Digraph&) { } 457 ///\e 458 458 ArcMap(const Digraph&, T) { } 459 460 459 private: 461 460 ///Copy constructor -
lemon/concepts/graph.h
r734 r657 19 19 ///\ingroup graph_concepts 20 20 ///\file 21 ///\brief The concept of undirected graphs.21 ///\brief The concept of Undirected Graphs. 22 22 23 23 #ifndef LEMON_CONCEPTS_GRAPH_H … … 25 25 26 26 #include <lemon/concepts/graph_components.h> 27 #include <lemon/concepts/maps.h>28 #include <lemon/concept_check.h>29 27 #include <lemon/core.h> 30 28 … … 34 32 /// \ingroup graph_concepts 35 33 /// 36 /// \brief Class describing the concept of undirected graphs.34 /// \brief Class describing the concept of Undirected Graphs. 37 35 /// 38 /// This class describes the common interface of all undirected39 /// graphs.36 /// This class describes the common interface of all Undirected 37 /// Graphs. 40 38 /// 41 /// Like all concept classes, it only provides aninterface42 /// without any sensible implementation. So any generalalgorithm for43 /// undirected graph sshould compile with this class, but it will not39 /// As all concept describing classes it provides only interface 40 /// without any sensible implementation. So any algorithm for 41 /// undirected graph should compile with this class, but it will not 44 42 /// run properly, of course. 45 /// An actual graph implementation like \ref ListGraph or46 /// \ref SmartGraph may have additional functionality.47 43 /// 48 /// The undirected graphs also fulfill the concept of \ref Digraph 49 /// "directed graphs", since each edge can also be regarded as two 50 /// oppositely directed arcs. 51 /// Undirected graphs provide an Edge type for the undirected edges and 52 /// an Arc type for the directed arcs. The Arc type is convertible to 53 /// Edge or inherited from it, i.e. the corresponding edge can be 54 /// obtained from an arc. 55 /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt 56 /// and ArcMap classes can be used for the arcs (just like in digraphs). 57 /// Both InArcIt and OutArcIt iterates on the same edges but with 58 /// opposite direction. IncEdgeIt also iterates on the same edges 59 /// as OutArcIt and InArcIt, but it is not convertible to Arc, 60 /// only to Edge. 44 /// The LEMON undirected graphs also fulfill the concept of 45 /// directed graphs (\ref lemon::concepts::Digraph "Digraph 46 /// Concept"). Each edges can be seen as two opposite 47 /// directed arc and consequently the undirected graph can be 48 /// seen as the direceted graph of these directed arcs. The 49 /// Graph has the Edge inner class for the edges and 50 /// the Arc type for the directed arcs. The Arc type is 51 /// convertible to Edge or inherited from it so from a directed 52 /// arc we can get the represented edge. 61 53 /// 62 /// In LEMON, each undirected edge has an inherent orientation. 63 /// Thus it can defined if an arc is forward or backward oriented in 64 /// an undirected graph with respect to this default oriantation of 65 /// the represented edge. 66 /// With the direction() and direct() functions the direction 67 /// of an arc can be obtained and set, respectively. 54 /// In the sense of the LEMON each edge has a default 55 /// direction (it should be in every computer implementation, 56 /// because the order of edge's nodes defines an 57 /// orientation). With the default orientation we can define that 58 /// the directed arc is forward or backward directed. With the \c 59 /// direction() and \c direct() function we can get the direction 60 /// of the directed arc and we can direct an edge. 68 61 /// 69 /// Only nodes and edges can be added to or removed from an undirected 70 /// graph and the corresponding arcs are added or removed automatically. 71 /// 72 /// \sa Digraph 62 /// The EdgeIt is an iterator for the edges. We can use 63 /// the EdgeMap to map values for the edges. The InArcIt and 64 /// OutArcIt iterates on the same edges but with opposite 65 /// direction. The IncEdgeIt iterates also on the same edges 66 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 67 /// to Edge. 73 68 class Graph { 74 private:75 /// Graphs are \e not copy constructible. Use DigraphCopy instead.76 Graph(const Graph&) {}77 /// \brief Assignment of a graph to another one is \e not allowed.78 /// Use DigraphCopy instead.79 void operator=(const Graph&) {}80 81 69 public: 82 /// Default constructor. 83 Graph() {} 84 85 /// \brief Undirected graphs should be tagged with \c UndirectedTag. 86 /// 87 /// Undirected graphs should be tagged with \c UndirectedTag. 88 /// 89 /// This tag helps the \c enable_if technics to make compile time 70 /// \brief The undirected graph should be tagged by the 71 /// UndirectedTag. 72 /// 73 /// The undirected graph should be tagged by the UndirectedTag. This 74 /// tag helps the enable_if technics to make compile time 90 75 /// specializations for undirected graphs. 91 76 typedef True UndirectedTag; 92 77 93 /// The node type of the graph 94 95 /// This class identifies a node of the graph. It also serves 96 /// as a base class of the node iterators, 97 /// thus they convert to this type. 78 /// \brief The base type of node iterators, 79 /// or in other words, the trivial node iterator. 80 /// 81 /// This is the base type of each node iterator, 82 /// thus each kind of node iterator converts to this. 83 /// More precisely each kind of node iterator should be inherited 84 /// from the trivial node iterator. 98 85 class Node { 99 86 public: 100 87 /// Default constructor 101 88 102 /// Default constructor.103 /// \warning It sets the objectto an undefined value.89 /// @warning The default constructor sets the iterator 90 /// to an undefined value. 104 91 Node() { } 105 92 /// Copy constructor. … … 109 96 Node(const Node&) { } 110 97 111 /// %Invalid constructor \& conversion.112 113 /// Initializes the objectto be invalid.98 /// Invalid constructor \& conversion. 99 100 /// This constructor initializes the iterator to be invalid. 114 101 /// \sa Invalid for more details. 115 102 Node(Invalid) { } 116 103 /// Equality operator 117 104 118 /// Equality operator.119 ///120 105 /// Two iterators are equal if and only if they point to the 121 /// same object or both are \c INVALID.106 /// same object or both are invalid. 122 107 bool operator==(Node) const { return true; } 123 108 124 109 /// Inequality operator 125 110 126 /// Inequality operator. 111 /// \sa operator==(Node n) 112 /// 127 113 bool operator!=(Node) const { return true; } 128 114 129 115 /// Artificial ordering operator. 130 116 131 /// Artificial ordering operator. 132 /// 133 /// \note This operator only has to define some strict ordering of 117 /// To allow the use of graph descriptors as key type in std::map or 118 /// similar associative container we require this. 119 /// 120 /// \note This operator only have to define some strict ordering of 134 121 /// the items; this order has nothing to do with the iteration 135 122 /// ordering of the items. … … 138 125 }; 139 126 140 /// Iterator class for the nodes.141 142 /// This iterator goes through each node of the graph.127 /// This iterator goes through each node. 128 129 /// This iterator goes through each node. 143 130 /// Its usage is quite simple, for example you can count the number 144 /// of nodes in a graph \c g of type \c %Graph like this:131 /// of nodes in graph \c g of type \c Graph like this: 145 132 ///\code 146 133 /// int count=0; … … 151 138 /// Default constructor 152 139 153 /// Default constructor.154 /// \warning It sets the iteratorto an undefined value.140 /// @warning The default constructor sets the iterator 141 /// to an undefined value. 155 142 NodeIt() { } 156 143 /// Copy constructor. … … 159 146 /// 160 147 NodeIt(const NodeIt& n) : Node(n) { } 161 /// %Invalid constructor \& conversion.162 163 /// Initialize sthe iterator to be invalid.148 /// Invalid constructor \& conversion. 149 150 /// Initialize the iterator to be invalid. 164 151 /// \sa Invalid for more details. 165 152 NodeIt(Invalid) { } 166 153 /// Sets the iterator to the first node. 167 154 168 /// Sets the iterator to the first node of the given digraph. 169 /// 170 explicit NodeIt(const Graph&) { } 171 /// Sets the iterator to the given node. 172 173 /// Sets the iterator to the given node of the given digraph. 174 /// 155 /// Sets the iterator to the first node of \c g. 156 /// 157 NodeIt(const Graph&) { } 158 /// Node -> NodeIt conversion. 159 160 /// Sets the iterator to the node of \c the graph pointed by 161 /// the trivial iterator. 162 /// This feature necessitates that each time we 163 /// iterate the arc-set, the iteration order is the same. 175 164 NodeIt(const Graph&, const Node&) { } 176 165 /// Next node. … … 182 171 183 172 184 /// The edge type of the graph 185 186 /// This class identifies an edge of the graph. It also serves 187 /// as a base class of the edge iterators, 188 /// thus they will convert to this type. 173 /// The base type of the edge iterators. 174 175 /// The base type of the edge iterators. 176 /// 189 177 class Edge { 190 178 public: 191 179 /// Default constructor 192 180 193 /// Default constructor.194 /// \warning It sets the objectto an undefined value.181 /// @warning The default constructor sets the iterator 182 /// to an undefined value. 195 183 Edge() { } 196 184 /// Copy constructor. … … 199 187 /// 200 188 Edge(const Edge&) { } 201 /// %Invalid constructor \& conversion.202 203 /// Initialize s the objectto be invalid.204 /// \sa Invalid for more details.189 /// Initialize the iterator to be invalid. 190 191 /// Initialize the iterator to be invalid. 192 /// 205 193 Edge(Invalid) { } 206 194 /// Equality operator 207 195 208 /// Equality operator.209 ///210 196 /// Two iterators are equal if and only if they point to the 211 /// same object or both are \c INVALID.197 /// same object or both are invalid. 212 198 bool operator==(Edge) const { return true; } 213 199 /// Inequality operator 214 200 215 /// Inequality operator. 201 /// \sa operator==(Edge n) 202 /// 216 203 bool operator!=(Edge) const { return true; } 217 204 218 205 /// Artificial ordering operator. 219 206 220 /// Artificial ordering operator. 221 /// 222 /// \note This operator only has to define some strict ordering of 223 /// the edges; this order has nothing to do with the iteration 224 /// ordering of the edges. 207 /// To allow the use of graph descriptors as key type in std::map or 208 /// similar associative container we require this. 209 /// 210 /// \note This operator only have to define some strict ordering of 211 /// the items; this order has nothing to do with the iteration 212 /// ordering of the items. 225 213 bool operator<(Edge) const { return false; } 226 214 }; 227 215 228 /// Iterator class for the edges.229 230 /// This iterator goes through each edge of thegraph.216 /// This iterator goes through each edge. 217 218 /// This iterator goes through each edge of a graph. 231 219 /// Its usage is quite simple, for example you can count the number 232 /// of edges in a graph \c g of type \c %Graph as follows:220 /// of edges in a graph \c g of type \c Graph as follows: 233 221 ///\code 234 222 /// int count=0; … … 239 227 /// Default constructor 240 228 241 /// Default constructor.242 /// \warning It sets the iteratorto an undefined value.229 /// @warning The default constructor sets the iterator 230 /// to an undefined value. 243 231 EdgeIt() { } 244 232 /// Copy constructor. … … 247 235 /// 248 236 EdgeIt(const EdgeIt& e) : Edge(e) { } 249 /// %Invalid constructor \& conversion.250 251 /// Initialize sthe iterator to be invalid.252 /// \sa Invalid for more details.237 /// Initialize the iterator to be invalid. 238 239 /// Initialize the iterator to be invalid. 240 /// 253 241 EdgeIt(Invalid) { } 254 /// Sets the iterator to the first edge. 255 256 /// Sets the iterator to the first edge of the given graph. 257 /// 258 explicit EdgeIt(const Graph&) { } 259 /// Sets the iterator to the given edge. 260 261 /// Sets the iterator to the given edge of the given graph. 262 /// 242 /// This constructor sets the iterator to the first edge. 243 244 /// This constructor sets the iterator to the first edge. 245 EdgeIt(const Graph&) { } 246 /// Edge -> EdgeIt conversion 247 248 /// Sets the iterator to the value of the trivial iterator. 249 /// This feature necessitates that each time we 250 /// iterate the edge-set, the iteration order is the 251 /// same. 263 252 EdgeIt(const Graph&, const Edge&) { } 264 253 /// Next edge 265 254 266 255 /// Assign the iterator to the next edge. 267 ///268 256 EdgeIt& operator++() { return *this; } 269 257 }; 270 258 271 /// Iterator class for the incident edges of a node. 272 273 /// This iterator goes trough the incident undirected edges 274 /// of a certain node of a graph. 259 /// \brief This iterator goes trough the incident undirected 260 /// arcs of a node. 261 /// 262 /// This iterator goes trough the incident edges 263 /// of a certain node of a graph. You should assume that the 264 /// loop arcs will be iterated twice. 265 /// 275 266 /// Its usage is quite simple, for example you can compute the 276 /// degree (i.e. the number of incident edges)of a node \c n277 /// in a graph \c g of type \c %Graph as follows.267 /// degree (i.e. count the number of incident arcs of a node \c n 268 /// in graph \c g of type \c Graph as follows. 278 269 /// 279 270 ///\code … … 281 272 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 282 273 ///\endcode 283 ///284 /// \warning Loop edges will be iterated twice.285 274 class IncEdgeIt : public Edge { 286 275 public: 287 276 /// Default constructor 288 277 289 /// Default constructor.290 /// \warning It sets the iteratorto an undefined value.278 /// @warning The default constructor sets the iterator 279 /// to an undefined value. 291 280 IncEdgeIt() { } 292 281 /// Copy constructor. … … 295 284 /// 296 285 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 297 /// %Invalid constructor \& conversion.298 299 /// Initialize sthe iterator to be invalid.300 /// \sa Invalid for more details.286 /// Initialize the iterator to be invalid. 287 288 /// Initialize the iterator to be invalid. 289 /// 301 290 IncEdgeIt(Invalid) { } 302 /// Sets the iterator to the first incident edge.303 304 /// Sets the iterator to the first incident edge of the given node.305 /// 291 /// This constructor sets the iterator to first incident arc. 292 293 /// This constructor set the iterator to the first incident arc of 294 /// the node. 306 295 IncEdgeIt(const Graph&, const Node&) { } 307 /// Sets the iterator to the given edge. 308 309 /// Sets the iterator to the given edge of the given graph. 310 /// 296 /// Edge -> IncEdgeIt conversion 297 298 /// Sets the iterator to the value of the trivial iterator \c e. 299 /// This feature necessitates that each time we 300 /// iterate the arc-set, the iteration order is the same. 311 301 IncEdgeIt(const Graph&, const Edge&) { } 312 /// Next incident edge313 314 /// Assign the iterator to the next incident edge302 /// Next incident arc 303 304 /// Assign the iterator to the next incident arc 315 305 /// of the corresponding node. 316 306 IncEdgeIt& operator++() { return *this; } 317 307 }; 318 308 319 /// The arc type of the graph320 321 /// Th is class identifies a directed arc of the graph. It also serves322 /// as a base class of the arc iterators,323 /// thus they will convert to this type.309 /// The directed arc type. 310 311 /// The directed arc type. It can be converted to the 312 /// edge or it should be inherited from the undirected 313 /// edge. 324 314 class Arc { 325 315 public: 326 316 /// Default constructor 327 317 328 /// Default constructor.329 /// \warning It sets the objectto an undefined value.318 /// @warning The default constructor sets the iterator 319 /// to an undefined value. 330 320 Arc() { } 331 321 /// Copy constructor. … … 334 324 /// 335 325 Arc(const Arc&) { } 336 /// %Invalid constructor \& conversion.337 338 /// Initialize s the objectto be invalid.339 /// \sa Invalid for more details.326 /// Initialize the iterator to be invalid. 327 328 /// Initialize the iterator to be invalid. 329 /// 340 330 Arc(Invalid) { } 341 331 /// Equality operator 342 332 343 /// Equality operator.344 ///345 333 /// Two iterators are equal if and only if they point to the 346 /// same object or both are \c INVALID.334 /// same object or both are invalid. 347 335 bool operator==(Arc) const { return true; } 348 336 /// Inequality operator 349 337 350 /// Inequality operator. 338 /// \sa operator==(Arc n) 339 /// 351 340 bool operator!=(Arc) const { return true; } 352 341 353 342 /// Artificial ordering operator. 354 343 355 /// Artificial ordering operator. 356 /// 357 /// \note This operator only has to define some strict ordering of 358 /// the arcs; this order has nothing to do with the iteration 359 /// ordering of the arcs. 344 /// To allow the use of graph descriptors as key type in std::map or 345 /// similar associative container we require this. 346 /// 347 /// \note This operator only have to define some strict ordering of 348 /// the items; this order has nothing to do with the iteration 349 /// ordering of the items. 360 350 bool operator<(Arc) const { return false; } 361 351 362 /// Converison to \c Edge 363 364 /// Converison to \c Edge. 365 /// 352 /// Converison to Edge 366 353 operator Edge() const { return Edge(); } 367 354 }; 368 369 /// Iterator class for the arcs. 370 371 /// This iterator goes through each directed arc of the graph. 355 /// This iterator goes through each directed arc. 356 357 /// This iterator goes through each arc of a graph. 372 358 /// Its usage is quite simple, for example you can count the number 373 /// of arcs in a graph \c g of type \c %Graph as follows:359 /// of arcs in a graph \c g of type \c Graph as follows: 374 360 ///\code 375 361 /// int count=0; 376 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;362 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count; 377 363 ///\endcode 378 364 class ArcIt : public Arc { … … 380 366 /// Default constructor 381 367 382 /// Default constructor.383 /// \warning It sets the iteratorto an undefined value.368 /// @warning The default constructor sets the iterator 369 /// to an undefined value. 384 370 ArcIt() { } 385 371 /// Copy constructor. … … 388 374 /// 389 375 ArcIt(const ArcIt& e) : Arc(e) { } 390 /// %Invalid constructor \& conversion.391 392 /// Initialize sthe iterator to be invalid.393 /// \sa Invalid for more details.376 /// Initialize the iterator to be invalid. 377 378 /// Initialize the iterator to be invalid. 379 /// 394 380 ArcIt(Invalid) { } 395 /// Sets the iterator to the first arc. 396 397 /// Sets the iterator to the first arc of the given graph. 398 /// 399 explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } 400 /// Sets the iterator to the given arc. 401 402 /// Sets the iterator to the given arc of the given graph. 403 /// 381 /// This constructor sets the iterator to the first arc. 382 383 /// This constructor sets the iterator to the first arc of \c g. 384 ///@param g the graph 385 ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } 386 /// Arc -> ArcIt conversion 387 388 /// Sets the iterator to the value of the trivial iterator \c e. 389 /// This feature necessitates that each time we 390 /// iterate the arc-set, the iteration order is the same. 404 391 ArcIt(const Graph&, const Arc&) { } 405 /// 392 ///Next arc 406 393 407 394 /// Assign the iterator to the next arc. 408 ///409 395 ArcIt& operator++() { return *this; } 410 396 }; 411 397 412 /// Iterator class for the outgoingarcs of a node.413 414 /// This iterator goes trough the \e outgoing directed arcs of a415 /// certain nodeof a graph.398 /// This iterator goes trough the outgoing directed arcs of a node. 399 400 /// This iterator goes trough the \e outgoing arcs of a certain node 401 /// of a graph. 416 402 /// Its usage is quite simple, for example you can count the number 417 403 /// of outgoing arcs of a node \c n 418 /// in a graph \c g of type \c %Graph as follows.404 /// in graph \c g of type \c Graph as follows. 419 405 ///\code 420 406 /// int count=0; 421 /// for ( Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;407 /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; 422 408 ///\endcode 409 423 410 class OutArcIt : public Arc { 424 411 public: 425 412 /// Default constructor 426 413 427 /// Default constructor.428 /// \warning It sets the iteratorto an undefined value.414 /// @warning The default constructor sets the iterator 415 /// to an undefined value. 429 416 OutArcIt() { } 430 417 /// Copy constructor. … … 433 420 /// 434 421 OutArcIt(const OutArcIt& e) : Arc(e) { } 435 /// %Invalid constructor \& conversion.436 437 /// Initialize sthe iterator to be invalid.438 /// \sa Invalid for more details.422 /// Initialize the iterator to be invalid. 423 424 /// Initialize the iterator to be invalid. 425 /// 439 426 OutArcIt(Invalid) { } 440 /// Sets the iterator to the first outgoing arc. 441 442 /// Sets the iterator to the first outgoing arc of the given node. 443 /// 427 /// This constructor sets the iterator to the first outgoing arc. 428 429 /// This constructor sets the iterator to the first outgoing arc of 430 /// the node. 431 ///@param n the node 432 ///@param g the graph 444 433 OutArcIt(const Graph& n, const Node& g) { 445 434 ignore_unused_variable_warning(n); 446 435 ignore_unused_variable_warning(g); 447 436 } 448 /// Sets the iterator to the given arc. 449 450 /// Sets the iterator to the given arc of the given graph. 451 /// 437 /// Arc -> OutArcIt conversion 438 439 /// Sets the iterator to the value of the trivial iterator. 440 /// This feature necessitates that each time we 441 /// iterate the arc-set, the iteration order is the same. 452 442 OutArcIt(const Graph&, const Arc&) { } 453 /// 443 ///Next outgoing arc 454 444 455 445 /// Assign the iterator to the next … … 458 448 }; 459 449 460 /// Iterator class for the incomingarcs of a node.461 462 /// This iterator goes trough the \e incoming directed arcs of a463 /// certain nodeof a graph.450 /// This iterator goes trough the incoming directed arcs of a node. 451 452 /// This iterator goes trough the \e incoming arcs of a certain node 453 /// of a graph. 464 454 /// Its usage is quite simple, for example you can count the number 465 /// of incoming arcs of a node \c n466 /// in a graph \c g of type \c %Graph as follows.455 /// of outgoing arcs of a node \c n 456 /// in graph \c g of type \c Graph as follows. 467 457 ///\code 468 458 /// int count=0; 469 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;459 /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; 470 460 ///\endcode 461 471 462 class InArcIt : public Arc { 472 463 public: 473 464 /// Default constructor 474 465 475 /// Default constructor.476 /// \warning It sets the iteratorto an undefined value.466 /// @warning The default constructor sets the iterator 467 /// to an undefined value. 477 468 InArcIt() { } 478 469 /// Copy constructor. … … 481 472 /// 482 473 InArcIt(const InArcIt& e) : Arc(e) { } 483 /// %Invalid constructor \& conversion.484 485 /// Initialize sthe iterator to be invalid.486 /// \sa Invalid for more details.474 /// Initialize the iterator to be invalid. 475 476 /// Initialize the iterator to be invalid. 477 /// 487 478 InArcIt(Invalid) { } 488 /// Sets the iterator to the first incoming arc. 489 490 /// Sets the iterator to the first incoming arc of the given node. 491 /// 479 /// This constructor sets the iterator to first incoming arc. 480 481 /// This constructor set the iterator to the first incoming arc of 482 /// the node. 483 ///@param n the node 484 ///@param g the graph 492 485 InArcIt(const Graph& g, const Node& n) { 493 486 ignore_unused_variable_warning(n); 494 487 ignore_unused_variable_warning(g); 495 488 } 496 /// Sets the iterator to the given arc. 497 498 /// Sets the iterator to the given arc of the given graph. 499 /// 489 /// Arc -> InArcIt conversion 490 491 /// Sets the iterator to the value of the trivial iterator \c e. 492 /// This feature necessitates that each time we 493 /// iterate the arc-set, the iteration order is the same. 500 494 InArcIt(const Graph&, const Arc&) { } 501 495 /// Next incoming arc 502 496 503 /// Assign the iterator to the next 504 /// incoming arc of the corresponding node.497 /// Assign the iterator to the next inarc of the corresponding node. 498 /// 505 499 InArcIt& operator++() { return *this; } 506 500 }; 507 501 508 /// \brief Standard graph map type for the nodes. 509 /// 510 /// Standard graph map type for the nodes. 511 /// It conforms to the ReferenceMap concept. 502 /// \brief Reference map of the nodes to type \c T. 503 /// 504 /// Reference map of the nodes to type \c T. 512 505 template<class T> 513 506 class NodeMap : public ReferenceMap<Node, T, T&, const T&> … … 515 508 public: 516 509 517 /// Constructor518 explicitNodeMap(const Graph&) { }519 /// Constructor with given initial value510 ///\e 511 NodeMap(const Graph&) { } 512 ///\e 520 513 NodeMap(const Graph&, T) { } 521 514 … … 532 525 }; 533 526 534 /// \brief Standard graph map type for the arcs. 535 /// 536 /// Standard graph map type for the arcs. 537 /// It conforms to the ReferenceMap concept. 527 /// \brief Reference map of the arcs to type \c T. 528 /// 529 /// Reference map of the arcs to type \c T. 538 530 template<class T> 539 531 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> … … 541 533 public: 542 534 543 /// Constructor544 explicitArcMap(const Graph&) { }545 /// Constructor with given initial value535 ///\e 536 ArcMap(const Graph&) { } 537 ///\e 546 538 ArcMap(const Graph&, T) { } 547 548 539 private: 549 540 ///Copy constructor … … 558 549 }; 559 550 560 /// \brief Standard graph map type for the edges. 561 /// 562 /// Standard graph map type for the edges. 563 /// It conforms to the ReferenceMap concept. 551 /// Reference map of the edges to type \c T. 552 553 /// Reference map of the edges to type \c T. 564 554 template<class T> 565 555 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> … … 567 557 public: 568 558 569 /// Constructor570 explicitEdgeMap(const Graph&) { }571 /// Constructor with given initial value559 ///\e 560 EdgeMap(const Graph&) { } 561 ///\e 572 562 EdgeMap(const Graph&, T) { } 573 574 563 private: 575 564 ///Copy constructor … … 584 573 }; 585 574 586 /// \brief The first node of the edge. 587 /// 588 /// Returns the first node of the given edge. 589 /// 590 /// Edges don't have source and target nodes, however methods 591 /// u() and v() are used to query the two end-nodes of an edge. 592 /// The orientation of an edge that arises this way is called 593 /// the inherent direction, it is used to define the default 594 /// direction for the corresponding arcs. 575 /// \brief Direct the given edge. 576 /// 577 /// Direct the given edge. The returned arc source 578 /// will be the given node. 579 Arc direct(const Edge&, const Node&) const { 580 return INVALID; 581 } 582 583 /// \brief Direct the given edge. 584 /// 585 /// Direct the given edge. The returned arc 586 /// represents the given edge and the direction comes 587 /// from the bool parameter. The source of the edge and 588 /// the directed arc is the same when the given bool is true. 589 Arc direct(const Edge&, bool) const { 590 return INVALID; 591 } 592 593 /// \brief Returns true if the arc has default orientation. 594 /// 595 /// Returns whether the given directed arc is same orientation as 596 /// the corresponding edge's default orientation. 597 bool direction(Arc) const { return true; } 598 599 /// \brief Returns the opposite directed arc. 600 /// 601 /// Returns the opposite directed arc. 602 Arc oppositeArc(Arc) const { return INVALID; } 603 604 /// \brief Opposite node on an arc 605 /// 606 /// \return The opposite of the given node on the given edge. 607 Node oppositeNode(Node, Edge) const { return INVALID; } 608 609 /// \brief First node of the edge. 610 /// 611 /// \return The first node of the given edge. 612 /// 613 /// Naturally edges don't have direction and thus 614 /// don't have source and target node. However we use \c u() and \c v() 615 /// methods to query the two nodes of the arc. The direction of the 616 /// arc which arises this way is called the inherent direction of the 617 /// edge, and is used to define the "default" direction 618 /// of the directed versions of the arcs. 595 619 /// \sa v() 596 620 /// \sa direction() 597 621 Node u(Edge) const { return INVALID; } 598 622 599 /// \brief The second node of the edge. 600 /// 601 /// Returns the second node of the given edge. 602 /// 603 /// Edges don't have source and target nodes, however methods 604 /// u() and v() are used to query the two end-nodes of an edge. 605 /// The orientation of an edge that arises this way is called 606 /// the inherent direction, it is used to define the default 607 /// direction for the corresponding arcs. 623 /// \brief Second node of the edge. 624 /// 625 /// \return The second node of the given edge. 626 /// 627 /// Naturally edges don't have direction and thus 628 /// don't have source and target node. However we use \c u() and \c v() 629 /// methods to query the two nodes of the arc. The direction of the 630 /// arc which arises this way is called the inherent direction of the 631 /// edge, and is used to define the "default" direction 632 /// of the directed versions of the arcs. 608 633 /// \sa u() 609 634 /// \sa direction() 610 635 Node v(Edge) const { return INVALID; } 611 636 612 /// \brief The source node of the arc. 613 /// 614 /// Returns the source node of the given arc. 637 /// \brief Source node of the directed arc. 615 638 Node source(Arc) const { return INVALID; } 616 639 617 /// \brief The target node of the arc. 618 /// 619 /// Returns the target node of the given arc. 640 /// \brief Target node of the directed arc. 620 641 Node target(Arc) const { return INVALID; } 621 642 622 /// \brief The ID of the node. 623 /// 624 /// Returns the ID of the given node. 643 /// \brief Returns the id of the node. 625 644 int id(Node) const { return -1; } 626 645 627 /// \brief The ID of the edge. 628 /// 629 /// Returns the ID of the given edge. 646 /// \brief Returns the id of the edge. 630 647 int id(Edge) const { return -1; } 631 648 632 /// \brief The ID of the arc. 633 /// 634 /// Returns the ID of the given arc. 649 /// \brief Returns the id of the arc. 635 650 int id(Arc) const { return -1; } 636 651 637 /// \brief The node with the given ID. 638 /// 639 /// Returns the node with the given ID. 640 /// \pre The argument should be a valid node ID in the graph. 652 /// \brief Returns the node with the given id. 653 /// 654 /// \pre The argument should be a valid node id in the graph. 641 655 Node nodeFromId(int) const { return INVALID; } 642 656 643 /// \brief The edge with the given ID. 644 /// 645 /// Returns the edge with the given ID. 646 /// \pre The argument should be a valid edge ID in the graph. 657 /// \brief Returns the edge with the given id. 658 /// 659 /// \pre The argument should be a valid edge id in the graph. 647 660 Edge edgeFromId(int) const { return INVALID; } 648 661 649 /// \brief The arc with the given ID. 650 /// 651 /// Returns the arc with the given ID. 652 /// \pre The argument should be a valid arc ID in the graph. 662 /// \brief Returns the arc with the given id. 663 /// 664 /// \pre The argument should be a valid arc id in the graph. 653 665 Arc arcFromId(int) const { return INVALID; } 654 666 655 /// \brief An upper bound on the node IDs. 656 /// 657 /// Returns an upper bound on the node IDs. 667 /// \brief Returns an upper bound on the node IDs. 658 668 int maxNodeId() const { return -1; } 659 669 660 /// \brief An upper bound on the edge IDs. 661 /// 662 /// Returns an upper bound on the edge IDs. 670 /// \brief Returns an upper bound on the edge IDs. 663 671 int maxEdgeId() const { return -1; } 664 672 665 /// \brief An upper bound on the arc IDs. 666 /// 667 /// Returns an upper bound on the arc IDs. 673 /// \brief Returns an upper bound on the arc IDs. 668 674 int maxArcId() const { return -1; } 669 670 /// \brief The direction of the arc.671 ///672 /// Returns \c true if the direction of the given arc is the same as673 /// the inherent orientation of the represented edge.674 bool direction(Arc) const { return true; }675 676 /// \brief Direct the edge.677 ///678 /// Direct the given edge. The returned arc679 /// represents the given edge and its direction comes680 /// from the bool parameter. If it is \c true, then the direction681 /// of the arc is the same as the inherent orientation of the edge.682 Arc direct(Edge, bool) const {683 return INVALID;684 }685 686 /// \brief Direct the edge.687 ///688 /// Direct the given edge. The returned arc represents the given689 /// edge and its source node is the given node.690 Arc direct(Edge, Node) const {691 return INVALID;692 }693 694 /// \brief The oppositely directed arc.695 ///696 /// Returns the oppositely directed arc representing the same edge.697 Arc oppositeArc(Arc) const { return INVALID; }698 699 /// \brief The opposite node on the edge.700 ///701 /// Returns the opposite node on the given edge.702 Node oppositeNode(Node, Edge) const { return INVALID; }703 675 704 676 void first(Node&) const {} … … 734 706 int maxId(Arc) const { return -1; } 735 707 736 /// \brief The base node of the iterator. 737 /// 738 /// Returns the base node of the given incident edge iterator. 739 Node baseNode(IncEdgeIt) const { return INVALID; } 740 741 /// \brief The running node of the iterator. 742 /// 743 /// Returns the running node of the given incident edge iterator. 744 Node runningNode(IncEdgeIt) const { return INVALID; } 745 746 /// \brief The base node of the iterator. 747 /// 748 /// Returns the base node of the given outgoing arc iterator 749 /// (i.e. the source node of the corresponding arc). 750 Node baseNode(OutArcIt) const { return INVALID; } 751 752 /// \brief The running node of the iterator. 753 /// 754 /// Returns the running node of the given outgoing arc iterator 755 /// (i.e. the target node of the corresponding arc). 756 Node runningNode(OutArcIt) const { return INVALID; } 757 758 /// \brief The base node of the iterator. 759 /// 760 /// Returns the base node of the given incomming arc iterator 761 /// (i.e. the target node of the corresponding arc). 762 Node baseNode(InArcIt) const { return INVALID; } 763 764 /// \brief The running node of the iterator. 765 /// 766 /// Returns the running node of the given incomming arc iterator 767 /// (i.e. the source node of the corresponding arc). 768 Node runningNode(InArcIt) const { return INVALID; } 708 /// \brief Base node of the iterator 709 /// 710 /// Returns the base node (the source in this case) of the iterator 711 Node baseNode(OutArcIt e) const { 712 return source(e); 713 } 714 /// \brief Running node of the iterator 715 /// 716 /// Returns the running node (the target in this case) of the 717 /// iterator 718 Node runningNode(OutArcIt e) const { 719 return target(e); 720 } 721 722 /// \brief Base node of the iterator 723 /// 724 /// Returns the base node (the target in this case) of the iterator 725 Node baseNode(InArcIt e) const { 726 return target(e); 727 } 728 /// \brief Running node of the iterator 729 /// 730 /// Returns the running node (the source in this case) of the 731 /// iterator 732 Node runningNode(InArcIt e) const { 733 return source(e); 734 } 735 736 /// \brief Base node of the iterator 737 /// 738 /// Returns the base node of the iterator 739 Node baseNode(IncEdgeIt) const { 740 return INVALID; 741 } 742 743 /// \brief Running node of the iterator 744 /// 745 /// Returns the running node of the iterator 746 Node runningNode(IncEdgeIt) const { 747 return INVALID; 748 } 769 749 770 750 template <typename _Graph> -
lemon/concepts/graph_components.h
r734 r666 93 93 /// associative containers (e.g. \c std::map). 94 94 /// 95 /// \note This operator only ha sto define some strict ordering of95 /// \note This operator only have to define some strict ordering of 96 96 /// the items; this order has nothing to do with the iteration 97 97 /// ordering of the items. -
lemon/full_graph.h
r735 r617 25 25 ///\ingroup graphs 26 26 ///\file 27 ///\brief Full Digraph and FullGraph classes.27 ///\brief FullGraph and FullDigraph classes. 28 28 29 29 namespace lemon { … … 149 149 /// \ingroup graphs 150 150 /// 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, 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, 166 164 /// but there are two differences. While this class conforms only 167 /// to the \ref concepts::Digraph "Digraph" concept, FullGraph168 /// c onforms to the \ref concepts::Graph "Graph" concept,169 /// moreover FullGraph does not contain a loopfor each170 /// node as this classdoes.165 /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph 166 /// class conforms to the \ref concepts::Graph "Graph" concept, 167 /// moreover \c FullGraph does not contain a loop arc for each 168 /// node as \c FullDigraph does. 171 169 /// 172 170 /// \sa FullGraph … … 176 174 public: 177 175 178 /// \brief Default constructor. 179 /// 180 /// Default constructor. The number of nodes and arcs will be zero. 176 /// \brief Constructor 181 177 FullDigraph() { construct(0); } 182 178 … … 189 185 /// \brief Resizes the digraph 190 186 /// 191 /// This function resizes the digraph. It fully destroysand192 /// rebuild s the structure, therefore the maps of the digraph will be187 /// Resizes the digraph. The function will fully destroy and 188 /// rebuild the digraph. This cause that the maps of the digraph will 193 189 /// reallocated automatically and the previous values will be lost. 194 190 void resize(int n) { … … 202 198 /// \brief Returns the node with the given index. 203 199 /// 204 /// Returns the node with the given index. Since this structure is205 /// completely static, the nodes can be indexed with integers from206 /// the range<tt>[0..nodeNum()-1]</tt>.200 /// Returns the node with the given index. Since it is a static 201 /// digraph its nodes can be indexed with integers from the range 202 /// <tt>[0..nodeNum()-1]</tt>. 207 203 /// \sa index() 208 204 Node operator()(int ix) const { return Parent::operator()(ix); } … … 210 206 /// \brief Returns the index of the given node. 211 207 /// 212 /// Returns the index of the given node. Since this structure is213 /// completely static, the nodes can be indexed with integers from214 /// the range<tt>[0..nodeNum()-1]</tt>.215 /// \sa operator() ()216 int index( Nodenode) const { return Parent::index(node); }208 /// Returns the index of the given node. Since it is a static 209 /// digraph its nodes can be indexed with integers from the range 210 /// <tt>[0..nodeNum()-1]</tt>. 211 /// \sa operator() 212 int index(const Node& node) const { return Parent::index(node); } 217 213 218 214 /// \brief Returns the arc connecting the given nodes. 219 215 /// 220 216 /// Returns the arc connecting the given nodes. 221 Arc arc( Node u, Nodev) const {217 Arc arc(const Node& u, const Node& v) const { 222 218 return Parent::arc(u, v); 223 219 } … … 525 521 /// \brief An undirected full graph class. 526 522 /// 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 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 540 534 /// conforms only to the \ref concepts::Digraph "Digraph" concept, 541 535 /// this class conforms to the \ref concepts::Graph "Graph" concept, 542 /// moreover this class does not contain a loopfor each543 /// node as FullDigraph does.536 /// moreover \c FullGraph does not contain a loop arc for each 537 /// node as \c FullDigraph does. 544 538 /// 545 539 /// \sa FullDigraph … … 549 543 public: 550 544 551 /// \brief Default constructor. 552 /// 553 /// Default constructor. The number of nodes and edges will be zero. 545 /// \brief Constructor 554 546 FullGraph() { construct(0); } 555 547 … … 562 554 /// \brief Resizes the graph 563 555 /// 564 /// This function resizes the graph. It fully destroysand565 /// rebuild s the structure, therefore the maps of the graph will be556 /// Resizes the graph. The function will fully destroy and 557 /// rebuild the graph. This cause that the maps of the graph will 566 558 /// reallocated automatically and the previous values will be lost. 567 559 void resize(int n) { … … 577 569 /// \brief Returns the node with the given index. 578 570 /// 579 /// Returns the node with the given index. Since this structure is580 /// completely static, the nodes can be indexed with integers from581 /// the range<tt>[0..nodeNum()-1]</tt>.571 /// Returns the node with the given index. Since it is a static 572 /// graph its nodes can be indexed with integers from the range 573 /// <tt>[0..nodeNum()-1]</tt>. 582 574 /// \sa index() 583 575 Node operator()(int ix) const { return Parent::operator()(ix); } … … 585 577 /// \brief Returns the index of the given node. 586 578 /// 587 /// Returns the index of the given node. Since this structure is588 /// completely static, the nodes can be indexed with integers from589 /// the range<tt>[0..nodeNum()-1]</tt>.590 /// \sa operator() ()591 int index( Nodenode) const { return Parent::index(node); }579 /// Returns the index of the given node. Since it is a static 580 /// graph its nodes can be indexed with integers from the range 581 /// <tt>[0..nodeNum()-1]</tt>. 582 /// \sa operator() 583 int index(const Node& node) const { return Parent::index(node); } 592 584 593 585 /// \brief Returns the arc connecting the given nodes. 594 586 /// 595 587 /// Returns the arc connecting the given nodes. 596 Arc arc( Node s, Nodet) const {588 Arc arc(const Node& s, const Node& t) const { 597 589 return Parent::arc(s, t); 598 590 } 599 591 600 /// \brief Returns the edge connect ingthe given nodes.601 /// 602 /// Returns the edge connect ingthe given nodes.603 Edge edge( Node u, Nodev) const {592 /// \brief Returns the edge connects the given nodes. 593 /// 594 /// Returns the edge connects the given nodes. 595 Edge edge(const Node& u, const Node& v) const { 604 596 return Parent::edge(u, v); 605 597 } -
lemon/grid_graph.h
r735 r617 471 471 /// \brief Grid graph class 472 472 /// 473 /// GridGraphimplements a special graph type. The nodes of the474 /// graph can be indexed by two integer values \c (i,j)where \c i is475 /// in the range <tt>[0..width()-1]</tt> and j is in the range476 /// <tt>[0..height()-1]</tt>.Two nodes are connected in the graph if477 /// the ind ices differ exactly on one position and the difference is478 /// also exactly one. The nodes of the graph can be obtained by position479 /// using the \c operator()() function and the indices of the nodes can480 /// be obtained using\c pos(), \c col() and \c row() members. The outgoing473 /// This class implements a special graph type. The nodes of the 474 /// graph can be indexed by two integer \c (i,j) value where \c i is 475 /// in the \c [0..width()-1] range and j is in the \c 476 /// [0..height()-1] range. Two nodes are connected in the graph if 477 /// the indexes differ exactly on one position and exactly one is 478 /// the difference. The nodes of the graph can be indexed by position 479 /// with the \c operator()() function. The positions of the nodes can be 480 /// get with \c pos(), \c col() and \c row() members. The outgoing 481 481 /// arcs can be retrieved with the \c right(), \c up(), \c left() 482 482 /// and \c down() functions, where the bottom-left corner is the 483 483 /// origin. 484 ///485 /// This class is completely static and it needs constant memory space.486 /// Thus you can neither add nor delete nodes or edges, however487 /// the structure can be resized using resize().488 484 /// 489 485 /// \image html grid_graph.png … … 501 497 ///\endcode 502 498 /// 503 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 504 /// Most of its member functions and nested classes are documented 505 /// only in the concept class. 499 /// This graph type fully conforms to the \ref concepts::Graph 500 /// "Graph concept". 506 501 class GridGraph : public ExtendedGridGraphBase { 507 502 typedef ExtendedGridGraphBase Parent; … … 509 504 public: 510 505 511 /// \brief Map to get the indices of the nodes as \ref dim2::Point 512 /// "dim2::Point<int>". 513 /// 514 /// Map to get the indices of the nodes as \ref dim2::Point 515 /// "dim2::Point<int>". 506 /// \brief Map to get the indices of the nodes as dim2::Point<int>. 507 /// 508 /// Map to get the indices of the nodes as dim2::Point<int>. 516 509 class IndexMap { 517 510 public: … … 522 515 523 516 /// \brief Constructor 517 /// 518 /// Constructor 524 519 IndexMap(const GridGraph& graph) : _graph(graph) {} 525 520 526 521 /// \brief The subscript operator 522 /// 523 /// The subscript operator. 527 524 Value operator[](Key key) const { 528 525 return _graph.pos(key); … … 544 541 545 542 /// \brief Constructor 543 /// 544 /// Constructor 546 545 ColMap(const GridGraph& graph) : _graph(graph) {} 547 546 548 547 /// \brief The subscript operator 548 /// 549 /// The subscript operator. 549 550 Value operator[](Key key) const { 550 551 return _graph.col(key); … … 566 567 567 568 /// \brief Constructor 569 /// 570 /// Constructor 568 571 RowMap(const GridGraph& graph) : _graph(graph) {} 569 572 570 573 /// \brief The subscript operator 574 /// 575 /// The subscript operator. 571 576 Value operator[](Key key) const { 572 577 return _graph.row(key); … … 579 584 /// \brief Constructor 580 585 /// 581 /// Construct a grid graph with thegiven size.586 /// Construct a grid graph with given size. 582 587 GridGraph(int width, int height) { construct(width, height); } 583 588 584 /// \brief Resizes the graph 585 /// 586 /// This function resizes the graph. It fully destroys and 587 /// rebuilds the structure, therefore the maps of the graph will be 588 /// reallocated automatically and the previous values will be lost. 589 /// \brief Resize the graph 590 /// 591 /// Resize the graph. The function will fully destroy and rebuild 592 /// the graph. This cause that the maps of the graph will 593 /// reallocated automatically and the previous values will be 594 /// lost. 589 595 void resize(int width, int height) { 590 596 Parent::notifier(Arc()).clear(); … … 604 610 } 605 611 606 /// \brief The column index of the node.612 /// \brief Gives back the column index of the node. 607 613 /// 608 614 /// Gives back the column index of the node. … … 611 617 } 612 618 613 /// \brief The row index of the node.619 /// \brief Gives back the row index of the node. 614 620 /// 615 621 /// Gives back the row index of the node. … … 618 624 } 619 625 620 /// \brief The position of the node.626 /// \brief Gives back the position of the node. 621 627 /// 622 628 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. … … 625 631 } 626 632 627 /// \brief The number of the columns.633 /// \brief Gives back the number of the columns. 628 634 /// 629 635 /// Gives back the number of the columns. … … 632 638 } 633 639 634 /// \brief The number of the rows.640 /// \brief Gives back the number of the rows. 635 641 /// 636 642 /// Gives back the number of the rows. … … 639 645 } 640 646 641 /// \brief The arc goes right from the node.647 /// \brief Gives back the arc goes right from the node. 642 648 /// 643 649 /// Gives back the arc goes right from the node. If there is not … … 647 653 } 648 654 649 /// \brief The arc goes left from the node.655 /// \brief Gives back the arc goes left from the node. 650 656 /// 651 657 /// Gives back the arc goes left from the node. If there is not … … 655 661 } 656 662 657 /// \brief The arc goes up from the node.663 /// \brief Gives back the arc goes up from the node. 658 664 /// 659 665 /// Gives back the arc goes up from the node. If there is not … … 663 669 } 664 670 665 /// \brief The arc goes down from the node.671 /// \brief Gives back the arc goes down from the node. 666 672 /// 667 673 /// Gives back the arc goes down from the node. If there is not -
lemon/hypercube_graph.h
r737 r617 283 283 /// \brief Hypercube graph class 284 284 /// 285 /// HypercubeGraph implements a special graph type. The nodes of the286 /// graph are indexed with integers havingat most \c dim binary digits.285 /// This class implements a special graph type. The nodes of the graph 286 /// are indiced with integers with 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, however291 /// 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 documented295 /// only in the concept class.296 289 /// 297 290 /// \note The type of the indices is chosen to \c int for efficiency 298 291 /// reasons. Thus the maximum dimension of this implementation is 26 299 292 /// (assuming that the size of \c int is 32 bit). 293 /// 294 /// This graph type fully conforms to the \ref concepts::Graph 295 /// "Graph concept". 300 296 class HypercubeGraph : public ExtendedHypercubeGraphBase { 301 297 typedef ExtendedHypercubeGraphBase Parent; … … 307 303 /// Constructs a hypercube graph with \c dim dimensions. 308 304 HypercubeGraph(int dim) { construct(dim); } 309 310 /// \brief Resizes the graph311 ///312 /// This function resizes the graph. It fully destroys and313 /// rebuilds the structure, therefore the maps of the graph will be314 /// 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 }324 305 325 306 /// \brief The number of dimensions. … … 340 321 /// 341 322 /// Gives back the dimension id of the given edge. 342 /// It is in the range <tt>[0..dim-1]</tt>.323 /// It is in the [0..dim-1] range. 343 324 int dimension(Edge edge) const { 344 325 return Parent::dimension(edge); … … 348 329 /// 349 330 /// Gives back the dimension id of the given arc. 350 /// It is in the range <tt>[0..dim-1]</tt>.331 /// It is in the [0..dim-1] range. 351 332 int dimension(Arc arc) const { 352 333 return Parent::dimension(arc); -
lemon/list_graph.h
r741 r739 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief ListDigraph andListGraph classes.24 ///\brief ListDigraph, ListGraph classes. 25 25 26 26 #include <lemon/core.h> … … 32 32 33 33 namespace lemon { 34 35 class ListDigraph;36 34 37 35 class ListDigraphBase { … … 65 63 class Node { 66 64 friend class ListDigraphBase; 67 friend class ListDigraph;68 65 protected: 69 66 … … 81 78 class Arc { 82 79 friend class ListDigraphBase; 83 friend class ListDigraph;84 80 protected: 85 81 … … 316 312 ///A general directed graph structure. 317 313 318 ///\ref ListDigraph is a versatile and fast directed graph319 ///implementation based on linked lists that are stored in314 ///\ref ListDigraph is a simple and fast <em>directed graph</em> 315 ///implementation based on static linked lists that are stored in 320 316 ///\c std::vector structures. 321 317 /// 322 /// This type fully conforms to the \ref concepts::Digraph "Digraph concept"323 ///a nd it also provides several useful additional functionalities.324 ///Most of itsmember functions and nested classes are documented318 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it 319 ///also provides several useful additional functionalities. 320 ///Most of the member functions and nested classes are documented 325 321 ///only in the concept class. 326 322 /// 327 323 ///\sa concepts::Digraph 328 ///\sa ListGraph 324 329 325 class ListDigraph : public ExtendedListDigraphBase { 330 326 typedef ExtendedListDigraphBase Parent; 331 327 332 328 private: 333 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 329 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 330 331 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 332 /// 334 333 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; 335 /// \brief Assignment of a digraph to another one is \e not allowed. 336 /// Use DigraphCopy instead. 334 ///\brief Assignment of ListDigraph to another one is \e not allowed. 335 ///Use copyDigraph() instead. 336 337 ///Assignment of ListDigraph to another one is \e not allowed. 338 ///Use copyDigraph() instead. 337 339 void operator=(const ListDigraph &) {} 338 340 public: … … 346 348 ///Add a new node to the digraph. 347 349 348 /// This function addsa new node to the digraph.350 ///Add a new node to the digraph. 349 351 ///\return The new node. 350 352 Node addNode() { return Parent::addNode(); } … … 352 354 ///Add a new arc to the digraph. 353 355 354 /// This function addsa new arc to the digraph with source node \c s356 ///Add a new arc to the digraph with source node \c s 355 357 ///and target node \c t. 356 358 ///\return The new arc. 357 Arc addArc( Node s, Nodet) {359 Arc addArc(const Node& s, const Node& t) { 358 360 return Parent::addArc(s, t); 359 361 } … … 361 363 ///\brief Erase a node from the digraph. 362 364 /// 363 ///This function erases the given node from the digraph. 364 void erase(Node n) { Parent::erase(n); } 365 ///Erase a node from the digraph. 366 /// 367 void erase(const Node& n) { Parent::erase(n); } 365 368 366 369 ///\brief Erase an arc from the digraph. 367 370 /// 368 ///This function erases the given arc from the digraph. 369 void erase(Arc a) { Parent::erase(a); } 371 ///Erase an arc from the digraph. 372 /// 373 void erase(const Arc& a) { Parent::erase(a); } 370 374 371 375 /// Node validity check 372 376 373 /// This function gives back \c true if the given node is valid, 374 /// i.e. it is a real node of the digraph. 375 /// 376 /// \warning A removed node could become valid again if new nodes are 377 /// added to the digraph. 377 /// This function gives back true if the given node is valid, 378 /// ie. it is a real node of the graph. 379 /// 380 /// \warning A Node pointing to a removed item 381 /// could become valid again later if new nodes are 382 /// added to the graph. 378 383 bool valid(Node n) const { return Parent::valid(n); } 379 384 380 385 /// Arc validity check 381 386 382 /// This function gives back \c true if the given arc is valid, 383 /// i.e. it is a real arc of the digraph. 384 /// 385 /// \warning A removed arc could become valid again if new arcs are 386 /// added to the digraph. 387 /// This function gives back true if the given arc is valid, 388 /// ie. it is a real arc of the graph. 389 /// 390 /// \warning An Arc pointing to a removed item 391 /// could become valid again later if new nodes are 392 /// added to the graph. 387 393 bool valid(Arc a) const { return Parent::valid(a); } 388 394 389 /// Change the target node of an arc 390 391 /// This function changes the target node of the given arc \c a to \c n. 392 /// 393 ///\note \c ArcIt and \c OutArcIt iterators referencing the changed 394 ///arc remain valid, however \c InArcIt iterators are invalidated. 395 /// Change the target of \c a to \c n 396 397 /// Change the target of \c a to \c n 398 /// 399 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing 400 ///the changed arc remain valid. However <tt>InArcIt</tt>s are 401 ///invalidated. 395 402 /// 396 403 ///\warning This functionality cannot be used together with the Snapshot … … 399 406 Parent::changeTarget(a,n); 400 407 } 401 /// Change the source node of an arc 402 403 /// This function changes the source node of the given arc \c a to \c n. 404 /// 405 ///\note \c InArcIt iterators referencing the changed arc remain 406 ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated. 408 /// Change the source of \c a to \c n 409 410 /// Change the source of \c a to \c n 411 /// 412 ///\note The <tt>InArcIt</tt>s referencing the changed arc remain 413 ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are 414 ///invalidated. 407 415 /// 408 416 ///\warning This functionality cannot be used together with the Snapshot … … 412 420 } 413 421 414 /// Reversethe direction of an arc.415 416 /// This function reverses the direction of the given arc.417 /// \note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing418 /// the changed arc areinvalidated.422 /// Invert the direction of an arc. 423 424 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain 425 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are 426 ///invalidated. 419 427 /// 420 428 ///\warning This functionality cannot be used together with the Snapshot 421 429 ///feature. 422 void reverseArc(Arc a) { 423 Node t=target(a); 424 changeTarget(a,source(a)); 425 changeSource(a,t); 426 } 430 void reverseArc(Arc e) { 431 Node t=target(e); 432 changeTarget(e,source(e)); 433 changeSource(e,t); 434 } 435 436 /// Reserve memory for nodes. 437 438 /// Using this function it is possible to avoid the superfluous memory 439 /// allocation: if you know that the digraph you want to build will 440 /// be very large (e.g. it will contain millions of nodes and/or arcs) 441 /// then it is worth reserving space for this amount before starting 442 /// to build the digraph. 443 /// \sa reserveArc 444 void reserveNode(int n) { nodes.reserve(n); }; 445 446 /// Reserve memory for arcs. 447 448 /// Using this function it is possible to avoid the superfluous memory 449 /// allocation: if you know that the digraph you want to build will 450 /// be very large (e.g. it will contain millions of nodes and/or arcs) 451 /// then it is worth reserving space for this amount before starting 452 /// to build the digraph. 453 /// \sa reserveNode 454 void reserveArc(int m) { arcs.reserve(m); }; 427 455 428 456 ///Contract two nodes. 429 457 430 ///This function contracts the given two nodes. 431 ///Node \c v is removed, but instead of deleting its 432 ///incident arcs, they are joined to node \c u. 433 ///If the last parameter \c r is \c true (this is the default value), 434 ///then the newly created loops are removed. 435 /// 436 ///\note The moved arcs are joined to node \c u using changeSource() 437 ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are 438 ///invalidated for the outgoing arcs of node \c v and \c InArcIt 439 ///iterators are invalidated for the incomming arcs of \c v. 440 ///Moreover all iterators referencing node \c v or the removed 441 ///loops are also invalidated. Other iterators remain valid. 458 ///This function contracts two nodes. 459 ///Node \p b will be removed but instead of deleting 460 ///incident arcs, they will be joined to \p a. 461 ///The last parameter \p r controls whether to remove loops. \c true 462 ///means that loops will be removed. 463 /// 464 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 465 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s 466 ///may be invalidated. 442 467 /// 443 468 ///\warning This functionality cannot be used together with the Snapshot 444 469 ///feature. 445 void contract(Node u, Node v, bool r = true)470 void contract(Node a, Node b, bool r = true) 446 471 { 447 for(OutArcIt e(*this, v);e!=INVALID;) {472 for(OutArcIt e(*this,b);e!=INVALID;) { 448 473 OutArcIt f=e; 449 474 ++f; 450 if(r && target(e)== u) erase(e);451 else changeSource(e, u);475 if(r && target(e)==a) erase(e); 476 else changeSource(e,a); 452 477 e=f; 453 478 } 454 for(InArcIt e(*this, v);e!=INVALID;) {479 for(InArcIt e(*this,b);e!=INVALID;) { 455 480 InArcIt f=e; 456 481 ++f; 457 if(r && source(e)== u) erase(e);458 else changeTarget(e, u);482 if(r && source(e)==a) erase(e); 483 else changeTarget(e,a); 459 484 e=f; 460 485 } 461 erase( v);486 erase(b); 462 487 } 463 488 464 489 ///Split a node. 465 490 466 ///This function splits the given node. First, a new node is added 467 ///to the digraph, then the source of each outgoing arc of node \c n 468 ///is moved to this new node. 469 ///If the second parameter \c connect is \c true (this is the default 470 ///value), then a new arc from node \c n to the newly created node 471 ///is also added. 491 ///This function splits a node. First a new node is added to the digraph, 492 ///then the source of each outgoing arc of \c n is moved to this new node. 493 ///If \c connect is \c true (this is the default value), then a new arc 494 ///from \c n to the newly created node is also added. 472 495 ///\return The newly created node. 473 496 /// 474 ///\note All iterators remain valid. 475 /// 476 ///\warning This functionality cannot be used together with the 497 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 498 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may 499 ///be invalidated. 500 /// 501 ///\warning This functionality cannot be used in conjunction with the 477 502 ///Snapshot feature. 478 503 Node split(Node n, bool connect = true) { 479 504 Node b = addNode(); 480 nodes[b.id].first_out=nodes[n.id].first_out; 481 nodes[n.id].first_out=-1; 482 for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) { 483 arcs[i].source=b.id; 505 for(OutArcIt e(*this,n);e!=INVALID;) { 506 OutArcIt f=e; 507 ++f; 508 changeSource(e,b); 509 e=f; 484 510 } 485 511 if (connect) addArc(n,b); … … 489 515 ///Split an arc. 490 516 491 ///This function splits the given arc. First, a new node \c v is492 /// added to the digraph, then the target node of the original arc493 /// is set to \c v. Finally, an arc from \c v to the original target494 /// is added.517 ///This function splits an arc. First a new node \c b is added to 518 ///the digraph, then the original arc is re-targeted to \c 519 ///b. Finally an arc from \c b to the original target is added. 520 /// 495 521 ///\return The newly created node. 496 ///497 ///\note \c InArcIt iterators referencing the original arc are498 ///invalidated. Other iterators remain valid.499 522 /// 500 523 ///\warning This functionality cannot be used together with the 501 524 ///Snapshot feature. 502 Node split(Arc a) { 503 Node v = addNode(); 504 addArc(v,target(a)); 505 changeTarget(a,v); 506 return v; 507 } 508 509 ///Clear the digraph. 510 511 ///This function erases all nodes and arcs from the digraph. 512 /// 513 void clear() { 514 Parent::clear(); 515 } 516 517 /// Reserve memory for nodes. 518 519 /// Using this function, it is possible to avoid superfluous memory 520 /// allocation: if you know that the digraph you want to build will 521 /// be large (e.g. it will contain millions of nodes and/or arcs), 522 /// then it is worth reserving space for this amount before starting 523 /// to build the digraph. 524 /// \sa reserveArc() 525 void reserveNode(int n) { nodes.reserve(n); }; 526 527 /// Reserve memory for arcs. 528 529 /// Using this function, it is possible to avoid superfluous memory 530 /// allocation: if you know that the digraph you want to build will 531 /// be large (e.g. it will contain millions of nodes and/or arcs), 532 /// then it is worth reserving space for this amount before starting 533 /// to build the digraph. 534 /// \sa reserveNode() 535 void reserveArc(int m) { arcs.reserve(m); }; 525 Node split(Arc e) { 526 Node b = addNode(); 527 addArc(b,target(e)); 528 changeTarget(e,b); 529 return b; 530 } 536 531 537 532 /// \brief Class to make a snapshot of the digraph and restore … … 543 538 /// restore() function. 544 539 /// 545 /// \note After a state is restored, you cannot restore a later state, 546 /// i.e. you cannot add the removed nodes and arcs again using 547 /// another Snapshot instance. 548 /// 549 /// \warning Node and arc deletions and other modifications (e.g. 550 /// reversing, contracting, splitting arcs or nodes) cannot be 540 /// \warning Arc and node deletions and other modifications (e.g. 541 /// contracting, splitting, reversing arcs or nodes) cannot be 551 542 /// restored. These events invalidate the snapshot. 552 /// However the arcs and nodes that were added to the digraph after553 /// making the current snapshot can be removed without invalidating it.554 543 class Snapshot { 555 544 protected: … … 721 710 /// 722 711 /// Default constructor. 723 /// You have to call save() to actually make a snapshot.712 /// To actually make a snapshot you must call save(). 724 713 Snapshot() 725 714 : digraph(0), node_observer_proxy(*this), … … 728 717 /// \brief Constructor that immediately makes a snapshot. 729 718 /// 730 /// This constructor immediately makes a snapshot of the given digraph. 731 Snapshot(ListDigraph &gr) 719 /// This constructor immediately makes a snapshot of the digraph. 720 /// \param _digraph The digraph we make a snapshot of. 721 Snapshot(ListDigraph &_digraph) 732 722 : node_observer_proxy(*this), 733 723 arc_observer_proxy(*this) { 734 attach( gr);724 attach(_digraph); 735 725 } 736 726 737 727 /// \brief Make a snapshot. 738 728 /// 739 /// This function makes a snapshot of the given digraph. 740 /// It can be called more than once. In case of a repeated 729 /// Make a snapshot of the digraph. 730 /// 731 /// This function can be called more than once. In case of a repeated 741 732 /// call, the previous snapshot gets lost. 742 void save(ListDigraph &gr) { 733 /// \param _digraph The digraph we make the snapshot of. 734 void save(ListDigraph &_digraph) { 743 735 if (attached()) { 744 736 detach(); 745 737 clear(); 746 738 } 747 attach( gr);739 attach(_digraph); 748 740 } 749 741 750 742 /// \brief Undo the changes until the last snapshot. 751 /// 752 /// This function undos the changes until the last snapshot 753 /// created by save() or Snapshot(ListDigraph&). 754 /// 755 /// \warning This method invalidates the snapshot, i.e. repeated 756 /// restoring is not supported unless you call save() again. 743 // 744 /// Undo the changes until the last snapshot created by save(). 757 745 void restore() { 758 746 detach(); … … 768 756 } 769 757 770 /// \brief Returns \c true ifthe snapshot is valid.758 /// \brief Gives back true when the snapshot is valid. 771 759 /// 772 /// This function returns \c true ifthe snapshot is valid.760 /// Gives back true when the snapshot is valid. 773 761 bool valid() const { 774 762 return attached(); … … 807 795 808 796 typedef ListGraphBase Graph; 797 798 class Node; 799 class Arc; 800 class Edge; 809 801 810 802 class Node { … … 856 848 bool operator<(const Arc& arc) const {return id < arc.id;} 857 849 }; 850 851 858 852 859 853 ListGraphBase() … … 1171 1165 ///A general undirected graph structure. 1172 1166 1173 ///\ref ListGraph is a versatile and fast undirected graph1174 ///implementation based on linked lists that are stored in1167 ///\ref ListGraph is a simple and fast <em>undirected graph</em> 1168 ///implementation based on static linked lists that are stored in 1175 1169 ///\c std::vector structures. 1176 1170 /// 1177 /// This type fully conforms to the \ref concepts::Graph "Graph concept"1178 ///a nd it also provides several useful additional functionalities.1179 ///Most of itsmember functions and nested classes are documented1171 ///It conforms to the \ref concepts::Graph "Graph concept" and it 1172 ///also provides several useful additional functionalities. 1173 ///Most of the member functions and nested classes are documented 1180 1174 ///only in the concept class. 1181 1175 /// 1182 1176 ///\sa concepts::Graph 1183 ///\sa ListDigraph 1177 1184 1178 class ListGraph : public ExtendedListGraphBase { 1185 1179 typedef ExtendedListGraphBase Parent; 1186 1180 1187 1181 private: 1188 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1182 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1183 1184 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1185 /// 1189 1186 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; 1190 /// \brief Assignment of a graph to another one is \e not allowed. 1191 /// Use GraphCopy instead. 1187 ///\brief Assignment of ListGraph to another one is \e not allowed. 1188 ///Use copyGraph() instead. 1189 1190 ///Assignment of ListGraph to another one is \e not allowed. 1191 ///Use copyGraph() instead. 1192 1192 void operator=(const ListGraph &) {} 1193 1193 public: … … 1202 1202 /// \brief Add a new node to the graph. 1203 1203 /// 1204 /// This function addsa new node to the graph.1204 /// Add a new node to the graph. 1205 1205 /// \return The new node. 1206 1206 Node addNode() { return Parent::addNode(); } … … 1208 1208 /// \brief Add a new edge to the graph. 1209 1209 /// 1210 /// This function adds a new edge to the graph between nodes 1211 /// \c u and \c v with inherent orientation from node \c u to 1212 /// node \c v. 1210 /// Add a new edge to the graph with source node \c s 1211 /// and target node \c t. 1213 1212 /// \return The new edge. 1214 Edge addEdge(Node u, Node v) { 1215 return Parent::addEdge(u, v); 1216 } 1217 1218 ///\brief Erase a node from the graph. 1219 /// 1220 /// This function erases the given node from the graph. 1221 void erase(Node n) { Parent::erase(n); } 1222 1223 ///\brief Erase an edge from the graph. 1224 /// 1225 /// This function erases the given edge from the graph. 1226 void erase(Edge e) { Parent::erase(e); } 1213 Edge addEdge(const Node& s, const Node& t) { 1214 return Parent::addEdge(s, t); 1215 } 1216 1217 /// \brief Erase a node from the graph. 1218 /// 1219 /// Erase a node from the graph. 1220 /// 1221 void erase(const Node& n) { Parent::erase(n); } 1222 1223 /// \brief Erase an edge from the graph. 1224 /// 1225 /// Erase an edge from the graph. 1226 /// 1227 void erase(const Edge& e) { Parent::erase(e); } 1227 1228 /// Node validity check 1228 1229 1229 /// This function gives back \c true if the given node is valid, 1230 /// i.e. it is a real node of the graph. 1231 /// 1232 /// \warning A removed node could become valid again if new nodes are 1230 /// This function gives back true if the given node is valid, 1231 /// ie. it is a real node of the graph. 1232 /// 1233 /// \warning A Node pointing to a removed item 1234 /// could become valid again later if new nodes are 1233 1235 /// added to the graph. 1234 1236 bool valid(Node n) const { return Parent::valid(n); } 1237 /// Arc validity check 1238 1239 /// This function gives back true if the given arc is valid, 1240 /// ie. it is a real arc of the graph. 1241 /// 1242 /// \warning An Arc pointing to a removed item 1243 /// could become valid again later if new edges are 1244 /// added to the graph. 1245 bool valid(Arc a) const { return Parent::valid(a); } 1235 1246 /// Edge validity check 1236 1247 1237 /// This function gives back \c true if the given edge is valid, 1238 /// i.e. it is a real edge of the graph. 1239 /// 1240 /// \warning A removed edge could become valid again if new edges are 1248 /// This function gives back true if the given edge is valid, 1249 /// ie. it is a real arc of the graph. 1250 /// 1251 /// \warning A Edge pointing to a removed item 1252 /// could become valid again later if new edges are 1241 1253 /// added to the graph. 1242 1254 bool valid(Edge e) const { return Parent::valid(e); } 1243 /// Arc validity check 1244 1245 /// This function gives back \c true if the given arc is valid, 1246 /// i.e. it is a real arc of the graph. 1247 /// 1248 /// \warning A removed arc could become valid again if new edges are 1249 /// added to the graph. 1250 bool valid(Arc a) const { return Parent::valid(a); } 1251 1252 /// \brief Change the first node of an edge. 1253 /// 1254 /// This function changes the first node of the given edge \c e to \c n. 1255 /// 1256 ///\note \c EdgeIt and \c ArcIt iterators referencing the 1257 ///changed edge are invalidated and all other iterators whose 1258 ///base node is the changed node are also invalidated. 1255 /// \brief Change the end \c u of \c e to \c n 1256 /// 1257 /// This function changes the end \c u of \c e to node \c n. 1258 /// 1259 ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the 1260 ///changed edge are invalidated and if the changed node is the 1261 ///base node of an iterator then this iterator is also 1262 ///invalidated. 1259 1263 /// 1260 1264 ///\warning This functionality cannot be used together with the … … 1263 1267 Parent::changeU(e,n); 1264 1268 } 1265 /// \brief Change the second node of an edge. 1266 /// 1267 /// This function changes the second node of the given edge \c e to \c n. 1268 /// 1269 ///\note \c EdgeIt iterators referencing the changed edge remain 1270 ///valid, however \c ArcIt iterators referencing the changed edge and 1271 ///all other iterators whose base node is the changed node are also 1272 ///invalidated. 1269 /// \brief Change the end \c v of \c e to \c n 1270 /// 1271 /// This function changes the end \c v of \c e to \c n. 1272 /// 1273 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain 1274 ///valid, however <tt>ArcIt</tt>s and if the changed node is the 1275 ///base node of an iterator then this iterator is invalidated. 1273 1276 /// 1274 1277 ///\warning This functionality cannot be used together with the … … 1277 1280 Parent::changeV(e,n); 1278 1281 } 1279 1280 1282 /// \brief Contract two nodes. 1281 1283 /// 1282 /// This function contracts the given two nodes. 1283 /// Node \c b is removed, but instead of deleting 1284 /// its incident edges, they are joined to node \c a. 1285 /// If the last parameter \c r is \c true (this is the default value), 1286 /// then the newly created loops are removed. 1287 /// 1288 /// \note The moved edges are joined to node \c a using changeU() 1289 /// or changeV(), thus all edge and arc iterators whose base node is 1290 /// \c b are invalidated. 1291 /// Moreover all iterators referencing node \c b or the removed 1292 /// loops are also invalidated. Other iterators remain valid. 1284 /// This function contracts two nodes. 1285 /// Node \p b will be removed but instead of deleting 1286 /// its neighboring arcs, they will be joined to \p a. 1287 /// The last parameter \p r controls whether to remove loops. \c true 1288 /// means that loops will be removed. 1289 /// 1290 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain 1291 /// valid. 1293 1292 /// 1294 1293 ///\warning This functionality cannot be used together with the … … 1309 1308 } 1310 1309 1311 ///Clear the graph.1312 1313 ///This function erases all nodes and arcs from the graph.1314 ///1315 void clear() {1316 Parent::clear();1317 }1318 1319 /// Reserve memory for nodes.1320 1321 /// Using this function, it is possible to avoid superfluous memory1322 /// allocation: if you know that the graph you want to build will1323 /// be large (e.g. it will contain millions of nodes and/or edges),1324 /// then it is worth reserving space for this amount before starting1325 /// to build the graph.1326 /// \sa reserveEdge()1327 void reserveNode(int n) { nodes.reserve(n); };1328 1329 /// Reserve memory for edges.1330 1331 /// Using this function, it is possible to avoid superfluous memory1332 /// allocation: if you know that the graph you want to build will1333 /// be large (e.g. it will contain millions of nodes and/or edges),1334 /// then it is worth reserving space for this amount before starting1335 /// to build the graph.1336 /// \sa reserveNode()1337 void reserveEdge(int m) { arcs.reserve(2 * m); };1338 1310 1339 1311 /// \brief Class to make a snapshot of the graph and restore … … 1345 1317 /// using the restore() function. 1346 1318 /// 1347 /// \note After a state is restored, you cannot restore a later state, 1348 /// i.e. you cannot add the removed nodes and edges again using 1349 /// another Snapshot instance. 1350 /// 1351 /// \warning Node and edge deletions and other modifications 1352 /// (e.g. changing the end-nodes of edges or contracting nodes) 1353 /// cannot be restored. These events invalidate the snapshot. 1354 /// However the edges and nodes that were added to the graph after 1355 /// making the current snapshot can be removed without invalidating it. 1319 /// \warning Edge and node deletions and other modifications 1320 /// (e.g. changing nodes of edges, contracting nodes) cannot be 1321 /// restored. These events invalidate the snapshot. 1356 1322 class Snapshot { 1357 1323 protected: … … 1523 1489 /// 1524 1490 /// Default constructor. 1525 /// You have to call save() to actually make a snapshot.1491 /// To actually make a snapshot you must call save(). 1526 1492 Snapshot() 1527 1493 : graph(0), node_observer_proxy(*this), … … 1530 1496 /// \brief Constructor that immediately makes a snapshot. 1531 1497 /// 1532 /// This constructor immediately makes a snapshot of the given graph. 1533 Snapshot(ListGraph &gr) 1498 /// This constructor immediately makes a snapshot of the graph. 1499 /// \param _graph The graph we make a snapshot of. 1500 Snapshot(ListGraph &_graph) 1534 1501 : node_observer_proxy(*this), 1535 1502 edge_observer_proxy(*this) { 1536 attach( gr);1503 attach(_graph); 1537 1504 } 1538 1505 1539 1506 /// \brief Make a snapshot. 1540 1507 /// 1541 /// This function makes a snapshot of the given graph. 1542 /// It can be called more than once. In case of a repeated 1508 /// Make a snapshot of the graph. 1509 /// 1510 /// This function can be called more than once. In case of a repeated 1543 1511 /// call, the previous snapshot gets lost. 1544 void save(ListGraph &gr) { 1512 /// \param _graph The graph we make the snapshot of. 1513 void save(ListGraph &_graph) { 1545 1514 if (attached()) { 1546 1515 detach(); 1547 1516 clear(); 1548 1517 } 1549 attach( gr);1518 attach(_graph); 1550 1519 } 1551 1520 1552 1521 /// \brief Undo the changes until the last snapshot. 1553 /// 1554 /// This function undos the changes until the last snapshot 1555 /// created by save() or Snapshot(ListGraph&). 1556 /// 1557 /// \warning This method invalidates the snapshot, i.e. repeated 1558 /// restoring is not supported unless you call save() again. 1522 // 1523 /// Undo the changes until the last snapshot created by save(). 1559 1524 void restore() { 1560 1525 detach(); … … 1570 1535 } 1571 1536 1572 /// \brief Returns \c true ifthe snapshot is valid.1537 /// \brief Gives back true when the snapshot is valid. 1573 1538 /// 1574 /// This function returns \c true ifthe snapshot is valid.1539 /// Gives back true when the snapshot is valid. 1575 1540 bool valid() const { 1576 1541 return attached(); -
lemon/smart_graph.h
r736 r617 33 33 34 34 class SmartDigraph; 35 35 ///Base of SmartDigraph 36 37 ///Base of SmartDigraph 38 /// 36 39 class SmartDigraphBase { 37 40 protected: … … 185 188 ///\brief A smart directed graph class. 186 189 /// 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). 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". 191 195 /// 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 196 ///\sa concepts::Digraph. 199 197 class SmartDigraph : public ExtendedSmartDigraphBase { 200 198 typedef ExtendedSmartDigraphBase Parent; 201 199 202 200 private: 203 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 201 202 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 203 204 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 205 /// 204 206 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; 205 /// \brief Assignment of a digraph to another one is \e not allowed. 206 /// Use DigraphCopy instead. 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. 207 212 void operator=(const SmartDigraph &) {} 208 213 … … 217 222 ///Add a new node to the digraph. 218 223 219 /// This function addsa new node to the digraph.220 /// \return The new node.224 /// Add a new node to the digraph. 225 /// \return The new node. 221 226 Node addNode() { return Parent::addNode(); } 222 227 223 228 ///Add a new arc to the digraph. 224 229 225 /// This function addsa new arc to the digraph with source node \c s230 ///Add a new arc to the digraph with source node \c s 226 231 ///and target node \c t. 227 232 ///\return The new arc. 228 Arc addArc( Node s, Nodet) {233 Arc addArc(const Node& s, const Node& t) { 229 234 return Parent::addArc(s, t); 230 235 } 231 236 237 /// \brief Using this it is possible to avoid the superfluous memory 238 /// allocation. 239 240 /// Using this it is possible to avoid the superfluous memory 241 /// allocation: if you know that the digraph you want to build will 242 /// 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 starting 244 /// to build the digraph. 245 /// \sa reserveArc 246 void reserveNode(int n) { nodes.reserve(n); }; 247 248 /// \brief Using this it is possible to avoid the superfluous memory 249 /// allocation. 250 251 /// Using this it is possible to avoid the superfluous memory 252 /// allocation: if you know that the digraph you want to build will 253 /// 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 starting 255 /// to build the digraph. 256 /// \sa reserveNode 257 void reserveArc(int m) { arcs.reserve(m); }; 258 232 259 /// \brief Node validity check 233 260 /// 234 /// This function gives back \ctrue if the given node is valid,235 /// i .e. it is a real node of the digraph.261 /// This function gives back true if the given node is valid, 262 /// ie. it is a real node of the graph. 236 263 /// 237 264 /// \warning A removed node (using Snapshot) could become valid again 238 /// if new nodes are added to the digraph.265 /// when new nodes are added to the graph. 239 266 bool valid(Node n) const { return Parent::valid(n); } 240 267 241 268 /// \brief Arc validity check 242 269 /// 243 /// This function gives back \ctrue if the given arc is valid,244 /// i .e. it is a real arc of the digraph.270 /// This function gives back true if the given arc is valid, 271 /// ie. it is a real arc of the graph. 245 272 /// 246 273 /// \warning A removed arc (using Snapshot) could become valid again 247 /// ifnew arcs are added to the graph.274 /// when new arcs are added to the graph. 248 275 bool valid(Arc a) const { return Parent::valid(a); } 249 276 277 ///Clear the digraph. 278 279 ///Erase all the nodes and arcs from the digraph. 280 /// 281 void clear() { 282 Parent::clear(); 283 } 284 250 285 ///Split a node. 251 286 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. 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. 258 291 ///\return The newly created node. 259 292 /// 260 ///\note All iterators remain valid. 261 /// 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. 262 297 ///\warning This functionality cannot be used together with the Snapshot 263 298 ///feature. … … 274 309 } 275 310 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 memory287 /// allocation: if you know that the digraph you want to build will288 /// be large (e.g. it will contain millions of nodes and/or arcs),289 /// then it is worth reserving space for this amount before starting290 /// 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 memory297 /// allocation: if you know that the digraph you want to build will298 /// be large (e.g. it will contain millions of nodes and/or arcs),299 /// then it is worth reserving space for this amount before starting300 /// to build the digraph.301 /// \sa reserveNode()302 void reserveArc(int m) { arcs.reserve(m); };303 304 311 public: 305 312 … … 326 333 public: 327 334 328 ///Class to make a snapshot of the digraph and to rest oreit later.329 330 ///Class to make a snapshot of the digraph and to rest oreit later.335 ///Class to make a snapshot of the digraph and to restrore to it later. 336 337 ///Class to make a snapshot of the digraph and to restrore to it later. 331 338 /// 332 339 ///The newly added nodes and arcs can be removed using the 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. 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. 345 349 class Snapshot 346 350 { … … 354 358 355 359 ///Default constructor. 356 ///You have to call save() to actually make a snapshot. 360 ///To actually make a snapshot you must call save(). 361 /// 357 362 Snapshot() : _graph(0) {} 358 363 ///Constructor that immediately makes a snapshot 359 364 360 ///This constructor immediately makes a snapshot of the givendigraph.361 /// 362 Snapshot(SmartDigraph &gr ) : _graph(&gr) {365 ///This constructor immediately makes a snapshot of the digraph. 366 ///\param graph The digraph we make a snapshot of. 367 Snapshot(SmartDigraph &graph) : _graph(&graph) { 363 368 node_num=_graph->nodes.size(); 364 369 arc_num=_graph->arcs.size(); … … 367 372 ///Make a snapshot. 368 373 369 ///This function makes a snapshot of the given digraph. 370 ///It can be called more than once. In case of a repeated 374 ///Make a snapshot of the digraph. 375 /// 376 ///This function can be called more than once. In case of a repeated 371 377 ///call, the previous snapshot gets lost. 372 void save(SmartDigraph &gr) { 373 _graph=&gr; 378 ///\param graph The digraph we make the snapshot of. 379 void save(SmartDigraph &graph) 380 { 381 _graph=&graph; 374 382 node_num=_graph->nodes.size(); 375 383 arc_num=_graph->arcs.size(); … … 378 386 ///Undo the changes until a snapshot. 379 387 380 ///This function undos the changes until the last snapshot 381 ///created by save() or Snapshot(SmartDigraph&). 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(). 382 393 void restore() 383 394 { … … 611 622 /// \brief A smart undirected graph class. 612 623 /// 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). 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". 617 629 /// 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 630 /// \sa concepts::Graph. 625 631 class SmartGraph : public ExtendedSmartGraphBase { 626 632 typedef ExtendedSmartGraphBase Parent; 627 633 628 634 private: 629 /// Graphs are \e not copy constructible. Use GraphCopy instead. 635 636 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 637 638 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 639 /// 630 640 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; 631 /// \brief Assignment of a graph to another one is \e not allowed. 632 /// Use GraphCopy instead. 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. 633 647 void operator=(const SmartGraph &) {} 634 648 … … 641 655 SmartGraph() {} 642 656 643 /// \briefAdd a new node to the graph.644 /// 645 /// This function addsa new node to the graph.657 ///Add a new node to the graph. 658 659 /// Add a new node to the graph. 646 660 /// \return The new node. 647 661 Node addNode() { return Parent::addNode(); } 648 662 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); 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); 657 670 } 658 671 659 672 /// \brief Node validity check 660 673 /// 661 /// This function gives back \ctrue if the given node is valid,662 /// i .e. it is a real node of the graph.674 /// This function gives back true if the given node is valid, 675 /// ie. it is a real node of the graph. 663 676 /// 664 677 /// \warning A removed node (using Snapshot) could become valid again 665 /// ifnew nodes are added to the graph.678 /// when new nodes are added to the graph. 666 679 bool valid(Node n) const { return Parent::valid(n); } 667 680 681 /// \brief Arc validity check 682 /// 683 /// This function gives back true if the given arc is valid, 684 /// ie. it is a real arc of the graph. 685 /// 686 /// \warning A removed arc (using Snapshot) could become valid again 687 /// when new edges are added to the graph. 688 bool valid(Arc a) const { return Parent::valid(a); } 689 668 690 /// \brief Edge validity check 669 691 /// 670 /// This function gives back \ctrue if the given edge is valid,671 /// i .e. it is a real edge of the graph.692 /// This function gives back true if the given edge is valid, 693 /// ie. it is a real edge of the graph. 672 694 /// 673 695 /// \warning A removed edge (using Snapshot) could become valid again 674 /// ifnew edges are added to the graph.696 /// when new edges are added to the graph. 675 697 bool valid(Edge e) const { return Parent::valid(e); } 676 698 677 /// \brief Arc validity check678 ///679 /// This function gives back \c true if the given arc is valid,680 /// i.e. it is a real arc of the graph.681 ///682 /// \warning A removed arc (using Snapshot) could become valid again683 /// if new edges are added to the graph.684 bool valid(Arc a) const { return Parent::valid(a); }685 686 699 ///Clear the graph. 687 700 688 /// This function erases all nodes and arcs from the graph.701 ///Erase all the nodes and edges from the graph. 689 702 /// 690 703 void clear() { 691 704 Parent::clear(); 692 705 } 693 694 /// Reserve memory for nodes.695 696 /// Using this function, it is possible to avoid superfluous memory697 /// allocation: if you know that the graph you want to build will698 /// be large (e.g. it will contain millions of nodes and/or edges),699 /// then it is worth reserving space for this amount before starting700 /// 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 memory707 /// allocation: if you know that the graph you want to build will708 /// be large (e.g. it will contain millions of nodes and/or edges),709 /// then it is worth reserving space for this amount before starting710 /// to build the graph.711 /// \sa reserveNode()712 void reserveEdge(int m) { arcs.reserve(2 * m); };713 706 714 707 public: … … 750 743 public: 751 744 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. 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. 768 760 class Snapshot 769 761 { … … 777 769 778 770 ///Default constructor. 779 ///You have to call save() to actually make a snapshot. 771 ///To actually make a snapshot you must call save(). 772 /// 780 773 Snapshot() : _graph(0) {} 781 774 ///Constructor that immediately makes a snapshot 782 775 783 /// This constructor immediately makes a snapshot of the given graph. 776 ///This constructor immediately makes a snapshot of the digraph. 777 ///\param graph The digraph we make a snapshot of. 778 Snapshot(SmartGraph &graph) { 779 graph.saveSnapshot(*this); 780 } 781 782 ///Make a snapshot. 783 784 ///Make a snapshot of the graph. 784 785 /// 785 Snapshot(SmartGraph &gr) { 786 gr.saveSnapshot(*this); 787 } 788 789 ///Make a snapshot. 790 791 ///This function makes a snapshot of the given graph. 792 ///It can be called more than once. In case of a repeated 786 ///This function can be called more than once. In case of a repeated 793 787 ///call, the previous snapshot gets lost. 794 void save(SmartGraph &gr) 788 ///\param graph The digraph we make the snapshot of. 789 void save(SmartGraph &graph) 795 790 { 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&). 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(). 803 801 void restore() 804 802 { -
test/digraph_test.cc
r740 r440 36 36 checkGraphArcList(G, 0); 37 37 38 G.reserveNode(3);39 G.reserveArc(4);40 41 38 Node 42 39 n1 = G.addNode(), … … 287 284 288 285 snapshot.restore(); 289 snapshot.save(G);290 291 checkGraphNodeList(G, 4);292 checkGraphArcList(G, 4);293 294 G.addArc(G.addNode(), G.addNode());295 296 snapshot.restore();297 286 298 287 checkGraphNodeList(G, 4); … … 387 376 typedef FullDigraph Digraph; 388 377 DIGRAPH_TYPEDEFS(Digraph); 389 390 378 Digraph G(num); 391 check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");392 393 G.resize(num);394 check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");395 379 396 380 checkGraphNodeList(G, num); -
test/graph_test.cc
r740 r440 39 39 checkGraphArcList(G, 0); 40 40 41 G.reserveNode(3);42 G.reserveEdge(3);43 44 41 Node 45 42 n1 = G.addNode(), … … 260 257 261 258 snapshot.restore(); 262 snapshot.save(G);263 259 264 260 checkGraphNodeList(G, 4); 265 261 checkGraphEdgeList(G, 3); 266 262 checkGraphArcList(G, 6); 267 268 G.addEdge(G.addNode(), G.addNode());269 270 snapshot.restore();271 272 checkGraphNodeList(G, 4);273 checkGraphEdgeList(G, 3);274 checkGraphArcList(G, 6);275 263 } 276 264 … … 280 268 281 269 Graph G(num); 282 check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,283 "Wrong size");284 285 G.resize(num);286 check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,287 "Wrong size");288 289 270 checkGraphNodeList(G, num); 290 271 checkGraphEdgeList(G, num * (num - 1) / 2); … … 431 412 check(G.height() == height, "Wrong row number"); 432 413 433 G.resize(width, height);434 check(G.width() == width, "Wrong column number");435 check(G.height() == height, "Wrong row number");436 437 414 for (int i = 0; i < width; ++i) { 438 415 for (int j = 0; j < height; ++j) { … … 510 487 511 488 HypercubeGraph G(dim); 512 check(G.dimension() == dim, "Wrong dimension");513 514 G.resize(dim);515 check(G.dimension() == dim, "Wrong dimension");516 517 489 checkGraphNodeList(G, 1 << dim); 518 490 checkGraphEdgeList(G, dim * (1 << (dim-1)));
Note: See TracChangeset
for help on using the changeset viewer.
