Changeset 734:bd72f8d20f33 in lemon-1.2 for lemon/concepts/graph.h
- Timestamp:
- 08/23/09 11:07:50 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
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>
Note: See TracChangeset
for help on using the changeset viewer.