Changes in lemon/concepts/graph.h [263:be8a861d3bb7:781:bd72f8d20f33] in lemon
- File:
-
- 1 edited
-
lemon/concepts/graph.h (modified) (23 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/graph.h
r263 r781 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 19 19 ///\ingroup graph_concepts 20 20 ///\file 21 ///\brief The concept of Undirected Graphs.22 23 #ifndef LEMON_CONCEPT _GRAPH_H24 #define LEMON_CONCEPT _GRAPH_H21 ///\brief The concept of undirected graphs. 22 23 #ifndef LEMON_CONCEPTS_GRAPH_H 24 #define LEMON_CONCEPTS_GRAPH_H 25 25 26 26 #include <lemon/concepts/graph_components.h> 27 #include <lemon/concepts/graph.h> 27 #include <lemon/concepts/maps.h> 28 #include <lemon/concept_check.h> 28 29 #include <lemon/core.h> 29 30 … … 33 34 /// \ingroup graph_concepts 34 35 /// 35 /// \brief Class describing the concept of Undirected Graphs.36 /// \brief Class describing the concept of undirected graphs. 36 37 /// 37 /// This class describes the common interface of all Undirected38 /// Graphs.38 /// This class describes the common interface of all undirected 39 /// graphs. 39 40 /// 40 /// As all concept describing classes it provides onlyinterface41 /// without any sensible implementation. So any algorithm for42 /// 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 43 44 /// run properly, of course. 45 /// An actual graph implementation like \ref ListGraph or 46 /// \ref SmartGraph may have additional functionality. 44 47 /// 45 /// The LEMON undirected graphs also fulfill the concept of 46 /// directed graphs (\ref lemon::concepts::Digraph "Digraph 47 /// Concept"). Each edges can be seen as two opposite 48 /// directed arc and consequently the undirected graph can be 49 /// seen as the direceted graph of these directed arcs. The 50 /// Graph has the Edge inner class for the edges and 51 /// the Arc type for the directed arcs. The Arc type is 52 /// convertible to Edge or inherited from it so from a directed 53 /// 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. 54 61 /// 55 /// In the sense of the LEMON each edge has a default 56 /// direction (it should be in every computer implementation, 57 /// because the order of edge's nodes defines an 58 /// orientation). With the default orientation we can define that 59 /// the directed arc is forward or backward directed. With the \c 60 /// direction() and \c direct() function we can get the direction 61 /// 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. 62 68 /// 63 /// The EdgeIt is an iterator for the edges. We can use 64 /// the EdgeMap to map values for the edges. The InArcIt and 65 /// OutArcIt iterates on the same edges but with opposite 66 /// direction. The IncEdgeIt iterates also on the same edges 67 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 68 /// 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 69 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 70 81 public: 71 /// \brief The undirected graph should be tagged by the 72 /// UndirectedTag. 73 /// 74 /// The undirected graph should be tagged by the UndirectedTag. This 75 /// 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 76 90 /// specializations for undirected graphs. 77 91 typedef True UndirectedTag; 78 92 79 /// \brief The base type of node iterators, 80 /// or in other words, the trivial node iterator. 81 /// 82 /// This is the base type of each node iterator, 83 /// thus each kind of node iterator converts to this. 84 /// More precisely each kind of node iterator should be inherited 85 /// 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. 86 98 class Node { 87 99 public: 88 100 /// Default constructor 89 101 90 /// @warning The default constructor sets the iterator91 /// to an undefined value.102 /// Default constructor. 103 /// \warning It sets the object to an undefined value. 92 104 Node() { } 93 105 /// Copy constructor. … … 97 109 Node(const Node&) { } 98 110 99 /// Invalid constructor \& conversion.100 101 /// This constructor initializes the iteratorto be invalid.111 /// %Invalid constructor \& conversion. 112 113 /// Initializes the object to be invalid. 102 114 /// \sa Invalid for more details. 103 115 Node(Invalid) { } 104 116 /// Equality operator 105 117 118 /// Equality operator. 119 /// 106 120 /// Two iterators are equal if and only if they point to the 107 /// same object or both are invalid.121 /// same object or both are \c INVALID. 108 122 bool operator==(Node) const { return true; } 109 123 110 124 /// Inequality operator 111 125 112 /// \sa operator==(Node n) 113 /// 126 /// Inequality operator. 114 127 bool operator!=(Node) const { return true; } 115 128 116 129 /// Artificial ordering operator. 117 130 118 /// To allow the use of graph descriptors as key type in std::map or 119 /// similar associative container we require this. 120 /// 121 /// \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 122 134 /// the items; this order has nothing to do with the iteration 123 135 /// ordering of the items. … … 126 138 }; 127 139 128 /// This iterator goes through each node.129 130 /// This iterator goes through each node .140 /// Iterator class for the nodes. 141 142 /// This iterator goes through each node of the graph. 131 143 /// Its usage is quite simple, for example you can count the number 132 /// 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: 133 145 ///\code 134 146 /// int count=0; … … 139 151 /// Default constructor 140 152 141 /// @warning The default constructor sets the iterator142 /// to an undefined value.153 /// Default constructor. 154 /// \warning It sets the iterator to an undefined value. 143 155 NodeIt() { } 144 156 /// Copy constructor. … … 147 159 /// 148 160 NodeIt(const NodeIt& n) : Node(n) { } 149 /// Invalid constructor \& conversion.150 151 /// Initialize the iterator to be invalid.161 /// %Invalid constructor \& conversion. 162 163 /// Initializes the iterator to be invalid. 152 164 /// \sa Invalid for more details. 153 165 NodeIt(Invalid) { } 154 166 /// Sets the iterator to the first node. 155 167 156 /// Sets the iterator to the first node of \c g. 157 /// 158 NodeIt(const Graph&) { } 159 /// Node -> NodeIt conversion. 160 161 /// Sets the iterator to the node of \c the graph pointed by 162 /// the trivial iterator. 163 /// This feature necessitates that each time we 164 /// 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 /// 165 175 NodeIt(const Graph&, const Node&) { } 166 176 /// Next node. … … 172 182 173 183 174 /// The base type of the edge iterators. 175 176 /// The base type of the edge iterators. 177 /// 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. 178 189 class Edge { 179 190 public: 180 191 /// Default constructor 181 192 182 /// @warning The default constructor sets the iterator183 /// to an undefined value.193 /// Default constructor. 194 /// \warning It sets the object to an undefined value. 184 195 Edge() { } 185 196 /// Copy constructor. … … 188 199 /// 189 200 Edge(const Edge&) { } 190 /// Initialize the iterator to be invalid.191 192 /// Initialize the iteratorto be invalid.193 /// 201 /// %Invalid constructor \& conversion. 202 203 /// Initializes the object to be invalid. 204 /// \sa Invalid for more details. 194 205 Edge(Invalid) { } 195 206 /// Equality operator 196 207 208 /// Equality operator. 209 /// 197 210 /// Two iterators are equal if and only if they point to the 198 /// same object or both are invalid.211 /// same object or both are \c INVALID. 199 212 bool operator==(Edge) const { return true; } 200 213 /// Inequality operator 201 214 202 /// \sa operator==(Edge n) 203 /// 215 /// Inequality operator. 204 216 bool operator!=(Edge) const { return true; } 205 217 206 218 /// Artificial ordering operator. 207 219 208 /// To allow the use of graph descriptors as key type in std::map or 209 /// similar associative container we require this. 210 /// 211 /// \note This operator only have to define some strict ordering of 212 /// the items; this order has nothing to do with the iteration 213 /// 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. 214 225 bool operator<(Edge) const { return false; } 215 226 }; 216 227 217 /// This iterator goes through each edge.218 219 /// 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. 220 231 /// Its usage is quite simple, for example you can count the number 221 /// 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: 222 233 ///\code 223 234 /// int count=0; … … 228 239 /// Default constructor 229 240 230 /// @warning The default constructor sets the iterator231 /// to an undefined value.241 /// Default constructor. 242 /// \warning It sets the iterator to an undefined value. 232 243 EdgeIt() { } 233 244 /// Copy constructor. … … 236 247 /// 237 248 EdgeIt(const EdgeIt& e) : Edge(e) { } 238 /// Initialize the iterator to be invalid.239 240 /// Initialize the iterator to be invalid.241 /// 249 /// %Invalid constructor \& conversion. 250 251 /// Initializes the iterator to be invalid. 252 /// \sa Invalid for more details. 242 253 EdgeIt(Invalid) { } 243 /// This constructor sets the iterator to the first edge. 244 245 /// This constructor sets the iterator to the first edge. 246 EdgeIt(const Graph&) { } 247 /// Edge -> EdgeIt conversion 248 249 /// Sets the iterator to the value of the trivial iterator. 250 /// This feature necessitates that each time we 251 /// iterate the edge-set, the iteration order is the 252 /// 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 /// 253 263 EdgeIt(const Graph&, const Edge&) { } 254 264 /// Next edge 255 265 256 266 /// Assign the iterator to the next edge. 267 /// 257 268 EdgeIt& operator++() { return *this; } 258 269 }; 259 270 260 /// \brief This iterator goes trough the incident undirected 261 /// arcs of a node. 262 /// 263 /// This iterator goes trough the incident edges 264 /// of a certain node of a graph. You should assume that the 265 /// loop arcs will be iterated twice. 266 /// 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. 267 275 /// Its usage is quite simple, for example you can compute the 268 /// degree (i.e. count the number of incident arcsof a node \c n269 /// 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. 270 278 /// 271 279 ///\code … … 273 281 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 274 282 ///\endcode 283 /// 284 /// \warning Loop edges will be iterated twice. 275 285 class IncEdgeIt : public Edge { 276 286 public: 277 287 /// Default constructor 278 288 279 /// @warning The default constructor sets the iterator280 /// to an undefined value.289 /// Default constructor. 290 /// \warning It sets the iterator to an undefined value. 281 291 IncEdgeIt() { } 282 292 /// Copy constructor. … … 285 295 /// 286 296 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 287 /// Initialize the iterator to be invalid.288 289 /// Initialize the iterator to be invalid.290 /// 297 /// %Invalid constructor \& conversion. 298 299 /// Initializes the iterator to be invalid. 300 /// \sa Invalid for more details. 291 301 IncEdgeIt(Invalid) { } 292 /// This constructor sets the iterator to first incident arc.293 294 /// This constructor set the iterator to the first incident arc of295 /// 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 /// 296 306 IncEdgeIt(const Graph&, const Node&) { } 297 /// Edge -> IncEdgeIt conversion 298 299 /// Sets the iterator to the value of the trivial iterator \c e. 300 /// This feature necessitates that each time we 301 /// 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 /// 302 311 IncEdgeIt(const Graph&, const Edge&) { } 303 /// Next incident arc304 305 /// Assign the iterator to the next incident arc312 /// Next incident edge 313 314 /// Assign the iterator to the next incident edge 306 315 /// of the corresponding node. 307 316 IncEdgeIt& operator++() { return *this; } 308 317 }; 309 318 310 /// The directed arc type.311 312 /// Th e directed arc type. It can be converted to the313 /// edge or it should be inherited from the undirected314 /// arc.315 class Arc : public Edge{316 public: 317 /// Default constructor 318 319 /// @warning The default constructor sets the iterator320 /// to an undefined value.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. 324 class Arc { 325 public: 326 /// Default constructor 327 328 /// Default constructor. 329 /// \warning It sets the object to an undefined value. 321 330 Arc() { } 322 331 /// Copy constructor. … … 324 333 /// Copy constructor. 325 334 /// 326 Arc(const Arc& e) : Edge(e) { }327 /// Initialize the iterator to be invalid.328 329 /// Initialize the iteratorto be invalid.330 /// 335 Arc(const Arc&) { } 336 /// %Invalid constructor \& conversion. 337 338 /// Initializes the object to be invalid. 339 /// \sa Invalid for more details. 331 340 Arc(Invalid) { } 332 341 /// Equality operator 333 342 343 /// Equality operator. 344 /// 334 345 /// Two iterators are equal if and only if they point to the 335 /// same object or both are invalid.346 /// same object or both are \c INVALID. 336 347 bool operator==(Arc) const { return true; } 337 348 /// Inequality operator 338 349 339 /// \sa operator==(Arc n) 340 /// 350 /// Inequality operator. 341 351 bool operator!=(Arc) const { return true; } 342 352 343 353 /// Artificial ordering operator. 344 354 345 /// To allow the use of graph descriptors as key type in std::map or 346 /// similar associative container we require this. 347 /// 348 /// \note This operator only have to define some strict ordering of 349 /// the items; this order has nothing to do with the iteration 350 /// 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. 351 360 bool operator<(Arc) const { return false; } 352 361 353 }; 354 /// This iterator goes through each directed arc. 355 356 /// This iterator goes through each arc of a graph. 362 /// Converison to \c Edge 363 364 /// Converison to \c Edge. 365 /// 366 operator Edge() const { return Edge(); } 367 }; 368 369 /// Iterator class for the arcs. 370 371 /// This iterator goes through each directed arc of the graph. 357 372 /// Its usage is quite simple, for example you can count the number 358 /// 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: 359 374 ///\code 360 375 /// int count=0; 361 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;376 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count; 362 377 ///\endcode 363 378 class ArcIt : public Arc { … … 365 380 /// Default constructor 366 381 367 /// @warning The default constructor sets the iterator368 /// to an undefined value.382 /// Default constructor. 383 /// \warning It sets the iterator to an undefined value. 369 384 ArcIt() { } 370 385 /// Copy constructor. … … 373 388 /// 374 389 ArcIt(const ArcIt& e) : Arc(e) { } 375 /// Initialize the iterator to be invalid.376 377 /// Initialize the iterator to be invalid.378 /// 390 /// %Invalid constructor \& conversion. 391 392 /// Initializes the iterator to be invalid. 393 /// \sa Invalid for more details. 379 394 ArcIt(Invalid) { } 380 /// This constructor sets the iterator to the first arc. 381 382 /// This constructor sets the iterator to the first arc of \c g. 383 ///@param g the graph 384 ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } 385 /// Arc -> ArcIt conversion 386 387 /// Sets the iterator to the value of the trivial iterator \c e. 388 /// This feature necessitates that each time we 389 /// 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 /// 390 404 ArcIt(const Graph&, const Arc&) { } 391 /// Next arc405 /// Next arc 392 406 393 407 /// Assign the iterator to the next arc. 408 /// 394 409 ArcIt& operator++() { return *this; } 395 410 }; 396 411 397 /// This iterator goes trough the outgoing directedarcs of a node.398 399 /// This iterator goes trough the \e outgoing arcs of a certain node400 /// 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. 401 416 /// Its usage is quite simple, for example you can count the number 402 417 /// of outgoing arcs of a node \c n 403 /// in graph \c g of type \cGraph as follows.418 /// in a graph \c g of type \c %Graph as follows. 404 419 ///\code 405 420 /// int count=0; 406 /// for ( Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;421 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 407 422 ///\endcode 408 409 423 class OutArcIt : public Arc { 410 424 public: 411 425 /// Default constructor 412 426 413 /// @warning The default constructor sets the iterator414 /// to an undefined value.427 /// Default constructor. 428 /// \warning It sets the iterator to an undefined value. 415 429 OutArcIt() { } 416 430 /// Copy constructor. … … 419 433 /// 420 434 OutArcIt(const OutArcIt& e) : Arc(e) { } 421 /// Initialize the iterator to be invalid.422 423 /// Initialize the iterator to be invalid.424 /// 435 /// %Invalid constructor \& conversion. 436 437 /// Initializes the iterator to be invalid. 438 /// \sa Invalid for more details. 425 439 OutArcIt(Invalid) { } 426 /// This constructor sets the iterator to the first outgoing arc. 427 428 /// This constructor sets the iterator to the first outgoing arc of 429 /// the node. 430 ///@param n the node 431 ///@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 /// 432 444 OutArcIt(const Graph& n, const Node& g) { 433 445 ignore_unused_variable_warning(n); 434 446 ignore_unused_variable_warning(g); 435 447 } 436 /// Arc -> OutArcIt conversion 437 438 /// Sets the iterator to the value of the trivial iterator. 439 /// This feature necessitates that each time we 440 /// 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 /// 441 452 OutArcIt(const Graph&, const Arc&) { } 442 /// Next outgoing arc453 /// Next outgoing arc 443 454 444 455 /// Assign the iterator to the next … … 447 458 }; 448 459 449 /// This iterator goes trough the incoming directedarcs of a node.450 451 /// This iterator goes trough the \e incoming arcs of a certain node452 /// 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. 453 464 /// Its usage is quite simple, for example you can count the number 454 /// of outgoing arcs of a node \c n455 /// 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. 456 467 ///\code 457 468 /// int count=0; 458 /// for (Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;469 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 459 470 ///\endcode 460 461 471 class InArcIt : public Arc { 462 472 public: 463 473 /// Default constructor 464 474 465 /// @warning The default constructor sets the iterator466 /// to an undefined value.475 /// Default constructor. 476 /// \warning It sets the iterator to an undefined value. 467 477 InArcIt() { } 468 478 /// Copy constructor. … … 471 481 /// 472 482 InArcIt(const InArcIt& e) : Arc(e) { } 473 /// Initialize the iterator to be invalid.474 475 /// Initialize the iterator to be invalid.476 /// 483 /// %Invalid constructor \& conversion. 484 485 /// Initializes the iterator to be invalid. 486 /// \sa Invalid for more details. 477 487 InArcIt(Invalid) { } 478 /// This constructor sets the iterator to first incoming arc. 479 480 /// This constructor set the iterator to the first incoming arc of 481 /// the node. 482 ///@param n the node 483 ///@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 /// 484 492 InArcIt(const Graph& g, const Node& n) { 485 493 ignore_unused_variable_warning(n); 486 494 ignore_unused_variable_warning(g); 487 495 } 488 /// Arc -> InArcIt conversion 489 490 /// Sets the iterator to the value of the trivial iterator \c e. 491 /// This feature necessitates that each time we 492 /// 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 /// 493 500 InArcIt(const Graph&, const Arc&) { } 494 501 /// Next incoming arc 495 502 496 /// Assign the iterator to the next inarc of the corresponding node.497 /// 503 /// Assign the iterator to the next 504 /// incoming arc of the corresponding node. 498 505 InArcIt& operator++() { return *this; } 499 506 }; 500 507 501 /// \brief Read write map of the nodes to type \c T.502 /// 503 /// ReadWrite map of the nodes to type \c T.504 /// \sa Reference508 /// \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 class NodeMap : public Re adWriteMap< Node, T>513 class NodeMap : public ReferenceMap<Node, T, T&, const T&> 507 514 { 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 515 522 private: 516 523 ///Copy constructor 517 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } 524 NodeMap(const NodeMap& nm) : 525 ReferenceMap<Node, T, T&, const T&>(nm) { } 518 526 ///Assignment operator 519 527 template <typename CMap> … … 524 532 }; 525 533 526 /// \brief Read write map of the directed arcs to type \c T.527 /// 528 /// Reference map of the directed arcs to type \c T.529 /// \sa Reference534 /// \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 class ArcMap : public Re adWriteMap<Arc,T>539 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> 532 540 { 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 541 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { } 550 ArcMap(const ArcMap& em) : 551 ReferenceMap<Arc, T, T&, const T&>(em) { } 542 552 ///Assignment operator 543 553 template <typename CMap> … … 548 558 }; 549 559 550 /// Read write map of the edges to type \c T.551 552 /// Reference map of the arcs to type \c T.553 /// \sa Reference560 /// \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 class EdgeMap : public Re adWriteMap<Edge,T>565 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> 556 566 { 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 565 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {} 576 EdgeMap(const EdgeMap& em) : 577 ReferenceMap<Edge, T, T&, const T&>(em) {} 566 578 ///Assignment operator 567 579 template <typename CMap> … … 572 584 }; 573 585 574 /// \brief Direct the given edge. 575 /// 576 /// Direct the given edge. The returned arc source 577 /// will be the given node. 578 Arc direct(const Edge&, const Node&) const { 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. 595 /// \sa v() 596 /// \sa direction() 597 Node u(Edge) const { return INVALID; } 598 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. 608 /// \sa u() 609 /// \sa direction() 610 Node v(Edge) const { return INVALID; } 611 612 /// \brief The source node of the arc. 613 /// 614 /// Returns the source node of the given arc. 615 Node source(Arc) const { return INVALID; } 616 617 /// \brief The target node of the arc. 618 /// 619 /// Returns the target node of the given arc. 620 Node target(Arc) const { return INVALID; } 621 622 /// \brief The ID of the node. 623 /// 624 /// Returns the ID of the given node. 625 int id(Node) const { return -1; } 626 627 /// \brief The ID of the edge. 628 /// 629 /// Returns the ID of the given edge. 630 int id(Edge) const { return -1; } 631 632 /// \brief The ID of the arc. 633 /// 634 /// Returns the ID of the given arc. 635 int id(Arc) const { return -1; } 636 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. 641 Node nodeFromId(int) const { return INVALID; } 642 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. 647 Edge edgeFromId(int) const { return INVALID; } 648 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. 653 Arc arcFromId(int) const { return INVALID; } 654 655 /// \brief An upper bound on the node IDs. 656 /// 657 /// Returns an upper bound on the node IDs. 658 int maxNodeId() const { return -1; } 659 660 /// \brief An upper bound on the edge IDs. 661 /// 662 /// Returns an upper bound on the edge IDs. 663 int maxEdgeId() const { return -1; } 664 665 /// \brief An upper bound on the arc IDs. 666 /// 667 /// Returns an upper bound on the arc IDs. 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 { 579 683 return INVALID; 580 684 } 581 685 582 /// \brief Direct the given edge. 583 /// 584 /// Direct the given edge. The returned arc 585 /// represents the given edge and the direction comes 586 /// from the bool parameter. The source of the edge and 587 /// the directed arc is the same when the given bool is true. 588 Arc direct(const Edge&, bool) const { 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 { 589 691 return INVALID; 590 692 } 591 693 592 /// \brief Returns true if the arc has default orientation. 593 /// 594 /// Returns whether the given directed arc is same orientation as 595 /// the corresponding edge's default orientation. 596 bool direction(Arc) const { return true; } 597 598 /// \brief Returns the opposite directed arc. 599 /// 600 /// Returns the opposite directed arc. 694 /// \brief The oppositely directed arc. 695 /// 696 /// Returns the oppositely directed arc representing the same edge. 601 697 Arc oppositeArc(Arc) const { return INVALID; } 602 698 603 /// \brief Opposite node on an arc604 /// 605 /// \return the opposite of the given Node on the given Edge699 /// \brief The opposite node on the edge. 700 /// 701 /// Returns the opposite node on the given edge. 606 702 Node oppositeNode(Node, Edge) const { return INVALID; } 607 608 /// \brief First node of the edge.609 ///610 /// \return the first node of the given Edge.611 ///612 /// Naturally edges don't have direction and thus613 /// don't have source and target node. But we use these two methods614 /// to query the two nodes of the arc. The direction of the arc615 /// which arises this way is called the inherent direction of the616 /// edge, and is used to define the "default" direction617 /// of the directed versions of the arcs.618 /// \sa direction619 Node u(Edge) const { return INVALID; }620 621 /// \brief Second node of the edge.622 Node v(Edge) const { return INVALID; }623 624 /// \brief Source node of the directed arc.625 Node source(Arc) const { return INVALID; }626 627 /// \brief Target node of the directed arc.628 Node target(Arc) const { return INVALID; }629 630 /// \brief Returns the id of the node.631 int id(Node) const { return -1; }632 633 /// \brief Returns the id of the edge.634 int id(Edge) const { return -1; }635 636 /// \brief Returns the id of the arc.637 int id(Arc) const { return -1; }638 639 /// \brief Returns the node with the given id.640 ///641 /// \pre The argument should be a valid node id in the graph.642 Node nodeFromId(int) const { return INVALID; }643 644 /// \brief Returns the edge with the given id.645 ///646 /// \pre The argument should be a valid edge id in the graph.647 Edge edgeFromId(int) const { return INVALID; }648 649 /// \brief Returns the arc with the given id.650 ///651 /// \pre The argument should be a valid arc id in the graph.652 Arc arcFromId(int) const { return INVALID; }653 654 /// \brief Returns an upper bound on the node IDs.655 int maxNodeId() const { return -1; }656 657 /// \brief Returns an upper bound on the edge IDs.658 int maxEdgeId() const { return -1; }659 660 /// \brief Returns an upper bound on the arc IDs.661 int maxArcId() const { return -1; }662 703 663 704 void first(Node&) const {} … … 693 734 int maxId(Arc) const { return -1; } 694 735 695 /// \brief Base node of the iterator 696 /// 697 /// Returns the base node (the source in this case) of the iterator 698 Node baseNode(OutArcIt e) const { 699 return source(e); 700 } 701 /// \brief Running node of the iterator 702 /// 703 /// Returns the running node (the target in this case) of the 704 /// iterator 705 Node runningNode(OutArcIt e) const { 706 return target(e); 707 } 708 709 /// \brief Base node of the iterator 710 /// 711 /// Returns the base node (the target in this case) of the iterator 712 Node baseNode(InArcIt e) const { 713 return target(e); 714 } 715 /// \brief Running node of the iterator 716 /// 717 /// Returns the running node (the source in this case) of the 718 /// iterator 719 Node runningNode(InArcIt e) const { 720 return source(e); 721 } 722 723 /// \brief Base node of the iterator 724 /// 725 /// Returns the base node of the iterator 726 Node baseNode(IncEdgeIt) const { 727 return INVALID; 728 } 729 730 /// \brief Running node of the iterator 731 /// 732 /// Returns the running node of the iterator 733 Node runningNode(IncEdgeIt) const { 734 return INVALID; 735 } 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; } 736 769 737 770 template <typename _Graph> 738 771 struct Constraints { 739 772 void constraints() { 773 checkConcept<BaseGraphComponent, _Graph>(); 740 774 checkConcept<IterableGraphComponent<>, _Graph>(); 741 775 checkConcept<IDableGraphComponent<>, _Graph>();
Note: See TracChangeset
for help on using the changeset viewer.
