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