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