Changeset 626:d11bf7998905 in lemon for lemon/concepts/graph_components.h
 Timestamp:
 04/14/09 10:33:17 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/graph_components.h
r606 r626 32 32 namespace concepts { 33 33 34 /// \brief Skeleton class for graph Node and Arc types35 /// 36 /// This class describes the interface of Node and Arc (andEdge37 /// in undirected graphs) subtypes ofgraph types.34 /// \brief Concept class for \c Node, \c Arc and \c Edge types. 35 /// 36 /// This class describes the concept of \c Node, \c Arc and \c Edge 37 /// subtypes of digraph and graph types. 38 38 /// 39 39 /// \note This class is a template class so that we can use it to 40 /// create graph skeleton classes. The reason for this is than Node 41 /// and Arc types should \em not derive from the same base class. 42 /// For Node you should instantiate it with character 'n' and for Arc 43 /// with 'a'. 44 40 /// create graph skeleton classes. The reason for this is that \c Node 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 42 /// base class. For \c Node you should instantiate it with character 43 /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. 45 44 #ifndef DOXYGEN 46 45 template <char sel = '0'> … … 50 49 /// \brief Default constructor. 51 50 /// 51 /// Default constructor. 52 52 /// \warning The default constructor is not required to set 53 53 /// the item to some welldefined value. So you should consider it 54 54 /// as uninitialized. 55 55 GraphItem() {} 56 56 57 /// \brief Copy constructor. 57 58 /// 58 59 /// Copy constructor. 59 ///60 60 GraphItem(const GraphItem &) {} 61 /// \brief Invalid constructor \& conversion. 62 /// 63 /// This constructor initializes the item to be invalid. 61 62 /// \brief Constructor for conversion from \c INVALID. 63 /// 64 /// Constructor for conversion from \c INVALID. 65 /// It initializes the item to be invalid. 64 66 /// \sa Invalid for more details. 65 67 GraphItem(Invalid) {} 66 /// \brief Assign operator for nodes. 67 /// 68 /// The nodes are assignable. 69 /// 70 GraphItem& operator=(GraphItem const&) { return *this; } 68 69 /// \brief Assignment operator. 70 /// 71 /// Assignment operator for the item. 72 GraphItem& operator=(const GraphItem&) { return *this; } 73 71 74 /// \brief Equality operator. 72 75 /// 73 /// Two iterators are equal if and only if they represents the74 /// same node in the graph or both are invalid.75 bool operator==(GraphItem) const { return false; } 76 /// Equality operator. 77 bool operator==(const GraphItem&) const { return false; } 78 76 79 /// \brief Inequality operator. 77 80 /// 78 /// \sa operator==(const Node& n)79 ///80 bool operator!=(GraphItem) const { return false; } 81 82 /// \brief Artificial ordering operator.83 /// 84 /// To allow the use of graph descriptors as key type in std::map or85 /// similar associative container we require this.81 /// Inequality operator. 82 bool operator!=(const GraphItem&) const { return false; } 83 84 /// \brief Ordering operator. 85 /// 86 /// This operator defines an ordering of the items. 87 /// It makes possible to use graph item types as key types in 88 /// associative containers (e.g. \c std::map). 86 89 /// 87 90 /// \note This operator only have to define some strict ordering of 88 91 /// the items; this order has nothing to do with the iteration 89 92 /// ordering of the items. 90 bool operator<( GraphItem) const { return false; }93 bool operator<(const GraphItem&) const { return false; } 91 94 92 95 template<typename _GraphItem> … … 100 103 101 104 bool b; 102 // b = (ia == ib) && (ia != ib) && (ia < ib);103 105 b = (ia == ib) && (ia != ib); 104 106 b = (ia == INVALID) && (ib != INVALID); … … 111 113 }; 112 114 113 /// \brief An empty base directed graph class. 114 /// 115 /// This class provides the minimal set of features needed for a 116 /// directed graph structure. All digraph concepts have to 117 /// conform to this base directed graph. It just provides types 118 /// for nodes and arcs and functions to get the source and the 119 /// target of the arcs. 115 /// \brief Base skeleton class for directed graphs. 116 /// 117 /// This class describes the base interface of directed graph types. 118 /// All digraph %concepts have to conform to this class. 119 /// It just provides types for nodes and arcs and functions 120 /// to get the source and the target nodes of arcs. 120 121 class BaseDigraphComponent { 121 122 public: … … 125 126 /// \brief Node class of the digraph. 126 127 /// 127 /// This class represents the Nodes of the digraph. 128 /// 128 /// This class represents the nodes of the digraph. 129 129 typedef GraphItem<'n'> Node; 130 130 131 131 /// \brief Arc class of the digraph. 132 132 /// 133 /// This class represents the Arcs of the digraph. 134 /// 135 typedef GraphItem<'e'> Arc; 136 137 /// \brief Gives back the target node of an arc. 138 /// 139 /// Gives back the target node of an arc. 140 /// 141 Node target(const Arc&) const { return INVALID;} 142 143 /// \brief Gives back the source node of an arc. 144 /// 145 /// Gives back the source node of an arc. 146 /// 147 Node source(const Arc&) const { return INVALID;} 148 149 /// \brief Gives back the opposite node on the given arc. 150 /// 151 /// Gives back the opposite node on the given arc. 133 /// This class represents the arcs of the digraph. 134 typedef GraphItem<'a'> Arc; 135 136 /// \brief Return the source node of an arc. 137 /// 138 /// This function returns the source node of an arc. 139 Node source(const Arc&) const { return INVALID; } 140 141 /// \brief Return the target node of an arc. 142 /// 143 /// This function returns the target node of an arc. 144 Node target(const Arc&) const { return INVALID; } 145 146 /// \brief Return the opposite node on the given arc. 147 /// 148 /// This function returns the opposite node on the given arc. 152 149 Node oppositeNode(const Node&, const Arc&) const { 153 150 return INVALID; … … 175 172 }; 176 173 177 /// \brief An empty base undirected graph class. 178 /// 179 /// This class provides the minimal set of features needed for an 180 /// undirected graph structure. All undirected graph concepts have 181 /// to conform to this base graph. It just provides types for 182 /// nodes, arcs and edges and functions to get the 183 /// source and the target of the arcs and edges, 184 /// conversion from arcs to edges and function to get 185 /// both direction of the edges. 174 /// \brief Base skeleton class for undirected graphs. 175 /// 176 /// This class describes the base interface of undirected graph types. 177 /// All graph %concepts have to conform to this class. 178 /// It extends the interface of \ref BaseDigraphComponent with an 179 /// \c Edge type and functions to get the end nodes of edges, 180 /// to convert from arcs to edges and to get both direction of edges. 186 181 class BaseGraphComponent : public BaseDigraphComponent { 187 182 public: 188 183 typedef BaseDigraphComponent::Node Node; 189 184 typedef BaseDigraphComponent::Arc Arc; 190 /// \brief Undirected arc class of the graph. 191 /// 192 /// This class represents the edges of the graph. 193 /// The undirected graphs can be used as a directed graph which 194 /// for each arc contains the opposite arc too so the graph is 195 /// bidirected. The edge represents two opposite 196 /// directed arcs. 197 class Edge : public GraphItem<'u'> { 185 186 /// \brief Undirected edge class of the graph. 187 /// 188 /// This class represents the undirected edges of the graph. 189 /// Undirected graphs can be used as directed graphs, each edge is 190 /// represented by two opposite directed arcs. 191 class Edge : public GraphItem<'e'> { 198 192 public: 199 typedef GraphItem<'u'> Parent; 193 typedef GraphItem<'e'> Parent; 194 200 195 /// \brief Default constructor. 201 196 /// 197 /// Default constructor. 202 198 /// \warning The default constructor is not required to set 203 199 /// the item to some welldefined value. So you should consider it 204 200 /// as uninitialized. 205 201 Edge() {} 202 206 203 /// \brief Copy constructor. 207 204 /// 208 205 /// Copy constructor. 209 ///210 206 Edge(const Edge &) : Parent() {} 211 /// \brief Invalid constructor \& conversion. 212 /// 213 /// This constructor initializes the item to be invalid. 207 208 /// \brief Constructor for conversion from \c INVALID. 209 /// 210 /// Constructor for conversion from \c INVALID. 211 /// It initializes the item to be invalid. 214 212 /// \sa Invalid for more details. 215 213 Edge(Invalid) {} 216 /// \brief Converter from arc to edge. 217 /// 214 215 /// \brief Constructor for conversion from an arc. 216 /// 217 /// Constructor for conversion from an arc. 218 218 /// Besides the core graph item functionality each arc should 219 219 /// be convertible to the represented edge. 220 220 Edge(const Arc&) {} 221 /// \brief Assign arc to edge. 222 /// 221 222 /// \brief Assign an arc to an edge. 223 /// 224 /// This function assigns an arc to an edge. 223 225 /// Besides the core graph item functionality each arc should 224 226 /// be convertible to the represented edge. … … 226 228 }; 227 229 228 /// \brief Returns the direction of the arc. 230 /// \brief Return one end node of an edge. 231 /// 232 /// This function returns one end node of an edge. 233 Node u(const Edge&) const { return INVALID; } 234 235 /// \brief Return the other end node of an edge. 236 /// 237 /// This function returns the other end node of an edge. 238 Node v(const Edge&) const { return INVALID; } 239 240 /// \brief Return a directed arc related to an edge. 241 /// 242 /// This function returns a directed arc from its direction and the 243 /// represented edge. 244 Arc direct(const Edge&, bool) const { return INVALID; } 245 246 /// \brief Return a directed arc related to an edge. 247 /// 248 /// This function returns a directed arc from its source node and the 249 /// represented edge. 250 Arc direct(const Edge&, const Node&) const { return INVALID; } 251 252 /// \brief Return the direction of the arc. 229 253 /// 230 254 /// Returns the direction of the arc. Each arc represents an … … 233 257 bool direction(const Arc&) const { return true; } 234 258 235 /// \brief Returns the directed arc. 236 /// 237 /// Returns the directed arc from its direction and the 238 /// represented edge. 239 Arc direct(const Edge&, bool) const { return INVALID;} 240 241 /// \brief Returns the directed arc. 242 /// 243 /// Returns the directed arc from its source and the 244 /// represented edge. 245 Arc direct(const Edge&, const Node&) const { return INVALID;} 246 247 /// \brief Returns the opposite arc. 248 /// 249 /// Returns the opposite arc. It is the arc representing the 250 /// same edge and has opposite direction. 251 Arc oppositeArc(const Arc&) const { return INVALID;} 252 253 /// \brief Gives back one ending of an edge. 254 /// 255 /// Gives back one ending of an edge. 256 Node u(const Edge&) const { return INVALID;} 257 258 /// \brief Gives back the other ending of an edge. 259 /// 260 /// Gives back the other ending of an edge. 261 Node v(const Edge&) const { return INVALID;} 259 /// \brief Return the opposite arc. 260 /// 261 /// This function returns the opposite arc, i.e. the arc representing 262 /// the same edge and has opposite direction. 263 Arc oppositeArc(const Arc&) const { return INVALID; } 262 264 263 265 template <typename _Graph> … … 269 271 void constraints() { 270 272 checkConcept<BaseDigraphComponent, _Graph>(); 271 checkConcept<GraphItem<' u'>, Edge>();273 checkConcept<GraphItem<'e'>, Edge>(); 272 274 { 273 275 Node n; … … 277 279 n = graph.v(ue); 278 280 e = graph.direct(ue, true); 281 e = graph.direct(ue, false); 279 282 e = graph.direct(ue, n); 280 283 e = graph.oppositeArc(e); … … 290 293 }; 291 294 292 /// \brief An empty idable base digraph class.293 /// 294 /// This class provides beside the core digraph features295 /// core id functions for the digraph structure.296 /// The most of the base digraphs should conform to this concept.297 /// Th e id's are unique and immutable.295 /// \brief Skeleton class for \e idable directed graphs. 296 /// 297 /// This class describes the interface of \e idable directed graphs. 298 /// It extends \ref BaseDigraphComponent with the core ID functions. 299 /// The ids of the items must be unique and immutable. 300 /// This concept is part of the Digraph concept. 298 301 template <typename BAS = BaseDigraphComponent> 299 302 class IDableDigraphComponent : public BAS { … … 304 307 typedef typename Base::Arc Arc; 305 308 306 /// \brief Gives back an unique integer id for the Node. 307 /// 308 /// Gives back an unique integer id for the Node. 309 /// 310 int id(const Node&) const { return 1;} 311 312 /// \brief Gives back the node by the unique id. 313 /// 314 /// Gives back the node by the unique id. 315 /// If the digraph does not contain node with the given id 316 /// then the result of the function is undetermined. 317 Node nodeFromId(int) const { return INVALID;} 318 319 /// \brief Gives back an unique integer id for the Arc. 320 /// 321 /// Gives back an unique integer id for the Arc. 322 /// 323 int id(const Arc&) const { return 1;} 324 325 /// \brief Gives back the arc by the unique id. 326 /// 327 /// Gives back the arc by the unique id. 328 /// If the digraph does not contain arc with the given id 329 /// then the result of the function is undetermined. 330 Arc arcFromId(int) const { return INVALID;} 331 332 /// \brief Gives back an integer greater or equal to the maximum 333 /// Node id. 334 /// 335 /// Gives back an integer greater or equal to the maximum Node 336 /// id. 337 int maxNodeId() const { return 1;} 338 339 /// \brief Gives back an integer greater or equal to the maximum 340 /// Arc id. 341 /// 342 /// Gives back an integer greater or equal to the maximum Arc 343 /// id. 344 int maxArcId() const { return 1;} 309 /// \brief Return a unique integer id for the given node. 310 /// 311 /// This function returns a unique integer id for the given node. 312 int id(const Node&) const { return 1; } 313 314 /// \brief Return the node by its unique id. 315 /// 316 /// This function returns the node by its unique id. 317 /// If the digraph does not contain a node with the given id, 318 /// then the result of the function is undefined. 319 Node nodeFromId(int) const { return INVALID; } 320 321 /// \brief Return a unique integer id for the given arc. 322 /// 323 /// This function returns a unique integer id for the given arc. 324 int id(const Arc&) const { return 1; } 325 326 /// \brief Return the arc by its unique id. 327 /// 328 /// This function returns the arc by its unique id. 329 /// If the digraph does not contain an arc with the given id, 330 /// then the result of the function is undefined. 331 Arc arcFromId(int) const { return INVALID; } 332 333 /// \brief Return an integer greater or equal to the maximum 334 /// node id. 335 /// 336 /// This function returns an integer greater or equal to the 337 /// maximum node id. 338 int maxNodeId() const { return 1; } 339 340 /// \brief Return an integer greater or equal to the maximum 341 /// arc id. 342 /// 343 /// This function returns an integer greater or equal to the 344 /// maximum arc id. 345 int maxArcId() const { return 1; } 345 346 346 347 template <typename _Digraph> … … 368 369 }; 369 370 370 /// \brief An empty idable base undirected graph class. 371 /// 372 /// This class provides beside the core undirected graph features 373 /// core id functions for the undirected graph structure. The 374 /// most of the base undirected graphs should conform to this 375 /// concept. The id's are unique and immutable. 371 /// \brief Skeleton class for \e idable undirected graphs. 372 /// 373 /// This class describes the interface of \e idable undirected 374 /// graphs. It extends \ref IDableDigraphComponent with the core ID 375 /// functions of undirected graphs. 376 /// The ids of the items must be unique and immutable. 377 /// This concept is part of the Graph concept. 376 378 template <typename BAS = BaseGraphComponent> 377 379 class IDableGraphComponent : public IDableDigraphComponent<BAS> { … … 383 385 using IDableDigraphComponent<Base>::id; 384 386 385 /// \brief Gives back an unique integer id for the Edge. 386 /// 387 /// Gives back an unique integer id for the Edge. 388 /// 389 int id(const Edge&) const { return 1;} 390 391 /// \brief Gives back the edge by the unique id. 392 /// 393 /// Gives back the edge by the unique id. If the 394 /// graph does not contain arc with the given id then the 395 /// result of the function is undetermined. 396 Edge edgeFromId(int) const { return INVALID;} 397 398 /// \brief Gives back an integer greater or equal to the maximum 399 /// Edge id. 400 /// 401 /// Gives back an integer greater or equal to the maximum Edge 402 /// id. 403 int maxEdgeId() const { return 1;} 387 /// \brief Return a unique integer id for the given edge. 388 /// 389 /// This function returns a unique integer id for the given edge. 390 int id(const Edge&) const { return 1; } 391 392 /// \brief Return the edge by its unique id. 393 /// 394 /// This function returns the edge by its unique id. 395 /// If the graph does not contain an edge with the given id, 396 /// then the result of the function is undefined. 397 Edge edgeFromId(int) const { return INVALID; } 398 399 /// \brief Return an integer greater or equal to the maximum 400 /// edge id. 401 /// 402 /// This function returns an integer greater or equal to the 403 /// maximum edge id. 404 int maxEdgeId() const { return 1; } 404 405 405 406 template <typename _Graph> … … 407 408 408 409 void constraints() { 409 checkConcept<Base, _Graph >();410 410 checkConcept<IDableDigraphComponent<Base>, _Graph >(); 411 411 typename _Graph::Edge edge; … … 421 421 }; 422 422 423 /// \brief Skeleton class for graph NodeIt and ArcIt424 /// 425 /// Skeleton class for graph NodeIt and ArcIt.426 /// 423 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. 424 /// 425 /// This class describes the concept of \c NodeIt, \c ArcIt and 426 /// \c EdgeIt subtypes of digraph and graph types. 427 427 template <typename GR, typename Item> 428 428 class GraphItemIt : public Item { … … 430 430 /// \brief Default constructor. 431 431 /// 432 /// @warning The default constructor sets the iterator 433 /// to an undefined value. 432 /// Default constructor. 433 /// \warning The default constructor is not required to set 434 /// the iterator to some welldefined value. So you should consider it 435 /// as uninitialized. 434 436 GraphItemIt() {} 437 435 438 /// \brief Copy constructor. 436 439 /// 437 440 /// Copy constructor. 438 /// 439 GraphItemIt(const GraphItemIt& ) {} 440 /// \brief Sets the iterator to the first item. 441 /// 442 /// Sets the iterator to the first item of \c the graph. 443 /// 441 GraphItemIt(const GraphItemIt& it) : Item(it) {} 442 443 /// \brief Constructor that sets the iterator to the first item. 444 /// 445 /// Constructor that sets the iterator to the first item. 444 446 explicit GraphItemIt(const GR&) {} 445 /// \brief Invalid constructor \& conversion. 446 /// 447 /// This constructor initializes the item to be invalid. 447 448 /// \brief Constructor for conversion from \c INVALID. 449 /// 450 /// Constructor for conversion from \c INVALID. 451 /// It initializes the iterator to be invalid. 448 452 /// \sa Invalid for more details. 449 453 GraphItemIt(Invalid) {} 450 /// \brief Assign operator for items. 451 /// 452 /// The items are assignable.453 /// 454 455 /// \brief Assignment operator. 456 /// 457 /// Assignment operator for the iterator. 454 458 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 455 /// \brief Next item. 456 /// 457 /// Assign the iterator to the next item. 458 /// 459 460 /// \brief Increment the iterator. 461 /// 462 /// This operator increments the iterator, i.e. assigns it to the 463 /// next item. 459 464 GraphItemIt& operator++() { return *this; } 465 460 466 /// \brief Equality operator 461 467 /// 468 /// Equality operator. 462 469 /// Two iterators are equal if and only if they point to the 463 470 /// same object or both are invalid. 464 471 bool operator==(const GraphItemIt&) const { return true;} 472 465 473 /// \brief Inequality operator 466 474 /// 467 /// \sa operator==(Node n) 468 /// 475 /// Inequality operator. 476 /// Two iterators are equal if and only if they point to the 477 /// same object or both are invalid. 469 478 bool operator!=(const GraphItemIt&) const { return true;} 470 479 … … 472 481 struct Constraints { 473 482 void constraints() { 483 checkConcept<GraphItem<>, _GraphItemIt>(); 474 484 _GraphItemIt it1(g); 475 485 _GraphItemIt it2; 486 _GraphItemIt it3 = it1; 487 _GraphItemIt it4 = INVALID; 476 488 477 489 it2 = ++it1; … … 482 494 bi = it2; 483 495 } 484 GR& g; 485 }; 486 }; 487 488 /// \brief Skeleton class for graph InArcIt and OutArcIt 489 /// 490 /// \note Because InArcIt and OutArcIt may not inherit from the same 491 /// base class, the \c sel is a additional template parameter (selector). 492 /// For InArcIt you should instantiate it with character 'i' and for 493 /// OutArcIt with 'o'. 496 const GR& g; 497 }; 498 }; 499 500 /// \brief Concept class for \c InArcIt, \c OutArcIt and 501 /// \c IncEdgeIt types. 502 /// 503 /// This class describes the concept of \c InArcIt, \c OutArcIt 504 /// and \c IncEdgeIt subtypes of digraph and graph types. 505 /// 506 /// \note Since these iterator classes do not inherit from the same 507 /// base class, there is an additional template parameter (selector) 508 /// \c sel. For \c InArcIt you should instantiate it with character 509 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. 494 510 template <typename GR, 495 511 typename Item = typename GR::Arc, … … 500 516 /// \brief Default constructor. 501 517 /// 502 /// @warning The default constructor sets the iterator 503 /// to an undefined value. 518 /// Default constructor. 519 /// \warning The default constructor is not required to set 520 /// the iterator to some welldefined value. So you should consider it 521 /// as uninitialized. 504 522 GraphIncIt() {} 523 505 524 /// \brief Copy constructor. 506 525 /// 507 526 /// Copy constructor. 508 /// 509 GraphIncIt(GraphIncIt const& gi) : Item(gi) {} 510 /// \brief Sets the iterator to the first arc incoming into or outgoing 511 /// from the node. 512 /// 513 /// Sets the iterator to the first arc incoming into or outgoing 514 /// from the node. 515 /// 527 GraphIncIt(const GraphIncIt& it) : Item(it) {} 528 529 /// \brief Constructor that sets the iterator to the first 530 /// incoming or outgoing arc. 531 /// 532 /// Constructor that sets the iterator to the first arc 533 /// incoming to or outgoing from the given node. 516 534 explicit GraphIncIt(const GR&, const Base&) {} 517 /// \brief Invalid constructor \& conversion. 518 /// 519 /// This constructor initializes the item to be invalid. 535 536 /// \brief Constructor for conversion from \c INVALID. 537 /// 538 /// Constructor for conversion from \c INVALID. 539 /// It initializes the iterator to be invalid. 520 540 /// \sa Invalid for more details. 521 541 GraphIncIt(Invalid) {} 522 /// \brief Assign operator for iterators. 523 /// 524 /// The iterators are assignable. 525 /// 526 GraphIncIt& operator=(GraphIncIt const&) { return *this; } 527 /// \brief Next item. 528 /// 529 /// Assign the iterator to the next item. 530 /// 542 543 /// \brief Assignment operator. 544 /// 545 /// Assignment operator for the iterator. 546 GraphIncIt& operator=(const GraphIncIt&) { return *this; } 547 548 /// \brief Increment the iterator. 549 /// 550 /// This operator increments the iterator, i.e. assigns it to the 551 /// next arc incoming to or outgoing from the given node. 531 552 GraphIncIt& operator++() { return *this; } 532 553 533 554 /// \brief Equality operator 534 555 /// 556 /// Equality operator. 535 557 /// Two iterators are equal if and only if they point to the 536 558 /// same object or both are invalid. … … 539 561 /// \brief Inequality operator 540 562 /// 541 /// \sa operator==(Node n) 542 /// 563 /// Inequality operator. 564 /// Two iterators are equal if and only if they point to the 565 /// same object or both are invalid. 543 566 bool operator!=(const GraphIncIt&) const { return true;} 544 567 … … 549 572 _GraphIncIt it1(graph, node); 550 573 _GraphIncIt it2; 574 _GraphIncIt it3 = it1; 575 _GraphIncIt it4 = INVALID; 551 576 552 577 it2 = ++it1; … … 555 580 Item e = it1; 556 581 e = it2; 557 558 } 559 560 Item arc; 561 Base node; 562 GR graph; 563 _GraphIncIt it; 564 }; 565 }; 566 567 568 /// \brief An empty iterable digraph class. 569 /// 570 /// This class provides beside the core digraph features 571 /// iterator based iterable interface for the digraph structure. 582 } 583 const Base& node; 584 const GR& graph; 585 }; 586 }; 587 588 /// \brief Skeleton class for iterable directed graphs. 589 /// 590 /// This class describes the interface of iterable directed 591 /// graphs. It extends \ref BaseDigraphComponent with the core 592 /// iterable interface. 572 593 /// This concept is part of the Digraph concept. 573 594 template <typename BAS = BaseDigraphComponent> … … 584 605 /// \name Base iteration 585 606 /// 586 /// This interface provides functions for iteration on digraph items 607 /// This interface provides functions for iteration on digraph items. 587 608 /// 588 609 /// @{ 589 610 590 /// \brief Gives back the first node in the iterating order. 591 /// 592 /// Gives back the first node in the iterating order. 593 /// 611 /// \brief Return the first node. 612 /// 613 /// This function gives back the first node in the iteration order. 594 614 void first(Node&) const {} 595 615 596 /// \brief Gives back the next node in the iterating order. 597 /// 598 /// Gives back the next node in the iterating order. 599 /// 616 /// \brief Return the next node. 617 /// 618 /// This function gives back the next node in the iteration order. 600 619 void next(Node&) const {} 601 620 602 /// \brief Gives back the first arc in the iterating order. 603 /// 604 /// Gives back the first arc in the iterating order. 605 /// 621 /// \brief Return the first arc. 622 /// 623 /// This function gives back the first arc in the iteration order. 606 624 void first(Arc&) const {} 607 625 608 /// \brief Gives back the next arc in the iterating order. 609 /// 610 /// Gives back the next arc in the iterating order. 611 /// 626 /// \brief Return the next arc. 627 /// 628 /// This function gives back the next arc in the iteration order. 612 629 void next(Arc&) const {} 613 630 614 615 /// \brief Gives back the first of the arcs point to the given 616 /// node. 617 /// 618 /// Gives back the first of the arcs point to the given node. 619 /// 631 /// \brief Return the first arc incomming to the given node. 632 /// 633 /// This function gives back the first arc incomming to the 634 /// given node. 620 635 void firstIn(Arc&, const Node&) const {} 621 636 622 /// \brief Gives back the next of the arcs points to the given 623 /// node. 624 /// 625 /// Gives back the next of the arcs points to the given node. 626 /// 637 /// \brief Return the next arc incomming to the given node. 638 /// 639 /// This function gives back the next arc incomming to the 640 /// given node. 627 641 void nextIn(Arc&) const {} 628 642 629 /// \brief Gives back the first of the arcs start from the 643 /// \brief Return the first arc outgoing form the given node. 644 /// 645 /// This function gives back the first arc outgoing form the 630 646 /// given node. 631 ///632 /// Gives back the first of the arcs start from the given node.633 ///634 647 void firstOut(Arc&, const Node&) const {} 635 648 636 /// \brief Gives back the next of the arcs start from the given 637 /// node. 638 /// 639 /// Gives back the next of the arcs start from the given node. 640 /// 649 /// \brief Return the next arc outgoing form the given node. 650 /// 651 /// This function gives back the next arc outgoing form the 652 /// given node. 641 653 void nextOut(Arc&) const {} 642 654 … … 645 657 /// \name Class based iteration 646 658 /// 647 /// This interface provides functions for iteration on digraph items659 /// This interface provides iterator classes for digraph items. 648 660 /// 649 661 /// @{ … … 655 667 typedef GraphItemIt<Digraph, Node> NodeIt; 656 668 657 /// \brief This iterator goes through each node.658 /// 659 /// This iterator goes through each node.669 /// \brief This iterator goes through each arc. 670 /// 671 /// This iterator goes through each arc. 660 672 /// 661 673 typedef GraphItemIt<Digraph, Arc> ArcIt; … … 663 675 /// \brief This iterator goes trough the incoming arcs of a node. 664 676 /// 665 /// This iterator goes trough the \e inc coming arcs of a certain node677 /// This iterator goes trough the \e incoming arcs of a certain node 666 678 /// of a digraph. 667 679 typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt; … … 675 687 /// \brief The base node of the iterator. 676 688 /// 677 /// Gives back the base node of the iterator.678 /// It is always the target of the pointed arc.689 /// This function gives back the base node of the iterator. 690 /// It is always the target node of the pointed arc. 679 691 Node baseNode(const InArcIt&) const { return INVALID; } 680 692 681 693 /// \brief The running node of the iterator. 682 694 /// 683 /// Gives back the running node of the iterator.684 /// It is always the source of the pointed arc.695 /// This function gives back the running node of the iterator. 696 /// It is always the source node of the pointed arc. 685 697 Node runningNode(const InArcIt&) const { return INVALID; } 686 698 687 699 /// \brief The base node of the iterator. 688 700 /// 689 /// Gives back the base node of the iterator.690 /// It is always the source of the pointed arc.701 /// This function gives back the base node of the iterator. 702 /// It is always the source node of the pointed arc. 691 703 Node baseNode(const OutArcIt&) const { return INVALID; } 692 704 693 705 /// \brief The running node of the iterator. 694 706 /// 695 /// Gives back the running node of the iterator.696 /// It is always the target of the pointed arc.707 /// This function gives back the running node of the iterator. 708 /// It is always the target node of the pointed arc. 697 709 Node runningNode(const OutArcIt&) const { return INVALID; } 698 710 … … 736 748 737 749 typename _Digraph::Node n; 738 typename _Digraph::InArcIt ieit(INVALID);739 typename _Digraph::OutArcIt oeit(INVALID);740 n = digraph.baseNode(i eit);741 n = digraph.runningNode(i eit);742 n = digraph.baseNode(o eit);743 n = digraph.runningNode(o eit);750 const typename _Digraph::InArcIt iait(INVALID); 751 const typename _Digraph::OutArcIt oait(INVALID); 752 n = digraph.baseNode(iait); 753 n = digraph.runningNode(iait); 754 n = digraph.baseNode(oait); 755 n = digraph.runningNode(oait); 744 756 ignore_unused_variable_warning(n); 745 757 } … … 747 759 748 760 const _Digraph& digraph; 749 750 751 }; 752 753 /// \brief An empty iterable undirected graph class.754 /// 755 /// This class provides beside the core graph features iterator756 /// based iterable interface for the undirected graph structure.761 }; 762 }; 763 764 /// \brief Skeleton class for iterable undirected graphs. 765 /// 766 /// This class describes the interface of iterable undirected 767 /// graphs. It extends \ref IterableDigraphComponent with the core 768 /// iterable interface of undirected graphs. 757 769 /// This concept is part of the Graph concept. 758 770 template <typename BAS = BaseGraphComponent> … … 770 782 /// \name Base iteration 771 783 /// 772 /// This interface provides functions for iteration on graph items 784 /// This interface provides functions for iteration on edges. 785 /// 773 786 /// @{ 774 787 … … 776 789 using IterableDigraphComponent<Base>::next; 777 790 778 /// \brief Gives back the first edge in the iterating 779 /// order. 780 /// 781 /// Gives back the first edge in the iterating order. 782 /// 791 /// \brief Return the first edge. 792 /// 793 /// This function gives back the first edge in the iteration order. 783 794 void first(Edge&) const {} 784 795 785 /// \brief Gives back the next edge in the iterating 786 /// order. 787 /// 788 /// Gives back the next edge in the iterating order. 789 /// 796 /// \brief Return the next edge. 797 /// 798 /// This function gives back the next edge in the iteration order. 790 799 void next(Edge&) const {} 791 800 792 793 /// \brief Gives back the first of the edges from the 801 /// \brief Return the first edge incident to the given node. 802 /// 803 /// This function gives back the first edge incident to the given 804 /// node. The bool parameter gives back the direction for which the 805 /// source node of the directed arc representing the edge is the 794 806 /// given node. 795 ///796 /// Gives back the first of the edges from the given797 /// node. The bool parameter gives back that direction which798 /// gives a good direction of the edge so the source of the799 /// directed arc is the given node.800 807 void firstInc(Edge&, bool&, const Node&) const {} 801 808 … … 803 810 /// given node. 804 811 /// 805 /// Gives back the next of the edges from the given 806 /// node. The bool parameter should be used as the \c firstInc() 807 /// use it. 812 /// This function gives back the next edge incident to the given 813 /// node. The bool parameter should be used as \c firstInc() use it. 808 814 void nextInc(Edge&, bool&) const {} 809 815 … … 815 821 /// \name Class based iteration 816 822 /// 817 /// This interface provides functions for iteration on graph items823 /// This interface provides iterator classes for edges. 818 824 /// 819 825 /// @{ 820 826 821 /// \brief This iterator goes through each node.822 /// 823 /// This iterator goes through each node.827 /// \brief This iterator goes through each edge. 828 /// 829 /// This iterator goes through each edge. 824 830 typedef GraphItemIt<Graph, Edge> EdgeIt; 825 /// \brief This iterator goes trough the incident arcs of a 831 832 /// \brief This iterator goes trough the incident edges of a 826 833 /// node. 827 834 /// 828 /// This iterator goes trough the incident arcs of a certain835 /// This iterator goes trough the incident edges of a certain 829 836 /// node of a graph. 830 typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt; 837 typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt; 838 831 839 /// \brief The base node of the iterator. 832 840 /// 833 /// Gives back the base node of the iterator.841 /// This function gives back the base node of the iterator. 834 842 Node baseNode(const IncEdgeIt&) const { return INVALID; } 835 843 836 844 /// \brief The running node of the iterator. 837 845 /// 838 /// Gives back the running node of the iterator.846 /// This function gives back the running node of the iterator. 839 847 Node runningNode(const IncEdgeIt&) const { return INVALID; } 840 848 … … 865 873 typename _Graph::EdgeIt >(); 866 874 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 867 typename _Graph::Node, ' u'>, typename _Graph::IncEdgeIt>();875 typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>(); 868 876 869 877 typename _Graph::Node n; 870 typename _Graph::IncEdgeIt ueit(INVALID);871 n = graph.baseNode( ueit);872 n = graph.runningNode( ueit);878 const typename _Graph::IncEdgeIt ieit(INVALID); 879 n = graph.baseNode(ieit); 880 n = graph.runningNode(ieit); 873 881 } 874 882 } … … 878 886 }; 879 887 880 /// \brief An empty alteration notifier digraph class. 881 /// 882 /// This class provides beside the core digraph features alteration 883 /// notifier interface for the digraph structure. This implements 888 /// \brief Skeleton class for alterable directed graphs. 889 /// 890 /// This class describes the interface of alterable directed 891 /// graphs. It extends \ref BaseDigraphComponent with the alteration 892 /// notifier interface. It implements 884 893 /// an observernotifier pattern for each digraph item. More 885 894 /// obsevers can be registered into the notifier and whenever an 886 /// alteration occured in the digraph all the observers will 895 /// alteration occured in the digraph all the observers will be 887 896 /// notified about it. 888 897 template <typename BAS = BaseDigraphComponent> … … 895 904 896 905 897 /// The node observer registry.906 /// Node alteration notifier class. 898 907 typedef AlterationNotifier<AlterableDigraphComponent, Node> 899 908 NodeNotifier; 900 /// The arc observer registry.909 /// Arc alteration notifier class. 901 910 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 902 911 ArcNotifier; 903 912 904 /// \brief Gives backthe node alteration notifier.905 /// 906 /// Gives back the node alteration notifier.913 /// \brief Return the node alteration notifier. 914 /// 915 /// This function gives back the node alteration notifier. 907 916 NodeNotifier& notifier(Node) const { 908 return NodeNotifier();917 return NodeNotifier(); 909 918 } 910 919 911 /// \brief Gives backthe arc alteration notifier.912 /// 913 /// Gives back the arc alteration notifier.920 /// \brief Return the arc alteration notifier. 921 /// 922 /// This function gives back the arc alteration notifier. 914 923 ArcNotifier& notifier(Arc) const { 915 924 return ArcNotifier(); … … 931 940 932 941 const _Digraph& digraph; 933 934 }; 935 936 }; 937 938 /// \brief An empty alteration notifier undirected graph class. 939 /// 940 /// This class provides beside the core graph features alteration 941 /// notifier interface for the graph structure. This implements 942 /// an observernotifier pattern for each graph item. More 942 }; 943 }; 944 945 /// \brief Skeleton class for alterable undirected graphs. 946 /// 947 /// This class describes the interface of alterable undirected 948 /// graphs. It extends \ref AlterableDigraphComponent with the alteration 949 /// notifier interface of undirected graphs. It implements 950 /// an observernotifier pattern for the edges. More 943 951 /// obsevers can be registered into the notifier and whenever an 944 /// alteration occured in the graph all the observers will 952 /// alteration occured in the graph all the observers will be 945 953 /// notified about it. 946 954 template <typename BAS = BaseGraphComponent> … … 952 960 953 961 954 /// The arc observer registry.962 /// Edge alteration notifier class. 955 963 typedef AlterationNotifier<AlterableGraphComponent, Edge> 956 964 EdgeNotifier; 957 965 958 /// \brief Gives back the arcalteration notifier.959 /// 960 /// Gives back the arcalteration notifier.966 /// \brief Return the edge alteration notifier. 967 /// 968 /// This function gives back the edge alteration notifier. 961 969 EdgeNotifier& notifier(Edge) const { 962 970 return EdgeNotifier(); … … 966 974 struct Constraints { 967 975 void constraints() { 968 checkConcept<Alterable GraphComponent<Base>, _Graph>();976 checkConcept<AlterableDigraphComponent<Base>, _Graph>(); 969 977 typename _Graph::EdgeNotifier& uen 970 978 = graph.notifier(typename _Graph::Edge()); … … 976 984 }; 977 985 978 /// \brief C lass describing the concept of graph maps979 /// 980 /// This class describes the co mmon interface of the graph maps981 /// (NodeMap, ArcMap), that is maps that can be used to982 /// associate data to graph descriptors (nodes or arcs).986 /// \brief Concept class for standard graph maps. 987 /// 988 /// This class describes the concept of standard graph maps, i.e. 989 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 990 /// graph types, which can be used for associating data to graph items. 983 991 template <typename GR, typename K, typename V> 984 992 class GraphMap : public ReadWriteMap<K, V> { … … 1000 1008 /// \brief Construct a new map with default value. 1001 1009 /// 1002 /// Construct a new map for the graph and initali se the values.1010 /// Construct a new map for the graph and initalize the values. 1003 1011 GraphMap(const Graph&, const Value&) {} 1004 1012 … … 1009 1017 GraphMap(const GraphMap&) : Parent() {} 1010 1018 1011 /// \brief Assign operator.1012 /// 1013 /// Assign operator. It does not mofify the underlying graph,1019 /// \brief Assignment operator. 1020 /// 1021 /// Assignment operator. It does not mofify the underlying graph, 1014 1022 /// it just iterates on the current item set and set the map 1015 1023 /// with the value returned by the assigned map. … … 1025 1033 void constraints() { 1026 1034 checkConcept<ReadWriteMap<Key, Value>, _Map >(); 1027 // Construction with a graph parameter1028 _Map a(g);1029 // Constructor with a graph and a default value parameter1030 _Map a2(g,t);1031 // Copy constructor.1032 // _Map b(c); 1033 1035 _Map m1(g); 1036 _Map m2(g,t); 1037 1038 // Copy constructor 1039 // _Map m3(m); 1040 1041 // Assignment operator 1034 1042 // ReadMap<Key, Value> cmap; 1035 // b= cmap;1036 1037 ignore_unused_variable_warning( a);1038 ignore_unused_variable_warning( a2);1039 // ignore_unused_variable_warning( b);1040 } 1041 1042 const _Map & c;1043 // m3 = cmap; 1044 1045 ignore_unused_variable_warning(m1); 1046 ignore_unused_variable_warning(m2); 1047 // ignore_unused_variable_warning(m3); 1048 } 1049 1050 const _Map &m; 1043 1051 const Graph &g; 1044 1052 const typename GraphMap::Value &t; … … 1047 1055 }; 1048 1056 1049 /// \brief An empty mappable digraph class. 1050 /// 1051 /// This class provides beside the core digraph features 1052 /// map interface for the digraph structure. 1057 /// \brief Skeleton class for mappable directed graphs. 1058 /// 1059 /// This class describes the interface of mappable directed graphs. 1060 /// It extends \ref BaseDigraphComponent with the standard digraph 1061 /// map classes, namely \c NodeMap and \c ArcMap. 1053 1062 /// This concept is part of the Digraph concept. 1054 1063 template <typename BAS = BaseDigraphComponent> … … 1062 1071 typedef MappableDigraphComponent Digraph; 1063 1072 1064 /// \brief ReadWrite map of the nodes. 1065 /// 1066 /// ReadWrite map of the nodes. 1067 /// 1073 /// \brief Standard graph map for the nodes. 1074 /// 1075 /// Standard graph map for the nodes. 1068 1076 template <typename V> 1069 class NodeMap : public GraphMap< Digraph, Node, V> {1077 class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> { 1070 1078 public: 1071 1079 typedef GraphMap<MappableDigraphComponent, Node, V> Parent; … … 1079 1087 /// \brief Construct a new map with default value. 1080 1088 /// 1081 /// Construct a new map for the digraph and initali se the values.1089 /// Construct a new map for the digraph and initalize the values. 1082 1090 NodeMap(const MappableDigraphComponent& digraph, const V& value) 1083 1091 : Parent(digraph, value) {} … … 1089 1097 NodeMap(const NodeMap& nm) : Parent(nm) {} 1090 1098 1091 /// \brief Assign operator.1092 /// 1093 /// Assign operator.1099 /// \brief Assignment operator. 1100 /// 1101 /// Assignment operator. 1094 1102 template <typename CMap> 1095 1103 NodeMap& operator=(const CMap&) { … … 1100 1108 }; 1101 1109 1102 /// \brief ReadWrite map of the arcs. 1103 /// 1104 /// ReadWrite map of the arcs. 1105 /// 1110 /// \brief Standard graph map for the arcs. 1111 /// 1112 /// Standard graph map for the arcs. 1106 1113 template <typename V> 1107 class ArcMap : public GraphMap< Digraph, Arc, V> {1114 class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> { 1108 1115 public: 1109 1116 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent; … … 1117 1124 /// \brief Construct a new map with default value. 1118 1125 /// 1119 /// Construct a new map for the digraph and initali se the values.1126 /// Construct a new map for the digraph and initalize the values. 1120 1127 ArcMap(const MappableDigraphComponent& digraph, const V& value) 1121 1128 : Parent(digraph, value) {} … … 1127 1134 ArcMap(const ArcMap& nm) : Parent(nm) {} 1128 1135 1129 /// \brief Assign operator.1130 /// 1131 /// Assign operator.1136 /// \brief Assignment operator. 1137 /// 1138 /// Assignment operator. 1132 1139 template <typename CMap> 1133 1140 ArcMap& operator=(const CMap&) { … … 1179 1186 } 1180 1187 1181 _Digraph& digraph; 1182 }; 1183 }; 1184 1185 /// \brief An empty mappable base bipartite graph class. 1186 /// 1187 /// This class provides beside the core graph features 1188 /// map interface for the graph structure. 1188 const _Digraph& digraph; 1189 }; 1190 }; 1191 1192 /// \brief Skeleton class for mappable undirected graphs. 1193 /// 1194 /// This class describes the interface of mappable undirected graphs. 1195 /// It extends \ref MappableDigraphComponent with the standard graph 1196 /// map class for edges (\c EdgeMap). 1189 1197 /// This concept is part of the Graph concept. 1190 1198 template <typename BAS = BaseGraphComponent> … … 1197 1205 typedef MappableGraphComponent Graph; 1198 1206 1199 /// \brief ReadWrite map of the edges. 1200 /// 1201 /// ReadWrite map of the edges. 1202 /// 1207 /// \brief Standard graph map for the edges. 1208 /// 1209 /// Standard graph map for the edges. 1203 1210 template <typename V> 1204 class EdgeMap : public GraphMap< Graph, Edge, V> {1211 class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> { 1205 1212 public: 1206 1213 typedef GraphMap<MappableGraphComponent, Edge, V> Parent; … … 1214 1221 /// \brief Construct a new map with default value. 1215 1222 /// 1216 /// Construct a new map for the graph and initali se the values.1223 /// Construct a new map for the graph and initalize the values. 1217 1224 EdgeMap(const MappableGraphComponent& graph, const V& value) 1218 1225 : Parent(graph, value) {} … … 1224 1231 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1225 1232 1226 /// \brief Assign operator.1227 /// 1228 /// Assign operator.1233 /// \brief Assignment operator. 1234 /// 1235 /// Assignment operator. 1229 1236 template <typename CMap> 1230 1237 EdgeMap& operator=(const CMap&) { … … 1246 1253 1247 1254 void constraints() { 1248 checkConcept<Mappable GraphComponent<Base>, _Graph>();1255 checkConcept<MappableDigraphComponent<Base>, _Graph>(); 1249 1256 1250 1257 { // int map test … … 1263 1270 } 1264 1271 1265 _Graph& graph;1266 }; 1267 }; 1268 1269 /// \brief An empty extendable digraph class.1270 /// 1271 /// This class provides beside the core digraph features digraph1272 /// extendable interface for the digraph structure. The main1273 /// difference between the base and this interface is that the1274 /// digraph alterations should handled already on this level.1272 const _Graph& graph; 1273 }; 1274 }; 1275 1276 /// \brief Skeleton class for extendable directed graphs. 1277 /// 1278 /// This class describes the interface of extendable directed graphs. 1279 /// It extends \ref BaseDigraphComponent with functions for adding 1280 /// nodes and arcs to the digraph. 1281 /// This concept requires \ref AlterableDigraphComponent. 1275 1282 template <typename BAS = BaseDigraphComponent> 1276 1283 class ExtendableDigraphComponent : public BAS { … … 1281 1288 typedef typename Base::Arc Arc; 1282 1289 1283 /// \brief Adds a new node to the digraph. 1284 /// 1285 /// Adds a new node to the digraph. 1286 /// 1290 /// \brief Add a new node to the digraph. 1291 /// 1292 /// This function adds a new node to the digraph. 1287 1293 Node addNode() { 1288 1294 return INVALID; 1289 1295 } 1290 1296 1291 /// \brief Adds a new arc connects the given two nodes. 1292 /// 1293 /// Adds a new arc connects the the given two nodes. 1297 /// \brief Add a new arc connecting the given two nodes. 1298 /// 1299 /// This function adds a new arc connecting the given two nodes 1300 /// of the digraph. 1294 1301 Arc addArc(const Node&, const Node&) { 1295 1302 return INVALID; … … 1311 1318 }; 1312 1319 1313 /// \brief An empty extendable base undirected graph class. 1314 /// 1315 /// This class provides beside the core undirected graph features 1316 /// core undircted graph extend interface for the graph structure. 1317 /// The main difference between the base and this interface is 1318 /// that the graph alterations should handled already on this 1319 /// level. 1320 /// \brief Skeleton class for extendable undirected graphs. 1321 /// 1322 /// This class describes the interface of extendable undirected graphs. 1323 /// It extends \ref BaseGraphComponent with functions for adding 1324 /// nodes and edges to the graph. 1325 /// This concept requires \ref AlterableGraphComponent. 1320 1326 template <typename BAS = BaseGraphComponent> 1321 1327 class ExtendableGraphComponent : public BAS { … … 1326 1332 typedef typename Base::Edge Edge; 1327 1333 1328 /// \brief Adds a new node to the graph. 1329 /// 1330 /// Adds a new node to the graph. 1331 /// 1334 /// \brief Add a new node to the digraph. 1335 /// 1336 /// This function adds a new node to the digraph. 1332 1337 Node addNode() { 1333 1338 return INVALID; 1334 1339 } 1335 1340 1336 /// \brief Adds a new arc connects the given two nodes. 1337 /// 1338 /// Adds a new arc connects the the given two nodes. 1339 Edge addArc(const Node&, const Node&) { 1341 /// \brief Add a new edge connecting the given two nodes. 1342 /// 1343 /// This function adds a new edge connecting the given two nodes 1344 /// of the graph. 1345 Edge addEdge(const Node&, const Node&) { 1340 1346 return INVALID; 1341 1347 } … … 1356 1362 }; 1357 1363 1358 /// \brief An empty erasable digraph class.1359 /// 1360 /// This class provides beside the core digraph features core erase1361 /// functions for the digraph structure. The main difference between1362 /// the base and this interface is that the digraph alterations1363 /// should handled already on this level.1364 /// \brief Skeleton class for erasable directed graphs. 1365 /// 1366 /// This class describes the interface of erasable directed graphs. 1367 /// It extends \ref BaseDigraphComponent with functions for removing 1368 /// nodes and arcs from the digraph. 1369 /// This concept requires \ref AlterableDigraphComponent. 1364 1370 template <typename BAS = BaseDigraphComponent> 1365 1371 class ErasableDigraphComponent : public BAS { … … 1372 1378 /// \brief Erase a node from the digraph. 1373 1379 /// 1374 /// Erase a node from the digraph. This function should1375 /// erase all arcs connectingto the node.1380 /// This function erases the given node from the digraph and all arcs 1381 /// connected to the node. 1376 1382 void erase(const Node&) {} 1377 1383 1378 1384 /// \brief Erase an arc from the digraph. 1379 1385 /// 1380 /// Erase an arc from the digraph. 1381 /// 1386 /// This function erases the given arc from the digraph. 1382 1387 void erase(const Arc&) {} 1383 1388 … … 1386 1391 void constraints() { 1387 1392 checkConcept<Base, _Digraph>(); 1388 typename _Digraph::Node node;1393 const typename _Digraph::Node node(INVALID); 1389 1394 digraph.erase(node); 1390 typename _Digraph::Arc arc;1395 const typename _Digraph::Arc arc(INVALID); 1391 1396 digraph.erase(arc); 1392 1397 } … … 1396 1401 }; 1397 1402 1398 /// \brief An empty erasable base undirected graph class.1399 /// 1400 /// This class provides beside the core undirected graph features1401 /// core erase functions for the undirceted graph structure. The1402 /// main difference between the base and this interface is that1403 /// the graph alterations should handled already on this level.1403 /// \brief Skeleton class for erasable undirected graphs. 1404 /// 1405 /// This class describes the interface of erasable undirected graphs. 1406 /// It extends \ref BaseGraphComponent with functions for removing 1407 /// nodes and edges from the graph. 1408 /// This concept requires \ref AlterableGraphComponent. 1404 1409 template <typename BAS = BaseGraphComponent> 1405 1410 class ErasableGraphComponent : public BAS { … … 1412 1417 /// \brief Erase a node from the graph. 1413 1418 /// 1414 /// Erase a node from the graph. This function should erase1415 /// arcs connectingto the node.1419 /// This function erases the given node from the graph and all edges 1420 /// connected to the node. 1416 1421 void erase(const Node&) {} 1417 1422 1418 /// \brief Erase an arc from the graph. 1419 /// 1420 /// Erase an arc from the graph. 1421 /// 1423 /// \brief Erase an edge from the digraph. 1424 /// 1425 /// This function erases the given edge from the digraph. 1422 1426 void erase(const Edge&) {} 1423 1427 … … 1426 1430 void constraints() { 1427 1431 checkConcept<Base, _Graph>(); 1428 typename _Graph::Node node;1432 const typename _Graph::Node node(INVALID); 1429 1433 graph.erase(node); 1430 typename _Graph::Edge edge;1434 const typename _Graph::Edge edge(INVALID); 1431 1435 graph.erase(edge); 1432 1436 } … … 1436 1440 }; 1437 1441 1438 /// \brief An empty clearable base digraph class.1439 /// 1440 /// This class provides beside the core digraph features core clear1441 /// functions for the digraph structure. The main difference between1442 /// the base and this interface is that the digraph alterations1443 /// should handled already on this level.1442 /// \brief Skeleton class for clearable directed graphs. 1443 /// 1444 /// This class describes the interface of clearable directed graphs. 1445 /// It extends \ref BaseDigraphComponent with a function for clearing 1446 /// the digraph. 1447 /// This concept requires \ref AlterableDigraphComponent. 1444 1448 template <typename BAS = BaseDigraphComponent> 1445 1449 class ClearableDigraphComponent : public BAS { … … 1450 1454 /// \brief Erase all nodes and arcs from the digraph. 1451 1455 /// 1452 /// Erase all nodes and arcs from the digraph. 1453 /// 1456 /// This function erases all nodes and arcs from the digraph. 1454 1457 void clear() {} 1455 1458 … … 1461 1464 } 1462 1465 1463 _Digraph digraph;1464 }; 1465 }; 1466 1467 /// \brief An empty clearable base undirected graph class.1468 /// 1469 /// This class provides beside the core undirected graph features1470 /// core clear functions for the undirected graph structure. The1471 /// main difference between the base and this interface is that1472 /// the graph alterations should handled already on this level.1466 _Digraph& digraph; 1467 }; 1468 }; 1469 1470 /// \brief Skeleton class for clearable undirected graphs. 1471 /// 1472 /// This class describes the interface of clearable undirected graphs. 1473 /// It extends \ref BaseGraphComponent with a function for clearing 1474 /// the graph. 1475 /// This concept requires \ref AlterableGraphComponent. 1473 1476 template <typename BAS = BaseGraphComponent> 1474 1477 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> { … … 1477 1480 typedef BAS Base; 1478 1481 1482 /// \brief Erase all nodes and edges from the graph. 1483 /// 1484 /// This function erases all nodes and edges from the graph. 1485 void clear() {} 1486 1479 1487 template <typename _Graph> 1480 1488 struct Constraints { 1481 1489 void constraints() { 1482 checkConcept<ClearableGraphComponent<Base>, _Graph>(); 1483 } 1484 1485 _Graph graph; 1490 checkConcept<Base, _Graph>(); 1491 graph.clear(); 1492 } 1493 1494 _Graph& graph; 1486 1495 }; 1487 1496 };
Note: See TracChangeset
for help on using the changeset viewer.