Changes in lemon/concepts/graph_components.h [313:64f8f7cc6168:664:4137ef9aacc6] in lemon
- File:
-
- 1 edited
-
lemon/concepts/graph_components.h (modified) (55 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/graph_components.h
r313 r664 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 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 24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H 25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H 24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H 26 25 27 26 #include <lemon/core.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 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. 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 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. 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: 183 184 typedef BaseGraphComponent Graph; 185 189 186 typedef BaseDigraphComponent::Node Node; 190 187 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'> { 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 199 197 public: 200 typedef GraphItem<'u'> Parent;201 198 /// \brief Default constructor. 202 199 /// 200 /// Default constructor. 203 201 /// \warning The default constructor is not required to set 204 202 /// the item to some well-defined value. So you should consider it 205 203 /// as uninitialized. 206 204 Edge() {} 205 207 206 /// \brief Copy constructor. 208 207 /// 209 208 /// Copy constructor. 210 ///211 209 Edge(const Edge &) : Parent() {} 212 /// \brief Invalid constructor \& conversion. 213 /// 214 /// This constructor initializes the item to be invalid. 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. 215 215 /// \sa Invalid for more details. 216 216 Edge(Invalid) {} 217 /// \brief Converter from arc to edge. 218 /// 217 218 /// \brief Constructor for conversion from an arc. 219 /// 220 /// Constructor for conversion from an arc. 219 221 /// Besides the core graph item functionality each arc should 220 222 /// be convertible to the represented edge. 221 223 Edge(const Arc&) {} 222 /// \brief Assign arc to edge. 223 /// 224 225 /// \brief Assign an arc to an edge. 226 /// 227 /// This function assigns an arc to an edge. 224 228 /// Besides the core graph item functionality each arc should 225 229 /// be convertible to the represented edge. … … 227 231 }; 228 232 229 /// \brief Returns the direction of the arc. 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. 230 256 /// 231 257 /// Returns the direction of the arc. Each arc represents an … … 234 260 bool direction(const Arc&) const { return true; } 235 261 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;} 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; } 263 267 264 268 template <typename _Graph> … … 270 274 void constraints() { 271 275 checkConcept<BaseDigraphComponent, _Graph>(); 272 checkConcept<GraphItem<' u'>, Edge>();276 checkConcept<GraphItem<'e'>, Edge>(); 273 277 { 274 278 Node n; … … 278 282 n = graph.v(ue); 279 283 e = graph.direct(ue, true); 284 e = graph.direct(ue, false); 280 285 e = graph.direct(ue, n); 281 286 e = graph.oppositeArc(e); … … 291 296 }; 292 297 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 be 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;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 /// This concept is part of the Digraph concept. 304 template <typename BAS = BaseDigraphComponent> 305 class IDableDigraphComponent : public BAS { 306 public: 307 308 typedef BAS Base; 304 309 typedef typename Base::Node Node; 305 310 typedef typename Base::Arc Arc; 306 311 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;} 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; } 346 349 347 350 template <typename _Digraph> … … 369 372 }; 370 373 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; 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; 382 386 typedef typename Base::Edge Edge; 383 387 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;} 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; } 405 408 406 409 template <typename _Graph> … … 408 411 409 412 void constraints() { 410 checkConcept<Base, _Graph >();411 413 checkConcept<IDableDigraphComponent<Base>, _Graph >(); 412 414 typename _Graph::Edge edge; … … 422 424 }; 423 425 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 {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 and 429 /// \c EdgeIt subtypes of digraph and graph types. 430 template <typename GR, typename Item> 431 class GraphItemIt : public Item { 430 432 public: 431 433 /// \brief Default constructor. 432 434 /// 433 /// @warning The default constructor sets the iterator 434 /// to an undefined value. 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. 435 439 GraphItemIt() {} 440 436 441 /// \brief Copy constructor. 437 442 /// 438 443 /// 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. 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. 449 455 /// \sa Invalid for more details. 450 456 GraphItemIt(Invalid) {} 451 /// \brief Assign operator for items. 452 /// 453 /// The items are assignable.454 /// 457 458 /// \brief Assignment operator. 459 /// 460 /// Assignment operator for the iterator. 455 461 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 456 /// \brief Next item. 457 /// 458 /// Assign the iterator to the next item. 459 /// 462 463 /// \brief Increment the iterator. 464 /// 465 /// This operator increments the iterator, i.e. assigns it to the 466 /// next item. 460 467 GraphItemIt& operator++() { return *this; } 468 461 469 /// \brief Equality operator 462 470 /// 471 /// Equality operator. 463 472 /// Two iterators are equal if and only if they point to the 464 473 /// same object or both are invalid. 465 474 bool operator==(const GraphItemIt&) const { return true;} 475 466 476 /// \brief Inequality operator 467 477 /// 468 /// \sa operator==(Node n) 469 /// 478 /// Inequality operator. 479 /// Two iterators are equal if and only if they point to the 480 /// same object or both are invalid. 470 481 bool operator!=(const GraphItemIt&) const { return true;} 471 482 … … 473 484 struct Constraints { 474 485 void constraints() { 486 checkConcept<GraphItem<>, _GraphItemIt>(); 475 487 _GraphItemIt it1(g); 476 488 _GraphItemIt it2; 489 _GraphItemIt it3 = it1; 490 _GraphItemIt it4 = INVALID; 477 491 478 492 it2 = ++it1; … … 480 494 ++(++it1); 481 495 482 _Item bi = it1;496 Item bi = it1; 483 497 bi = it2; 484 498 } 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 { 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 { 500 518 public: 501 519 /// \brief Default constructor. 502 520 /// 503 /// @warning The default constructor sets the iterator 504 /// to an undefined value. 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. 505 525 GraphIncIt() {} 526 506 527 /// \brief Copy constructor. 507 528 /// 508 529 /// 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. 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. 521 543 /// \sa Invalid for more details. 522 544 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 /// 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. 532 555 GraphIncIt& operator++() { return *this; } 533 556 534 557 /// \brief Equality operator 535 558 /// 559 /// Equality operator. 536 560 /// Two iterators are equal if and only if they point to the 537 561 /// same object or both are invalid. … … 540 564 /// \brief Inequality operator 541 565 /// 542 /// \sa operator==(Node n) 543 /// 566 /// Inequality operator. 567 /// Two iterators are equal if and only if they point to the 568 /// same object or both are invalid. 544 569 bool operator!=(const GraphIncIt&) const { return true;} 545 570 … … 547 572 struct Constraints { 548 573 void constraints() { 549 checkConcept<GraphItem< _selector>, _GraphIncIt>();574 checkConcept<GraphItem<sel>, _GraphIncIt>(); 550 575 _GraphIncIt it1(graph, node); 551 576 _GraphIncIt it2; 577 _GraphIncIt it3 = it1; 578 _GraphIncIt it4 = INVALID; 552 579 553 580 it2 = ++it1; 554 581 ++it2 = it1; 555 582 ++(++it1); 556 _Item e = it1;583 Item e = it1; 557 584 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. 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. 573 596 /// 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;597 template <typename BAS = BaseDigraphComponent> 598 class IterableDigraphComponent : public BAS { 599 600 public: 601 602 typedef BAS Base; 580 603 typedef typename Base::Node Node; 581 604 typedef typename Base::Arc Arc; … … 583 606 typedef IterableDigraphComponent Digraph; 584 607 585 /// \name Base iteration586 /// 587 /// This interface provides functions for iteration on digraph items 608 /// \name Base Iteration 609 /// 610 /// This interface provides functions for iteration on digraph items. 588 611 /// 589 612 /// @{ 590 613 591 /// \brief Gives back the first node in the iterating order. 592 /// 593 /// Gives back the first node in the iterating order. 594 /// 614 /// \brief Return the first node. 615 /// 616 /// This function gives back the first node in the iteration order. 595 617 void first(Node&) const {} 596 618 597 /// \brief Gives back the next node in the iterating order. 598 /// 599 /// Gives back the next node in the iterating order. 600 /// 619 /// \brief Return the next node. 620 /// 621 /// This function gives back the next node in the iteration order. 601 622 void next(Node&) const {} 602 623 603 /// \brief Gives back the first arc in the iterating order. 604 /// 605 /// Gives back the first arc in the iterating order. 606 /// 624 /// \brief Return the first arc. 625 /// 626 /// This function gives back the first arc in the iteration order. 607 627 void first(Arc&) const {} 608 628 609 /// \brief Gives back the next arc in the iterating order. 610 /// 611 /// Gives back the next arc in the iterating order. 612 /// 629 /// \brief Return the next arc. 630 /// 631 /// This function gives back the next arc in the iteration order. 613 632 void next(Arc&) const {} 614 633 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 /// 634 /// \brief Return the first arc incomming to the given node. 635 /// 636 /// This function gives back the first arc incomming to the 637 /// given node. 621 638 void firstIn(Arc&, const Node&) const {} 622 639 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 /// 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. 628 644 void nextIn(Arc&) const {} 629 645 630 /// \brief Gives back the first of the arcs start from the 646 /// \brief Return the first arc outgoing form the given node. 647 /// 648 /// This function gives back the first arc outgoing form the 631 649 /// given node. 632 ///633 /// Gives back the first of the arcs start from the given node.634 ///635 650 void firstOut(Arc&, const Node&) const {} 636 651 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 /// 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. 642 656 void nextOut(Arc&) const {} 643 657 644 658 /// @} 645 659 646 /// \name Class based iteration647 /// 648 /// This interface provides functions for iteration on digraph items660 /// \name Class Based Iteration 661 /// 662 /// This interface provides iterator classes for digraph items. 649 663 /// 650 664 /// @{ … … 656 670 typedef GraphItemIt<Digraph, Node> NodeIt; 657 671 658 /// \brief This iterator goes through each node.659 /// 660 /// This iterator goes through each node.672 /// \brief This iterator goes through each arc. 673 /// 674 /// This iterator goes through each arc. 661 675 /// 662 676 typedef GraphItemIt<Digraph, Arc> ArcIt; … … 664 678 /// \brief This iterator goes trough the incoming arcs of a node. 665 679 /// 666 /// This iterator goes trough the \e inc coming arcs of a certain node680 /// This iterator goes trough the \e incoming arcs of a certain node 667 681 /// of a digraph. 668 682 typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt; … … 676 690 /// \brief The base node of the iterator. 677 691 /// 678 /// Gives back the base node of the iterator.679 /// It is always the target of the pointed arc.692 /// This function gives back the base node of the iterator. 693 /// It is always the target node of the pointed arc. 680 694 Node baseNode(const InArcIt&) const { return INVALID; } 681 695 682 696 /// \brief The running node of the iterator. 683 697 /// 684 /// Gives back the running node of the iterator.685 /// It is always the source of the pointed arc.698 /// This function gives back the running node of the iterator. 699 /// It is always the source node of the pointed arc. 686 700 Node runningNode(const InArcIt&) const { return INVALID; } 687 701 688 702 /// \brief The base node of the iterator. 689 703 /// 690 /// Gives back the base node of the iterator.691 /// It is always the source of the pointed arc.704 /// This function gives back the base node of the iterator. 705 /// It is always the source node of the pointed arc. 692 706 Node baseNode(const OutArcIt&) const { return INVALID; } 693 707 694 708 /// \brief The running node of the iterator. 695 709 /// 696 /// Gives back the running node of the iterator.697 /// It is always the target of the pointed arc.710 /// This function gives back the running node of the iterator. 711 /// It is always the target node of the pointed arc. 698 712 Node runningNode(const OutArcIt&) const { return INVALID; } 699 713 … … 737 751 738 752 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);753 const typename _Digraph::InArcIt iait(INVALID); 754 const typename _Digraph::OutArcIt oait(INVALID); 755 n = digraph.baseNode(iait); 756 n = digraph.runningNode(iait); 757 n = digraph.baseNode(oait); 758 n = digraph.runningNode(oait); 745 759 ignore_unused_variable_warning(n); 746 760 } … … 748 762 749 763 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.764 }; 765 }; 766 767 /// \brief Skeleton class for iterable undirected graphs. 768 /// 769 /// This class describes the interface of iterable undirected 770 /// graphs. It extends \ref IterableDigraphComponent with the core 771 /// iterable interface of undirected graphs. 758 772 /// 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;773 template <typename BAS = BaseGraphComponent> 774 class IterableGraphComponent : public IterableDigraphComponent<BAS> { 775 public: 776 777 typedef BAS Base; 764 778 typedef typename Base::Node Node; 765 779 typedef typename Base::Arc Arc; … … 769 783 typedef IterableGraphComponent Graph; 770 784 771 /// \name Base iteration 772 /// 773 /// This interface provides functions for iteration on graph items 785 /// \name Base Iteration 786 /// 787 /// This interface provides functions for iteration on edges. 788 /// 774 789 /// @{ 775 790 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 /// 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. 784 797 void first(Edge&) const {} 785 798 786 /// \brief Gives back the next edge in the iterating 787 /// order. 788 /// 789 /// Gives back the next edge in the iterating order. 790 /// 799 /// \brief Return the next edge. 800 /// 801 /// This function gives back the next edge in the iteration order. 791 802 void next(Edge&) const {} 792 803 793 794 /// \brief Gives back the first of the edges from the 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 795 809 /// 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 810 void firstInc(Edge&, bool&, const Node&) const {} 802 811 … … 804 813 /// given node. 805 814 /// 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. 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. 809 817 void nextInc(Edge&, bool&) const {} 810 818 811 using IterableDigraphComponent< _Base>::baseNode;812 using IterableDigraphComponent< _Base>::runningNode;819 using IterableDigraphComponent<Base>::baseNode; 820 using IterableDigraphComponent<Base>::runningNode; 813 821 814 822 /// @} 815 823 816 /// \name Class based iteration817 /// 818 /// This interface provides functions for iteration on graph items824 /// \name Class Based Iteration 825 /// 826 /// This interface provides iterator classes for edges. 819 827 /// 820 828 /// @{ 821 829 822 /// \brief This iterator goes through each node.823 /// 824 /// This iterator goes through each node.830 /// \brief This iterator goes through each edge. 831 /// 832 /// This iterator goes through each edge. 825 833 typedef GraphItemIt<Graph, Edge> EdgeIt; 826 /// \brief This iterator goes trough the incident arcs of a 834 835 /// \brief This iterator goes trough the incident edges of a 827 836 /// node. 828 837 /// 829 /// This iterator goes trough the incident arcs of a certain838 /// This iterator goes trough the incident edges of a certain 830 839 /// node of a graph. 831 typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt; 840 typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt; 841 832 842 /// \brief The base node of the iterator. 833 843 /// 834 /// Gives back the base node of the iterator.844 /// This function gives back the base node of the iterator. 835 845 Node baseNode(const IncEdgeIt&) const { return INVALID; } 836 846 837 847 /// \brief The running node of the iterator. 838 848 /// 839 /// Gives back the running node of the iterator.849 /// This function gives back the running node of the iterator. 840 850 Node runningNode(const IncEdgeIt&) const { return INVALID; } 841 851 … … 866 876 typename _Graph::EdgeIt >(); 867 877 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 868 typename _Graph::Node, ' u'>, typename _Graph::IncEdgeIt>();878 typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>(); 869 879 870 880 typename _Graph::Node n; 871 typename _Graph::IncEdgeIt ueit(INVALID);872 n = graph.baseNode( ueit);873 n = graph.runningNode( ueit);881 const typename _Graph::IncEdgeIt ieit(INVALID); 882 n = graph.baseNode(ieit); 883 n = graph.runningNode(ieit); 874 884 } 875 885 } 876 886 877 887 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. Thisimplements888 }; 889 }; 890 891 /// \brief Skeleton class for alterable directed graphs. 892 /// 893 /// This class describes the interface of alterable directed 894 /// graphs. It extends \ref BaseDigraphComponent with the alteration 895 /// notifier interface. It implements 886 896 /// an observer-notifier pattern for each digraph item. More 887 897 /// obsevers can be registered into the notifier and whenever an 888 /// alteration occured in the digraph all the observers will 898 /// alteration occured in the digraph all the observers will be 889 899 /// notified about it. 890 template <typename _Base= BaseDigraphComponent>891 class AlterableDigraphComponent : public _Base{892 public: 893 894 typedef _BaseBase;900 template <typename BAS = BaseDigraphComponent> 901 class AlterableDigraphComponent : public BAS { 902 public: 903 904 typedef BAS Base; 895 905 typedef typename Base::Node Node; 896 906 typedef typename Base::Arc Arc; 897 907 898 908 899 /// The node observer registry.909 /// Node alteration notifier class. 900 910 typedef AlterationNotifier<AlterableDigraphComponent, Node> 901 911 NodeNotifier; 902 /// The arc observer registry.912 /// Arc alteration notifier class. 903 913 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 904 914 ArcNotifier; 905 915 906 /// \brief Gives backthe node alteration notifier.907 /// 908 /// Gives back the node alteration notifier.916 /// \brief Return the node alteration notifier. 917 /// 918 /// This function gives back the node alteration notifier. 909 919 NodeNotifier& notifier(Node) const { 910 return NodeNotifier();920 return NodeNotifier(); 911 921 } 912 922 913 /// \brief Gives backthe arc alteration notifier.914 /// 915 /// Gives back the arc alteration notifier.923 /// \brief Return the arc alteration notifier. 924 /// 925 /// This function gives back the arc alteration notifier. 916 926 ArcNotifier& notifier(Arc) const { 917 927 return ArcNotifier(); … … 933 943 934 944 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 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 945 954 /// obsevers can be registered into the notifier and whenever an 946 /// alteration occured in the graph all the observers will 955 /// alteration occured in the graph all the observers will be 947 956 /// notified about it. 948 template <typename _Base= BaseGraphComponent>949 class AlterableGraphComponent : public AlterableDigraphComponent< _Base> {950 public: 951 952 typedef _BaseBase;957 template <typename BAS = BaseGraphComponent> 958 class AlterableGraphComponent : public AlterableDigraphComponent<BAS> { 959 public: 960 961 typedef BAS Base; 953 962 typedef typename Base::Edge Edge; 954 963 955 964 956 /// The arc observer registry.965 /// Edge alteration notifier class. 957 966 typedef AlterationNotifier<AlterableGraphComponent, Edge> 958 967 EdgeNotifier; 959 968 960 /// \brief Gives back the arcalteration notifier.961 /// 962 /// Gives back the arcalteration notifier.969 /// \brief Return the edge alteration notifier. 970 /// 971 /// This function gives back the edge alteration notifier. 963 972 EdgeNotifier& notifier(Edge) const { 964 973 return EdgeNotifier(); … … 968 977 struct Constraints { 969 978 void constraints() { 970 checkConcept<Alterable GraphComponent<Base>, _Graph>();979 checkConcept<AlterableDigraphComponent<Base>, _Graph>(); 971 980 typename _Graph::EdgeNotifier& uen 972 981 = graph.notifier(typename _Graph::Edge()); … … 975 984 976 985 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; 992 993 /// The graph type of the map. 994 typedef _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 995 1001 /// The key type of the map. 996 typedef _ItemKey;1002 typedef K Key; 997 1003 /// The value type of the map. 998 typedef _Value Value; 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; 999 1012 1000 1013 /// \brief Construct a new map. 1001 1014 /// 1002 1015 /// Construct a new map for the graph. 1003 explicit GraphMap(const G raph&) {}1016 explicit GraphMap(const GR&) {} 1004 1017 /// \brief Construct a new map with default value. 1005 1018 /// 1006 /// Construct a new map for the graph and initali se the values.1007 GraphMap(const G raph&, const Value&) {}1019 /// Construct a new map for the graph and initalize the values. 1020 GraphMap(const GR&, const Value&) {} 1008 1021 1009 1022 private: … … 1013 1026 GraphMap(const GraphMap&) : Parent() {} 1014 1027 1015 /// \brief Assign operator.1016 /// 1017 /// Assign operator. It does not mofify the underlying graph,1028 /// \brief Assignment operator. 1029 /// 1030 /// Assignment operator. It does not mofify the underlying graph, 1018 1031 /// it just iterates on the current item set and set the map 1019 1032 /// with the value returned by the assigned map. … … 1028 1041 struct Constraints { 1029 1042 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 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 1038 1052 // 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;1047 const G raph&g;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 GR &g; 1048 1062 const typename GraphMap::Value &t; 1049 1063 }; … … 1051 1065 }; 1052 1066 1053 /// \brief An empty mappable digraph class. 1054 /// 1055 /// This class provides beside the core digraph features 1056 /// map interface for the digraph structure. 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. 1057 1072 /// This concept is part of the Digraph concept. 1058 template <typename _Base= BaseDigraphComponent>1059 class MappableDigraphComponent : public _Base{1060 public: 1061 1062 typedef _BaseBase;1073 template <typename BAS = BaseDigraphComponent> 1074 class MappableDigraphComponent : public BAS { 1075 public: 1076 1077 typedef BAS Base; 1063 1078 typedef typename Base::Node Node; 1064 1079 typedef typename Base::Arc Arc; … … 1066 1081 typedef MappableDigraphComponent Digraph; 1067 1082 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> { 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 1074 1091 public: 1075 typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;1076 1077 1092 /// \brief Construct a new map. 1078 1093 /// … … 1083 1098 /// \brief Construct a new map with default value. 1084 1099 /// 1085 /// Construct a new map for the digraph and initali se the values.1086 NodeMap(const MappableDigraphComponent& digraph, const _Value& value)1100 /// Construct a new map for the digraph and initalize the values. 1101 NodeMap(const MappableDigraphComponent& digraph, const V& value) 1087 1102 : Parent(digraph, value) {} 1088 1103 … … 1093 1108 NodeMap(const NodeMap& nm) : Parent(nm) {} 1094 1109 1095 /// \brief Assign operator.1096 /// 1097 /// Assign operator.1110 /// \brief Assignment operator. 1111 /// 1112 /// Assignment operator. 1098 1113 template <typename CMap> 1099 1114 NodeMap& operator=(const CMap&) { 1100 checkConcept<ReadMap<Node, _Value>, CMap>();1115 checkConcept<ReadMap<Node, V>, CMap>(); 1101 1116 return *this; 1102 1117 } … … 1104 1119 }; 1105 1120 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> { 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 1112 1129 public: 1113 typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;1114 1115 1130 /// \brief Construct a new map. 1116 1131 /// … … 1121 1136 /// \brief Construct a new map with default value. 1122 1137 /// 1123 /// Construct a new map for the digraph and initali se the values.1124 ArcMap(const MappableDigraphComponent& digraph, const _Value& value)1138 /// Construct a new map for the digraph and initalize the values. 1139 ArcMap(const MappableDigraphComponent& digraph, const V& value) 1125 1140 : Parent(digraph, value) {} 1126 1141 … … 1131 1146 ArcMap(const ArcMap& nm) : Parent(nm) {} 1132 1147 1133 /// \brief Assign operator.1134 /// 1135 /// Assign operator.1148 /// \brief Assignment operator. 1149 /// 1150 /// Assignment operator. 1136 1151 template <typename CMap> 1137 1152 ArcMap& operator=(const CMap&) { 1138 checkConcept<ReadMap<Arc, _Value>, CMap>();1153 checkConcept<ReadMap<Arc, V>, CMap>(); 1139 1154 return *this; 1140 1155 } … … 1183 1198 } 1184 1199 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. 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). 1193 1209 /// 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;1210 template <typename BAS = BaseGraphComponent> 1211 class MappableGraphComponent : public MappableDigraphComponent<BAS> { 1212 public: 1213 1214 typedef BAS Base; 1199 1215 typedef typename Base::Edge Edge; 1200 1216 1201 1217 typedef MappableGraphComponent Graph; 1202 1218 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> { 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 1209 1227 public: 1210 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;1211 1212 1228 /// \brief Construct a new map. 1213 1229 /// … … 1218 1234 /// \brief Construct a new map with default value. 1219 1235 /// 1220 /// Construct a new map for the graph and initali se the values.1221 EdgeMap(const MappableGraphComponent& graph, const _Value& value)1236 /// Construct a new map for the graph and initalize the values. 1237 EdgeMap(const MappableGraphComponent& graph, const V& value) 1222 1238 : Parent(graph, value) {} 1223 1239 … … 1228 1244 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1229 1245 1230 /// \brief Assign operator.1231 /// 1232 /// Assign operator.1246 /// \brief Assignment operator. 1247 /// 1248 /// Assignment operator. 1233 1249 template <typename CMap> 1234 1250 EdgeMap& operator=(const CMap&) { 1235 checkConcept<ReadMap<Edge, _Value>, CMap>();1251 checkConcept<ReadMap<Edge, V>, CMap>(); 1236 1252 return *this; 1237 1253 } … … 1250 1266 1251 1267 void constraints() { 1252 checkConcept<Mappable GraphComponent<Base>, _Graph>();1268 checkConcept<MappableDigraphComponent<Base>, _Graph>(); 1253 1269 1254 1270 { // int map test … … 1267 1283 } 1268 1284 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 /// 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. 1291 1306 Node addNode() { 1292 1307 return INVALID; 1293 1308 } 1294 1309 1295 /// \brief Adds a new arc connects the given two nodes. 1296 /// 1297 /// Adds a new arc connects the the given two nodes. 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. 1298 1314 Arc addArc(const Node&, const Node&) { 1299 1315 return INVALID; … … 1315 1331 }; 1316 1332 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 /// 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. 1336 1350 Node addNode() { 1337 1351 return INVALID; 1338 1352 } 1339 1353 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&) { 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&) { 1344 1359 return INVALID; 1345 1360 } … … 1360 1375 }; 1361 1376 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;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 removing 1381 /// 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 BAS Base; 1373 1388 typedef typename Base::Node Node; 1374 1389 typedef typename Base::Arc Arc; … … 1376 1391 /// \brief Erase a node from the digraph. 1377 1392 /// 1378 /// Erase a node from the digraph. This function should1379 /// erase all arcs connectingto the node.1393 /// This function erases the given node from the digraph and all arcs 1394 /// connected to the node. 1380 1395 void erase(const Node&) {} 1381 1396 1382 1397 /// \brief Erase an arc from the digraph. 1383 1398 /// 1384 /// Erase an arc from the digraph. 1385 /// 1399 /// This function erases the given arc from the digraph. 1386 1400 void erase(const Arc&) {} 1387 1401 … … 1390 1404 void constraints() { 1391 1405 checkConcept<Base, _Digraph>(); 1392 typename _Digraph::Node node;1406 const typename _Digraph::Node node(INVALID); 1393 1407 digraph.erase(node); 1394 typename _Digraph::Arc arc;1408 const typename _Digraph::Arc arc(INVALID); 1395 1409 digraph.erase(arc); 1396 1410 } … … 1400 1414 }; 1401 1415 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;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 removing 1420 /// 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 BAS Base; 1413 1427 typedef typename Base::Node Node; 1414 1428 typedef typename Base::Edge Edge; … … 1416 1430 /// \brief Erase a node from the graph. 1417 1431 /// 1418 /// Erase a node from the graph. This function should erase1419 /// arcs connectingto the node.1432 /// This function erases the given node from the graph and all edges 1433 /// connected to the node. 1420 1434 void erase(const Node&) {} 1421 1435 1422 /// \brief Erase an arc from the graph. 1423 /// 1424 /// Erase an arc from the graph. 1425 /// 1436 /// \brief Erase an edge from the digraph. 1437 /// 1438 /// This function erases the given edge from the digraph. 1426 1439 void erase(const Edge&) {} 1427 1440 … … 1430 1443 void constraints() { 1431 1444 checkConcept<Base, _Graph>(); 1432 typename _Graph::Node node;1445 const typename _Graph::Node node(INVALID); 1433 1446 graph.erase(node); 1434 typename _Graph::Edge edge;1447 const typename _Graph::Edge edge(INVALID); 1435 1448 graph.erase(edge); 1436 1449 } … … 1440 1453 }; 1441 1454 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;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 clearing 1459 /// the digraph. 1460 /// This concept requires \ref AlterableDigraphComponent. 1461 template <typename BAS = BaseDigraphComponent> 1462 class ClearableDigraphComponent : public BAS { 1463 public: 1464 1465 typedef BAS Base; 1453 1466 1454 1467 /// \brief Erase all nodes and arcs from the digraph. 1455 1468 /// 1456 /// Erase all nodes and arcs from the digraph. 1457 /// 1469 /// This function erases all nodes and arcs from the digraph. 1458 1470 void clear() {} 1459 1471 … … 1465 1477 } 1466 1478 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; 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() {} 1482 1499 1483 1500 template <typename _Graph> 1484 1501 struct Constraints { 1485 1502 void constraints() { 1486 checkConcept<ClearableGraphComponent<Base>, _Graph>(); 1487 } 1488 1489 _Graph graph; 1503 checkConcept<Base, _Graph>(); 1504 graph.clear(); 1505 } 1506 1507 _Graph& graph; 1490 1508 }; 1491 1509 };
Note: See TracChangeset
for help on using the changeset viewer.
