Changes in lemon/concepts/graph_components.h [617:4137ef9aacc6:313:64f8f7cc6168] in lemon-1.2
- File:
-
- 1 edited
-
lemon/concepts/graph_components.h (modified) (55 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/graph_components.h
r617 r313 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 21 21 ///\brief The concept of graph components. 22 22 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H 24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H 23 24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H 25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H 25 26 26 27 #include <lemon/core.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 be 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 be 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 184 typedef BaseGraphComponent Graph;185 186 189 typedef BaseDigraphComponent::Node Node; 187 190 typedef BaseDigraphComponent::Arc Arc; 188 189 /// \brief Undirected edge class of the graph. 190 /// 191 /// This class represents the undirected edges of the graph. 192 /// Undirected graphs can be used as directed graphs, each edge is 193 /// represented by two opposite directed arcs. 194 class Edge : public GraphItem<'e'> { 195 typedef GraphItem<'e'> Parent; 196 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'> { 197 199 public: 200 typedef GraphItem<'u'> Parent; 198 201 /// \brief Default constructor. 199 202 /// 200 /// Default constructor.201 203 /// \warning The default constructor is not required to set 202 204 /// the item to some well-defined value. So you should consider it 203 205 /// as uninitialized. 204 206 Edge() {} 205 206 207 /// \brief Copy constructor. 207 208 /// 208 209 /// Copy constructor. 210 /// 209 211 Edge(const Edge &) : Parent() {} 210 211 /// \brief Constructor for conversion from \c INVALID. 212 /// 213 /// Constructor for conversion from \c INVALID. 214 /// It initializes the item to be invalid. 212 /// \brief Invalid constructor \& conversion. 213 /// 214 /// This constructor initializes the item to be invalid. 215 215 /// \sa Invalid for more details. 216 216 Edge(Invalid) {} 217 218 /// \brief Constructor for conversion from an arc. 219 /// 220 /// Constructor for conversion from an arc. 217 /// \brief Converter from arc to edge. 218 /// 221 219 /// Besides the core graph item functionality each arc should 222 220 /// be convertible to the represented edge. 223 221 Edge(const Arc&) {} 224 225 /// \brief Assign an arc to an edge. 226 /// 227 /// This function assigns an arc to an edge. 222 /// \brief Assign arc to edge. 223 /// 228 224 /// Besides the core graph item functionality each arc should 229 225 /// be convertible to the represented edge. … … 231 227 }; 232 228 233 /// \brief Return one end node of an edge. 234 /// 235 /// This function returns one end node of an edge. 236 Node u(const Edge&) const { return INVALID; } 237 238 /// \brief Return the other end node of an edge. 239 /// 240 /// This function returns the other end node of an edge. 241 Node v(const Edge&) const { return INVALID; } 242 243 /// \brief Return a directed arc related to an edge. 244 /// 245 /// This function returns a directed arc from its direction and the 246 /// represented edge. 247 Arc direct(const Edge&, bool) const { return INVALID; } 248 249 /// \brief Return a directed arc related to an edge. 250 /// 251 /// This function returns a directed arc from its source node and the 252 /// represented edge. 253 Arc direct(const Edge&, const Node&) const { return INVALID; } 254 255 /// \brief Return the direction of the arc. 229 /// \brief Returns the direction of the arc. 256 230 /// 257 231 /// Returns the direction of the arc. Each arc represents an … … 260 234 bool direction(const Arc&) const { return true; } 261 235 262 /// \brief Return the opposite arc. 263 /// 264 /// This function returns the opposite arc, i.e. the arc representing 265 /// the same edge and has opposite direction. 266 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;} 267 263 268 264 template <typename _Graph> … … 274 270 void constraints() { 275 271 checkConcept<BaseDigraphComponent, _Graph>(); 276 checkConcept<GraphItem<' e'>, Edge>();272 checkConcept<GraphItem<'u'>, Edge>(); 277 273 { 278 274 Node n; … … 282 278 n = graph.v(ue); 283 279 e = graph.direct(ue, true); 284 e = graph.direct(ue, false);285 280 e = graph.direct(ue, n); 286 281 e = graph.oppositeArc(e); … … 296 291 }; 297 292 298 /// \brief Skeleton class for \e idable directed graphs.299 /// 300 /// This class describes the interface of \e idable directed graphs.301 /// It extends \ref BaseDigraphComponent with the core ID functions.302 /// The ids of the items must be unique and immutable.303 /// Th is concept is part of the Digraph concept.304 template <typename BAS= BaseDigraphComponent>305 class IDableDigraphComponent : public BAS{306 public: 307 308 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 be 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; 309 304 typedef typename Base::Node Node; 310 305 typedef typename Base::Arc Arc; 311 306 312 /// \brief Return a unique integer id for the given node. 313 /// 314 /// This function returns a unique integer id for the given node. 315 int id(const Node&) const { return -1; } 316 317 /// \brief Return the node by its unique id. 318 /// 319 /// This function returns the node by its unique id. 320 /// If the digraph does not contain a node with the given id, 321 /// then the result of the function is undefined. 322 Node nodeFromId(int) const { return INVALID; } 323 324 /// \brief Return a unique integer id for the given arc. 325 /// 326 /// This function returns a unique integer id for the given arc. 327 int id(const Arc&) const { return -1; } 328 329 /// \brief Return the arc by its unique id. 330 /// 331 /// This function returns the arc by its unique id. 332 /// If the digraph does not contain an arc with the given id, 333 /// then the result of the function is undefined. 334 Arc arcFromId(int) const { return INVALID; } 335 336 /// \brief Return an integer greater or equal to the maximum 337 /// node id. 338 /// 339 /// This function returns an integer greater or equal to the 340 /// maximum node id. 341 int maxNodeId() const { return -1; } 342 343 /// \brief Return an integer greater or equal to the maximum 344 /// arc id. 345 /// 346 /// This function returns an integer greater or equal to the 347 /// maximum arc id. 348 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;} 349 346 350 347 template <typename _Digraph> … … 372 369 }; 373 370 374 /// \brief Skeleton class for \e idable undirected graphs. 375 /// 376 /// This class describes the interface of \e idable undirected 377 /// graphs. It extends \ref IDableDigraphComponent with the core ID 378 /// functions of undirected graphs. 379 /// The ids of the items must be unique and immutable. 380 /// This concept is part of the Graph concept. 381 template <typename BAS = BaseGraphComponent> 382 class IDableGraphComponent : public IDableDigraphComponent<BAS> { 383 public: 384 385 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 be 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; 386 382 typedef typename Base::Edge Edge; 387 383 388 using IDableDigraphComponent<Base>::id; 389 390 /// \brief Return a unique integer id for the given edge. 391 /// 392 /// This function returns a unique integer id for the given edge. 393 int id(const Edge&) const { return -1; } 394 395 /// \brief Return the edge by its unique id. 396 /// 397 /// This function returns the edge by its unique id. 398 /// If the graph does not contain an edge with the given id, 399 /// then the result of the function is undefined. 400 Edge edgeFromId(int) const { return INVALID; } 401 402 /// \brief Return an integer greater or equal to the maximum 403 /// edge id. 404 /// 405 /// This function returns an integer greater or equal to the 406 /// maximum edge id. 407 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;} 408 405 409 406 template <typename _Graph> … … 411 408 412 409 void constraints() { 410 checkConcept<Base, _Graph >(); 413 411 checkConcept<IDableDigraphComponent<Base>, _Graph >(); 414 412 typename _Graph::Edge edge; … … 424 422 }; 425 423 426 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.427 /// 428 /// This class describes the concept of \c NodeIt, \c ArcIt and429 /// \c EdgeIt subtypes of digraph and graph types.430 template <typename GR, typenameItem>431 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 { 432 430 public: 433 431 /// \brief Default constructor. 434 432 /// 435 /// Default constructor. 436 /// \warning The default constructor is not required to set 437 /// the iterator to some well-defined value. So you should consider it 438 /// as uninitialized. 433 /// @warning The default constructor sets the iterator 434 /// to an undefined value. 439 435 GraphItemIt() {} 440 441 436 /// \brief Copy constructor. 442 437 /// 443 438 /// Copy constructor. 444 GraphItemIt(const GraphItemIt& it) : Item(it) {} 445 446 /// \brief Constructor that sets the iterator to the first item. 447 /// 448 /// Constructor that sets the iterator to the first item. 449 explicit GraphItemIt(const GR&) {} 450 451 /// \brief Constructor for conversion from \c INVALID. 452 /// 453 /// Constructor for conversion from \c INVALID. 454 /// 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. 455 449 /// \sa Invalid for more details. 456 450 GraphItemIt(Invalid) {} 457 458 /// \brief Assignment operator.459 /// 460 /// Assignment operator for the iterator.451 /// \brief Assign operator for items. 452 /// 453 /// The items are assignable. 454 /// 461 455 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 462 463 /// \brief Increment the iterator. 464 /// 465 /// This operator increments the iterator, i.e. assigns it to the 466 /// next item. 456 /// \brief Next item. 457 /// 458 /// Assign the iterator to the next item. 459 /// 467 460 GraphItemIt& operator++() { return *this; } 468 469 461 /// \brief Equality operator 470 462 /// 471 /// Equality operator.472 463 /// Two iterators are equal if and only if they point to the 473 464 /// same object or both are invalid. 474 465 bool operator==(const GraphItemIt&) const { return true;} 475 476 466 /// \brief Inequality operator 477 467 /// 478 /// Inequality operator. 479 /// Two iterators are equal if and only if they point to the 480 /// same object or both are invalid. 468 /// \sa operator==(Node n) 469 /// 481 470 bool operator!=(const GraphItemIt&) const { return true;} 482 471 … … 484 473 struct Constraints { 485 474 void constraints() { 486 checkConcept<GraphItem<>, _GraphItemIt>();487 475 _GraphItemIt it1(g); 488 476 _GraphItemIt it2; 489 _GraphItemIt it3 = it1;490 _GraphItemIt it4 = INVALID;491 477 492 478 it2 = ++it1; … … 494 480 ++(++it1); 495 481 496 Item bi = it1;482 _Item bi = it1; 497 483 bi = it2; 498 484 } 499 const GR& g; 500 }; 501 }; 502 503 /// \brief Concept class for \c InArcIt, \c OutArcIt and 504 /// \c IncEdgeIt types. 505 /// 506 /// This class describes the concept of \c InArcIt, \c OutArcIt 507 /// and \c IncEdgeIt subtypes of digraph and graph types. 508 /// 509 /// \note Since these iterator classes do not inherit from the same 510 /// base class, there is an additional template parameter (selector) 511 /// \c sel. For \c InArcIt you should instantiate it with character 512 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. 513 template <typename GR, 514 typename Item = typename GR::Arc, 515 typename Base = typename GR::Node, 516 char sel = '0'> 517 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 { 518 500 public: 519 501 /// \brief Default constructor. 520 502 /// 521 /// Default constructor. 522 /// \warning The default constructor is not required to set 523 /// the iterator to some well-defined value. So you should consider it 524 /// as uninitialized. 503 /// @warning The default constructor sets the iterator 504 /// to an undefined value. 525 505 GraphIncIt() {} 526 527 506 /// \brief Copy constructor. 528 507 /// 529 508 /// Copy constructor. 530 GraphIncIt(const GraphIncIt& it) : Item(it) {} 531 532 /// \brief Constructor that sets the iterator to the first 533 /// incoming or outgoing arc. 534 /// 535 /// Constructor that sets the iterator to the first arc 536 /// incoming to or outgoing from the given node. 537 explicit GraphIncIt(const GR&, const Base&) {} 538 539 /// \brief Constructor for conversion from \c INVALID. 540 /// 541 /// Constructor for conversion from \c INVALID. 542 /// 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. 543 521 /// \sa Invalid for more details. 544 522 GraphIncIt(Invalid) {} 545 546 /// \brief Assignment operator. 547 /// 548 /// Assignment operator for the iterator. 549 GraphIncIt& operator=(const GraphIncIt&) { return *this; } 550 551 /// \brief Increment the iterator. 552 /// 553 /// This operator increments the iterator, i.e. assigns it to the 554 /// 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 /// 555 532 GraphIncIt& operator++() { return *this; } 556 533 557 534 /// \brief Equality operator 558 535 /// 559 /// Equality operator.560 536 /// Two iterators are equal if and only if they point to the 561 537 /// same object or both are invalid. … … 564 540 /// \brief Inequality operator 565 541 /// 566 /// Inequality operator. 567 /// Two iterators are equal if and only if they point to the 568 /// same object or both are invalid. 542 /// \sa operator==(Node n) 543 /// 569 544 bool operator!=(const GraphIncIt&) const { return true;} 570 545 … … 572 547 struct Constraints { 573 548 void constraints() { 574 checkConcept<GraphItem< sel>, _GraphIncIt>();549 checkConcept<GraphItem<_selector>, _GraphIncIt>(); 575 550 _GraphIncIt it1(graph, node); 576 551 _GraphIncIt it2; 577 _GraphIncIt it3 = it1;578 _GraphIncIt it4 = INVALID;579 552 580 553 it2 = ++it1; 581 554 ++it2 = it1; 582 555 ++(++it1); 583 Item e = it1;556 _Item e = it1; 584 557 e = it2; 585 } 586 const Base& node; 587 const GR& graph; 588 }; 589 }; 590 591 /// \brief Skeleton class for iterable directed graphs. 592 /// 593 /// This class describes the interface of iterable directed 594 /// graphs. It extends \ref BaseDigraphComponent with the core 595 /// 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. 596 573 /// This concept is part of the Digraph concept. 597 template <typename BAS= BaseDigraphComponent>598 class IterableDigraphComponent : public BAS{599 600 public: 601 602 typedef BASBase;574 template <typename _Base = BaseDigraphComponent> 575 class IterableDigraphComponent : public _Base { 576 577 public: 578 579 typedef _Base Base; 603 580 typedef typename Base::Node Node; 604 581 typedef typename Base::Arc Arc; … … 606 583 typedef IterableDigraphComponent Digraph; 607 584 608 /// \name Base Iteration609 /// 610 /// This interface provides functions for iteration on digraph items .585 /// \name Base iteration 586 /// 587 /// This interface provides functions for iteration on digraph items 611 588 /// 612 589 /// @{ 613 590 614 /// \brief Return the first node. 615 /// 616 /// 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 /// 617 595 void first(Node&) const {} 618 596 619 /// \brief Return the next node. 620 /// 621 /// 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 /// 622 601 void next(Node&) const {} 623 602 624 /// \brief Return the first arc. 625 /// 626 /// 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 /// 627 607 void first(Arc&) const {} 628 608 629 /// \brief Return the next arc. 630 /// 631 /// 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 /// 632 613 void next(Arc&) const {} 633 614 634 /// \brief Return the first arc incomming to the given node. 635 /// 636 /// 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 637 631 /// given node. 638 void firstIn(Arc&, const Node&) const {} 639 640 /// \brief Return the next arc incomming to the given node. 641 /// 642 /// This function gives back the next arc incomming to the 643 /// given node. 644 void nextIn(Arc&) const {} 645 646 /// \brief Return the first arc outgoing form the given node. 647 /// 648 /// This function gives back the first arc outgoing form the 649 /// given node. 632 /// 633 /// Gives back the first of the arcs start from the given node. 634 /// 650 635 void firstOut(Arc&, const Node&) const {} 651 636 652 /// \brief Return the next arc outgoing form the given node. 653 /// 654 /// This function gives back the next arc outgoing form the 655 /// 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 /// 656 642 void nextOut(Arc&) const {} 657 643 658 644 /// @} 659 645 660 /// \name Class Based Iteration661 /// 662 /// This interface provides iterator classes for digraph items.646 /// \name Class based iteration 647 /// 648 /// This interface provides functions for iteration on digraph items 663 649 /// 664 650 /// @{ … … 670 656 typedef GraphItemIt<Digraph, Node> NodeIt; 671 657 672 /// \brief This iterator goes through each arc.673 /// 674 /// This iterator goes through each arc.658 /// \brief This iterator goes through each node. 659 /// 660 /// This iterator goes through each node. 675 661 /// 676 662 typedef GraphItemIt<Digraph, Arc> ArcIt; … … 678 664 /// \brief This iterator goes trough the incoming arcs of a node. 679 665 /// 680 /// 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 681 667 /// of a digraph. 682 668 typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt; … … 690 676 /// \brief The base node of the iterator. 691 677 /// 692 /// This function gives back the base node of the iterator.693 /// 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. 694 680 Node baseNode(const InArcIt&) const { return INVALID; } 695 681 696 682 /// \brief The running node of the iterator. 697 683 /// 698 /// This function gives back the running node of the iterator.699 /// 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. 700 686 Node runningNode(const InArcIt&) const { return INVALID; } 701 687 702 688 /// \brief The base node of the iterator. 703 689 /// 704 /// This function gives back the base node of the iterator.705 /// 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. 706 692 Node baseNode(const OutArcIt&) const { return INVALID; } 707 693 708 694 /// \brief The running node of the iterator. 709 695 /// 710 /// This function gives back the running node of the iterator.711 /// 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. 712 698 Node runningNode(const OutArcIt&) const { return INVALID; } 713 699 … … 751 737 752 738 typename _Digraph::Node n; 753 const typename _Digraph::InArcIt iait(INVALID);754 const typename _Digraph::OutArcIt oait(INVALID);755 n = digraph.baseNode(i ait);756 n = digraph.runningNode(i ait);757 n = digraph.baseNode(o ait);758 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); 759 745 ignore_unused_variable_warning(n); 760 746 } … … 762 748 763 749 const _Digraph& digraph; 764 }; 765 };766 767 /// \brief Skeleton class for iterable undirected graphs. 768 /// 769 /// This class describes the interface of iterable undirected770 /// graphs. It extends \ref IterableDigraphComponent with the core771 /// 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. 772 758 /// This concept is part of the Graph concept. 773 template <typename BAS= BaseGraphComponent>774 class IterableGraphComponent : public IterableDigraphComponent< BAS> {775 public: 776 777 typedef BASBase;759 template <typename _Base = BaseGraphComponent> 760 class IterableGraphComponent : public IterableDigraphComponent<_Base> { 761 public: 762 763 typedef _Base Base; 778 764 typedef typename Base::Node Node; 779 765 typedef typename Base::Arc Arc; … … 783 769 typedef IterableGraphComponent Graph; 784 770 785 /// \name Base Iteration 786 /// 787 /// This interface provides functions for iteration on edges. 788 /// 771 /// \name Base iteration 772 /// 773 /// This interface provides functions for iteration on graph items 789 774 /// @{ 790 775 791 using IterableDigraphComponent<Base>::first; 792 using IterableDigraphComponent<Base>::next; 793 794 /// \brief Return the first edge. 795 /// 796 /// 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 /// 797 784 void first(Edge&) const {} 798 785 799 /// \brief Return the next edge. 800 /// 801 /// 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 /// 802 791 void next(Edge&) const {} 803 792 804 /// \brief Return the first edge incident to the given node. 805 /// 806 /// This function gives back the first edge incident to the given 807 /// node. The bool parameter gives back the direction for which the 808 /// source node of the directed arc representing the edge is the 793 794 /// \brief Gives back the first of the edges from the 809 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. 810 801 void firstInc(Edge&, bool&, const Node&) const {} 811 802 … … 813 804 /// given node. 814 805 /// 815 /// This function gives back the next edge incident to the given 816 /// 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. 817 809 void nextInc(Edge&, bool&) const {} 818 810 819 using IterableDigraphComponent< Base>::baseNode;820 using IterableDigraphComponent< Base>::runningNode;811 using IterableDigraphComponent<_Base>::baseNode; 812 using IterableDigraphComponent<_Base>::runningNode; 821 813 822 814 /// @} 823 815 824 /// \name Class Based Iteration825 /// 826 /// This interface provides iterator classes for edges.816 /// \name Class based iteration 817 /// 818 /// This interface provides functions for iteration on graph items 827 819 /// 828 820 /// @{ 829 821 830 /// \brief This iterator goes through each edge.831 /// 832 /// This iterator goes through each edge.822 /// \brief This iterator goes through each node. 823 /// 824 /// This iterator goes through each node. 833 825 typedef GraphItemIt<Graph, Edge> EdgeIt; 834 835 /// \brief This iterator goes trough the incident edges of a 826 /// \brief This iterator goes trough the incident arcs of a 836 827 /// node. 837 828 /// 838 /// This iterator goes trough the incident edges of a certain829 /// This iterator goes trough the incident arcs of a certain 839 830 /// node of a graph. 840 typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt; 841 831 typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt; 842 832 /// \brief The base node of the iterator. 843 833 /// 844 /// This function gives back the base node of the iterator.834 /// Gives back the base node of the iterator. 845 835 Node baseNode(const IncEdgeIt&) const { return INVALID; } 846 836 847 837 /// \brief The running node of the iterator. 848 838 /// 849 /// This function gives back the running node of the iterator.839 /// Gives back the running node of the iterator. 850 840 Node runningNode(const IncEdgeIt&) const { return INVALID; } 851 841 … … 876 866 typename _Graph::EdgeIt >(); 877 867 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 878 typename _Graph::Node, ' e'>, typename _Graph::IncEdgeIt>();868 typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>(); 879 869 880 870 typename _Graph::Node n; 881 const typename _Graph::IncEdgeIt ieit(INVALID);882 n = graph.baseNode( ieit);883 n = graph.runningNode( ieit);871 typename _Graph::IncEdgeIt ueit(INVALID); 872 n = graph.baseNode(ueit); 873 n = graph.runningNode(ueit); 884 874 } 885 875 } 886 876 887 877 const _Graph& graph; 888 }; 889 };890 891 /// \brief Skeleton class for alterable directed graphs. 892 /// 893 /// This class describes the interface of alterable directed894 /// graphs. It extends \ref BaseDigraphComponent with thealteration895 /// 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 896 886 /// an observer-notifier pattern for each digraph item. More 897 887 /// obsevers can be registered into the notifier and whenever an 898 /// alteration occured in the digraph all the observers will be888 /// alteration occured in the digraph all the observers will 899 889 /// notified about it. 900 template <typename BAS= BaseDigraphComponent>901 class AlterableDigraphComponent : public BAS{902 public: 903 904 typedef BASBase;890 template <typename _Base = BaseDigraphComponent> 891 class AlterableDigraphComponent : public _Base { 892 public: 893 894 typedef _Base Base; 905 895 typedef typename Base::Node Node; 906 896 typedef typename Base::Arc Arc; 907 897 908 898 909 /// Node alteration notifier class.899 /// The node observer registry. 910 900 typedef AlterationNotifier<AlterableDigraphComponent, Node> 911 901 NodeNotifier; 912 /// Arc alteration notifier class.902 /// The arc observer registry. 913 903 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 914 904 ArcNotifier; 915 905 916 /// \brief Returnthe node alteration notifier.917 /// 918 /// This function gives back the node alteration notifier.906 /// \brief Gives back the node alteration notifier. 907 /// 908 /// Gives back the node alteration notifier. 919 909 NodeNotifier& notifier(Node) const { 920 910 return NodeNotifier(); 921 911 } 922 912 923 /// \brief Returnthe arc alteration notifier.924 /// 925 /// This function gives back the arc alteration notifier.913 /// \brief Gives back the arc alteration notifier. 914 /// 915 /// Gives back the arc alteration notifier. 926 916 ArcNotifier& notifier(Arc) const { 927 917 return ArcNotifier(); … … 943 933 944 934 const _Digraph& digraph; 945 }; 946 }; 947 948 /// \brief Skeleton class for alterable undirected graphs. 949 /// 950 /// This class describes the interface of alterable undirected 951 /// graphs. It extends \ref AlterableDigraphComponent with the alteration 952 /// notifier interface of undirected graphs. It implements 953 /// 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 954 945 /// obsevers can be registered into the notifier and whenever an 955 /// alteration occured in the graph all the observers will be946 /// alteration occured in the graph all the observers will 956 947 /// notified about it. 957 template <typename BAS= BaseGraphComponent>958 class AlterableGraphComponent : public AlterableDigraphComponent< BAS> {959 public: 960 961 typedef BASBase;948 template <typename _Base = BaseGraphComponent> 949 class AlterableGraphComponent : public AlterableDigraphComponent<_Base> { 950 public: 951 952 typedef _Base Base; 962 953 typedef typename Base::Edge Edge; 963 954 964 955 965 /// Edge alteration notifier class.956 /// The arc observer registry. 966 957 typedef AlterationNotifier<AlterableGraphComponent, Edge> 967 958 EdgeNotifier; 968 959 969 /// \brief Return the edgealteration notifier.970 /// 971 /// This function gives back the edgealteration notifier.960 /// \brief Gives back the arc alteration notifier. 961 /// 962 /// Gives back the arc alteration notifier. 972 963 EdgeNotifier& notifier(Edge) const { 973 964 return EdgeNotifier(); … … 977 968 struct Constraints { 978 969 void constraints() { 979 checkConcept<Alterable DigraphComponent<Base>, _Graph>();970 checkConcept<AlterableGraphComponent<Base>, _Graph>(); 980 971 typename _Graph::EdgeNotifier& uen 981 972 = graph.notifier(typename _Graph::Edge()); … … 984 975 985 976 const _Graph& graph; 986 }; 987 }; 988 989 /// \brief Concept class for standard graph maps. 990 /// 991 /// This class describes the concept of standard graph maps, i.e. 992 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 993 /// graph types, which can be used for associating data to graph items. 994 /// The standard graph maps must conform to the ReferenceMap concept. 995 template <typename GR, typename K, typename V> 996 class GraphMap : public ReferenceMap<K, V, V&, const V&> { 997 typedef ReferenceMap<K, V, V&, const V&> Parent; 998 999 public: 1000 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; 992 993 /// The graph type of the map. 994 typedef _Graph Graph; 1001 995 /// The key type of the map. 1002 typedef KKey;996 typedef _Item Key; 1003 997 /// The value type of the map. 1004 typedef V Value; 1005 /// The reference type of the map. 1006 typedef Value& Reference; 1007 /// The const reference type of the map. 1008 typedef const Value& ConstReference; 1009 1010 // The reference map tag. 1011 typedef True ReferenceMapTag; 998 typedef _Value Value; 1012 999 1013 1000 /// \brief Construct a new map. 1014 1001 /// 1015 1002 /// Construct a new map for the graph. 1016 explicit GraphMap(const G R&) {}1003 explicit GraphMap(const Graph&) {} 1017 1004 /// \brief Construct a new map with default value. 1018 1005 /// 1019 /// Construct a new map for the graph and initali ze the values.1020 GraphMap(const G R&, const Value&) {}1006 /// Construct a new map for the graph and initalise the values. 1007 GraphMap(const Graph&, const Value&) {} 1021 1008 1022 1009 private: … … 1026 1013 GraphMap(const GraphMap&) : Parent() {} 1027 1014 1028 /// \brief Assign mentoperator.1029 /// 1030 /// Assign mentoperator. It does not mofify the underlying graph,1015 /// \brief Assign operator. 1016 /// 1017 /// Assign operator. It does not mofify the underlying graph, 1031 1018 /// it just iterates on the current item set and set the map 1032 1019 /// with the value returned by the assigned map. … … 1041 1028 struct Constraints { 1042 1029 void constraints() { 1043 checkConcept 1044 <ReferenceMap<Key, Value, Value&, const Value&>, _Map>(); 1045 _Map m1(g); 1046 _Map m2(g,t); 1047 1048 // Copy constructor 1049 // _Map m3(m); 1050 1051 // 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 1052 1038 // ReadMap<Key, Value> cmap; 1053 // m3= cmap;1054 1055 ignore_unused_variable_warning( m1);1056 ignore_unused_variable_warning( m2);1057 // ignore_unused_variable_warning( m3);1058 } 1059 1060 const _Map & m;1061 const G R&g;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; 1047 const Graph &g; 1062 1048 const typename GraphMap::Value &t; 1063 1049 }; … … 1065 1051 }; 1066 1052 1067 /// \brief Skeleton class for mappable directed graphs. 1068 /// 1069 /// This class describes the interface of mappable directed graphs. 1070 /// It extends \ref BaseDigraphComponent with the standard digraph 1071 /// 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. 1072 1057 /// This concept is part of the Digraph concept. 1073 template <typename BAS= BaseDigraphComponent>1074 class MappableDigraphComponent : public BAS{1075 public: 1076 1077 typedef BASBase;1058 template <typename _Base = BaseDigraphComponent> 1059 class MappableDigraphComponent : public _Base { 1060 public: 1061 1062 typedef _Base Base; 1078 1063 typedef typename Base::Node Node; 1079 1064 typedef typename Base::Arc Arc; … … 1081 1066 typedef MappableDigraphComponent Digraph; 1082 1067 1083 /// \brief Standard graph map for the nodes. 1084 /// 1085 /// Standard graph map for the nodes. 1086 /// It conforms to the ReferenceMap concept. 1087 template <typename V> 1088 class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> { 1089 typedef GraphMap<MappableDigraphComponent, Node, V> Parent; 1090 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> { 1091 1074 public: 1075 typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent; 1076 1092 1077 /// \brief Construct a new map. 1093 1078 /// … … 1098 1083 /// \brief Construct a new map with default value. 1099 1084 /// 1100 /// Construct a new map for the digraph and initali ze the values.1101 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) 1102 1087 : Parent(digraph, value) {} 1103 1088 … … 1108 1093 NodeMap(const NodeMap& nm) : Parent(nm) {} 1109 1094 1110 /// \brief Assign mentoperator.1111 /// 1112 /// Assign mentoperator.1095 /// \brief Assign operator. 1096 /// 1097 /// Assign operator. 1113 1098 template <typename CMap> 1114 1099 NodeMap& operator=(const CMap&) { 1115 checkConcept<ReadMap<Node, V>, CMap>();1100 checkConcept<ReadMap<Node, _Value>, CMap>(); 1116 1101 return *this; 1117 1102 } … … 1119 1104 }; 1120 1105 1121 /// \brief Standard graph map for the arcs. 1122 /// 1123 /// Standard graph map for the arcs. 1124 /// It conforms to the ReferenceMap concept. 1125 template <typename V> 1126 class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> { 1127 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent; 1128 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> { 1129 1112 public: 1113 typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent; 1114 1130 1115 /// \brief Construct a new map. 1131 1116 /// … … 1136 1121 /// \brief Construct a new map with default value. 1137 1122 /// 1138 /// Construct a new map for the digraph and initali ze the values.1139 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) 1140 1125 : Parent(digraph, value) {} 1141 1126 … … 1146 1131 ArcMap(const ArcMap& nm) : Parent(nm) {} 1147 1132 1148 /// \brief Assign mentoperator.1149 /// 1150 /// Assign mentoperator.1133 /// \brief Assign operator. 1134 /// 1135 /// Assign operator. 1151 1136 template <typename CMap> 1152 1137 ArcMap& operator=(const CMap&) { 1153 checkConcept<ReadMap<Arc, V>, CMap>();1138 checkConcept<ReadMap<Arc, _Value>, CMap>(); 1154 1139 return *this; 1155 1140 } … … 1198 1183 } 1199 1184 1200 const _Digraph& digraph; 1201 }; 1202 }; 1203 1204 /// \brief Skeleton class for mappable undirected graphs. 1205 /// 1206 /// This class describes the interface of mappable undirected graphs. 1207 /// It extends \ref MappableDigraphComponent with the standard graph 1208 /// 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. 1209 1193 /// This concept is part of the Graph concept. 1210 template <typename BAS= BaseGraphComponent>1211 class MappableGraphComponent : public MappableDigraphComponent< BAS> {1212 public: 1213 1214 typedef BASBase;1194 template <typename _Base = BaseGraphComponent> 1195 class MappableGraphComponent : public MappableDigraphComponent<_Base> { 1196 public: 1197 1198 typedef _Base Base; 1215 1199 typedef typename Base::Edge Edge; 1216 1200 1217 1201 typedef MappableGraphComponent Graph; 1218 1202 1219 /// \brief Standard graph map for the edges. 1220 /// 1221 /// Standard graph map for the edges. 1222 /// It conforms to the ReferenceMap concept. 1223 template <typename V> 1224 class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> { 1225 typedef GraphMap<MappableGraphComponent, Edge, V> Parent; 1226 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> { 1227 1209 public: 1210 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent; 1211 1228 1212 /// \brief Construct a new map. 1229 1213 /// … … 1234 1218 /// \brief Construct a new map with default value. 1235 1219 /// 1236 /// Construct a new map for the graph and initali ze the values.1237 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) 1238 1222 : Parent(graph, value) {} 1239 1223 … … 1244 1228 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1245 1229 1246 /// \brief Assign mentoperator.1247 /// 1248 /// Assign mentoperator.1230 /// \brief Assign operator. 1231 /// 1232 /// Assign operator. 1249 1233 template <typename CMap> 1250 1234 EdgeMap& operator=(const CMap&) { 1251 checkConcept<ReadMap<Edge, V>, CMap>();1235 checkConcept<ReadMap<Edge, _Value>, CMap>(); 1252 1236 return *this; 1253 1237 } … … 1266 1250 1267 1251 void constraints() { 1268 checkConcept<Mappable DigraphComponent<Base>, _Graph>();1252 checkConcept<MappableGraphComponent<Base>, _Graph>(); 1269 1253 1270 1254 { // int map test … … 1283 1267 } 1284 1268 1285 const _Graph& graph; 1286 }; 1287 }; 1288 1289 /// \brief Skeleton class for extendable directed graphs. 1290 /// 1291 /// This class describes the interface of extendable directed graphs. 1292 /// It extends \ref BaseDigraphComponent with functions for adding 1293 /// nodes and arcs to the digraph. 1294 /// This concept requires \ref AlterableDigraphComponent. 1295 template <typename BAS = BaseDigraphComponent> 1296 class ExtendableDigraphComponent : public BAS { 1297 public: 1298 typedef BAS Base; 1299 1300 typedef typename Base::Node Node; 1301 typedef typename Base::Arc Arc; 1302 1303 /// \brief Add a new node to the digraph. 1304 /// 1305 /// 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 /// 1306 1291 Node addNode() { 1307 1292 return INVALID; 1308 1293 } 1309 1294 1310 /// \brief Add a new arc connecting the given two nodes. 1311 /// 1312 /// This function adds a new arc connecting the given two nodes 1313 /// 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. 1314 1298 Arc addArc(const Node&, const Node&) { 1315 1299 return INVALID; … … 1331 1315 }; 1332 1316 1333 /// \brief Skeleton class for extendable undirected graphs. 1334 /// 1335 /// This class describes the interface of extendable undirected graphs. 1336 /// It extends \ref BaseGraphComponent with functions for adding 1337 /// nodes and edges to the graph. 1338 /// This concept requires \ref AlterableGraphComponent. 1339 template <typename BAS = BaseGraphComponent> 1340 class ExtendableGraphComponent : public BAS { 1341 public: 1342 1343 typedef BAS Base; 1344 typedef typename Base::Node Node; 1345 typedef typename Base::Edge Edge; 1346 1347 /// \brief Add a new node to the digraph. 1348 /// 1349 /// 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 /// 1350 1336 Node addNode() { 1351 1337 return INVALID; 1352 1338 } 1353 1339 1354 /// \brief Add a new edge connecting the given two nodes. 1355 /// 1356 /// This function adds a new edge connecting the given two nodes 1357 /// of the graph. 1358 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&) { 1359 1344 return INVALID; 1360 1345 } … … 1375 1360 }; 1376 1361 1377 /// \brief Skeleton class for erasable directed graphs.1378 /// 1379 /// This class describes the interface of erasable directed graphs.1380 /// It extends \ref BaseDigraphComponent with functions for removing1381 /// nodes and arcs from the digraph.1382 /// This concept requires \ref AlterableDigraphComponent.1383 template <typename BAS= BaseDigraphComponent>1384 class ErasableDigraphComponent : public BAS{1385 public: 1386 1387 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; 1388 1373 typedef typename Base::Node Node; 1389 1374 typedef typename Base::Arc Arc; … … 1391 1376 /// \brief Erase a node from the digraph. 1392 1377 /// 1393 /// This function erases the given node from the digraph and all arcs1394 /// connectedto the node.1378 /// Erase a node from the digraph. This function should 1379 /// erase all arcs connecting to the node. 1395 1380 void erase(const Node&) {} 1396 1381 1397 1382 /// \brief Erase an arc from the digraph. 1398 1383 /// 1399 /// This function erases the given arc from the digraph. 1384 /// Erase an arc from the digraph. 1385 /// 1400 1386 void erase(const Arc&) {} 1401 1387 … … 1404 1390 void constraints() { 1405 1391 checkConcept<Base, _Digraph>(); 1406 const typename _Digraph::Node node(INVALID);1392 typename _Digraph::Node node; 1407 1393 digraph.erase(node); 1408 const typename _Digraph::Arc arc(INVALID);1394 typename _Digraph::Arc arc; 1409 1395 digraph.erase(arc); 1410 1396 } … … 1414 1400 }; 1415 1401 1416 /// \brief Skeleton class for erasable undirected graphs.1417 /// 1418 /// This class describes the interface of erasable undirected graphs.1419 /// It extends \ref BaseGraphComponent with functions for removing1420 /// nodes and edges from the graph.1421 /// This concept requires \ref AlterableGraphComponent.1422 template <typename BAS= BaseGraphComponent>1423 class ErasableGraphComponent : public BAS{1424 public: 1425 1426 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; 1427 1413 typedef typename Base::Node Node; 1428 1414 typedef typename Base::Edge Edge; … … 1430 1416 /// \brief Erase a node from the graph. 1431 1417 /// 1432 /// This function erases the given node from the graph and all edges1433 /// connectedto the node.1418 /// Erase a node from the graph. This function should erase 1419 /// arcs connecting to the node. 1434 1420 void erase(const Node&) {} 1435 1421 1436 /// \brief Erase an edge from the digraph. 1437 /// 1438 /// 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 /// 1439 1426 void erase(const Edge&) {} 1440 1427 … … 1443 1430 void constraints() { 1444 1431 checkConcept<Base, _Graph>(); 1445 const typename _Graph::Node node(INVALID);1432 typename _Graph::Node node; 1446 1433 graph.erase(node); 1447 const typename _Graph::Edge edge(INVALID);1434 typename _Graph::Edge edge; 1448 1435 graph.erase(edge); 1449 1436 } … … 1453 1440 }; 1454 1441 1455 /// \brief Skeleton class for clearable directed graphs.1456 /// 1457 /// This class describes the interface of clearable directed graphs.1458 /// It extends \ref BaseDigraphComponent with a function for clearing1459 /// the digraph.1460 /// This concept requires \ref AlterableDigraphComponent.1461 template <typename BAS= BaseDigraphComponent>1462 class ClearableDigraphComponent : public BAS{1463 public: 1464 1465 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; 1466 1453 1467 1454 /// \brief Erase all nodes and arcs from the digraph. 1468 1455 /// 1469 /// This function erases all nodes and arcs from the digraph. 1456 /// Erase all nodes and arcs from the digraph. 1457 /// 1470 1458 void clear() {} 1471 1459 … … 1477 1465 } 1478 1466 1479 _Digraph& digraph; 1480 }; 1481 }; 1482 1483 /// \brief Skeleton class for clearable undirected graphs. 1484 /// 1485 /// This class describes the interface of clearable undirected graphs. 1486 /// It extends \ref BaseGraphComponent with a function for clearing 1487 /// the graph. 1488 /// This concept requires \ref AlterableGraphComponent. 1489 template <typename BAS = BaseGraphComponent> 1490 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> { 1491 public: 1492 1493 typedef BAS Base; 1494 1495 /// \brief Erase all nodes and edges from the graph. 1496 /// 1497 /// This function erases all nodes and edges from the graph. 1498 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; 1499 1482 1500 1483 template <typename _Graph> 1501 1484 struct Constraints { 1502 1485 void constraints() { 1503 checkConcept<Base, _Graph>(); 1504 graph.clear(); 1505 } 1506 1507 _Graph& graph; 1486 checkConcept<ClearableGraphComponent<Base>, _Graph>(); 1487 } 1488 1489 _Graph graph; 1508 1490 }; 1509 1491 };
Note: See TracChangeset
for help on using the changeset viewer.
