Changes in / [733:abf31e4af617:742:8e68671af789] in lemon-main
- Files:
-
- 11 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r715 r742 680 680 \brief Skeleton and concept checking classes for graph structures 681 681 682 This group contains the skeletons and concept checking classes of LEMON's683 graph structures and helper classes used to implement these.682 This group contains the skeletons and concept checking classes of 683 graph structures. 684 684 */ 685 685 -
lemon/concepts/digraph.h
r580 r734 36 36 /// \brief Class describing the concept of directed graphs. 37 37 /// 38 /// This class describes the \ref concept "concept" of the39 /// immutable directed digraphs.38 /// This class describes the common interface of all directed 39 /// graphs (digraphs). 40 40 /// 41 /// Note that actual digraph implementation like @ref ListDigraph or 42 /// @ref SmartDigraph may have several additional functionality. 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. 43 47 /// 44 /// \sa concept48 /// \sa Graph 45 49 class Digraph { 46 50 private: 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 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. 58 55 void operator=(const Digraph &) {} 56 59 57 public: 60 ///\e 61 62 /// Defalult constructor. 63 64 /// Defalult constructor. 65 /// 58 /// Default constructor. 66 59 Digraph() { } 67 /// Class for identifying a node of the digraph 60 61 /// The node type of the digraph 68 62 69 63 /// This class identifies a node of the digraph. It also serves 70 64 /// as a base class of the node iterators, 71 /// thus they willconvert to this type.65 /// thus they convert to this type. 72 66 class Node { 73 67 public: 74 68 /// Default constructor 75 69 76 /// @warning The default constructor sets the iterator77 /// to an undefined value.70 /// Default constructor. 71 /// \warning It sets the object to an undefined value. 78 72 Node() { } 79 73 /// Copy constructor. … … 83 77 Node(const Node&) { } 84 78 85 /// Invalid constructor \& conversion.86 87 /// This constructor initializes the iteratorto be invalid.79 /// %Invalid constructor \& conversion. 80 81 /// Initializes the object to be invalid. 88 82 /// \sa Invalid for more details. 89 83 Node(Invalid) { } 90 84 /// Equality operator 91 85 86 /// Equality operator. 87 /// 92 88 /// Two iterators are equal if and only if they point to the 93 /// same object or both are invalid.89 /// same object or both are \c INVALID. 94 90 bool operator==(Node) const { return true; } 95 91 96 92 /// Inequality operator 97 93 98 /// \sa operator==(Node n) 99 /// 94 /// Inequality operator. 100 95 bool operator!=(Node) const { return true; } 101 96 102 97 /// Artificial ordering operator. 103 98 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. 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. 110 104 bool operator<(Node) const { return false; } 111 112 }; 113 114 /// This iterator goes through each node. 115 116 /// This iterator goes through each node. 105 }; 106 107 /// Iterator class for the nodes. 108 109 /// This iterator goes through each node of the digraph. 117 110 /// Its usage is quite simple, for example you can count the number 118 /// of nodes in digraph \c g of type \cDigraph like this:111 /// of nodes in a digraph \c g of type \c %Digraph like this: 119 112 ///\code 120 113 /// int count=0; … … 125 118 /// Default constructor 126 119 127 /// @warning The default constructor sets the iterator128 /// to an undefined value.120 /// Default constructor. 121 /// \warning It sets the iterator to an undefined value. 129 122 NodeIt() { } 130 123 /// Copy constructor. … … 133 126 /// 134 127 NodeIt(const NodeIt& n) : Node(n) { } 135 /// Invalid constructor \& conversion.136 137 /// Initialize the iterator to be invalid.128 /// %Invalid constructor \& conversion. 129 130 /// Initializes the iterator to be invalid. 138 131 /// \sa Invalid for more details. 139 132 NodeIt(Invalid) { } 140 133 /// Sets the iterator to the first node. 141 134 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. 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 /// 151 142 NodeIt(const Digraph&, const Node&) { } 152 143 /// Next node. … … 158 149 159 150 160 /// Class for identifying an arcof the digraph151 /// The arc type of the digraph 161 152 162 153 /// This class identifies an arc of the digraph. It also serves … … 167 158 /// Default constructor 168 159 169 /// @warning The default constructor sets the iterator170 /// to an undefined value.160 /// Default constructor. 161 /// \warning It sets the object to an undefined value. 171 162 Arc() { } 172 163 /// Copy constructor. … … 175 166 /// 176 167 Arc(const Arc&) { } 177 /// Initialize the iterator to be invalid.178 179 /// Initialize the iteratorto be invalid.180 /// 168 /// %Invalid constructor \& conversion. 169 170 /// Initializes the object to be invalid. 171 /// \sa Invalid for more details. 181 172 Arc(Invalid) { } 182 173 /// Equality operator 183 174 175 /// Equality operator. 176 /// 184 177 /// Two iterators are equal if and only if they point to the 185 /// same object or both are invalid.178 /// same object or both are \c INVALID. 186 179 bool operator==(Arc) const { return true; } 187 180 /// Inequality operator 188 181 189 /// \sa operator==(Arc n) 190 /// 182 /// Inequality operator. 191 183 bool operator!=(Arc) const { return true; } 192 184 193 185 /// Artificial ordering operator. 194 186 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. 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. 201 192 bool operator<(Arc) const { return false; } 202 193 }; 203 194 204 /// This iterator goes troughthe outgoing arcs of a node.195 /// Iterator class for the outgoing arcs of a node. 205 196 206 197 /// This iterator goes trough the \e outgoing arcs of a certain node … … 208 199 /// Its usage is quite simple, for example you can count the number 209 200 /// of outgoing arcs of a node \c n 210 /// in digraph \c g of type \cDigraph as follows.201 /// in a digraph \c g of type \c %Digraph as follows. 211 202 ///\code 212 203 /// int count=0; 213 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;204 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 214 205 ///\endcode 215 216 206 class OutArcIt : public Arc { 217 207 public: 218 208 /// Default constructor 219 209 220 /// @warning The default constructor sets the iterator221 /// to an undefined value.210 /// Default constructor. 211 /// \warning It sets the iterator to an undefined value. 222 212 OutArcIt() { } 223 213 /// Copy constructor. … … 226 216 /// 227 217 OutArcIt(const OutArcIt& e) : Arc(e) { } 228 /// Initialize the iterator to be invalid.229 230 /// Initialize the iterator to be invalid.231 /// 218 /// %Invalid constructor \& conversion. 219 220 /// Initializes the iterator to be invalid. 221 /// \sa Invalid for more details. 232 222 OutArcIt(Invalid) { } 233 /// This constructor sets the iterator to the first outgoing arc.234 235 /// This constructor sets the iterator to the first outgoing arc of236 /// the node.223 /// Sets the iterator to the first outgoing arc. 224 225 /// Sets the iterator to the first outgoing arc of the given node. 226 /// 237 227 OutArcIt(const Digraph&, const Node&) { } 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. 228 /// Sets the iterator to the given arc. 229 230 /// Sets the iterator to the given arc of the given digraph. 231 /// 243 232 OutArcIt(const Digraph&, const Arc&) { } 244 /// Next outgoing arc233 /// Next outgoing arc 245 234 246 235 /// Assign the iterator to the next … … 249 238 }; 250 239 251 /// This iterator goes troughthe incoming arcs of a node.240 /// Iterator class for the incoming arcs of a node. 252 241 253 242 /// This iterator goes trough the \e incoming arcs of a certain node 254 243 /// of a digraph. 255 244 /// Its usage is quite simple, for example you can count the number 256 /// of outgoing arcs of a node \c n257 /// in digraph \c g of type \cDigraph as follows.245 /// of incoming arcs of a node \c n 246 /// in a digraph \c g of type \c %Digraph as follows. 258 247 ///\code 259 248 /// int count=0; 260 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;249 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 261 250 ///\endcode 262 263 251 class InArcIt : public Arc { 264 252 public: 265 253 /// Default constructor 266 254 267 /// @warning The default constructor sets the iterator268 /// to an undefined value.255 /// Default constructor. 256 /// \warning It sets the iterator to an undefined value. 269 257 InArcIt() { } 270 258 /// Copy constructor. … … 273 261 /// 274 262 InArcIt(const InArcIt& e) : Arc(e) { } 275 /// Initialize the iterator to be invalid.276 277 /// Initialize the iterator to be invalid.278 /// 263 /// %Invalid constructor \& conversion. 264 265 /// Initializes the iterator to be invalid. 266 /// \sa Invalid for more details. 279 267 InArcIt(Invalid) { } 280 /// This constructor sets the iterator tofirst incoming arc.281 282 /// This constructor set the iterator to the first incoming arc of283 /// the node.268 /// Sets the iterator to the first incoming arc. 269 270 /// Sets the iterator to the first incoming arc of the given node. 271 /// 284 272 InArcIt(const Digraph&, const Node&) { } 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. 273 /// Sets the iterator to the given arc. 274 275 /// Sets the iterator to the given arc of the given digraph. 276 /// 290 277 InArcIt(const Digraph&, const Arc&) { } 291 278 /// Next incoming arc 292 279 293 /// Assign the iterator to the next inarc of the corresponding node.294 /// 280 /// Assign the iterator to the next 281 /// incoming arc of the corresponding node. 295 282 InArcIt& operator++() { return *this; } 296 283 }; 297 /// This iterator goes through each arc. 298 299 /// This iterator goes through each arc of a digraph. 284 285 /// Iterator class for the arcs. 286 287 /// This iterator goes through each arc of the digraph. 300 288 /// Its usage is quite simple, for example you can count the number 301 /// of arcs in a digraph \c g of type \c Digraph as follows:289 /// of arcs in a digraph \c g of type \c %Digraph as follows: 302 290 ///\code 303 291 /// int count=0; 304 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;292 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count; 305 293 ///\endcode 306 294 class ArcIt : public Arc { … … 308 296 /// Default constructor 309 297 310 /// @warning The default constructor sets the iterator311 /// to an undefined value.298 /// Default constructor. 299 /// \warning It sets the iterator to an undefined value. 312 300 ArcIt() { } 313 301 /// Copy constructor. … … 316 304 /// 317 305 ArcIt(const ArcIt& e) : Arc(e) { } 318 /// Initialize the iterator to be invalid.319 320 /// Initialize the iterator to be invalid.321 /// 306 /// %Invalid constructor \& conversion. 307 308 /// Initializes the iterator to be invalid. 309 /// \sa Invalid for more details. 322 310 ArcIt(Invalid) { } 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. 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 /// 333 320 ArcIt(const Digraph&, const Arc&) { } 334 /// Next arc321 /// Next arc 335 322 336 323 /// Assign the iterator to the next arc. 324 /// 337 325 ArcIt& operator++() { return *this; } 338 326 }; 339 ///Gives back the target node of an arc. 340 341 ///Gives back the target node of an arc. 342 /// 327 328 /// \brief The source node of the arc. 329 /// 330 /// Returns the source node of the given arc. 331 Node source(Arc) const { return INVALID; } 332 333 /// \brief The target node of the arc. 334 /// 335 /// Returns the target node of the given arc. 343 336 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 /// 348 Node source(Arc) const { return INVALID; } 349 350 /// \brief Returns the ID of the node. 337 338 /// \brief The ID of the node. 339 /// 340 /// Returns the ID of the given node. 351 341 int id(Node) const { return -1; } 352 342 353 /// \brief Returns the ID of the arc. 343 /// \brief The ID of the arc. 344 /// 345 /// Returns the ID of the given arc. 354 346 int id(Arc) const { return -1; } 355 347 356 /// \brief Returns the node with the given ID. 357 /// 358 /// \pre The argument should be a valid node ID in the graph. 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. 359 352 Node nodeFromId(int) const { return INVALID; } 360 353 361 /// \brief Returns the arc with the given ID. 362 /// 363 /// \pre The argument should be a valid arc ID in the graph. 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. 364 358 Arc arcFromId(int) const { return INVALID; } 365 359 366 /// \brief Returns an upper bound on the node IDs. 360 /// \brief An upper bound on the node IDs. 361 /// 362 /// Returns an upper bound on the node IDs. 367 363 int maxNodeId() const { return -1; } 368 364 369 /// \brief Returns an upper bound on the arc IDs. 365 /// \brief An upper bound on the arc IDs. 366 /// 367 /// Returns an upper bound on the arc IDs. 370 368 int maxArcId() const { return -1; } 371 369 … … 393 391 int maxId(Arc) const { return -1; } 394 392 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 395 398 /// \brief The base node of the iterator. 396 399 /// 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; }400 /// Returns the base node of the given outgoing arc iterator 401 /// (i.e. the source node of the corresponding arc). 402 Node baseNode(OutArcIt) const { return INVALID; } 400 403 401 404 /// \brief The running node of the iterator. 402 405 /// 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; }406 /// Returns the running node of the given outgoing arc iterator 407 /// (i.e. the target node of the corresponding arc). 408 Node runningNode(OutArcIt) const { return INVALID; } 406 409 407 410 /// \brief The base node of the iterator. 408 411 /// 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; }412 /// Returns the base node of the given incomming arc iterator 413 /// (i.e. the target node of the corresponding arc). 414 Node baseNode(InArcIt) const { return INVALID; } 412 415 413 416 /// \brief The running node of the iterator. 414 417 /// 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. 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. 427 426 template<class T> 428 427 class NodeMap : public ReferenceMap<Node, T, T&, const T&> { 429 428 public: 430 429 431 /// \e432 NodeMap(const Digraph&) { }433 /// \e430 /// Constructor 431 explicit NodeMap(const Digraph&) { } 432 /// Constructor with given initial value 434 433 NodeMap(const Digraph&, T) { } 435 434 … … 446 445 }; 447 446 448 /// \brief Reference map of the arcs to type \c T. 449 /// 450 /// Reference map of the arcs to type \c T. 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. 451 451 template<class T> 452 452 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> { 453 453 public: 454 454 455 /// \e456 ArcMap(const Digraph&) { }457 /// \e455 /// Constructor 456 explicit ArcMap(const Digraph&) { } 457 /// Constructor with given initial value 458 458 ArcMap(const Digraph&, T) { } 459 459 460 private: 460 461 ///Copy constructor -
lemon/concepts/graph.h
r657 r734 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> 27 29 #include <lemon/core.h> 28 30 … … 32 34 /// \ingroup graph_concepts 33 35 /// 34 /// \brief Class describing the concept of Undirected Graphs.36 /// \brief Class describing the concept of undirected graphs. 35 37 /// 36 /// This class describes the common interface of all Undirected37 /// Graphs.38 /// This class describes the common interface of all undirected 39 /// graphs. 38 40 /// 39 /// As all concept describing classes it provides onlyinterface40 /// without any sensible implementation. So any algorithm for41 /// undirected graph should compile with this class, but it will not41 /// Like all concept classes, it only provides an interface 42 /// without any sensible implementation. So any general algorithm for 43 /// undirected graphs should compile with this class, but it will not 42 44 /// run properly, of course. 45 /// An actual graph implementation like \ref ListGraph or 46 /// \ref SmartGraph may have additional functionality. 43 47 /// 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. 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. 53 61 /// 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. 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. 61 68 /// 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. 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 68 73 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 69 81 public: 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 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 75 90 /// specializations for undirected graphs. 76 91 typedef True UndirectedTag; 77 92 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. 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. 85 98 class Node { 86 99 public: 87 100 /// Default constructor 88 101 89 /// @warning The default constructor sets the iterator90 /// to an undefined value.102 /// Default constructor. 103 /// \warning It sets the object to an undefined value. 91 104 Node() { } 92 105 /// Copy constructor. … … 96 109 Node(const Node&) { } 97 110 98 /// Invalid constructor \& conversion.99 100 /// This constructor initializes the iteratorto be invalid.111 /// %Invalid constructor \& conversion. 112 113 /// Initializes the object to be invalid. 101 114 /// \sa Invalid for more details. 102 115 Node(Invalid) { } 103 116 /// Equality operator 104 117 118 /// Equality operator. 119 /// 105 120 /// Two iterators are equal if and only if they point to the 106 /// same object or both are invalid.121 /// same object or both are \c INVALID. 107 122 bool operator==(Node) const { return true; } 108 123 109 124 /// Inequality operator 110 125 111 /// \sa operator==(Node n) 112 /// 126 /// Inequality operator. 113 127 bool operator!=(Node) const { return true; } 114 128 115 129 /// Artificial ordering operator. 116 130 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 131 /// Artificial ordering operator. 132 /// 133 /// \note This operator only has to define some strict ordering of 121 134 /// the items; this order has nothing to do with the iteration 122 135 /// ordering of the items. … … 125 138 }; 126 139 127 /// This iterator goes through each node.128 129 /// This iterator goes through each node .140 /// Iterator class for the nodes. 141 142 /// This iterator goes through each node of the graph. 130 143 /// Its usage is quite simple, for example you can count the number 131 /// of nodes in graph \c g of type \cGraph like this:144 /// of nodes in a graph \c g of type \c %Graph like this: 132 145 ///\code 133 146 /// int count=0; … … 138 151 /// Default constructor 139 152 140 /// @warning The default constructor sets the iterator141 /// to an undefined value.153 /// Default constructor. 154 /// \warning It sets the iterator to an undefined value. 142 155 NodeIt() { } 143 156 /// Copy constructor. … … 146 159 /// 147 160 NodeIt(const NodeIt& n) : Node(n) { } 148 /// Invalid constructor \& conversion.149 150 /// Initialize the iterator to be invalid.161 /// %Invalid constructor \& conversion. 162 163 /// Initializes the iterator to be invalid. 151 164 /// \sa Invalid for more details. 152 165 NodeIt(Invalid) { } 153 166 /// Sets the iterator to the first node. 154 167 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. 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 /// 164 175 NodeIt(const Graph&, const Node&) { } 165 176 /// Next node. … … 171 182 172 183 173 /// The base type of the edge iterators. 174 175 /// The base type of the edge iterators. 176 /// 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. 177 189 class Edge { 178 190 public: 179 191 /// Default constructor 180 192 181 /// @warning The default constructor sets the iterator182 /// to an undefined value.193 /// Default constructor. 194 /// \warning It sets the object to an undefined value. 183 195 Edge() { } 184 196 /// Copy constructor. … … 187 199 /// 188 200 Edge(const Edge&) { } 189 /// Initialize the iterator to be invalid.190 191 /// Initialize the iteratorto be invalid.192 /// 201 /// %Invalid constructor \& conversion. 202 203 /// Initializes the object to be invalid. 204 /// \sa Invalid for more details. 193 205 Edge(Invalid) { } 194 206 /// Equality operator 195 207 208 /// Equality operator. 209 /// 196 210 /// Two iterators are equal if and only if they point to the 197 /// same object or both are invalid.211 /// same object or both are \c INVALID. 198 212 bool operator==(Edge) const { return true; } 199 213 /// Inequality operator 200 214 201 /// \sa operator==(Edge n) 202 /// 215 /// Inequality operator. 203 216 bool operator!=(Edge) const { return true; } 204 217 205 218 /// Artificial ordering operator. 206 219 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. 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. 213 225 bool operator<(Edge) const { return false; } 214 226 }; 215 227 216 /// This iterator goes through each edge.217 218 /// This iterator goes through each edge of agraph.228 /// Iterator class for the edges. 229 230 /// This iterator goes through each edge of the graph. 219 231 /// Its usage is quite simple, for example you can count the number 220 /// of edges in a graph \c g of type \c Graph as follows:232 /// of edges in a graph \c g of type \c %Graph as follows: 221 233 ///\code 222 234 /// int count=0; … … 227 239 /// Default constructor 228 240 229 /// @warning The default constructor sets the iterator230 /// to an undefined value.241 /// Default constructor. 242 /// \warning It sets the iterator to an undefined value. 231 243 EdgeIt() { } 232 244 /// Copy constructor. … … 235 247 /// 236 248 EdgeIt(const EdgeIt& e) : Edge(e) { } 237 /// Initialize the iterator to be invalid.238 239 /// Initialize the iterator to be invalid.240 /// 249 /// %Invalid constructor \& conversion. 250 251 /// Initializes the iterator to be invalid. 252 /// \sa Invalid for more details. 241 253 EdgeIt(Invalid) { } 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. 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 /// 252 263 EdgeIt(const Graph&, const Edge&) { } 253 264 /// Next edge 254 265 255 266 /// Assign the iterator to the next edge. 267 /// 256 268 EdgeIt& operator++() { return *this; } 257 269 }; 258 270 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 /// 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. 266 275 /// Its usage is quite simple, for example you can compute the 267 /// degree (i.e. count the number of incident arcsof a node \c n268 /// in graph \c g of type \cGraph as follows.276 /// degree (i.e. the number of incident edges) of a node \c n 277 /// in a graph \c g of type \c %Graph as follows. 269 278 /// 270 279 ///\code … … 272 281 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 273 282 ///\endcode 283 /// 284 /// \warning Loop edges will be iterated twice. 274 285 class IncEdgeIt : public Edge { 275 286 public: 276 287 /// Default constructor 277 288 278 /// @warning The default constructor sets the iterator279 /// to an undefined value.289 /// Default constructor. 290 /// \warning It sets the iterator to an undefined value. 280 291 IncEdgeIt() { } 281 292 /// Copy constructor. … … 284 295 /// 285 296 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 286 /// Initialize the iterator to be invalid.287 288 /// Initialize the iterator to be invalid.289 /// 297 /// %Invalid constructor \& conversion. 298 299 /// Initializes the iterator to be invalid. 300 /// \sa Invalid for more details. 290 301 IncEdgeIt(Invalid) { } 291 /// This constructor sets the iterator to first incident arc.292 293 /// This constructor set the iterator to the first incident arc of294 /// the node.302 /// Sets the iterator to the first incident edge. 303 304 /// Sets the iterator to the first incident edge of the given node. 305 /// 295 306 IncEdgeIt(const Graph&, const Node&) { } 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. 307 /// Sets the iterator to the given edge. 308 309 /// Sets the iterator to the given edge of the given graph. 310 /// 301 311 IncEdgeIt(const Graph&, const Edge&) { } 302 /// Next incident arc303 304 /// Assign the iterator to the next incident arc312 /// Next incident edge 313 314 /// Assign the iterator to the next incident edge 305 315 /// of the corresponding node. 306 316 IncEdgeIt& operator++() { return *this; } 307 317 }; 308 318 309 /// The directed arc type.310 311 /// Th e directed arc type. It can be converted to the312 /// edge or it should be inherited from the undirected313 /// edge.319 /// The arc type of the graph 320 321 /// This class identifies a directed arc of the graph. It also serves 322 /// as a base class of the arc iterators, 323 /// thus they will convert to this type. 314 324 class Arc { 315 325 public: 316 326 /// Default constructor 317 327 318 /// @warning The default constructor sets the iterator319 /// to an undefined value.328 /// Default constructor. 329 /// \warning It sets the object to an undefined value. 320 330 Arc() { } 321 331 /// Copy constructor. … … 324 334 /// 325 335 Arc(const Arc&) { } 326 /// Initialize the iterator to be invalid.327 328 /// Initialize the iteratorto be invalid.329 /// 336 /// %Invalid constructor \& conversion. 337 338 /// Initializes the object to be invalid. 339 /// \sa Invalid for more details. 330 340 Arc(Invalid) { } 331 341 /// Equality operator 332 342 343 /// Equality operator. 344 /// 333 345 /// Two iterators are equal if and only if they point to the 334 /// same object or both are invalid.346 /// same object or both are \c INVALID. 335 347 bool operator==(Arc) const { return true; } 336 348 /// Inequality operator 337 349 338 /// \sa operator==(Arc n) 339 /// 350 /// Inequality operator. 340 351 bool operator!=(Arc) const { return true; } 341 352 342 353 /// Artificial ordering operator. 343 354 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. 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. 350 360 bool operator<(Arc) const { return false; } 351 361 352 /// Converison to Edge 362 /// Converison to \c Edge 363 364 /// Converison to \c Edge. 365 /// 353 366 operator Edge() const { return Edge(); } 354 367 }; 355 /// This iterator goes through each directed arc. 356 357 /// This iterator goes through each arc of a graph. 368 369 /// Iterator class for the arcs. 370 371 /// This iterator goes through each directed arc of the graph. 358 372 /// Its usage is quite simple, for example you can count the number 359 /// of arcs in a graph \c g of type \c Graph as follows:373 /// of arcs in a graph \c g of type \c %Graph as follows: 360 374 ///\code 361 375 /// int count=0; 362 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;376 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count; 363 377 ///\endcode 364 378 class ArcIt : public Arc { … … 366 380 /// Default constructor 367 381 368 /// @warning The default constructor sets the iterator369 /// to an undefined value.382 /// Default constructor. 383 /// \warning It sets the iterator to an undefined value. 370 384 ArcIt() { } 371 385 /// Copy constructor. … … 374 388 /// 375 389 ArcIt(const ArcIt& e) : Arc(e) { } 376 /// Initialize the iterator to be invalid.377 378 /// Initialize the iterator to be invalid.379 /// 390 /// %Invalid constructor \& conversion. 391 392 /// Initializes the iterator to be invalid. 393 /// \sa Invalid for more details. 380 394 ArcIt(Invalid) { } 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. 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 /// 391 404 ArcIt(const Graph&, const Arc&) { } 392 /// Next arc405 /// Next arc 393 406 394 407 /// Assign the iterator to the next arc. 408 /// 395 409 ArcIt& operator++() { return *this; } 396 410 }; 397 411 398 /// This iterator goes trough the outgoing directedarcs of a node.399 400 /// This iterator goes trough the \e outgoing arcs of a certain node401 /// of a graph.412 /// Iterator class for the outgoing arcs of a node. 413 414 /// This iterator goes trough the \e outgoing directed arcs of a 415 /// certain node of a graph. 402 416 /// Its usage is quite simple, for example you can count the number 403 417 /// of outgoing arcs of a node \c n 404 /// in graph \c g of type \cGraph as follows.418 /// in a graph \c g of type \c %Graph as follows. 405 419 ///\code 406 420 /// int count=0; 407 /// for ( Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;421 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 408 422 ///\endcode 409 410 423 class OutArcIt : public Arc { 411 424 public: 412 425 /// Default constructor 413 426 414 /// @warning The default constructor sets the iterator415 /// to an undefined value.427 /// Default constructor. 428 /// \warning It sets the iterator to an undefined value. 416 429 OutArcIt() { } 417 430 /// Copy constructor. … … 420 433 /// 421 434 OutArcIt(const OutArcIt& e) : Arc(e) { } 422 /// Initialize the iterator to be invalid.423 424 /// Initialize the iterator to be invalid.425 /// 435 /// %Invalid constructor \& conversion. 436 437 /// Initializes the iterator to be invalid. 438 /// \sa Invalid for more details. 426 439 OutArcIt(Invalid) { } 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 440 /// Sets the iterator to the first outgoing arc. 441 442 /// Sets the iterator to the first outgoing arc of the given node. 443 /// 433 444 OutArcIt(const Graph& n, const Node& g) { 434 445 ignore_unused_variable_warning(n); 435 446 ignore_unused_variable_warning(g); 436 447 } 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. 448 /// Sets the iterator to the given arc. 449 450 /// Sets the iterator to the given arc of the given graph. 451 /// 442 452 OutArcIt(const Graph&, const Arc&) { } 443 /// Next outgoing arc453 /// Next outgoing arc 444 454 445 455 /// Assign the iterator to the next … … 448 458 }; 449 459 450 /// This iterator goes trough the incoming directedarcs of a node.451 452 /// This iterator goes trough the \e incoming arcs of a certain node453 /// of a graph.460 /// Iterator class for the incoming arcs of a node. 461 462 /// This iterator goes trough the \e incoming directed arcs of a 463 /// certain node of a graph. 454 464 /// Its usage is quite simple, for example you can count the number 455 /// of outgoing arcs of a node \c n456 /// in graph \c g of type \cGraph as follows.465 /// of incoming arcs of a node \c n 466 /// in a graph \c g of type \c %Graph as follows. 457 467 ///\code 458 468 /// int count=0; 459 /// for (Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;469 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 460 470 ///\endcode 461 462 471 class InArcIt : public Arc { 463 472 public: 464 473 /// Default constructor 465 474 466 /// @warning The default constructor sets the iterator467 /// to an undefined value.475 /// Default constructor. 476 /// \warning It sets the iterator to an undefined value. 468 477 InArcIt() { } 469 478 /// Copy constructor. … … 472 481 /// 473 482 InArcIt(const InArcIt& e) : Arc(e) { } 474 /// Initialize the iterator to be invalid.475 476 /// Initialize the iterator to be invalid.477 /// 483 /// %Invalid constructor \& conversion. 484 485 /// Initializes the iterator to be invalid. 486 /// \sa Invalid for more details. 478 487 InArcIt(Invalid) { } 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 488 /// Sets the iterator to the first incoming arc. 489 490 /// Sets the iterator to the first incoming arc of the given node. 491 /// 485 492 InArcIt(const Graph& g, const Node& n) { 486 493 ignore_unused_variable_warning(n); 487 494 ignore_unused_variable_warning(g); 488 495 } 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. 496 /// Sets the iterator to the given arc. 497 498 /// Sets the iterator to the given arc of the given graph. 499 /// 494 500 InArcIt(const Graph&, const Arc&) { } 495 501 /// Next incoming arc 496 502 497 /// Assign the iterator to the next inarc of the corresponding node.498 /// 503 /// Assign the iterator to the next 504 /// incoming arc of the corresponding node. 499 505 InArcIt& operator++() { return *this; } 500 506 }; 501 507 502 /// \brief Reference map of the nodes to type \c T. 503 /// 504 /// Reference map of the nodes to type \c T. 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. 505 512 template<class T> 506 513 class NodeMap : public ReferenceMap<Node, T, T&, const T&> … … 508 515 public: 509 516 510 /// \e511 NodeMap(const Graph&) { }512 /// \e517 /// Constructor 518 explicit NodeMap(const Graph&) { } 519 /// Constructor with given initial value 513 520 NodeMap(const Graph&, T) { } 514 521 … … 525 532 }; 526 533 527 /// \brief Reference map of the arcs to type \c T. 528 /// 529 /// Reference map of the arcs to type \c T. 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. 530 538 template<class T> 531 539 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> … … 533 541 public: 534 542 535 /// \e536 ArcMap(const Graph&) { }537 /// \e543 /// Constructor 544 explicit ArcMap(const Graph&) { } 545 /// Constructor with given initial value 538 546 ArcMap(const Graph&, T) { } 547 539 548 private: 540 549 ///Copy constructor … … 549 558 }; 550 559 551 /// Reference map of the edges to type \c T. 552 553 /// Reference map of the edges to type \c T. 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. 554 564 template<class T> 555 565 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> … … 557 567 public: 558 568 559 /// \e560 EdgeMap(const Graph&) { }561 /// \e569 /// Constructor 570 explicit EdgeMap(const Graph&) { } 571 /// Constructor with given initial value 562 572 EdgeMap(const Graph&, T) { } 573 563 574 private: 564 575 ///Copy constructor … … 573 584 }; 574 585 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. 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. 619 595 /// \sa v() 620 596 /// \sa direction() 621 597 Node u(Edge) const { return INVALID; } 622 598 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. 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. 633 608 /// \sa u() 634 609 /// \sa direction() 635 610 Node v(Edge) const { return INVALID; } 636 611 637 /// \brief Source node of the directed arc. 612 /// \brief The source node of the arc. 613 /// 614 /// Returns the source node of the given arc. 638 615 Node source(Arc) const { return INVALID; } 639 616 640 /// \brief Target node of the directed arc. 617 /// \brief The target node of the arc. 618 /// 619 /// Returns the target node of the given arc. 641 620 Node target(Arc) const { return INVALID; } 642 621 643 /// \brief Returns the id of the node. 622 /// \brief The ID of the node. 623 /// 624 /// Returns the ID of the given node. 644 625 int id(Node) const { return -1; } 645 626 646 /// \brief Returns the id of the edge. 627 /// \brief The ID of the edge. 628 /// 629 /// Returns the ID of the given edge. 647 630 int id(Edge) const { return -1; } 648 631 649 /// \brief Returns the id of the arc. 632 /// \brief The ID of the arc. 633 /// 634 /// Returns the ID of the given arc. 650 635 int id(Arc) const { return -1; } 651 636 652 /// \brief Returns the node with the given id. 653 /// 654 /// \pre The argument should be a valid node id in the graph. 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. 655 641 Node nodeFromId(int) const { return INVALID; } 656 642 657 /// \brief Returns the edge with the given id. 658 /// 659 /// \pre The argument should be a valid edge id in the graph. 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. 660 647 Edge edgeFromId(int) const { return INVALID; } 661 648 662 /// \brief Returns the arc with the given id. 663 /// 664 /// \pre The argument should be a valid arc id in the graph. 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. 665 653 Arc arcFromId(int) const { return INVALID; } 666 654 667 /// \brief Returns an upper bound on the node IDs. 655 /// \brief An upper bound on the node IDs. 656 /// 657 /// Returns an upper bound on the node IDs. 668 658 int maxNodeId() const { return -1; } 669 659 670 /// \brief Returns an upper bound on the edge IDs. 660 /// \brief An upper bound on the edge IDs. 661 /// 662 /// Returns an upper bound on the edge IDs. 671 663 int maxEdgeId() const { return -1; } 672 664 673 /// \brief Returns an upper bound on the arc IDs. 665 /// \brief An upper bound on the arc IDs. 666 /// 667 /// Returns an upper bound on the arc IDs. 674 668 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 as 673 /// 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 arc 679 /// represents the given edge and its direction comes 680 /// from the bool parameter. If it is \c true, then the direction 681 /// 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 given 689 /// 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; } 675 703 676 704 void first(Node&) const {} … … 706 734 int maxId(Arc) const { return -1; } 707 735 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 } 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; } 749 769 750 770 template <typename _Graph> -
lemon/concepts/graph_components.h
r666 r734 93 93 /// associative containers (e.g. \c std::map). 94 94 /// 95 /// \note This operator only ha veto define some strict ordering of95 /// \note This operator only has 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
r617 r735 25 25 ///\ingroup graphs 26 26 ///\file 27 ///\brief Full Graph and FullDigraph classes.27 ///\brief FullDigraph and FullGraph classes. 28 28 29 29 namespace lemon { … … 149 149 /// \ingroup graphs 150 150 /// 151 /// \brief A full digraph class. 152 /// 153 /// This is a simple and fast directed full graph implementation. 154 /// From each node go arcs to each node (including the source node), 155 /// therefore the number of the arcs in the digraph is the square of 156 /// the node number. This digraph type is completely static, so you 157 /// can neither add nor delete either arcs or nodes, and it needs 158 /// constant space in memory. 159 /// 160 /// This class fully conforms to the \ref concepts::Digraph 161 /// "Digraph concept". 162 /// 163 /// The \c FullDigraph and \c FullGraph classes are very similar, 151 /// \brief A directed full graph class. 152 /// 153 /// FullDigraph is a simple and fast implmenetation of directed full 154 /// (complete) graphs. It contains an arc from each node to each node 155 /// (including a loop for each node), therefore the number of arcs 156 /// is the square of the number of nodes. 157 /// This class is completely static and it needs constant memory space. 158 /// Thus you can neither add nor delete nodes or arcs, however 159 /// the structure can be resized using resize(). 160 /// 161 /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". 162 /// Most of its member functions and nested classes are documented 163 /// only in the concept class. 164 /// 165 /// \note FullDigraph and FullGraph classes are very similar, 164 166 /// but there are two differences. While this class conforms only 165 /// to the \ref concepts::Digraph "Digraph" concept, the \cFullGraph166 /// c lass conforms to the \ref concepts::Graph "Graph" concept,167 /// moreover \c FullGraph does not contain a loop arcfor each168 /// node as \c FullDigraphdoes.167 /// to the \ref concepts::Digraph "Digraph" concept, FullGraph 168 /// conforms to the \ref concepts::Graph "Graph" concept, 169 /// moreover FullGraph does not contain a loop for each 170 /// node as this class does. 169 171 /// 170 172 /// \sa FullGraph … … 174 176 public: 175 177 176 /// \brief Constructor 178 /// \brief Default constructor. 179 /// 180 /// Default constructor. The number of nodes and arcs will be zero. 177 181 FullDigraph() { construct(0); } 178 182 … … 185 189 /// \brief Resizes the digraph 186 190 /// 187 /// Resizes the digraph. The function will fully destroyand188 /// rebuild the digraph. This cause that the maps of the digraph will191 /// This function resizes the digraph. It fully destroys and 192 /// rebuilds the structure, therefore the maps of the digraph will be 189 193 /// reallocated automatically and the previous values will be lost. 190 194 void resize(int n) { … … 198 202 /// \brief Returns the node with the given index. 199 203 /// 200 /// Returns the node with the given index. Since it is a static201 /// digraph its nodes can be indexed with integers from the range202 /// <tt>[0..nodeNum()-1]</tt>.204 /// Returns the node with the given index. Since this structure is 205 /// completely static, the nodes can be indexed with integers from 206 /// the range <tt>[0..nodeNum()-1]</tt>. 203 207 /// \sa index() 204 208 Node operator()(int ix) const { return Parent::operator()(ix); } … … 206 210 /// \brief Returns the index of the given node. 207 211 /// 208 /// Returns the index of the given node. Since it is a static209 /// digraph its nodes can be indexed with integers from the range210 /// <tt>[0..nodeNum()-1]</tt>.211 /// \sa operator() 212 int index( const Node&node) const { return Parent::index(node); }212 /// Returns the index of the given node. Since this structure is 213 /// completely static, the nodes can be indexed with integers from 214 /// the range <tt>[0..nodeNum()-1]</tt>. 215 /// \sa operator()() 216 int index(Node node) const { return Parent::index(node); } 213 217 214 218 /// \brief Returns the arc connecting the given nodes. 215 219 /// 216 220 /// Returns the arc connecting the given nodes. 217 Arc arc( const Node& u, const Node&v) const {221 Arc arc(Node u, Node v) const { 218 222 return Parent::arc(u, v); 219 223 } … … 521 525 /// \brief An undirected full graph class. 522 526 /// 523 /// This is a simple and fast undirected full graph 524 /// implementation. From each node go edge to each other node, 525 /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. 526 /// This graph type is completely static, so you can neither 527 /// add nor delete either edges or nodes, and it needs constant 528 /// space in memory. 529 /// 530 /// This class fully conforms to the \ref concepts::Graph "Graph concept". 531 /// 532 /// The \c FullGraph and \c FullDigraph classes are very similar, 533 /// but there are two differences. While the \c FullDigraph class 527 /// FullGraph is a simple and fast implmenetation of undirected full 528 /// (complete) graphs. It contains an edge between every distinct pair 529 /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>. 530 /// This class is completely static and it needs constant memory space. 531 /// Thus you can neither add nor delete nodes or edges, however 532 /// the structure can be resized using resize(). 533 /// 534 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 535 /// Most of its member functions and nested classes are documented 536 /// only in the concept class. 537 /// 538 /// \note FullDigraph and FullGraph classes are very similar, 539 /// but there are two differences. While FullDigraph 534 540 /// conforms only to the \ref concepts::Digraph "Digraph" concept, 535 541 /// this class conforms to the \ref concepts::Graph "Graph" concept, 536 /// moreover \c FullGraph does not contain a loop arcfor each537 /// node as \cFullDigraph does.542 /// moreover this class does not contain a loop for each 543 /// node as FullDigraph does. 538 544 /// 539 545 /// \sa FullDigraph … … 543 549 public: 544 550 545 /// \brief Constructor 551 /// \brief Default constructor. 552 /// 553 /// Default constructor. The number of nodes and edges will be zero. 546 554 FullGraph() { construct(0); } 547 555 … … 554 562 /// \brief Resizes the graph 555 563 /// 556 /// Resizes the graph. The function will fully destroyand557 /// rebuild the graph. This cause that the maps of the graph will564 /// This function resizes the graph. It fully destroys and 565 /// rebuilds the structure, therefore the maps of the graph will be 558 566 /// reallocated automatically and the previous values will be lost. 559 567 void resize(int n) { … … 569 577 /// \brief Returns the node with the given index. 570 578 /// 571 /// Returns the node with the given index. Since it is a static572 /// graph its nodes can be indexed with integers from the range573 /// <tt>[0..nodeNum()-1]</tt>.579 /// Returns the node with the given index. Since this structure is 580 /// completely static, the nodes can be indexed with integers from 581 /// the range <tt>[0..nodeNum()-1]</tt>. 574 582 /// \sa index() 575 583 Node operator()(int ix) const { return Parent::operator()(ix); } … … 577 585 /// \brief Returns the index of the given node. 578 586 /// 579 /// Returns the index of the given node. Since it is a static580 /// graph its nodes can be indexed with integers from the range581 /// <tt>[0..nodeNum()-1]</tt>.582 /// \sa operator() 583 int index( const Node&node) const { return Parent::index(node); }587 /// Returns the index of the given node. Since this structure is 588 /// completely static, the nodes can be indexed with integers from 589 /// the range <tt>[0..nodeNum()-1]</tt>. 590 /// \sa operator()() 591 int index(Node node) const { return Parent::index(node); } 584 592 585 593 /// \brief Returns the arc connecting the given nodes. 586 594 /// 587 595 /// Returns the arc connecting the given nodes. 588 Arc arc( const Node& s, const Node&t) const {596 Arc arc(Node s, Node t) const { 589 597 return Parent::arc(s, t); 590 598 } 591 599 592 /// \brief Returns the edge connect sthe given nodes.593 /// 594 /// Returns the edge connect sthe given nodes.595 Edge edge( const Node& u, const Node&v) const {600 /// \brief Returns the edge connecting the given nodes. 601 /// 602 /// Returns the edge connecting the given nodes. 603 Edge edge(Node u, Node v) const { 596 604 return Parent::edge(u, v); 597 605 } -
lemon/grid_graph.h
r617 r735 471 471 /// \brief Grid graph class 472 472 /// 473 /// This classimplements a special graph type. The nodes of the474 /// graph can be indexed by two integer \c (i,j) valuewhere \c i is475 /// in the \c [0..width()-1] range and j is in the \c476 /// [0..height()-1] range.Two nodes are connected in the graph if477 /// the ind exes differ exactly on one position and exactly one is478 /// the difference. The nodes of the graph can be indexed by position479 /// with the \c operator()() function. The positions of the nodes can be480 /// get with\c pos(), \c col() and \c row() members. The outgoing473 /// GridGraph implements a special graph type. The nodes of the 474 /// graph can be indexed by two integer values \c (i,j) where \c i is 475 /// in the range <tt>[0..width()-1]</tt> and j is in the range 476 /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if 477 /// the indices differ exactly on one position and the difference is 478 /// also exactly one. The nodes of the graph can be obtained by position 479 /// using the \c operator()() function and the indices of the nodes can 480 /// be obtained using \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, however 487 /// the structure can be resized using resize(). 484 488 /// 485 489 /// \image html grid_graph.png … … 497 501 ///\endcode 498 502 /// 499 /// This graph type fully conforms to the \ref concepts::Graph 500 /// "Graph concept". 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. 501 506 class GridGraph : public ExtendedGridGraphBase { 502 507 typedef ExtendedGridGraphBase Parent; … … 504 509 public: 505 510 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>. 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>". 509 516 class IndexMap { 510 517 public: … … 515 522 516 523 /// \brief Constructor 517 ///518 /// Constructor519 524 IndexMap(const GridGraph& graph) : _graph(graph) {} 520 525 521 526 /// \brief The subscript operator 522 ///523 /// The subscript operator.524 527 Value operator[](Key key) const { 525 528 return _graph.pos(key); … … 541 544 542 545 /// \brief Constructor 543 ///544 /// Constructor545 546 ColMap(const GridGraph& graph) : _graph(graph) {} 546 547 547 548 /// \brief The subscript operator 548 ///549 /// The subscript operator.550 549 Value operator[](Key key) const { 551 550 return _graph.col(key); … … 567 566 568 567 /// \brief Constructor 569 ///570 /// Constructor571 568 RowMap(const GridGraph& graph) : _graph(graph) {} 572 569 573 570 /// \brief The subscript operator 574 ///575 /// The subscript operator.576 571 Value operator[](Key key) const { 577 572 return _graph.row(key); … … 584 579 /// \brief Constructor 585 580 /// 586 /// Construct a grid graph with given size.581 /// Construct a grid graph with the given size. 587 582 GridGraph(int width, int height) { construct(width, height); } 588 583 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. 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. 595 589 void resize(int width, int height) { 596 590 Parent::notifier(Arc()).clear(); … … 610 604 } 611 605 612 /// \brief Gives back the column index of the node.606 /// \brief The column index of the node. 613 607 /// 614 608 /// Gives back the column index of the node. … … 617 611 } 618 612 619 /// \brief Gives back the row index of the node.613 /// \brief The row index of the node. 620 614 /// 621 615 /// Gives back the row index of the node. … … 624 618 } 625 619 626 /// \brief Gives back the position of the node.620 /// \brief The position of the node. 627 621 /// 628 622 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. … … 631 625 } 632 626 633 /// \brief Gives back the number of the columns.627 /// \brief The number of the columns. 634 628 /// 635 629 /// Gives back the number of the columns. … … 638 632 } 639 633 640 /// \brief Gives back the number of the rows.634 /// \brief The number of the rows. 641 635 /// 642 636 /// Gives back the number of the rows. … … 645 639 } 646 640 647 /// \brief Gives back the arc goes right from the node.641 /// \brief The arc goes right from the node. 648 642 /// 649 643 /// Gives back the arc goes right from the node. If there is not … … 653 647 } 654 648 655 /// \brief Gives back the arc goes left from the node.649 /// \brief The arc goes left from the node. 656 650 /// 657 651 /// Gives back the arc goes left from the node. If there is not … … 661 655 } 662 656 663 /// \brief Gives back the arc goes up from the node.657 /// \brief The arc goes up from the node. 664 658 /// 665 659 /// Gives back the arc goes up from the node. If there is not … … 669 663 } 670 664 671 /// \brief Gives back the arc goes down from the node.665 /// \brief The arc goes down from the node. 672 666 /// 673 667 /// Gives back the arc goes down from the node. If there is not -
lemon/hypercube_graph.h
r617 r737 283 283 /// \brief Hypercube graph class 284 284 /// 285 /// This class implements a special graph type. The nodes of the graph286 /// are indiced with integers withat most \c dim binary digits.285 /// HypercubeGraph implements a special graph type. The nodes of the 286 /// graph are indexed with integers having at most \c dim binary digits. 287 287 /// Two nodes are connected in the graph if and only if their indices 288 288 /// differ only on one position in the binary form. 289 /// This class is completely static and it needs constant memory space. 290 /// Thus you can neither add nor delete nodes or edges, however 291 /// the structure can be resized using resize(). 292 /// 293 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 294 /// Most of its member functions and nested classes are documented 295 /// only in the concept class. 289 296 /// 290 297 /// \note The type of the indices is chosen to \c int for efficiency 291 298 /// reasons. Thus the maximum dimension of this implementation is 26 292 299 /// (assuming that the size of \c int is 32 bit). 293 ///294 /// This graph type fully conforms to the \ref concepts::Graph295 /// "Graph concept".296 300 class HypercubeGraph : public ExtendedHypercubeGraphBase { 297 301 typedef ExtendedHypercubeGraphBase Parent; … … 303 307 /// Constructs a hypercube graph with \c dim dimensions. 304 308 HypercubeGraph(int dim) { construct(dim); } 309 310 /// \brief Resizes the graph 311 /// 312 /// This function resizes the graph. It fully destroys and 313 /// rebuilds the structure, therefore the maps of the graph will be 314 /// reallocated automatically and the previous values will be lost. 315 void resize(int dim) { 316 Parent::notifier(Arc()).clear(); 317 Parent::notifier(Edge()).clear(); 318 Parent::notifier(Node()).clear(); 319 construct(dim); 320 Parent::notifier(Node()).build(); 321 Parent::notifier(Edge()).build(); 322 Parent::notifier(Arc()).build(); 323 } 305 324 306 325 /// \brief The number of dimensions. … … 321 340 /// 322 341 /// Gives back the dimension id of the given edge. 323 /// It is in the [0..dim-1] range.342 /// It is in the range <tt>[0..dim-1]</tt>. 324 343 int dimension(Edge edge) const { 325 344 return Parent::dimension(edge); … … 329 348 /// 330 349 /// Gives back the dimension id of the given arc. 331 /// It is in the [0..dim-1] range.350 /// It is in the range <tt>[0..dim-1]</tt>. 332 351 int dimension(Arc arc) const { 333 352 return Parent::dimension(arc); -
lemon/list_graph.h
r617 r741 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief ListDigraph ,ListGraph classes.24 ///\brief ListDigraph and ListGraph classes. 25 25 26 26 #include <lemon/core.h> … … 32 32 33 33 namespace lemon { 34 35 class ListDigraph; 34 36 35 37 class ListDigraphBase { … … 63 65 class Node { 64 66 friend class ListDigraphBase; 67 friend class ListDigraph; 65 68 protected: 66 69 … … 78 81 class Arc { 79 82 friend class ListDigraphBase; 83 friend class ListDigraph; 80 84 protected: 81 85 … … 117 121 int n; 118 122 for(n = first_node; 119 n !=-1 && nodes[n].first_in== -1;123 n != -1 && nodes[n].first_out == -1; 120 124 n = nodes[n].next) {} 121 arc.id = (n == -1) ? -1 : nodes[n].first_ in;125 arc.id = (n == -1) ? -1 : nodes[n].first_out; 122 126 } 123 127 124 128 void next(Arc& arc) const { 125 if (arcs[arc.id].next_ in!= -1) {126 arc.id = arcs[arc.id].next_ in;129 if (arcs[arc.id].next_out != -1) { 130 arc.id = arcs[arc.id].next_out; 127 131 } else { 128 132 int n; 129 for(n = nodes[arcs[arc.id]. target].next;130 n !=-1 && nodes[n].first_in== -1;133 for(n = nodes[arcs[arc.id].source].next; 134 n != -1 && nodes[n].first_out == -1; 131 135 n = nodes[n].next) {} 132 arc.id = (n == -1) ? -1 : nodes[n].first_ in;136 arc.id = (n == -1) ? -1 : nodes[n].first_out; 133 137 } 134 138 } … … 312 316 ///A general directed graph structure. 313 317 314 ///\ref ListDigraph is a simple and fast <em>directed graph</em>315 ///implementation based on staticlinked lists that are stored in318 ///\ref ListDigraph is a versatile and fast directed graph 319 ///implementation based on linked lists that are stored in 316 320 ///\c std::vector structures. 317 321 /// 318 /// It conforms to the \ref concepts::Digraph "Digraph concept" and it319 ///a lso provides several useful additional functionalities.320 ///Most of themember functions and nested classes are documented322 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 323 ///and it also provides several useful additional functionalities. 324 ///Most of its member functions and nested classes are documented 321 325 ///only in the concept class. 322 326 /// 323 327 ///\sa concepts::Digraph 324 328 ///\sa ListGraph 325 329 class ListDigraph : public ExtendedListDigraphBase { 326 330 typedef ExtendedListDigraphBase Parent; 327 331 328 332 private: 329 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 330 331 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 332 /// 333 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 333 334 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; 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. 335 /// \brief Assignment of a digraph to another one is \e not allowed. 336 /// Use DigraphCopy instead. 339 337 void operator=(const ListDigraph &) {} 340 338 public: … … 348 346 ///Add a new node to the digraph. 349 347 350 /// Adda new node to the digraph.348 ///This function adds a new node to the digraph. 351 349 ///\return The new node. 352 350 Node addNode() { return Parent::addNode(); } … … 354 352 ///Add a new arc to the digraph. 355 353 356 /// Adda new arc to the digraph with source node \c s354 ///This function adds a new arc to the digraph with source node \c s 357 355 ///and target node \c t. 358 356 ///\return The new arc. 359 Arc addArc( const Node& s, const Node&t) {357 Arc addArc(Node s, Node t) { 360 358 return Parent::addArc(s, t); 361 359 } … … 363 361 ///\brief Erase a node from the digraph. 364 362 /// 365 ///Erase a node from the digraph. 366 /// 367 void erase(const Node& n) { Parent::erase(n); } 363 ///This function erases the given node from the digraph. 364 void erase(Node n) { Parent::erase(n); } 368 365 369 366 ///\brief Erase an arc from the digraph. 370 367 /// 371 ///Erase an arc from the digraph. 372 /// 373 void erase(const Arc& a) { Parent::erase(a); } 368 ///This function erases the given arc from the digraph. 369 void erase(Arc a) { Parent::erase(a); } 374 370 375 371 /// Node validity check 376 372 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. 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. 383 378 bool valid(Node n) const { return Parent::valid(n); } 384 379 385 380 /// Arc validity check 386 381 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. 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. 393 387 bool valid(Arc a) const { return Parent::valid(a); } 394 388 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. 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. 402 395 /// 403 396 ///\warning This functionality cannot be used together with the Snapshot … … 406 399 Parent::changeTarget(a,n); 407 400 } 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. 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. 415 407 /// 416 408 ///\warning This functionality cannot be used together with the Snapshot … … 420 412 } 421 413 422 /// Invertthe direction of an arc.423 424 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain425 /// valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are426 /// invalidated.414 /// Reverse the 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 referencing 418 ///the changed arc are invalidated. 427 419 /// 428 420 ///\warning This functionality cannot be used together with the Snapshot 429 421 ///feature. 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); }; 422 void reverseArc(Arc a) { 423 Node t=target(a); 424 changeTarget(a,source(a)); 425 changeSource(a,t); 426 } 455 427 456 428 ///Contract two nodes. 457 429 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. 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. 467 442 /// 468 443 ///\warning This functionality cannot be used together with the Snapshot 469 444 ///feature. 470 void contract(Node a, Node b, bool r = true)445 void contract(Node u, Node v, bool r = true) 471 446 { 472 for(OutArcIt e(*this, b);e!=INVALID;) {447 for(OutArcIt e(*this,v);e!=INVALID;) { 473 448 OutArcIt f=e; 474 449 ++f; 475 if(r && target(e)== a) erase(e);476 else changeSource(e, a);450 if(r && target(e)==u) erase(e); 451 else changeSource(e,u); 477 452 e=f; 478 453 } 479 for(InArcIt e(*this, b);e!=INVALID;) {454 for(InArcIt e(*this,v);e!=INVALID;) { 480 455 InArcIt f=e; 481 456 ++f; 482 if(r && source(e)== a) erase(e);483 else changeTarget(e, a);457 if(r && source(e)==u) erase(e); 458 else changeTarget(e,u); 484 459 e=f; 485 460 } 486 erase( b);461 erase(v); 487 462 } 488 463 489 464 ///Split a node. 490 465 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. 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. 495 472 ///\return The newly created node. 496 473 /// 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 474 ///\note All iterators remain valid. 475 /// 476 ///\warning This functionality cannot be used together with the 502 477 ///Snapshot feature. 503 478 Node split(Node n, bool connect = true) { 504 479 Node b = addNode(); 505 for(OutArcIt e(*this,n);e!=INVALID;) { 506 OutArcIt f=e; 507 ++f; 508 changeSource(e,b); 509 e=f; 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; 510 484 } 511 485 if (connect) addArc(n,b); … … 515 489 ///Split an arc. 516 490 517 ///This function splits an arc. First a new node \c b is added to518 /// the digraph, then the original arc is re-targeted to \c519 /// b. Finally an arc from \c b to the original target is added.520 /// 491 ///This function splits the given arc. First, a new node \c v is 492 ///added to the digraph, then the target node of the original arc 493 ///is set to \c v. Finally, an arc from \c v to the original target 494 ///is added. 521 495 ///\return The newly created node. 496 /// 497 ///\note \c InArcIt iterators referencing the original arc are 498 ///invalidated. Other iterators remain valid. 522 499 /// 523 500 ///\warning This functionality cannot be used together with the 524 501 ///Snapshot feature. 525 Node split(Arc e) { 526 Node b = addNode(); 527 addArc(b,target(e)); 528 changeTarget(e,b); 529 return b; 530 } 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); }; 531 536 532 537 /// \brief Class to make a snapshot of the digraph and restore … … 538 543 /// restore() function. 539 544 /// 540 /// \warning Arc and node deletions and other modifications (e.g. 541 /// contracting, splitting, reversing arcs or nodes) cannot be 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 542 551 /// restored. These events invalidate the snapshot. 552 /// However the arcs and nodes that were added to the digraph after 553 /// making the current snapshot can be removed without invalidating it. 543 554 class Snapshot { 544 555 protected: … … 710 721 /// 711 722 /// Default constructor. 712 /// To actually make a snapshot you must call save().723 /// You have to call save() to actually make a snapshot. 713 724 Snapshot() 714 725 : digraph(0), node_observer_proxy(*this), … … 717 728 /// \brief Constructor that immediately makes a snapshot. 718 729 /// 719 /// This constructor immediately makes a snapshot of the digraph. 720 /// \param _digraph The digraph we make a snapshot of. 721 Snapshot(ListDigraph &_digraph) 730 /// This constructor immediately makes a snapshot of the given digraph. 731 Snapshot(ListDigraph &gr) 722 732 : node_observer_proxy(*this), 723 733 arc_observer_proxy(*this) { 724 attach( _digraph);734 attach(gr); 725 735 } 726 736 727 737 /// \brief Make a snapshot. 728 738 /// 729 /// Make a snapshot of the digraph. 730 /// 731 /// This function can be called more than once. In case of a repeated 739 /// This function makes a snapshot of the given digraph. 740 /// It can be called more than once. In case of a repeated 732 741 /// call, the previous snapshot gets lost. 733 /// \param _digraph The digraph we make the snapshot of. 734 void save(ListDigraph &_digraph) { 742 void save(ListDigraph &gr) { 735 743 if (attached()) { 736 744 detach(); 737 745 clear(); 738 746 } 739 attach( _digraph);747 attach(gr); 740 748 } 741 749 742 750 /// \brief Undo the changes until the last snapshot. 743 // 744 /// Undo the changes until the last snapshot created by save(). 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. 745 757 void restore() { 746 758 detach(); … … 756 768 } 757 769 758 /// \brief Gives back true whenthe snapshot is valid.770 /// \brief Returns \c true if the snapshot is valid. 759 771 /// 760 /// Gives back true whenthe snapshot is valid.772 /// This function returns \c true if the snapshot is valid. 761 773 bool valid() const { 762 774 return attached(); … … 795 807 796 808 typedef ListGraphBase Graph; 797 798 class Node;799 class Arc;800 class Edge;801 809 802 810 class Node { … … 848 856 bool operator<(const Arc& arc) const {return id < arc.id;} 849 857 }; 850 851 852 858 853 859 ListGraphBase() … … 1165 1171 ///A general undirected graph structure. 1166 1172 1167 ///\ref ListGraph is a simple and fast <em>undirected graph</em>1168 ///implementation based on staticlinked lists that are stored in1173 ///\ref ListGraph is a versatile and fast undirected graph 1174 ///implementation based on linked lists that are stored in 1169 1175 ///\c std::vector structures. 1170 1176 /// 1171 /// It conforms to the \ref concepts::Graph "Graph concept" and it1172 ///a lso provides several useful additional functionalities.1173 ///Most of themember functions and nested classes are documented1177 ///This type fully conforms to the \ref concepts::Graph "Graph concept" 1178 ///and it also provides several useful additional functionalities. 1179 ///Most of its member functions and nested classes are documented 1174 1180 ///only in the concept class. 1175 1181 /// 1176 1182 ///\sa concepts::Graph 1177 1183 ///\sa ListDigraph 1178 1184 class ListGraph : public ExtendedListGraphBase { 1179 1185 typedef ExtendedListGraphBase Parent; 1180 1186 1181 1187 private: 1182 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1183 1184 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1185 /// 1188 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1186 1189 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; 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. 1190 /// \brief Assignment of a graph to another one is \e not allowed. 1191 /// Use GraphCopy instead. 1192 1192 void operator=(const ListGraph &) {} 1193 1193 public: … … 1202 1202 /// \brief Add a new node to the graph. 1203 1203 /// 1204 /// Adda new node to the graph.1204 /// This function adds 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 /// Add a new edge to the graph with source node \c s 1211 /// and target node \c t. 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. 1212 1213 /// \return The new edge. 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); } 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); } 1228 1227 /// Node validity check 1229 1228 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 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 1235 1233 /// added to the graph. 1236 1234 bool valid(Node n) const { return Parent::valid(n); } 1235 /// Edge validity check 1236 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 1241 /// added to the graph. 1242 bool valid(Edge e) const { return Parent::valid(e); } 1237 1243 /// Arc validity check 1238 1244 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 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 1244 1249 /// added to the graph. 1245 1250 bool valid(Arc a) const { return Parent::valid(a); } 1246 /// Edge validity check 1247 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 1253 /// added to the graph. 1254 bool valid(Edge e) const { return Parent::valid(e); } 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. 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. 1263 1259 /// 1264 1260 ///\warning This functionality cannot be used together with the … … 1267 1263 Parent::changeU(e,n); 1268 1264 } 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. 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. 1276 1273 /// 1277 1274 ///\warning This functionality cannot be used together with the … … 1280 1277 Parent::changeV(e,n); 1281 1278 } 1279 1282 1280 /// \brief Contract two nodes. 1283 1281 /// 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. 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. 1292 1293 /// 1293 1294 ///\warning This functionality cannot be used together with the … … 1308 1309 } 1309 1310 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 memory 1322 /// allocation: if you know that the graph you want to build will 1323 /// be large (e.g. it will contain millions of nodes and/or edges), 1324 /// then it is worth reserving space for this amount before starting 1325 /// 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 memory 1332 /// allocation: if you know that the graph you want to build will 1333 /// be large (e.g. it will contain millions of nodes and/or edges), 1334 /// then it is worth reserving space for this amount before starting 1335 /// to build the graph. 1336 /// \sa reserveNode() 1337 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1310 1338 1311 1339 /// \brief Class to make a snapshot of the graph and restore … … 1317 1345 /// using the restore() function. 1318 1346 /// 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. 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. 1322 1356 class Snapshot { 1323 1357 protected: … … 1489 1523 /// 1490 1524 /// Default constructor. 1491 /// To actually make a snapshot you must call save().1525 /// You have to call save() to actually make a snapshot. 1492 1526 Snapshot() 1493 1527 : graph(0), node_observer_proxy(*this), … … 1496 1530 /// \brief Constructor that immediately makes a snapshot. 1497 1531 /// 1498 /// This constructor immediately makes a snapshot of the graph. 1499 /// \param _graph The graph we make a snapshot of. 1500 Snapshot(ListGraph &_graph) 1532 /// This constructor immediately makes a snapshot of the given graph. 1533 Snapshot(ListGraph &gr) 1501 1534 : node_observer_proxy(*this), 1502 1535 edge_observer_proxy(*this) { 1503 attach( _graph);1536 attach(gr); 1504 1537 } 1505 1538 1506 1539 /// \brief Make a snapshot. 1507 1540 /// 1508 /// Make a snapshot of the graph. 1509 /// 1510 /// This function can be called more than once. In case of a repeated 1541 /// This function makes a snapshot of the given graph. 1542 /// It can be called more than once. In case of a repeated 1511 1543 /// call, the previous snapshot gets lost. 1512 /// \param _graph The graph we make the snapshot of. 1513 void save(ListGraph &_graph) { 1544 void save(ListGraph &gr) { 1514 1545 if (attached()) { 1515 1546 detach(); 1516 1547 clear(); 1517 1548 } 1518 attach( _graph);1549 attach(gr); 1519 1550 } 1520 1551 1521 1552 /// \brief Undo the changes until the last snapshot. 1522 // 1523 /// Undo the changes until the last snapshot created by save(). 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. 1524 1559 void restore() { 1525 1560 detach(); … … 1535 1570 } 1536 1571 1537 /// \brief Gives back true whenthe snapshot is valid.1572 /// \brief Returns \c true if the snapshot is valid. 1538 1573 /// 1539 /// Gives back true whenthe snapshot is valid.1574 /// This function returns \c true if the snapshot is valid. 1540 1575 bool valid() const { 1541 1576 return attached(); -
lemon/smart_graph.h
r617 r736 33 33 34 34 class SmartDigraph; 35 ///Base of SmartDigraph 36 37 ///Base of SmartDigraph 38 /// 35 39 36 class SmartDigraphBase { 40 37 protected: … … 188 185 ///\brief A smart directed graph class. 189 186 /// 190 ///This is a simple and fast digraph implementation. 191 ///It is also quite memory efficient, but at the price 192 ///that <b> it does support only limited (only stack-like) 193 ///node and arc deletions</b>. 194 ///It fully conforms to the \ref concepts::Digraph "Digraph concept". 187 ///\ref SmartDigraph is a simple and fast digraph implementation. 188 ///It is also quite memory efficient but at the price 189 ///that it does not support node and arc deletion 190 ///(except for the Snapshot feature). 195 191 /// 196 ///\sa concepts::Digraph. 192 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 193 ///and it also provides some additional functionalities. 194 ///Most of its member functions and nested classes are documented 195 ///only in the concept class. 196 /// 197 ///\sa concepts::Digraph 198 ///\sa SmartGraph 197 199 class SmartDigraph : public ExtendedSmartDigraphBase { 198 200 typedef ExtendedSmartDigraphBase Parent; 199 201 200 202 private: 201 202 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 203 204 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 205 /// 203 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 206 204 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; 207 ///\brief Assignment of SmartDigraph to another one is \e not allowed. 208 ///Use DigraphCopy() instead. 209 210 ///Assignment of SmartDigraph to another one is \e not allowed. 211 ///Use DigraphCopy() instead. 205 /// \brief Assignment of a digraph to another one is \e not allowed. 206 /// Use DigraphCopy instead. 212 207 void operator=(const SmartDigraph &) {} 213 208 … … 222 217 ///Add a new node to the digraph. 223 218 224 /// Adda new node to the digraph.225 /// 219 ///This function adds a new node to the digraph. 220 ///\return The new node. 226 221 Node addNode() { return Parent::addNode(); } 227 222 228 223 ///Add a new arc to the digraph. 229 224 230 /// Adda new arc to the digraph with source node \c s225 ///This function adds a new arc to the digraph with source node \c s 231 226 ///and target node \c t. 232 227 ///\return The new arc. 233 Arc addArc( const Node& s, const Node&t) {228 Arc addArc(Node s, Node t) { 234 229 return Parent::addArc(s, t); 235 230 } 236 231 237 /// \brief Using this it is possible to avoid the superfluous memory238 /// allocation.239 240 /// Using this it is possible to avoid the superfluous memory241 /// allocation: if you know that the digraph you want to build will242 /// be very large (e.g. it will contain millions of nodes and/or arcs)243 /// then it is worth reserving space for this amount before starting244 /// to build the digraph.245 /// \sa reserveArc246 void reserveNode(int n) { nodes.reserve(n); };247 248 /// \brief Using this it is possible to avoid the superfluous memory249 /// allocation.250 251 /// Using this it is possible to avoid the superfluous memory252 /// allocation: if you know that the digraph you want to build will253 /// be very large (e.g. it will contain millions of nodes and/or arcs)254 /// then it is worth reserving space for this amount before starting255 /// to build the digraph.256 /// \sa reserveNode257 void reserveArc(int m) { arcs.reserve(m); };258 259 232 /// \brief Node validity check 260 233 /// 261 /// This function gives back true if the given node is valid,262 /// i e. it is a real node of thegraph.234 /// This function gives back \c true if the given node is valid, 235 /// i.e. it is a real node of the digraph. 263 236 /// 264 237 /// \warning A removed node (using Snapshot) could become valid again 265 /// when new nodes are added to thegraph.238 /// if new nodes are added to the digraph. 266 239 bool valid(Node n) const { return Parent::valid(n); } 267 240 268 241 /// \brief Arc validity check 269 242 /// 270 /// This function gives back true if the given arc is valid,271 /// i e. it is a real arc of thegraph.243 /// This function gives back \c true if the given arc is valid, 244 /// i.e. it is a real arc of the digraph. 272 245 /// 273 246 /// \warning A removed arc (using Snapshot) could become valid again 274 /// whennew arcs are added to the graph.247 /// if new arcs are added to the graph. 275 248 bool valid(Arc a) const { return Parent::valid(a); } 276 249 277 ///Clear the digraph.278 279 ///Erase all the nodes and arcs from the digraph.280 ///281 void clear() {282 Parent::clear();283 }284 285 250 ///Split a node. 286 251 287 ///This function splits a node. First a new node is added to the digraph, 288 ///then the source of each outgoing arc of \c n is moved to this new node. 289 ///If \c connect is \c true (this is the default value), then a new arc 290 ///from \c n to the newly created node is also added. 252 ///This function splits the given node. First, a new node is added 253 ///to the digraph, then the source of each outgoing arc of node \c n 254 ///is moved to this new node. 255 ///If the second parameter \c connect is \c true (this is the default 256 ///value), then a new arc from node \c n to the newly created node 257 ///is also added. 291 258 ///\return The newly created node. 292 259 /// 293 ///\note The <tt>Arc</tt>s 294 ///referencing a moved arc remain 295 ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s 296 ///may be invalidated. 260 ///\note All iterators remain valid. 261 /// 297 262 ///\warning This functionality cannot be used together with the Snapshot 298 263 ///feature. … … 309 274 } 310 275 276 ///Clear the digraph. 277 278 ///This function erases all nodes and arcs from the digraph. 279 /// 280 void clear() { 281 Parent::clear(); 282 } 283 284 /// Reserve memory for nodes. 285 286 /// Using this function, it is possible to avoid superfluous memory 287 /// allocation: if you know that the digraph you want to build will 288 /// be large (e.g. it will contain millions of nodes and/or arcs), 289 /// then it is worth reserving space for this amount before starting 290 /// to build the digraph. 291 /// \sa reserveArc() 292 void reserveNode(int n) { nodes.reserve(n); }; 293 294 /// Reserve memory for arcs. 295 296 /// Using this function, it is possible to avoid superfluous memory 297 /// allocation: if you know that the digraph you want to build will 298 /// be large (e.g. it will contain millions of nodes and/or arcs), 299 /// then it is worth reserving space for this amount before starting 300 /// to build the digraph. 301 /// \sa reserveNode() 302 void reserveArc(int m) { arcs.reserve(m); }; 303 311 304 public: 312 305 … … 333 326 public: 334 327 335 ///Class to make a snapshot of the digraph and to rest rore toit later.336 337 ///Class to make a snapshot of the digraph and to rest rore toit later.328 ///Class to make a snapshot of the digraph and to restore it later. 329 330 ///Class to make a snapshot of the digraph and to restore it later. 338 331 /// 339 332 ///The newly added nodes and arcs can be removed using the 340 ///restore() function. 341 ///\note After you restore a state, you cannot restore 342 ///a later state, in other word you cannot add again the arcs deleted 343 ///by restore() using another one Snapshot instance. 344 /// 345 ///\warning If you do not use correctly the snapshot that can cause 346 ///either broken program, invalid state of the digraph, valid but 347 ///not the restored digraph or no change. Because the runtime performance 348 ///the validity of the snapshot is not stored. 333 ///restore() function. This is the only way for deleting nodes and/or 334 ///arcs from a SmartDigraph structure. 335 /// 336 ///\note After a state is restored, you cannot restore a later state, 337 ///i.e. you cannot add the removed nodes and arcs again using 338 ///another Snapshot instance. 339 /// 340 ///\warning Node splitting cannot be restored. 341 ///\warning The validity of the snapshot is not stored due to 342 ///performance reasons. If you do not use the snapshot correctly, 343 ///it can cause broken program, invalid or not restored state of 344 ///the digraph or no change. 349 345 class Snapshot 350 346 { … … 358 354 359 355 ///Default constructor. 360 ///To actually make a snapshot you must call save(). 361 /// 356 ///You have to call save() to actually make a snapshot. 362 357 Snapshot() : _graph(0) {} 363 358 ///Constructor that immediately makes a snapshot 364 359 365 ///This constructor immediately makes a snapshot of the digraph.366 /// \param graph The digraph we make a snapshot of.367 Snapshot(SmartDigraph &gr aph) : _graph(&graph) {360 ///This constructor immediately makes a snapshot of the given digraph. 361 /// 362 Snapshot(SmartDigraph &gr) : _graph(&gr) { 368 363 node_num=_graph->nodes.size(); 369 364 arc_num=_graph->arcs.size(); … … 372 367 ///Make a snapshot. 373 368 374 ///Make a snapshot of the digraph. 375 /// 376 ///This function can be called more than once. In case of a repeated 369 ///This function makes a snapshot of the given digraph. 370 ///It can be called more than once. In case of a repeated 377 371 ///call, the previous snapshot gets lost. 378 ///\param graph The digraph we make the snapshot of. 379 void save(SmartDigraph &graph) 380 { 381 _graph=&graph; 372 void save(SmartDigraph &gr) { 373 _graph=&gr; 382 374 node_num=_graph->nodes.size(); 383 375 arc_num=_graph->arcs.size(); … … 386 378 ///Undo the changes until a snapshot. 387 379 388 ///Undo the changes until a snapshot created by save(). 389 /// 390 ///\note After you restored a state, you cannot restore 391 ///a later state, in other word you cannot add again the arcs deleted 392 ///by restore(). 380 ///This function undos the changes until the last snapshot 381 ///created by save() or Snapshot(SmartDigraph&). 393 382 void restore() 394 383 { … … 622 611 /// \brief A smart undirected graph class. 623 612 /// 624 /// This is a simple and fast graph implementation. 625 /// It is also quite memory efficient, but at the price 626 /// that <b> it does support only limited (only stack-like) 627 /// node and arc deletions</b>. 628 /// It fully conforms to the \ref concepts::Graph "Graph concept". 613 /// \ref SmartGraph is a simple and fast graph implementation. 614 /// It is also quite memory efficient but at the price 615 /// that it does not support node and edge deletion 616 /// (except for the Snapshot feature). 629 617 /// 630 /// \sa concepts::Graph. 618 /// This type fully conforms to the \ref concepts::Graph "Graph concept" 619 /// and it also provides some additional functionalities. 620 /// Most of its member functions and nested classes are documented 621 /// only in the concept class. 622 /// 623 /// \sa concepts::Graph 624 /// \sa SmartDigraph 631 625 class SmartGraph : public ExtendedSmartGraphBase { 632 626 typedef ExtendedSmartGraphBase Parent; 633 627 634 628 private: 635 636 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 637 638 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 639 /// 629 /// Graphs are \e not copy constructible. Use GraphCopy instead. 640 630 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; 641 642 ///\brief Assignment of SmartGraph to another one is \e not allowed. 643 ///Use GraphCopy() instead. 644 645 ///Assignment of SmartGraph to another one is \e not allowed. 646 ///Use GraphCopy() instead. 631 /// \brief Assignment of a graph to another one is \e not allowed. 632 /// Use GraphCopy instead. 647 633 void operator=(const SmartGraph &) {} 648 634 … … 655 641 SmartGraph() {} 656 642 657 /// Add a new node to the graph.658 659 /// Adda new node to the graph.643 /// \brief Add a new node to the graph. 644 /// 645 /// This function adds a new node to the graph. 660 646 /// \return The new node. 661 647 Node addNode() { return Parent::addNode(); } 662 648 663 ///Add a new edge to the graph. 664 665 ///Add a new edge to the graph with node \c s 666 ///and \c t. 667 ///\return The new edge. 668 Edge addEdge(const Node& s, const Node& t) { 669 return Parent::addEdge(s, t); 649 /// \brief Add a new edge to the graph. 650 /// 651 /// This function adds a new edge to the graph between nodes 652 /// \c u and \c v with inherent orientation from node \c u to 653 /// node \c v. 654 /// \return The new edge. 655 Edge addEdge(Node u, Node v) { 656 return Parent::addEdge(u, v); 670 657 } 671 658 672 659 /// \brief Node validity check 673 660 /// 674 /// This function gives back true if the given node is valid,675 /// i e. it is a real node of the graph.661 /// This function gives back \c true if the given node is valid, 662 /// i.e. it is a real node of the graph. 676 663 /// 677 664 /// \warning A removed node (using Snapshot) could become valid again 678 /// whennew nodes are added to the graph.665 /// if new nodes are added to the graph. 679 666 bool valid(Node n) const { return Parent::valid(n); } 680 667 668 /// \brief Edge validity check 669 /// 670 /// This function gives back \c true if the given edge is valid, 671 /// i.e. it is a real edge of the graph. 672 /// 673 /// \warning A removed edge (using Snapshot) could become valid again 674 /// if new edges are added to the graph. 675 bool valid(Edge e) const { return Parent::valid(e); } 676 681 677 /// \brief Arc validity check 682 678 /// 683 /// This function gives back true if the given arc is valid,684 /// i e. it is a real arc of the graph.679 /// This function gives back \c true if the given arc is valid, 680 /// i.e. it is a real arc of the graph. 685 681 /// 686 682 /// \warning A removed arc (using Snapshot) could become valid again 687 /// whennew edges are added to the graph.683 /// if new edges are added to the graph. 688 684 bool valid(Arc a) const { return Parent::valid(a); } 689 685 690 /// \brief Edge validity check691 ///692 /// This function gives back true if the given edge is valid,693 /// ie. it is a real edge of the graph.694 ///695 /// \warning A removed edge (using Snapshot) could become valid again696 /// when new edges are added to the graph.697 bool valid(Edge e) const { return Parent::valid(e); }698 699 686 ///Clear the graph. 700 687 701 /// Erase all the nodes and edges from the graph.688 ///This function erases all nodes and arcs from the graph. 702 689 /// 703 690 void clear() { 704 691 Parent::clear(); 705 692 } 693 694 /// Reserve memory for nodes. 695 696 /// Using this function, it is possible to avoid superfluous memory 697 /// allocation: if you know that the graph you want to build will 698 /// be large (e.g. it will contain millions of nodes and/or edges), 699 /// then it is worth reserving space for this amount before starting 700 /// to build the graph. 701 /// \sa reserveEdge() 702 void reserveNode(int n) { nodes.reserve(n); }; 703 704 /// Reserve memory for edges. 705 706 /// Using this function, it is possible to avoid superfluous memory 707 /// allocation: if you know that the graph you want to build will 708 /// be large (e.g. it will contain millions of nodes and/or edges), 709 /// then it is worth reserving space for this amount before starting 710 /// to build the graph. 711 /// \sa reserveNode() 712 void reserveEdge(int m) { arcs.reserve(2 * m); }; 706 713 707 714 public: … … 743 750 public: 744 751 745 ///Class to make a snapshot of the digraph and to restrore to it later. 746 747 ///Class to make a snapshot of the digraph and to restrore to it later. 748 /// 749 ///The newly added nodes and arcs can be removed using the 750 ///restore() function. 751 /// 752 ///\note After you restore a state, you cannot restore 753 ///a later state, in other word you cannot add again the arcs deleted 754 ///by restore() using another one Snapshot instance. 755 /// 756 ///\warning If you do not use correctly the snapshot that can cause 757 ///either broken program, invalid state of the digraph, valid but 758 ///not the restored digraph or no change. Because the runtime performance 759 ///the validity of the snapshot is not stored. 752 ///Class to make a snapshot of the graph and to restore it later. 753 754 ///Class to make a snapshot of the graph and to restore it later. 755 /// 756 ///The newly added nodes and edges can be removed using the 757 ///restore() function. This is the only way for deleting nodes and/or 758 ///edges from a SmartGraph structure. 759 /// 760 ///\note After a state is restored, you cannot restore a later state, 761 ///i.e. you cannot add the removed nodes and edges again using 762 ///another Snapshot instance. 763 /// 764 ///\warning The validity of the snapshot is not stored due to 765 ///performance reasons. If you do not use the snapshot correctly, 766 ///it can cause broken program, invalid or not restored state of 767 ///the graph or no change. 760 768 class Snapshot 761 769 { … … 769 777 770 778 ///Default constructor. 771 ///To actually make a snapshot you must call save(). 772 /// 779 ///You have to call save() to actually make a snapshot. 773 780 Snapshot() : _graph(0) {} 774 781 ///Constructor that immediately makes a snapshot 775 782 776 /// This constructor immediately makes a snapshot of the digraph.777 /// \param graph The digraph we make a snapshot of.778 Snapshot(SmartGraph &gr aph) {779 gr aph.saveSnapshot(*this);783 /// This constructor immediately makes a snapshot of the given graph. 784 /// 785 Snapshot(SmartGraph &gr) { 786 gr.saveSnapshot(*this); 780 787 } 781 788 782 789 ///Make a snapshot. 783 790 784 ///Make a snapshot of the graph. 785 /// 786 ///This function can be called more than once. In case of a repeated 791 ///This function makes a snapshot of the given graph. 792 ///It can be called more than once. In case of a repeated 787 793 ///call, the previous snapshot gets lost. 788 ///\param graph The digraph we make the snapshot of. 789 void save(SmartGraph &graph) 794 void save(SmartGraph &gr) 790 795 { 791 graph.saveSnapshot(*this); 792 } 793 794 ///Undo the changes until a snapshot. 795 796 ///Undo the changes until a snapshot created by save(). 797 /// 798 ///\note After you restored a state, you cannot restore 799 ///a later state, in other word you cannot add again the arcs deleted 800 ///by restore(). 796 gr.saveSnapshot(*this); 797 } 798 799 ///Undo the changes until the last snapshot. 800 801 ///This function undos the changes until the last snapshot 802 ///created by save() or Snapshot(SmartGraph&). 801 803 void restore() 802 804 { -
test/digraph_test.cc
r440 r740 36 36 checkGraphArcList(G, 0); 37 37 38 G.reserveNode(3); 39 G.reserveArc(4); 40 38 41 Node 39 42 n1 = G.addNode(), … … 284 287 285 288 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(); 286 297 287 298 checkGraphNodeList(G, 4); … … 376 387 typedef FullDigraph Digraph; 377 388 DIGRAPH_TYPEDEFS(Digraph); 389 378 390 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"); 379 395 380 396 checkGraphNodeList(G, num); -
test/graph_test.cc
r440 r740 39 39 checkGraphArcList(G, 0); 40 40 41 G.reserveNode(3); 42 G.reserveEdge(3); 43 41 44 Node 42 45 n1 = G.addNode(), … … 257 260 258 261 snapshot.restore(); 262 snapshot.save(G); 263 264 checkGraphNodeList(G, 4); 265 checkGraphEdgeList(G, 3); 266 checkGraphArcList(G, 6); 267 268 G.addEdge(G.addNode(), G.addNode()); 269 270 snapshot.restore(); 259 271 260 272 checkGraphNodeList(G, 4); … … 268 280 269 281 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 270 289 checkGraphNodeList(G, num); 271 290 checkGraphEdgeList(G, num * (num - 1) / 2); … … 412 431 check(G.height() == height, "Wrong row number"); 413 432 433 G.resize(width, height); 434 check(G.width() == width, "Wrong column number"); 435 check(G.height() == height, "Wrong row number"); 436 414 437 for (int i = 0; i < width; ++i) { 415 438 for (int j = 0; j < height; ++j) { … … 487 510 488 511 HypercubeGraph G(dim); 512 check(G.dimension() == dim, "Wrong dimension"); 513 514 G.resize(dim); 515 check(G.dimension() == dim, "Wrong dimension"); 516 489 517 checkGraphNodeList(G, 1 << dim); 490 518 checkGraphEdgeList(G, dim * (1 << (dim-1)));
Note: See TracChangeset
for help on using the changeset viewer.