Changes in lemon/concepts/graph.h [877:141f9c0db4a3:657:bf7928412136] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/graph.h
r877 r657 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 105 * 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.21 ///\brief The concept of Undirected Graphs. 22 22 23 23 #ifndef LEMON_CONCEPTS_GRAPH_H … … 25 25 26 26 #include <lemon/concepts/graph_components.h> 27 #include <lemon/concepts/maps.h>28 #include <lemon/concept_check.h>29 27 #include <lemon/core.h> 30 28 … … 34 32 /// \ingroup graph_concepts 35 33 /// 36 /// \brief Class describing the concept of undirected graphs.34 /// \brief Class describing the concept of Undirected Graphs. 37 35 /// 38 /// This class describes the common interface of all undirected39 /// graphs.36 /// This class describes the common interface of all Undirected 37 /// Graphs. 40 38 /// 41 /// Like all concept classes, it only provides aninterface42 /// without any sensible implementation. So any generalalgorithm for43 /// undirected graph sshould compile with this class, but it will not39 /// As all concept describing classes it provides only interface 40 /// without any sensible implementation. So any algorithm for 41 /// undirected graph should compile with this class, but it will not 44 42 /// run properly, of course. 45 /// An actual graph implementation like \ref ListGraph or46 /// \ref SmartGraph may have additional functionality.47 43 /// 48 /// The undirected graphs also fulfill the concept of \ref Digraph 49 /// "directed graphs", since each edge can also be regarded as two 50 /// oppositely directed arcs. 51 /// Undirected graphs provide an Edge type for the undirected edges and 52 /// an Arc type for the directed arcs. The Arc type is convertible to 53 /// Edge or inherited from it, i.e. the corresponding edge can be 54 /// obtained from an arc. 55 /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt 56 /// and ArcMap classes can be used for the arcs (just like in digraphs). 57 /// Both InArcIt and OutArcIt iterates on the same edges but with 58 /// opposite direction. IncEdgeIt also iterates on the same edges 59 /// as OutArcIt and InArcIt, but it is not convertible to Arc, 60 /// only to Edge. 44 /// The LEMON undirected graphs also fulfill the concept of 45 /// directed graphs (\ref lemon::concepts::Digraph "Digraph 46 /// Concept"). Each edges can be seen as two opposite 47 /// directed arc and consequently the undirected graph can be 48 /// seen as the direceted graph of these directed arcs. The 49 /// Graph has the Edge inner class for the edges and 50 /// the Arc type for the directed arcs. The Arc type is 51 /// convertible to Edge or inherited from it so from a directed 52 /// arc we can get the represented edge. 61 53 /// 62 /// In LEMON, each undirected edge has an inherent orientation. 63 /// Thus it can defined if an arc is forward or backward oriented in 64 /// an undirected graph with respect to this default oriantation of 65 /// the represented edge. 66 /// With the direction() and direct() functions the direction 67 /// of an arc can be obtained and set, respectively. 54 /// In the sense of the LEMON each edge has a default 55 /// direction (it should be in every computer implementation, 56 /// because the order of edge's nodes defines an 57 /// orientation). With the default orientation we can define that 58 /// the directed arc is forward or backward directed. With the \c 59 /// direction() and \c direct() function we can get the direction 60 /// of the directed arc and we can direct an edge. 68 61 /// 69 /// Only nodes and edges can be added to or removed from an undirected 70 /// graph and the corresponding arcs are added or removed automatically. 71 /// 72 /// \sa Digraph 62 /// The EdgeIt is an iterator for the edges. We can use 63 /// the EdgeMap to map values for the edges. The InArcIt and 64 /// OutArcIt iterates on the same edges but with opposite 65 /// direction. The IncEdgeIt iterates also on the same edges 66 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 67 /// to Edge. 73 68 class Graph { 74 private:75 /// Graphs are \e not copy constructible. Use DigraphCopy instead.76 Graph(const Graph&) {}77 /// \brief Assignment of a graph to another one is \e not allowed.78 /// Use DigraphCopy instead.79 void operator=(const Graph&) {}80 81 69 public: 82 /// Default constructor. 83 Graph() {} 84 85 /// \brief Undirected graphs should be tagged with \c UndirectedTag. 86 /// 87 /// Undirected graphs should be tagged with \c UndirectedTag. 88 /// 89 /// This tag helps the \c enable_if technics to make compile time 70 /// \brief The undirected graph should be tagged by the 71 /// UndirectedTag. 72 /// 73 /// The undirected graph should be tagged by the UndirectedTag. This 74 /// tag helps the enable_if technics to make compile time 90 75 /// specializations for undirected graphs. 91 76 typedef True UndirectedTag; 92 77 93 /// The node type of the graph 94 95 /// This class identifies a node of the graph. It also serves 96 /// as a base class of the node iterators, 97 /// thus they convert to this type. 78 /// \brief The base type of node iterators, 79 /// or in other words, the trivial node iterator. 80 /// 81 /// This is the base type of each node iterator, 82 /// thus each kind of node iterator converts to this. 83 /// More precisely each kind of node iterator should be inherited 84 /// from the trivial node iterator. 98 85 class Node { 99 86 public: 100 87 /// Default constructor 101 88 102 /// Default constructor.103 /// \warning It sets the objectto an undefined value.89 /// @warning The default constructor sets the iterator 90 /// to an undefined value. 104 91 Node() { } 105 92 /// Copy constructor. … … 109 96 Node(const Node&) { } 110 97 111 /// %Invalid constructor \& conversion.112 113 /// Initializes the objectto be invalid.98 /// Invalid constructor \& conversion. 99 100 /// This constructor initializes the iterator to be invalid. 114 101 /// \sa Invalid for more details. 115 102 Node(Invalid) { } 116 103 /// Equality operator 117 104 118 /// Equality operator.119 ///120 105 /// Two iterators are equal if and only if they point to the 121 /// same object or both are \c INVALID.106 /// same object or both are invalid. 122 107 bool operator==(Node) const { return true; } 123 108 124 109 /// Inequality operator 125 110 126 /// Inequality operator. 111 /// \sa operator==(Node n) 112 /// 127 113 bool operator!=(Node) const { return true; } 128 114 129 115 /// Artificial ordering operator. 130 116 131 /// Artificial ordering operator. 132 /// 133 /// \note This operator only has to define some strict ordering of 117 /// To allow the use of graph descriptors as key type in std::map or 118 /// similar associative container we require this. 119 /// 120 /// \note This operator only have to define some strict ordering of 134 121 /// the items; this order has nothing to do with the iteration 135 122 /// ordering of the items. … … 138 125 }; 139 126 140 /// Iterator class for the nodes.141 142 /// This iterator goes through each node of the graph.143 /// Its usage is quite simple, for example ,you can count the number144 /// of nodes in a graph \c g of type \c %Graph like this:127 /// This iterator goes through each node. 128 129 /// This iterator goes through each node. 130 /// Its usage is quite simple, for example you can count the number 131 /// of nodes in graph \c g of type \c Graph like this: 145 132 ///\code 146 133 /// int count=0; … … 151 138 /// Default constructor 152 139 153 /// Default constructor.154 /// \warning It sets the iteratorto an undefined value.140 /// @warning The default constructor sets the iterator 141 /// to an undefined value. 155 142 NodeIt() { } 156 143 /// Copy constructor. … … 159 146 /// 160 147 NodeIt(const NodeIt& n) : Node(n) { } 161 /// %Invalid constructor \& conversion.162 163 /// Initialize sthe iterator to be invalid.148 /// Invalid constructor \& conversion. 149 150 /// Initialize the iterator to be invalid. 164 151 /// \sa Invalid for more details. 165 152 NodeIt(Invalid) { } 166 153 /// Sets the iterator to the first node. 167 154 168 /// Sets the iterator to the first node of the given digraph. 169 /// 170 explicit NodeIt(const Graph&) { } 171 /// Sets the iterator to the given node. 172 173 /// Sets the iterator to the given node of the given digraph. 174 /// 155 /// Sets the iterator to the first node of \c g. 156 /// 157 NodeIt(const Graph&) { } 158 /// Node -> NodeIt conversion. 159 160 /// Sets the iterator to the node of \c the graph pointed by 161 /// the trivial iterator. 162 /// This feature necessitates that each time we 163 /// iterate the arc-set, the iteration order is the same. 175 164 NodeIt(const Graph&, const Node&) { } 176 165 /// Next node. … … 182 171 183 172 184 /// The edge type of the graph 185 186 /// This class identifies an edge of the graph. It also serves 187 /// as a base class of the edge iterators, 188 /// thus they will convert to this type. 173 /// The base type of the edge iterators. 174 175 /// The base type of the edge iterators. 176 /// 189 177 class Edge { 190 178 public: 191 179 /// Default constructor 192 180 193 /// Default constructor.194 /// \warning It sets the objectto an undefined value.181 /// @warning The default constructor sets the iterator 182 /// to an undefined value. 195 183 Edge() { } 196 184 /// Copy constructor. … … 199 187 /// 200 188 Edge(const Edge&) { } 201 /// %Invalid constructor \& conversion.202 203 /// Initialize s the objectto be invalid.204 /// \sa Invalid for more details.189 /// Initialize the iterator to be invalid. 190 191 /// Initialize the iterator to be invalid. 192 /// 205 193 Edge(Invalid) { } 206 194 /// Equality operator 207 195 208 /// Equality operator.209 ///210 196 /// Two iterators are equal if and only if they point to the 211 /// same object or both are \c INVALID.197 /// same object or both are invalid. 212 198 bool operator==(Edge) const { return true; } 213 199 /// Inequality operator 214 200 215 /// Inequality operator. 201 /// \sa operator==(Edge n) 202 /// 216 203 bool operator!=(Edge) const { return true; } 217 204 218 205 /// Artificial ordering operator. 219 206 220 /// Artificial ordering operator. 221 /// 222 /// \note This operator only has to define some strict ordering of 223 /// the edges; this order has nothing to do with the iteration 224 /// ordering of the edges. 207 /// To allow the use of graph descriptors as key type in std::map or 208 /// similar associative container we require this. 209 /// 210 /// \note This operator only have to define some strict ordering of 211 /// the items; this order has nothing to do with the iteration 212 /// ordering of the items. 225 213 bool operator<(Edge) const { return false; } 226 214 }; 227 215 228 /// Iterator class for the edges.229 230 /// This iterator goes through each edge of thegraph.231 /// Its usage is quite simple, for example ,you can count the number232 /// of edges in a graph \c g of type \c %Graph as follows:216 /// This iterator goes through each edge. 217 218 /// This iterator goes through each edge of a graph. 219 /// 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: 233 221 ///\code 234 222 /// int count=0; … … 239 227 /// Default constructor 240 228 241 /// Default constructor.242 /// \warning It sets the iteratorto an undefined value.229 /// @warning The default constructor sets the iterator 230 /// to an undefined value. 243 231 EdgeIt() { } 244 232 /// Copy constructor. … … 247 235 /// 248 236 EdgeIt(const EdgeIt& e) : Edge(e) { } 249 /// %Invalid constructor \& conversion.250 251 /// Initialize sthe iterator to be invalid.252 /// \sa Invalid for more details.237 /// Initialize the iterator to be invalid. 238 239 /// Initialize the iterator to be invalid. 240 /// 253 241 EdgeIt(Invalid) { } 254 /// Sets the iterator to the first edge. 255 256 /// Sets the iterator to the first edge of the given graph. 257 /// 258 explicit EdgeIt(const Graph&) { } 259 /// Sets the iterator to the given edge. 260 261 /// Sets the iterator to the given edge of the given graph. 262 /// 242 /// This constructor sets the iterator to the first edge. 243 244 /// This constructor sets the iterator to the first edge. 245 EdgeIt(const Graph&) { } 246 /// Edge -> EdgeIt conversion 247 248 /// Sets the iterator to the value of the trivial iterator. 249 /// This feature necessitates that each time we 250 /// iterate the edge-set, the iteration order is the 251 /// same. 263 252 EdgeIt(const Graph&, const Edge&) { } 264 253 /// Next edge 265 254 266 255 /// Assign the iterator to the next edge. 267 ///268 256 EdgeIt& operator++() { return *this; } 269 257 }; 270 258 271 /// Iterator class for the incident edges of a node. 272 273 /// This iterator goes trough the incident undirected edges 274 /// of a certain node of a graph. 275 /// Its usage is quite simple, for example, you can compute the 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. 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 /// 266 /// Its usage is quite simple, for example you can compute the 267 /// degree (i.e. count the number of incident arcs of a node \c n 268 /// in graph \c g of type \c Graph as follows. 278 269 /// 279 270 ///\code … … 281 272 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 282 273 ///\endcode 283 ///284 /// \warning Loop edges will be iterated twice.285 274 class IncEdgeIt : public Edge { 286 275 public: 287 276 /// Default constructor 288 277 289 /// Default constructor.290 /// \warning It sets the iteratorto an undefined value.278 /// @warning The default constructor sets the iterator 279 /// to an undefined value. 291 280 IncEdgeIt() { } 292 281 /// Copy constructor. … … 295 284 /// 296 285 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 297 /// %Invalid constructor \& conversion.298 299 /// Initialize sthe iterator to be invalid.300 /// \sa Invalid for more details.286 /// Initialize the iterator to be invalid. 287 288 /// Initialize the iterator to be invalid. 289 /// 301 290 IncEdgeIt(Invalid) { } 302 /// Sets the iterator to the first incident edge.303 304 /// Sets the iterator to the first incident edge of the given node.305 /// 291 /// This constructor sets the iterator to first incident arc. 292 293 /// This constructor set the iterator to the first incident arc of 294 /// the node. 306 295 IncEdgeIt(const Graph&, const Node&) { } 307 /// Sets the iterator to the given edge. 308 309 /// Sets the iterator to the given edge of the given graph. 310 /// 296 /// Edge -> IncEdgeIt conversion 297 298 /// Sets the iterator to the value of the trivial iterator \c e. 299 /// This feature necessitates that each time we 300 /// iterate the arc-set, the iteration order is the same. 311 301 IncEdgeIt(const Graph&, const Edge&) { } 312 /// Next incident edge313 314 /// Assign the iterator to the next incident edge302 /// Next incident arc 303 304 /// Assign the iterator to the next incident arc 315 305 /// of the corresponding node. 316 306 IncEdgeIt& operator++() { return *this; } 317 307 }; 318 308 319 /// The arc type of the graph320 321 /// Th is class identifies a directed arc of the graph. It also serves322 /// as a base class of the arc iterators,323 /// thus they will convert to this type.309 /// The directed arc type. 310 311 /// The directed arc type. It can be converted to the 312 /// edge or it should be inherited from the undirected 313 /// edge. 324 314 class Arc { 325 315 public: 326 316 /// Default constructor 327 317 328 /// Default constructor.329 /// \warning It sets the objectto an undefined value.318 /// @warning The default constructor sets the iterator 319 /// to an undefined value. 330 320 Arc() { } 331 321 /// Copy constructor. … … 334 324 /// 335 325 Arc(const Arc&) { } 336 /// %Invalid constructor \& conversion.337 338 /// Initialize s the objectto be invalid.339 /// \sa Invalid for more details.326 /// Initialize the iterator to be invalid. 327 328 /// Initialize the iterator to be invalid. 329 /// 340 330 Arc(Invalid) { } 341 331 /// Equality operator 342 332 343 /// Equality operator.344 ///345 333 /// Two iterators are equal if and only if they point to the 346 /// same object or both are \c INVALID.334 /// same object or both are invalid. 347 335 bool operator==(Arc) const { return true; } 348 336 /// Inequality operator 349 337 350 /// Inequality operator. 338 /// \sa operator==(Arc n) 339 /// 351 340 bool operator!=(Arc) const { return true; } 352 341 353 342 /// Artificial ordering operator. 354 343 355 /// Artificial ordering operator. 356 /// 357 /// \note This operator only has to define some strict ordering of 358 /// the arcs; this order has nothing to do with the iteration 359 /// ordering of the arcs. 344 /// To allow the use of graph descriptors as key type in std::map or 345 /// similar associative container we require this. 346 /// 347 /// \note This operator only have to define some strict ordering of 348 /// the items; this order has nothing to do with the iteration 349 /// ordering of the items. 360 350 bool operator<(Arc) const { return false; } 361 351 362 /// Converison to \c Edge 363 364 /// Converison to \c Edge. 365 /// 352 /// Converison to Edge 366 353 operator Edge() const { return Edge(); } 367 354 }; 368 369 /// Iterator class for the arcs. 370 371 /// This iterator goes through each directed arc of the graph. 372 /// Its usage is quite simple, for example, you can count the number 373 /// of arcs in a graph \c g of type \c %Graph as follows: 355 /// This iterator goes through each directed arc. 356 357 /// This iterator goes through each arc of a graph. 358 /// 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: 374 360 ///\code 375 361 /// int count=0; 376 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;362 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count; 377 363 ///\endcode 378 364 class ArcIt : public Arc { … … 380 366 /// Default constructor 381 367 382 /// Default constructor.383 /// \warning It sets the iteratorto an undefined value.368 /// @warning The default constructor sets the iterator 369 /// to an undefined value. 384 370 ArcIt() { } 385 371 /// Copy constructor. … … 388 374 /// 389 375 ArcIt(const ArcIt& e) : Arc(e) { } 390 /// %Invalid constructor \& conversion.391 392 /// Initialize sthe iterator to be invalid.393 /// \sa Invalid for more details.376 /// Initialize the iterator to be invalid. 377 378 /// Initialize the iterator to be invalid. 379 /// 394 380 ArcIt(Invalid) { } 395 /// Sets the iterator to the first arc. 396 397 /// Sets the iterator to the first arc of the given graph. 398 /// 399 explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } 400 /// Sets the iterator to the given arc. 401 402 /// Sets the iterator to the given arc of the given graph. 403 /// 381 /// This constructor sets the iterator to the first arc. 382 383 /// This constructor sets the iterator to the first arc of \c g. 384 ///@param g the graph 385 ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } 386 /// Arc -> ArcIt conversion 387 388 /// Sets the iterator to the value of the trivial iterator \c e. 389 /// This feature necessitates that each time we 390 /// iterate the arc-set, the iteration order is the same. 404 391 ArcIt(const Graph&, const Arc&) { } 405 /// 392 ///Next arc 406 393 407 394 /// Assign the iterator to the next arc. 408 ///409 395 ArcIt& operator++() { return *this; } 410 396 }; 411 397 412 /// Iterator class for the outgoingarcs of a node.413 414 /// This iterator goes trough the \e outgoing directed arcs of a415 /// certain nodeof a graph.416 /// Its usage is quite simple, for example ,you can count the number398 /// This iterator goes trough the outgoing directed arcs of a node. 399 400 /// This iterator goes trough the \e outgoing arcs of a certain node 401 /// of a graph. 402 /// Its usage is quite simple, for example you can count the number 417 403 /// of outgoing arcs of a node \c n 418 /// in a graph \c g of type \c %Graph as follows.404 /// in graph \c g of type \c Graph as follows. 419 405 ///\code 420 406 /// int count=0; 421 /// for ( Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;407 /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; 422 408 ///\endcode 409 423 410 class OutArcIt : public Arc { 424 411 public: 425 412 /// Default constructor 426 413 427 /// Default constructor.428 /// \warning It sets the iteratorto an undefined value.414 /// @warning The default constructor sets the iterator 415 /// to an undefined value. 429 416 OutArcIt() { } 430 417 /// Copy constructor. … … 433 420 /// 434 421 OutArcIt(const OutArcIt& e) : Arc(e) { } 435 /// %Invalid constructor \& conversion.436 437 /// Initialize sthe iterator to be invalid.438 /// \sa Invalid for more details.422 /// Initialize the iterator to be invalid. 423 424 /// Initialize the iterator to be invalid. 425 /// 439 426 OutArcIt(Invalid) { } 440 /// Sets the iterator to the first outgoing arc. 441 442 /// Sets the iterator to the first outgoing arc of the given node. 443 /// 427 /// This constructor sets the iterator to the first outgoing arc. 428 429 /// This constructor sets the iterator to the first outgoing arc of 430 /// the node. 431 ///@param n the node 432 ///@param g the graph 444 433 OutArcIt(const Graph& n, const Node& g) { 445 434 ignore_unused_variable_warning(n); 446 435 ignore_unused_variable_warning(g); 447 436 } 448 /// Sets the iterator to the given arc. 449 450 /// Sets the iterator to the given arc of the given graph. 451 /// 437 /// Arc -> OutArcIt conversion 438 439 /// Sets the iterator to the value of the trivial iterator. 440 /// This feature necessitates that each time we 441 /// iterate the arc-set, the iteration order is the same. 452 442 OutArcIt(const Graph&, const Arc&) { } 453 /// 443 ///Next outgoing arc 454 444 455 445 /// Assign the iterator to the next … … 458 448 }; 459 449 460 /// Iterator class for the incomingarcs of a node.461 462 /// This iterator goes trough the \e incoming directed arcs of a463 /// certain nodeof a graph.464 /// Its usage is quite simple, for example ,you can count the number465 /// of incoming arcs of a node \c n466 /// in a graph \c g of type \c %Graph as follows.450 /// This iterator goes trough the incoming directed arcs of a node. 451 452 /// This iterator goes trough the \e incoming arcs of a certain node 453 /// of a graph. 454 /// Its usage is quite simple, for example you can count the number 455 /// of outgoing arcs of a node \c n 456 /// in graph \c g of type \c Graph as follows. 467 457 ///\code 468 458 /// int count=0; 469 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;459 /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; 470 460 ///\endcode 461 471 462 class InArcIt : public Arc { 472 463 public: 473 464 /// Default constructor 474 465 475 /// Default constructor.476 /// \warning It sets the iteratorto an undefined value.466 /// @warning The default constructor sets the iterator 467 /// to an undefined value. 477 468 InArcIt() { } 478 469 /// Copy constructor. … … 481 472 /// 482 473 InArcIt(const InArcIt& e) : Arc(e) { } 483 /// %Invalid constructor \& conversion.484 485 /// Initialize sthe iterator to be invalid.486 /// \sa Invalid for more details.474 /// Initialize the iterator to be invalid. 475 476 /// Initialize the iterator to be invalid. 477 /// 487 478 InArcIt(Invalid) { } 488 /// Sets the iterator to the first incoming arc. 489 490 /// Sets the iterator to the first incoming arc of the given node. 491 /// 479 /// This constructor sets the iterator to first incoming arc. 480 481 /// This constructor set the iterator to the first incoming arc of 482 /// the node. 483 ///@param n the node 484 ///@param g the graph 492 485 InArcIt(const Graph& g, const Node& n) { 493 486 ignore_unused_variable_warning(n); 494 487 ignore_unused_variable_warning(g); 495 488 } 496 /// Sets the iterator to the given arc. 497 498 /// Sets the iterator to the given arc of the given graph. 499 /// 489 /// Arc -> InArcIt conversion 490 491 /// Sets the iterator to the value of the trivial iterator \c e. 492 /// This feature necessitates that each time we 493 /// iterate the arc-set, the iteration order is the same. 500 494 InArcIt(const Graph&, const Arc&) { } 501 495 /// Next incoming arc 502 496 503 /// Assign the iterator to the next 504 /// incoming arc of the corresponding node.497 /// Assign the iterator to the next inarc of the corresponding node. 498 /// 505 499 InArcIt& operator++() { return *this; } 506 500 }; 507 501 508 /// \brief Standard graph map type for the nodes. 509 /// 510 /// Standard graph map type for the nodes. 511 /// It conforms to the ReferenceMap concept. 502 /// \brief Reference map of the nodes to type \c T. 503 /// 504 /// Reference map of the nodes to type \c T. 512 505 template<class T> 513 506 class NodeMap : public ReferenceMap<Node, T, T&, const T&> … … 515 508 public: 516 509 517 /// Constructor518 explicitNodeMap(const Graph&) { }519 /// Constructor with given initial value510 ///\e 511 NodeMap(const Graph&) { } 512 ///\e 520 513 NodeMap(const Graph&, T) { } 521 514 … … 532 525 }; 533 526 534 /// \brief Standard graph map type for the arcs. 535 /// 536 /// Standard graph map type for the arcs. 537 /// It conforms to the ReferenceMap concept. 527 /// \brief Reference map of the arcs to type \c T. 528 /// 529 /// Reference map of the arcs to type \c T. 538 530 template<class T> 539 531 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> … … 541 533 public: 542 534 543 /// Constructor544 explicitArcMap(const Graph&) { }545 /// Constructor with given initial value535 ///\e 536 ArcMap(const Graph&) { } 537 ///\e 546 538 ArcMap(const Graph&, T) { } 547 548 539 private: 549 540 ///Copy constructor … … 558 549 }; 559 550 560 /// \brief Standard graph map type for the edges. 561 /// 562 /// Standard graph map type for the edges. 563 /// It conforms to the ReferenceMap concept. 551 /// Reference map of the edges to type \c T. 552 553 /// Reference map of the edges to type \c T. 564 554 template<class T> 565 555 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> … … 567 557 public: 568 558 569 /// Constructor570 explicitEdgeMap(const Graph&) { }571 /// Constructor with given initial value559 ///\e 560 EdgeMap(const Graph&) { } 561 ///\e 572 562 EdgeMap(const Graph&, T) { } 573 574 563 private: 575 564 ///Copy constructor … … 584 573 }; 585 574 586 /// \brief The first node of the edge. 587 /// 588 /// Returns the first node of the given edge. 589 /// 590 /// Edges don't have source and target nodes, however, methods 591 /// u() and v() are used to query the two end-nodes of an edge. 592 /// The orientation of an edge that arises this way is called 593 /// the inherent direction, it is used to define the default 594 /// direction for the corresponding arcs. 575 /// \brief Direct the given edge. 576 /// 577 /// Direct the given edge. The returned arc source 578 /// will be the given node. 579 Arc direct(const Edge&, const Node&) const { 580 return INVALID; 581 } 582 583 /// \brief Direct the given edge. 584 /// 585 /// Direct the given edge. The returned arc 586 /// represents the given edge and the direction comes 587 /// from the bool parameter. The source of the edge and 588 /// the directed arc is the same when the given bool is true. 589 Arc direct(const Edge&, bool) const { 590 return INVALID; 591 } 592 593 /// \brief Returns true if the arc has default orientation. 594 /// 595 /// Returns whether the given directed arc is same orientation as 596 /// the corresponding edge's default orientation. 597 bool direction(Arc) const { return true; } 598 599 /// \brief Returns the opposite directed arc. 600 /// 601 /// Returns the opposite directed arc. 602 Arc oppositeArc(Arc) const { return INVALID; } 603 604 /// \brief Opposite node on an arc 605 /// 606 /// \return The opposite of the given node on the given edge. 607 Node oppositeNode(Node, Edge) const { return INVALID; } 608 609 /// \brief First node of the edge. 610 /// 611 /// \return The first node of the given edge. 612 /// 613 /// Naturally edges don't have direction and thus 614 /// don't have source and target node. However we use \c u() and \c v() 615 /// methods to query the two nodes of the arc. The direction of the 616 /// arc which arises this way is called the inherent direction of the 617 /// edge, and is used to define the "default" direction 618 /// of the directed versions of the arcs. 595 619 /// \sa v() 596 620 /// \sa direction() 597 621 Node u(Edge) const { return INVALID; } 598 622 599 /// \brief The second node of the edge. 600 /// 601 /// Returns the second node of the given edge. 602 /// 603 /// Edges don't have source and target nodes, however, methods 604 /// u() and v() are used to query the two end-nodes of an edge. 605 /// The orientation of an edge that arises this way is called 606 /// the inherent direction, it is used to define the default 607 /// direction for the corresponding arcs. 623 /// \brief Second node of the edge. 624 /// 625 /// \return The second node of the given edge. 626 /// 627 /// Naturally edges don't have direction and thus 628 /// don't have source and target node. However we use \c u() and \c v() 629 /// methods to query the two nodes of the arc. The direction of the 630 /// arc which arises this way is called the inherent direction of the 631 /// edge, and is used to define the "default" direction 632 /// of the directed versions of the arcs. 608 633 /// \sa u() 609 634 /// \sa direction() 610 635 Node v(Edge) const { return INVALID; } 611 636 612 /// \brief The source node of the arc. 613 /// 614 /// Returns the source node of the given arc. 637 /// \brief Source node of the directed arc. 615 638 Node source(Arc) const { return INVALID; } 616 639 617 /// \brief The target node of the arc. 618 /// 619 /// Returns the target node of the given arc. 640 /// \brief Target node of the directed arc. 620 641 Node target(Arc) const { return INVALID; } 621 642 622 /// \brief The ID of the node. 623 /// 624 /// Returns the ID of the given node. 643 /// \brief Returns the id of the node. 625 644 int id(Node) const { return -1; } 626 645 627 /// \brief The ID of the edge. 628 /// 629 /// Returns the ID of the given edge. 646 /// \brief Returns the id of the edge. 630 647 int id(Edge) const { return -1; } 631 648 632 /// \brief The ID of the arc. 633 /// 634 /// Returns the ID of the given arc. 649 /// \brief Returns the id of the arc. 635 650 int id(Arc) const { return -1; } 636 651 637 /// \brief The node with the given ID. 638 /// 639 /// Returns the node with the given ID. 640 /// \pre The argument should be a valid node ID in the graph. 652 /// \brief Returns the node with the given id. 653 /// 654 /// \pre The argument should be a valid node id in the graph. 641 655 Node nodeFromId(int) const { return INVALID; } 642 656 643 /// \brief The edge with the given ID. 644 /// 645 /// Returns the edge with the given ID. 646 /// \pre The argument should be a valid edge ID in the graph. 657 /// \brief Returns the edge with the given id. 658 /// 659 /// \pre The argument should be a valid edge id in the graph. 647 660 Edge edgeFromId(int) const { return INVALID; } 648 661 649 /// \brief The arc with the given ID. 650 /// 651 /// Returns the arc with the given ID. 652 /// \pre The argument should be a valid arc ID in the graph. 662 /// \brief Returns the arc with the given id. 663 /// 664 /// \pre The argument should be a valid arc id in the graph. 653 665 Arc arcFromId(int) const { return INVALID; } 654 666 655 /// \brief An upper bound on the node IDs. 656 /// 657 /// Returns an upper bound on the node IDs. 667 /// \brief Returns an upper bound on the node IDs. 658 668 int maxNodeId() const { return -1; } 659 669 660 /// \brief An upper bound on the edge IDs. 661 /// 662 /// Returns an upper bound on the edge IDs. 670 /// \brief Returns an upper bound on the edge IDs. 663 671 int maxEdgeId() const { return -1; } 664 672 665 /// \brief An upper bound on the arc IDs. 666 /// 667 /// Returns an upper bound on the arc IDs. 673 /// \brief Returns an upper bound on the arc IDs. 668 674 int maxArcId() const { return -1; } 669 670 /// \brief The direction of the arc.671 ///672 /// Returns \c true if the direction of the given arc is the same as673 /// the inherent orientation of the represented edge.674 bool direction(Arc) const { return true; }675 676 /// \brief Direct the edge.677 ///678 /// Direct the given edge. The returned arc679 /// represents the given edge and its direction comes680 /// from the bool parameter. If it is \c true, then the direction681 /// of the arc is the same as the inherent orientation of the edge.682 Arc direct(Edge, bool) const {683 return INVALID;684 }685 686 /// \brief Direct the edge.687 ///688 /// Direct the given edge. The returned arc represents the given689 /// edge and its source node is the given node.690 Arc direct(Edge, Node) const {691 return INVALID;692 }693 694 /// \brief The oppositely directed arc.695 ///696 /// Returns the oppositely directed arc representing the same edge.697 Arc oppositeArc(Arc) const { return INVALID; }698 699 /// \brief The opposite node on the edge.700 ///701 /// Returns the opposite node on the given edge.702 Node oppositeNode(Node, Edge) const { return INVALID; }703 675 704 676 void first(Node&) const {} … … 734 706 int maxId(Arc) const { return -1; } 735 707 736 /// \brief The base node of the iterator. 737 /// 738 /// Returns the base node of the given incident edge iterator. 739 Node baseNode(IncEdgeIt) const { return INVALID; } 740 741 /// \brief The running node of the iterator. 742 /// 743 /// Returns the running node of the given incident edge iterator. 744 Node runningNode(IncEdgeIt) const { return INVALID; } 745 746 /// \brief The base node of the iterator. 747 /// 748 /// Returns the base node of the given outgoing arc iterator 749 /// (i.e. the source node of the corresponding arc). 750 Node baseNode(OutArcIt) const { return INVALID; } 751 752 /// \brief The running node of the iterator. 753 /// 754 /// Returns the running node of the given outgoing arc iterator 755 /// (i.e. the target node of the corresponding arc). 756 Node runningNode(OutArcIt) const { return INVALID; } 757 758 /// \brief The base node of the iterator. 759 /// 760 /// Returns the base node of the given incomming arc iterator 761 /// (i.e. the target node of the corresponding arc). 762 Node baseNode(InArcIt) const { return INVALID; } 763 764 /// \brief The running node of the iterator. 765 /// 766 /// Returns the running node of the given incomming arc iterator 767 /// (i.e. the source node of the corresponding arc). 768 Node runningNode(InArcIt) const { return INVALID; } 708 /// \brief Base node of the iterator 709 /// 710 /// Returns the base node (the source in this case) of the iterator 711 Node baseNode(OutArcIt e) const { 712 return source(e); 713 } 714 /// \brief Running node of the iterator 715 /// 716 /// Returns the running node (the target in this case) of the 717 /// iterator 718 Node runningNode(OutArcIt e) const { 719 return target(e); 720 } 721 722 /// \brief Base node of the iterator 723 /// 724 /// Returns the base node (the target in this case) of the iterator 725 Node baseNode(InArcIt e) const { 726 return target(e); 727 } 728 /// \brief Running node of the iterator 729 /// 730 /// Returns the running node (the source in this case) of the 731 /// iterator 732 Node runningNode(InArcIt e) const { 733 return source(e); 734 } 735 736 /// \brief Base node of the iterator 737 /// 738 /// Returns the base node of the iterator 739 Node baseNode(IncEdgeIt) const { 740 return INVALID; 741 } 742 743 /// \brief Running node of the iterator 744 /// 745 /// Returns the running node of the iterator 746 Node runningNode(IncEdgeIt) const { 747 return INVALID; 748 } 769 749 770 750 template <typename _Graph>
Note: See TracChangeset
for help on using the changeset viewer.