Changes in lemon/concepts/graph_components.h [581:6d3a9eec82b4:631:33c6b6e755cd] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/graph_components.h
r581 r631 21 21 ///\brief The concept of graph components. 22 22 23 24 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H 25 24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H … … 33 32 namespace concepts { 34 33 35 /// \brief Skeleton class for graph Node and Arc types36 /// 37 /// This class describes the interface of Node and Arc (andEdge38 /// 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. 39 38 /// 40 39 /// \note This class is a template class so that we can use it to 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 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'. 46 44 #ifndef DOXYGEN 47 template <char _selector= '0'>45 template <char sel = '0'> 48 46 #endif 49 47 class GraphItem { … … 51 49 /// \brief Default constructor. 52 50 /// 51 /// Default constructor. 53 52 /// \warning The default constructor is not required to set 54 53 /// the item to some well-defined value. So you should consider it 55 54 /// as uninitialized. 56 55 GraphItem() {} 56 57 57 /// \brief Copy constructor. 58 58 /// 59 59 /// Copy constructor. 60 ///61 60 GraphItem(const GraphItem &) {} 62 /// \brief Invalid constructor \& conversion. 63 /// 64 /// 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. 65 66 /// \sa Invalid for more details. 66 67 GraphItem(Invalid) {} 67 /// \brief Assign operator for nodes. 68 /// 69 /// The nodes are assignable. 70 /// 71 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 72 74 /// \brief Equality operator. 73 75 /// 74 /// Two iterators are equal if and only if they represents the75 /// same node in the graph or both are invalid.76 bool operator==(GraphItem) const { return false; } 76 /// Equality operator. 77 bool operator==(const GraphItem&) const { return false; } 78 77 79 /// \brief Inequality operator. 78 80 /// 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 or86 /// 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). 87 89 /// 88 90 /// \note This operator only have to define some strict ordering of 89 91 /// the items; this order has nothing to do with the iteration 90 92 /// ordering of the items. 91 bool operator<( GraphItem) const { return false; }93 bool operator<(const GraphItem&) const { return false; } 92 94 93 95 template<typename _GraphItem> … … 101 103 102 104 bool b; 103 // b = (ia == ib) && (ia != ib) && (ia < ib);104 105 b = (ia == ib) && (ia != ib); 105 106 b = (ia == INVALID) && (ib != INVALID); … … 112 113 }; 113 114 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. 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. 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. 129 /// 128 /// This class represents the nodes of the digraph. 130 129 typedef GraphItem<'n'> Node; 131 130 132 131 /// \brief Arc class of the digraph. 133 132 /// 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. 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. 153 149 Node oppositeNode(const Node&, const Arc&) const { 154 150 return INVALID; … … 176 172 }; 177 173 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. 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. 187 181 class BaseGraphComponent : public BaseDigraphComponent { 188 182 public: 189 183 typedef BaseDigraphComponent::Node Node; 190 184 typedef BaseDigraphComponent::Arc Arc; 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'> { 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'> { 199 192 public: 200 typedef GraphItem<'u'> Parent; 193 typedef GraphItem<'e'> Parent; 194 201 195 /// \brief Default constructor. 202 196 /// 197 /// Default constructor. 203 198 /// \warning The default constructor is not required to set 204 199 /// the item to some well-defined value. So you should consider it 205 200 /// as uninitialized. 206 201 Edge() {} 202 207 203 /// \brief Copy constructor. 208 204 /// 209 205 /// Copy constructor. 210 ///211 206 Edge(const Edge &) : Parent() {} 212 /// \brief Invalid constructor \& conversion. 213 /// 214 /// 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. 215 212 /// \sa Invalid for more details. 216 213 Edge(Invalid) {} 217 /// \brief Converter from arc to edge. 218 /// 214 215 /// \brief Constructor for conversion from an arc. 216 /// 217 /// Constructor for conversion from an arc. 219 218 /// Besides the core graph item functionality each arc should 220 219 /// be convertible to the represented edge. 221 220 Edge(const Arc&) {} 222 /// \brief Assign arc to edge. 223 /// 221 222 /// \brief Assign an arc to an edge. 223 /// 224 /// This function assigns an arc to an edge. 224 225 /// Besides the core graph item functionality each arc should 225 226 /// be convertible to the represented edge. … … 227 228 }; 228 229 229 /// \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. 230 253 /// 231 254 /// Returns the direction of the arc. Each arc represents an … … 234 257 bool direction(const Arc&) const { return true; } 235 258 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;} 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; } 263 264 264 265 template <typename _Graph> … … 270 271 void constraints() { 271 272 checkConcept<BaseDigraphComponent, _Graph>(); 272 checkConcept<GraphItem<' u'>, Edge>();273 checkConcept<GraphItem<'e'>, Edge>(); 273 274 { 274 275 Node n; … … 278 279 n = graph.v(ue); 279 280 e = graph.direct(ue, true); 281 e = graph.direct(ue, false); 280 282 e = graph.direct(ue, n); 281 283 e = graph.oppositeArc(e); … … 291 293 }; 292 294 293 /// \brief An empty idable base digraph class.294 /// 295 /// This class provides beside the core digraph features296 /// core id functions for the digraph structure.297 /// The most of the base digraphs should conform to this concept.298 /// Th e id's are unique and immutable.299 template <typename _Base= BaseDigraphComponent>300 class IDableDigraphComponent : public _Base{301 public: 302 303 typedef _BaseBase;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. 301 template <typename BAS = BaseDigraphComponent> 302 class IDableDigraphComponent : public BAS { 303 public: 304 305 typedef BAS Base; 304 306 typedef typename Base::Node Node; 305 307 typedef typename Base::Arc Arc; 306 308 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;} 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; } 346 346 347 347 template <typename _Digraph> … … 369 369 }; 370 370 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; 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; 382 383 typedef typename Base::Edge Edge; 383 384 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;} 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; } 405 405 406 406 template <typename _Graph> … … 408 408 409 409 void constraints() { 410 checkConcept<Base, _Graph >();411 410 checkConcept<IDableDigraphComponent<Base>, _Graph >(); 412 411 typename _Graph::Edge edge; … … 422 421 }; 423 422 424 /// \brief Skeleton class for graph NodeIt and ArcIt425 /// 426 /// Skeleton class for graph NodeIt and ArcIt.427 /// 428 template <typename _Graph, typename _Item>429 class GraphItemIt : public _Item {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 template <typename GR, typename Item> 428 class GraphItemIt : public Item { 430 429 public: 431 430 /// \brief Default constructor. 432 431 /// 433 /// @warning The default constructor sets the iterator 434 /// to an undefined value. 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. 435 436 GraphItemIt() {} 437 436 438 /// \brief Copy constructor. 437 439 /// 438 440 /// Copy constructor. 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. 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. 449 452 /// \sa Invalid for more details. 450 453 GraphItemIt(Invalid) {} 451 /// \brief Assign operator for items. 452 /// 453 /// The items are assignable.454 /// 454 455 /// \brief Assignment operator. 456 /// 457 /// Assignment operator for the iterator. 455 458 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 456 /// \brief Next item. 457 /// 458 /// Assign the iterator to the next item. 459 /// 459 460 /// \brief Increment the iterator. 461 /// 462 /// This operator increments the iterator, i.e. assigns it to the 463 /// next item. 460 464 GraphItemIt& operator++() { return *this; } 465 461 466 /// \brief Equality operator 462 467 /// 468 /// Equality operator. 463 469 /// Two iterators are equal if and only if they point to the 464 470 /// same object or both are invalid. 465 471 bool operator==(const GraphItemIt&) const { return true;} 472 466 473 /// \brief Inequality operator 467 474 /// 468 /// \sa operator==(Node n) 469 /// 475 /// Inequality operator. 476 /// Two iterators are equal if and only if they point to the 477 /// same object or both are invalid. 470 478 bool operator!=(const GraphItemIt&) const { return true;} 471 479 … … 473 481 struct Constraints { 474 482 void constraints() { 483 checkConcept<GraphItem<>, _GraphItemIt>(); 475 484 _GraphItemIt it1(g); 476 485 _GraphItemIt it2; 486 _GraphItemIt it3 = it1; 487 _GraphItemIt it4 = INVALID; 477 488 478 489 it2 = ++it1; … … 480 491 ++(++it1); 481 492 482 _Item bi = it1;493 Item bi = it1; 483 494 bi = it2; 484 495 } 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 { 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 { 500 515 public: 501 516 /// \brief Default constructor. 502 517 /// 503 /// @warning The default constructor sets the iterator 504 /// to an undefined value. 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. 505 522 GraphIncIt() {} 523 506 524 /// \brief Copy constructor. 507 525 /// 508 526 /// Copy constructor. 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. 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. 521 540 /// \sa Invalid for more details. 522 541 GraphIncIt(Invalid) {} 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 /// 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. 532 552 GraphIncIt& operator++() { return *this; } 533 553 534 554 /// \brief Equality operator 535 555 /// 556 /// Equality operator. 536 557 /// Two iterators are equal if and only if they point to the 537 558 /// same object or both are invalid. … … 540 561 /// \brief Inequality operator 541 562 /// 542 /// \sa operator==(Node n) 543 /// 563 /// Inequality operator. 564 /// Two iterators are equal if and only if they point to the 565 /// same object or both are invalid. 544 566 bool operator!=(const GraphIncIt&) const { return true;} 545 567 … … 547 569 struct Constraints { 548 570 void constraints() { 549 checkConcept<GraphItem< _selector>, _GraphIncIt>();571 checkConcept<GraphItem<sel>, _GraphIncIt>(); 550 572 _GraphIncIt it1(graph, node); 551 573 _GraphIncIt it2; 574 _GraphIncIt it3 = it1; 575 _GraphIncIt it4 = INVALID; 552 576 553 577 it2 = ++it1; 554 578 ++it2 = it1; 555 579 ++(++it1); 556 _Item e = it1;580 Item e = it1; 557 581 e = it2; 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. 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. 573 593 /// This concept is part of the Digraph concept. 574 template <typename _Base= BaseDigraphComponent>575 class IterableDigraphComponent : public _Base{576 577 public: 578 579 typedef _BaseBase;594 template <typename BAS = BaseDigraphComponent> 595 class IterableDigraphComponent : public BAS { 596 597 public: 598 599 typedef BAS Base; 580 600 typedef typename Base::Node Node; 581 601 typedef typename Base::Arc Arc; … … 583 603 typedef IterableDigraphComponent Digraph; 584 604 585 /// \name Base iteration586 /// 587 /// This interface provides functions for iteration on digraph items 605 /// \name Base Iteration 606 /// 607 /// This interface provides functions for iteration on digraph items. 588 608 /// 589 609 /// @{ 590 610 591 /// \brief Gives back the first node in the iterating order. 592 /// 593 /// Gives back the first node in the iterating order. 594 /// 611 /// \brief Return the first node. 612 /// 613 /// This function gives back the first node in the iteration order. 595 614 void first(Node&) const {} 596 615 597 /// \brief Gives back the next node in the iterating order. 598 /// 599 /// Gives back the next node in the iterating order. 600 /// 616 /// \brief Return the next node. 617 /// 618 /// This function gives back the next node in the iteration order. 601 619 void next(Node&) const {} 602 620 603 /// \brief Gives back the first arc in the iterating order. 604 /// 605 /// Gives back the first arc in the iterating order. 606 /// 621 /// \brief Return the first arc. 622 /// 623 /// This function gives back the first arc in the iteration order. 607 624 void first(Arc&) const {} 608 625 609 /// \brief Gives back the next arc in the iterating order. 610 /// 611 /// Gives back the next arc in the iterating order. 612 /// 626 /// \brief Return the next arc. 627 /// 628 /// This function gives back the next arc in the iteration order. 613 629 void next(Arc&) const {} 614 630 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 /// 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. 621 635 void firstIn(Arc&, const Node&) const {} 622 636 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 /// 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. 628 641 void nextIn(Arc&) const {} 629 642 630 /// \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 631 646 /// given node. 632 ///633 /// Gives back the first of the arcs start from the given node.634 ///635 647 void firstOut(Arc&, const Node&) const {} 636 648 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 /// 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. 642 653 void nextOut(Arc&) const {} 643 654 644 655 /// @} 645 656 646 /// \name Class based iteration647 /// 648 /// This interface provides functions for iteration on digraph items657 /// \name Class Based Iteration 658 /// 659 /// This interface provides iterator classes for digraph items. 649 660 /// 650 661 /// @{ … … 656 667 typedef GraphItemIt<Digraph, Node> NodeIt; 657 668 658 /// \brief This iterator goes through each node.659 /// 660 /// This iterator goes through each node.669 /// \brief This iterator goes through each arc. 670 /// 671 /// This iterator goes through each arc. 661 672 /// 662 673 typedef GraphItemIt<Digraph, Arc> ArcIt; … … 664 675 /// \brief This iterator goes trough the incoming arcs of a node. 665 676 /// 666 /// 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 667 678 /// of a digraph. 668 679 typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt; … … 676 687 /// \brief The base node of the iterator. 677 688 /// 678 /// Gives back the base node of the iterator.679 /// 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. 680 691 Node baseNode(const InArcIt&) const { return INVALID; } 681 692 682 693 /// \brief The running node of the iterator. 683 694 /// 684 /// Gives back the running node of the iterator.685 /// 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. 686 697 Node runningNode(const InArcIt&) const { return INVALID; } 687 698 688 699 /// \brief The base node of the iterator. 689 700 /// 690 /// Gives back the base node of the iterator.691 /// 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. 692 703 Node baseNode(const OutArcIt&) const { return INVALID; } 693 704 694 705 /// \brief The running node of the iterator. 695 706 /// 696 /// Gives back the running node of the iterator.697 /// 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. 698 709 Node runningNode(const OutArcIt&) const { return INVALID; } 699 710 … … 737 748 738 749 typename _Digraph::Node n; 739 typename _Digraph::InArcIt ieit(INVALID);740 typename _Digraph::OutArcIt oeit(INVALID);741 n = digraph.baseNode(i eit);742 n = digraph.runningNode(i eit);743 n = digraph.baseNode(o eit);744 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); 745 756 ignore_unused_variable_warning(n); 746 757 } … … 748 759 749 760 const _Digraph& digraph; 750 751 752 }; 753 754 /// \brief An empty iterable undirected graph class.755 /// 756 /// This class provides beside the core graph features iterator757 /// 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. 758 769 /// This concept is part of the Graph concept. 759 template <typename _Base= BaseGraphComponent>760 class IterableGraphComponent : public IterableDigraphComponent< _Base> {761 public: 762 763 typedef _BaseBase;770 template <typename BAS = BaseGraphComponent> 771 class IterableGraphComponent : public IterableDigraphComponent<BAS> { 772 public: 773 774 typedef BAS Base; 764 775 typedef typename Base::Node Node; 765 776 typedef typename Base::Arc Arc; … … 769 780 typedef IterableGraphComponent Graph; 770 781 771 /// \name Base iteration 772 /// 773 /// This interface provides functions for iteration on graph items 782 /// \name Base Iteration 783 /// 784 /// This interface provides functions for iteration on edges. 785 /// 774 786 /// @{ 775 787 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 /// 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. 784 794 void first(Edge&) const {} 785 795 786 /// \brief Gives back the next edge in the iterating 787 /// order. 788 /// 789 /// Gives back the next edge in the iterating order. 790 /// 796 /// \brief Return the next edge. 797 /// 798 /// This function gives back the next edge in the iteration order. 791 799 void next(Edge&) const {} 792 800 793 794 /// \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 795 806 /// given node. 796 ///797 /// Gives back the first of the edges from the given798 /// node. The bool parameter gives back that direction which799 /// gives a good direction of the edge so the source of the800 /// directed arc is the given node.801 807 void firstInc(Edge&, bool&, const Node&) const {} 802 808 … … 804 810 /// given node. 805 811 /// 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. 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. 809 814 void nextInc(Edge&, bool&) const {} 810 815 811 using IterableDigraphComponent< _Base>::baseNode;812 using IterableDigraphComponent< _Base>::runningNode;816 using IterableDigraphComponent<Base>::baseNode; 817 using IterableDigraphComponent<Base>::runningNode; 813 818 814 819 /// @} 815 820 816 /// \name Class based iteration817 /// 818 /// This interface provides functions for iteration on graph items821 /// \name Class Based Iteration 822 /// 823 /// This interface provides iterator classes for edges. 819 824 /// 820 825 /// @{ 821 826 822 /// \brief This iterator goes through each node.823 /// 824 /// This iterator goes through each node.827 /// \brief This iterator goes through each edge. 828 /// 829 /// This iterator goes through each edge. 825 830 typedef GraphItemIt<Graph, Edge> EdgeIt; 826 /// \brief This iterator goes trough the incident arcs of a 831 832 /// \brief This iterator goes trough the incident edges of a 827 833 /// node. 828 834 /// 829 /// This iterator goes trough the incident arcs of a certain835 /// This iterator goes trough the incident edges of a certain 830 836 /// node of a graph. 831 typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt; 837 typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt; 838 832 839 /// \brief The base node of the iterator. 833 840 /// 834 /// Gives back the base node of the iterator.841 /// This function gives back the base node of the iterator. 835 842 Node baseNode(const IncEdgeIt&) const { return INVALID; } 836 843 837 844 /// \brief The running node of the iterator. 838 845 /// 839 /// Gives back the running node of the iterator.846 /// This function gives back the running node of the iterator. 840 847 Node runningNode(const IncEdgeIt&) const { return INVALID; } 841 848 … … 866 873 typename _Graph::EdgeIt >(); 867 874 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 868 typename _Graph::Node, ' u'>, typename _Graph::IncEdgeIt>();875 typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>(); 869 876 870 877 typename _Graph::Node n; 871 typename _Graph::IncEdgeIt ueit(INVALID);872 n = graph.baseNode( ueit);873 n = graph.runningNode( ueit);878 const typename _Graph::IncEdgeIt ieit(INVALID); 879 n = graph.baseNode(ieit); 880 n = graph.runningNode(ieit); 874 881 } 875 882 } 876 883 877 884 const _Graph& graph; 878 879 880 }; 881 882 /// \brief An empty alteration notifier digraph class.883 /// 884 /// This class provides beside the core digraph featuresalteration885 /// notifier interface for the digraph structure. Thisimplements885 }; 886 }; 887 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 886 893 /// an observer-notifier pattern for each digraph item. More 887 894 /// obsevers can be registered into the notifier and whenever an 888 /// alteration occured in the digraph all the observers will 895 /// alteration occured in the digraph all the observers will be 889 896 /// notified about it. 890 template <typename _Base= BaseDigraphComponent>891 class AlterableDigraphComponent : public _Base{892 public: 893 894 typedef _BaseBase;897 template <typename BAS = BaseDigraphComponent> 898 class AlterableDigraphComponent : public BAS { 899 public: 900 901 typedef BAS Base; 895 902 typedef typename Base::Node Node; 896 903 typedef typename Base::Arc Arc; 897 904 898 905 899 /// The node observer registry.906 /// Node alteration notifier class. 900 907 typedef AlterationNotifier<AlterableDigraphComponent, Node> 901 908 NodeNotifier; 902 /// The arc observer registry.909 /// Arc alteration notifier class. 903 910 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 904 911 ArcNotifier; 905 912 906 /// \brief Gives backthe node alteration notifier.907 /// 908 /// Gives back the node alteration notifier.913 /// \brief Return the node alteration notifier. 914 /// 915 /// This function gives back the node alteration notifier. 909 916 NodeNotifier& notifier(Node) const { 910 return NodeNotifier();917 return NodeNotifier(); 911 918 } 912 919 913 /// \brief Gives backthe arc alteration notifier.914 /// 915 /// Gives back the arc alteration notifier.920 /// \brief Return the arc alteration notifier. 921 /// 922 /// This function gives back the arc alteration notifier. 916 923 ArcNotifier& notifier(Arc) const { 917 924 return ArcNotifier(); … … 933 940 934 941 const _Digraph& digraph; 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 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 945 951 /// obsevers can be registered into the notifier and whenever an 946 /// alteration occured in the graph all the observers will 952 /// alteration occured in the graph all the observers will be 947 953 /// notified about it. 948 template <typename _Base= BaseGraphComponent>949 class AlterableGraphComponent : public AlterableDigraphComponent< _Base> {950 public: 951 952 typedef _BaseBase;954 template <typename BAS = BaseGraphComponent> 955 class AlterableGraphComponent : public AlterableDigraphComponent<BAS> { 956 public: 957 958 typedef BAS Base; 953 959 typedef typename Base::Edge Edge; 954 960 955 961 956 /// The arc observer registry.962 /// Edge alteration notifier class. 957 963 typedef AlterationNotifier<AlterableGraphComponent, Edge> 958 964 EdgeNotifier; 959 965 960 /// \brief Gives back the arcalteration notifier.961 /// 962 /// Gives back the arcalteration notifier.966 /// \brief Return the edge alteration notifier. 967 /// 968 /// This function gives back the edge alteration notifier. 963 969 EdgeNotifier& notifier(Edge) const { 964 970 return EdgeNotifier(); … … 968 974 struct Constraints { 969 975 void constraints() { 970 checkConcept<Alterable GraphComponent<Base>, _Graph>();976 checkConcept<AlterableDigraphComponent<Base>, _Graph>(); 971 977 typename _Graph::EdgeNotifier& uen 972 978 = graph.notifier(typename _Graph::Edge()); … … 975 981 976 982 const _Graph& graph; 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; 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; 992 997 993 998 /// The graph type of the map. 994 typedef _GraphGraph;999 typedef GR Graph; 995 1000 /// The key type of the map. 996 typedef _ItemKey;1001 typedef K Key; 997 1002 /// The value type of the map. 998 typedef _Value Value; 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; 999 1011 1000 1012 /// \brief Construct a new map. … … 1004 1016 /// \brief Construct a new map with default value. 1005 1017 /// 1006 /// Construct a new map for the graph and initali se the values.1018 /// Construct a new map for the graph and initalize the values. 1007 1019 GraphMap(const Graph&, const Value&) {} 1008 1020 … … 1013 1025 GraphMap(const GraphMap&) : Parent() {} 1014 1026 1015 /// \brief Assign operator.1016 /// 1017 /// Assign operator. It does not mofify the underlying graph,1027 /// \brief Assignment operator. 1028 /// 1029 /// Assignment operator. It does not mofify the underlying graph, 1018 1030 /// it just iterates on the current item set and set the map 1019 1031 /// with the value returned by the assigned map. … … 1028 1040 struct Constraints { 1029 1041 void constraints() { 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 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 1038 1051 // ReadMap<Key, Value> cmap; 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;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; 1047 1060 const Graph &g; 1048 1061 const typename GraphMap::Value &t; … … 1051 1064 }; 1052 1065 1053 /// \brief An empty mappable digraph class. 1054 /// 1055 /// This class provides beside the core digraph features 1056 /// map interface for the digraph structure. 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. 1057 1071 /// This concept is part of the Digraph concept. 1058 template <typename _Base= BaseDigraphComponent>1059 class MappableDigraphComponent : public _Base{1060 public: 1061 1062 typedef _BaseBase;1072 template <typename BAS = BaseDigraphComponent> 1073 class MappableDigraphComponent : public BAS { 1074 public: 1075 1076 typedef BAS Base; 1063 1077 typedef typename Base::Node Node; 1064 1078 typedef typename Base::Arc Arc; … … 1066 1080 typedef MappableDigraphComponent Digraph; 1067 1081 1068 /// \brief ReadWrite map ofthe nodes.1069 /// 1070 /// ReadWrite map ofthe nodes.1071 /// 1072 template <typename _Value>1073 class NodeMap : public GraphMap< Digraph, Node, _Value> {1082 /// \brief Standard graph map for the nodes. 1083 /// 1084 /// Standard graph map for the nodes. 1085 /// It conforms to the ReferenceMap concept. 1086 template <typename V> 1087 class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> { 1074 1088 public: 1075 typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;1089 typedef GraphMap<MappableDigraphComponent, Node, V> Parent; 1076 1090 1077 1091 /// \brief Construct a new map. … … 1083 1097 /// \brief Construct a new map with default value. 1084 1098 /// 1085 /// Construct a new map for the digraph and initali se the values.1086 NodeMap(const MappableDigraphComponent& digraph, const _Value& value)1099 /// Construct a new map for the digraph and initalize the values. 1100 NodeMap(const MappableDigraphComponent& digraph, const V& value) 1087 1101 : Parent(digraph, value) {} 1088 1102 … … 1093 1107 NodeMap(const NodeMap& nm) : Parent(nm) {} 1094 1108 1095 /// \brief Assign operator.1096 /// 1097 /// Assign operator.1109 /// \brief Assignment operator. 1110 /// 1111 /// Assignment operator. 1098 1112 template <typename CMap> 1099 1113 NodeMap& operator=(const CMap&) { 1100 checkConcept<ReadMap<Node, _Value>, CMap>();1114 checkConcept<ReadMap<Node, V>, CMap>(); 1101 1115 return *this; 1102 1116 } … … 1104 1118 }; 1105 1119 1106 /// \brief ReadWrite map ofthe arcs.1107 /// 1108 /// ReadWrite map ofthe arcs.1109 /// 1110 template <typename _Value>1111 class ArcMap : public GraphMap< Digraph, Arc, _Value> {1120 /// \brief Standard graph map for the arcs. 1121 /// 1122 /// Standard graph map for the arcs. 1123 /// It conforms to the ReferenceMap concept. 1124 template <typename V> 1125 class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> { 1112 1126 public: 1113 typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;1127 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent; 1114 1128 1115 1129 /// \brief Construct a new map. … … 1121 1135 /// \brief Construct a new map with default value. 1122 1136 /// 1123 /// Construct a new map for the digraph and initali se the values.1124 ArcMap(const MappableDigraphComponent& digraph, const _Value& value)1137 /// Construct a new map for the digraph and initalize the values. 1138 ArcMap(const MappableDigraphComponent& digraph, const V& value) 1125 1139 : Parent(digraph, value) {} 1126 1140 … … 1131 1145 ArcMap(const ArcMap& nm) : Parent(nm) {} 1132 1146 1133 /// \brief Assign operator.1134 /// 1135 /// Assign operator.1147 /// \brief Assignment operator. 1148 /// 1149 /// Assignment operator. 1136 1150 template <typename CMap> 1137 1151 ArcMap& operator=(const CMap&) { 1138 checkConcept<ReadMap<Arc, _Value>, CMap>();1152 checkConcept<ReadMap<Arc, V>, CMap>(); 1139 1153 return *this; 1140 1154 } … … 1183 1197 } 1184 1198 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. 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). 1193 1208 /// This concept is part of the Graph concept. 1194 template <typename _Base= BaseGraphComponent>1195 class MappableGraphComponent : public MappableDigraphComponent< _Base> {1196 public: 1197 1198 typedef _BaseBase;1209 template <typename BAS = BaseGraphComponent> 1210 class MappableGraphComponent : public MappableDigraphComponent<BAS> { 1211 public: 1212 1213 typedef BAS Base; 1199 1214 typedef typename Base::Edge Edge; 1200 1215 1201 1216 typedef MappableGraphComponent Graph; 1202 1217 1203 /// \brief ReadWrite map ofthe edges.1204 /// 1205 /// ReadWrite map ofthe edges.1206 /// 1207 template <typename _Value>1208 class EdgeMap : public GraphMap< Graph, Edge, _Value> {1218 /// \brief Standard graph map for the edges. 1219 /// 1220 /// Standard graph map for the edges. 1221 /// It conforms to the ReferenceMap concept. 1222 template <typename V> 1223 class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> { 1209 1224 public: 1210 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;1225 typedef GraphMap<MappableGraphComponent, Edge, V> Parent; 1211 1226 1212 1227 /// \brief Construct a new map. … … 1218 1233 /// \brief Construct a new map with default value. 1219 1234 /// 1220 /// Construct a new map for the graph and initali se the values.1221 EdgeMap(const MappableGraphComponent& graph, const _Value& value)1235 /// Construct a new map for the graph and initalize the values. 1236 EdgeMap(const MappableGraphComponent& graph, const V& value) 1222 1237 : Parent(graph, value) {} 1223 1238 … … 1228 1243 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1229 1244 1230 /// \brief Assign operator.1231 /// 1232 /// Assign operator.1245 /// \brief Assignment operator. 1246 /// 1247 /// Assignment operator. 1233 1248 template <typename CMap> 1234 1249 EdgeMap& operator=(const CMap&) { 1235 checkConcept<ReadMap<Edge, _Value>, CMap>();1250 checkConcept<ReadMap<Edge, V>, CMap>(); 1236 1251 return *this; 1237 1252 } … … 1250 1265 1251 1266 void constraints() { 1252 checkConcept<Mappable GraphComponent<Base>, _Graph>();1267 checkConcept<MappableDigraphComponent<Base>, _Graph>(); 1253 1268 1254 1269 { // int map test … … 1267 1282 } 1268 1283 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 /// 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. 1291 1305 Node addNode() { 1292 1306 return INVALID; 1293 1307 } 1294 1308 1295 /// \brief Adds a new arc connects the given two nodes. 1296 /// 1297 /// Adds a new arc connects the the given two nodes. 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. 1298 1313 Arc addArc(const Node&, const Node&) { 1299 1314 return INVALID; … … 1315 1330 }; 1316 1331 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 /// 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. 1336 1349 Node addNode() { 1337 1350 return INVALID; 1338 1351 } 1339 1352 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&) { 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&) { 1344 1358 return INVALID; 1345 1359 } … … 1360 1374 }; 1361 1375 1362 /// \brief An empty erasable digraph class.1363 /// 1364 /// This class provides beside the core digraph features core erase1365 /// functions for the digraph structure. The main difference between1366 /// the base and this interface is that the digraph alterations1367 /// should handled already on this level.1368 template <typename _Base= BaseDigraphComponent>1369 class ErasableDigraphComponent : public _Base{1370 public: 1371 1372 typedef _BaseBase;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 removing 1380 /// 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 BAS Base; 1373 1387 typedef typename Base::Node Node; 1374 1388 typedef typename Base::Arc Arc; … … 1376 1390 /// \brief Erase a node from the digraph. 1377 1391 /// 1378 /// Erase a node from the digraph. This function should1379 /// erase all arcs connectingto the node.1392 /// This function erases the given node from the digraph and all arcs 1393 /// connected to the node. 1380 1394 void erase(const Node&) {} 1381 1395 1382 1396 /// \brief Erase an arc from the digraph. 1383 1397 /// 1384 /// Erase an arc from the digraph. 1385 /// 1398 /// This function erases the given arc from the digraph. 1386 1399 void erase(const Arc&) {} 1387 1400 … … 1390 1403 void constraints() { 1391 1404 checkConcept<Base, _Digraph>(); 1392 typename _Digraph::Node node;1405 const typename _Digraph::Node node(INVALID); 1393 1406 digraph.erase(node); 1394 typename _Digraph::Arc arc;1407 const typename _Digraph::Arc arc(INVALID); 1395 1408 digraph.erase(arc); 1396 1409 } … … 1400 1413 }; 1401 1414 1402 /// \brief An empty erasable base undirected graph class.1403 /// 1404 /// This class provides beside the core undirected graph features1405 /// core erase functions for the undirceted graph structure. The1406 /// main difference between the base and this interface is that1407 /// the graph alterations should handled already on this level.1408 template <typename _Base= BaseGraphComponent>1409 class ErasableGraphComponent : public _Base{1410 public: 1411 1412 typedef _BaseBase;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 removing 1419 /// 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 BAS Base; 1413 1426 typedef typename Base::Node Node; 1414 1427 typedef typename Base::Edge Edge; … … 1416 1429 /// \brief Erase a node from the graph. 1417 1430 /// 1418 /// Erase a node from the graph. This function should erase1419 /// arcs connectingto the node.1431 /// This function erases the given node from the graph and all edges 1432 /// connected to the node. 1420 1433 void erase(const Node&) {} 1421 1434 1422 /// \brief Erase an arc from the graph. 1423 /// 1424 /// Erase an arc from the graph. 1425 /// 1435 /// \brief Erase an edge from the digraph. 1436 /// 1437 /// This function erases the given edge from the digraph. 1426 1438 void erase(const Edge&) {} 1427 1439 … … 1430 1442 void constraints() { 1431 1443 checkConcept<Base, _Graph>(); 1432 typename _Graph::Node node;1444 const typename _Graph::Node node(INVALID); 1433 1445 graph.erase(node); 1434 typename _Graph::Edge edge;1446 const typename _Graph::Edge edge(INVALID); 1435 1447 graph.erase(edge); 1436 1448 } … … 1440 1452 }; 1441 1453 1442 /// \brief An empty clearable base digraph class.1443 /// 1444 /// This class provides beside the core digraph features core clear1445 /// functions for the digraph structure. The main difference between1446 /// the base and this interface is that the digraph alterations1447 /// should handled already on this level.1448 template <typename _Base= BaseDigraphComponent>1449 class ClearableDigraphComponent : public _Base{1450 public: 1451 1452 typedef _BaseBase;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 clearing 1458 /// the digraph. 1459 /// This concept requires \ref AlterableDigraphComponent. 1460 template <typename BAS = BaseDigraphComponent> 1461 class ClearableDigraphComponent : public BAS { 1462 public: 1463 1464 typedef BAS Base; 1453 1465 1454 1466 /// \brief Erase all nodes and arcs from the digraph. 1455 1467 /// 1456 /// Erase all nodes and arcs from the digraph. 1457 /// 1468 /// This function erases all nodes and arcs from the digraph. 1458 1469 void clear() {} 1459 1470 … … 1465 1476 } 1466 1477 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; 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() {} 1482 1498 1483 1499 template <typename _Graph> 1484 1500 struct Constraints { 1485 1501 void constraints() { 1486 checkConcept<ClearableGraphComponent<Base>, _Graph>(); 1487 } 1488 1489 _Graph graph; 1502 checkConcept<Base, _Graph>(); 1503 graph.clear(); 1504 } 1505 1506 _Graph& graph; 1490 1507 }; 1491 1508 };
Note: See TracChangeset
for help on using the changeset viewer.