Changeset 209:765619b7cbb2 in lemon-1.2 for lemon/concepts
- Timestamp:
- 07/13/08 20:51:02 (17 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon/concepts
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/digraph.h
r125 r209 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 47 47 private: 48 48 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 49 49 50 50 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 51 51 /// … … 53 53 ///\brief Assignment of \ref Digraph "Digraph"s to another ones are 54 54 ///\e not allowed. Use DigraphCopy() instead. 55 55 56 56 ///Assignment of \ref Digraph "Digraph"s to another ones are 57 57 ///\e not allowed. Use DigraphCopy() instead. … … 96 96 97 97 /// Inequality operator 98 98 99 99 /// \sa operator==(Node n) 100 100 /// 101 101 bool operator!=(Node) const { return true; } 102 102 103 104 105 106 107 108 109 110 111 112 113 }; 114 103 /// Artificial ordering operator. 104 105 /// To allow the use of digraph descriptors as key type in std::map or 106 /// similar associative container we require this. 107 /// 108 /// \note This operator only have to define some strict ordering of 109 /// the items; this order has nothing to do with the iteration 110 /// ordering of the items. 111 bool operator<(Node) const { return false; } 112 113 }; 114 115 115 /// This iterator goes through each node. 116 116 … … 130 130 NodeIt() { } 131 131 /// Copy constructor. 132 132 133 133 /// Copy constructor. 134 134 /// … … 146 146 /// Node -> NodeIt conversion. 147 147 148 /// Sets the iterator to the node of \c the digraph pointed by 149 150 /// This feature necessitates that each time we 148 /// Sets the iterator to the node of \c the digraph pointed by 149 /// the trivial iterator. 150 /// This feature necessitates that each time we 151 151 /// iterate the arc-set, the iteration order is the same. 152 152 NodeIt(const Digraph&, const Node&) { } … … 157 157 NodeIt& operator++() { return *this; } 158 158 }; 159 160 159 160 161 161 /// Class for identifying an arc of the digraph 162 162 … … 192 192 bool operator!=(Arc) const { return true; } 193 193 194 195 196 197 198 199 200 201 202 203 }; 204 194 /// Artificial ordering operator. 195 196 /// To allow the use of digraph descriptors as key type in std::map or 197 /// similar associative container we require this. 198 /// 199 /// \note This operator only have to define some strict ordering of 200 /// the items; this order has nothing to do with the iteration 201 /// ordering of the items. 202 bool operator<(Arc) const { return false; } 203 }; 204 205 205 /// This iterator goes trough the outgoing arcs of a node. 206 206 … … 214 214 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; 215 215 ///\endcode 216 216 217 217 class OutArcIt : public Arc { 218 218 public: … … 233 233 OutArcIt(Invalid) { } 234 234 /// This constructor sets the iterator to the first outgoing arc. 235 235 236 236 /// This constructor sets the iterator to the first outgoing arc of 237 237 /// the node. … … 240 240 241 241 /// Sets the iterator to the value of the trivial iterator. 242 /// This feature necessitates that each time we 242 /// This feature necessitates that each time we 243 243 /// iterate the arc-set, the iteration order is the same. 244 244 OutArcIt(const Digraph&, const Arc&) { } 245 245 ///Next outgoing arc 246 247 /// Assign the iterator to the next 246 247 /// Assign the iterator to the next 248 248 /// outgoing arc of the corresponding node. 249 249 OutArcIt& operator++() { return *this; } … … 280 280 InArcIt(Invalid) { } 281 281 /// This constructor sets the iterator to first incoming arc. 282 282 283 283 /// This constructor set the iterator to the first incoming arc of 284 284 /// the node. … … 287 287 288 288 /// Sets the iterator to the value of the trivial iterator \c e. 289 /// This feature necessitates that each time we 289 /// This feature necessitates that each time we 290 290 /// iterate the arc-set, the iteration order is the same. 291 291 InArcIt(const Digraph&, const Arc&) { } … … 323 323 ArcIt(Invalid) { } 324 324 /// This constructor sets the iterator to the first arc. 325 325 326 326 /// This constructor sets the iterator to the first arc of \c g. 327 327 ///@param g the digraph … … 330 330 331 331 /// Sets the iterator to the value of the trivial iterator \c e. 332 /// This feature necessitates that each time we 332 /// This feature necessitates that each time we 333 333 /// iterate the arc-set, the iteration order is the same. 334 ArcIt(const Digraph&, const Arc&) { } 334 ArcIt(const Digraph&, const Arc&) { } 335 335 ///Next arc 336 336 337 337 /// Assign the iterator to the next arc. 338 338 ArcIt& operator++() { return *this; } … … 350 350 351 351 /// \brief Returns the ID of the node. 352 int id(Node) const { return -1; } 352 int id(Node) const { return -1; } 353 353 354 354 /// \brief Returns the ID of the arc. 355 int id(Arc) const { return -1; } 355 int id(Arc) const { return -1; } 356 356 357 357 /// \brief Returns the node with the given ID. 358 358 /// 359 359 /// \pre The argument should be a valid node ID in the graph. 360 Node nodeFromId(int) const { return INVALID; } 360 Node nodeFromId(int) const { return INVALID; } 361 361 362 362 /// \brief Returns the arc with the given ID. 363 363 /// 364 364 /// \pre The argument should be a valid arc ID in the graph. 365 Arc arcFromId(int) const { return INVALID; } 365 Arc arcFromId(int) const { return INVALID; } 366 366 367 367 /// \brief Returns an upper bound on the node IDs. 368 int maxNodeId() const { return -1; } 368 int maxNodeId() const { return -1; } 369 369 370 370 /// \brief Returns an upper bound on the arc IDs. 371 int maxArcId() const { return -1; } 371 int maxArcId() const { return -1; } 372 372 373 373 void first(Node&) const {} … … 390 390 391 391 // Dummy parameter. 392 int maxId(Node) const { return -1; } 392 int maxId(Node) const { return -1; } 393 393 // Dummy parameter. 394 int maxId(Arc) const { return -1; } 394 int maxId(Arc) const { return -1; } 395 395 396 396 /// \brief The base node of the iterator. … … 424 424 425 425 /// \brief Read write map of the nodes to type \c T. 426 /// 426 /// 427 427 /// ReadWrite map of the nodes to type \c T. 428 428 /// \sa Reference 429 template<class T> 429 template<class T> 430 430 class NodeMap : public ReadWriteMap< Node, T > { 431 431 public: … … 440 440 ///Assignment operator 441 441 template <typename CMap> 442 NodeMap& operator=(const CMap&) { 442 NodeMap& operator=(const CMap&) { 443 443 checkConcept<ReadMap<Node, T>, CMap>(); 444 return *this; 444 return *this; 445 445 } 446 446 }; … … 450 450 /// Reference map of the arcs to type \c T. 451 451 /// \sa Reference 452 template<class T> 452 template<class T> 453 453 class ArcMap : public ReadWriteMap<Arc,T> { 454 454 public: … … 462 462 ///Assignment operator 463 463 template <typename CMap> 464 ArcMap& operator=(const CMap&) { 464 ArcMap& operator=(const CMap&) { 465 465 checkConcept<ReadMap<Arc, T>, CMap>(); 466 return *this; 466 return *this; 467 467 } 468 468 }; … … 472 472 void constraints() { 473 473 checkConcept<IterableDigraphComponent<>, _Digraph>(); 474 474 checkConcept<IDableDigraphComponent<>, _Digraph>(); 475 475 checkConcept<MappableDigraphComponent<>, _Digraph>(); 476 476 } … … 478 478 479 479 }; 480 481 } //namespace concepts 480 481 } //namespace concepts 482 482 } //namespace lemon 483 483 -
lemon/concepts/graph.h
r125 r209 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 66 66 /// direction. The IncEdgeIt iterates also on the same edges 67 67 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 68 /// to Edge. 68 /// to Edge. 69 69 class Graph { 70 70 public: … … 73 73 /// 74 74 /// The undirected graph should be tagged by the UndirectedTag. This 75 /// tag helps the enable_if technics to make compile time 76 /// specializations for undirected graphs. 75 /// tag helps the enable_if technics to make compile time 76 /// specializations for undirected graphs. 77 77 typedef True UndirectedTag; 78 78 79 /// \brief The base type of node iterators, 79 /// \brief The base type of node iterators, 80 80 /// or in other words, the trivial node iterator. 81 81 /// 82 82 /// This is the base type of each node iterator, 83 83 /// thus each kind of node iterator converts to this. 84 /// More precisely each kind of node iterator should be inherited 84 /// More precisely each kind of node iterator should be inherited 85 85 /// from the trivial node iterator. 86 86 class Node { … … 109 109 110 110 /// Inequality operator 111 111 112 112 /// \sa operator==(Node n) 113 113 /// 114 114 bool operator!=(Node) const { return true; } 115 115 116 117 118 119 120 121 122 123 124 125 126 }; 127 116 /// Artificial ordering operator. 117 118 /// To allow the use of graph descriptors as key type in std::map or 119 /// similar associative container we require this. 120 /// 121 /// \note This operator only have to define some strict ordering of 122 /// the items; this order has nothing to do with the iteration 123 /// ordering of the items. 124 bool operator<(Node) const { return false; } 125 126 }; 127 128 128 /// This iterator goes through each node. 129 129 … … 143 143 NodeIt() { } 144 144 /// Copy constructor. 145 145 146 146 /// Copy constructor. 147 147 /// … … 159 159 /// Node -> NodeIt conversion. 160 160 161 /// Sets the iterator to the node of \c the graph pointed by 162 163 /// This feature necessitates that each time we 161 /// Sets the iterator to the node of \c the graph pointed by 162 /// the trivial iterator. 163 /// This feature necessitates that each time we 164 164 /// iterate the arc-set, the iteration order is the same. 165 165 NodeIt(const Graph&, const Node&) { } … … 170 170 NodeIt& operator++() { return *this; } 171 171 }; 172 173 172 173 174 174 /// The base type of the edge iterators. 175 175 … … 204 204 bool operator!=(Edge) const { return true; } 205 205 206 207 208 209 210 211 212 213 214 206 /// Artificial ordering operator. 207 208 /// To allow the use of graph descriptors as key type in std::map or 209 /// similar associative container we require this. 210 /// 211 /// \note This operator only have to define some strict ordering of 212 /// the items; this order has nothing to do with the iteration 213 /// ordering of the items. 214 bool operator<(Edge) const { return false; } 215 215 }; 216 216 … … 242 242 EdgeIt(Invalid) { } 243 243 /// This constructor sets the iterator to the first edge. 244 244 245 245 /// This constructor sets the iterator to the first edge. 246 246 EdgeIt(const Graph&) { } … … 249 249 /// Sets the iterator to the value of the trivial iterator. 250 250 /// This feature necessitates that each time we 251 /// iterate the edge-set, the iteration order is the 252 253 EdgeIt(const Graph&, const Edge&) { } 251 /// iterate the edge-set, the iteration order is the 252 /// same. 253 EdgeIt(const Graph&, const Edge&) { } 254 254 /// Next edge 255 255 256 256 /// Assign the iterator to the next edge. 257 257 EdgeIt& operator++() { return *this; } 258 258 }; 259 259 260 /// \brief This iterator goes trough the incident undirected 260 /// \brief This iterator goes trough the incident undirected 261 261 /// arcs of a node. 262 262 /// 263 263 /// This iterator goes trough the incident edges 264 /// of a certain node of a graph. You should assume that the 264 /// of a certain node of a graph. You should assume that the 265 265 /// loop arcs will be iterated twice. 266 /// 266 /// 267 267 /// Its usage is quite simple, for example you can compute the 268 268 /// degree (i.e. count the number of incident arcs of a node \c n 269 /// in graph \c g of type \c Graph as follows. 269 /// in graph \c g of type \c Graph as follows. 270 270 /// 271 271 ///\code … … 291 291 IncEdgeIt(Invalid) { } 292 292 /// This constructor sets the iterator to first incident arc. 293 293 294 294 /// This constructor set the iterator to the first incident arc of 295 295 /// the node. … … 298 298 299 299 /// Sets the iterator to the value of the trivial iterator \c e. 300 /// This feature necessitates that each time we 300 /// This feature necessitates that each time we 301 301 /// iterate the arc-set, the iteration order is the same. 302 302 IncEdgeIt(const Graph&, const Edge&) { } … … 304 304 305 305 /// Assign the iterator to the next incident arc 306 306 /// of the corresponding node. 307 307 IncEdgeIt& operator++() { return *this; } 308 308 }; … … 341 341 bool operator!=(Arc) const { return true; } 342 342 343 344 345 346 347 348 349 350 351 352 353 }; 343 /// Artificial ordering operator. 344 345 /// To allow the use of graph descriptors as key type in std::map or 346 /// similar associative container we require this. 347 /// 348 /// \note This operator only have to define some strict ordering of 349 /// the items; this order has nothing to do with the iteration 350 /// ordering of the items. 351 bool operator<(Arc) const { return false; } 352 353 }; 354 354 /// This iterator goes through each directed arc. 355 355 … … 379 379 ArcIt(Invalid) { } 380 380 /// This constructor sets the iterator to the first arc. 381 381 382 382 /// This constructor sets the iterator to the first arc of \c g. 383 383 ///@param g the graph … … 386 386 387 387 /// Sets the iterator to the value of the trivial iterator \c e. 388 /// This feature necessitates that each time we 388 /// This feature necessitates that each time we 389 389 /// iterate the arc-set, the iteration order is the same. 390 ArcIt(const Graph&, const Arc&) { } 390 ArcIt(const Graph&, const Arc&) { } 391 391 ///Next arc 392 392 393 393 /// Assign the iterator to the next arc. 394 394 ArcIt& operator++() { return *this; } 395 395 }; 396 396 397 397 /// This iterator goes trough the outgoing directed arcs of a node. 398 398 … … 406 406 /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; 407 407 ///\endcode 408 408 409 409 class OutArcIt : public Arc { 410 410 public: … … 425 425 OutArcIt(Invalid) { } 426 426 /// This constructor sets the iterator to the first outgoing arc. 427 427 428 428 /// This constructor sets the iterator to the first outgoing arc of 429 429 /// the node. … … 431 431 ///@param g the graph 432 432 OutArcIt(const Graph& n, const Node& g) { 433 434 435 433 ignore_unused_variable_warning(n); 434 ignore_unused_variable_warning(g); 435 } 436 436 /// Arc -> OutArcIt conversion 437 437 438 438 /// Sets the iterator to the value of the trivial iterator. 439 /// This feature necessitates that each time we 439 /// This feature necessitates that each time we 440 440 /// iterate the arc-set, the iteration order is the same. 441 441 OutArcIt(const Graph&, const Arc&) { } 442 442 ///Next outgoing arc 443 444 /// Assign the iterator to the next 443 444 /// Assign the iterator to the next 445 445 /// outgoing arc of the corresponding node. 446 446 OutArcIt& operator++() { return *this; } … … 477 477 InArcIt(Invalid) { } 478 478 /// This constructor sets the iterator to first incoming arc. 479 479 480 480 /// This constructor set the iterator to the first incoming arc of 481 481 /// the node. 482 482 ///@param n the node 483 483 ///@param g the graph 484 InArcIt(const Graph& g, const Node& n) { 485 486 487 484 InArcIt(const Graph& g, const Node& n) { 485 ignore_unused_variable_warning(n); 486 ignore_unused_variable_warning(g); 487 } 488 488 /// Arc -> InArcIt conversion 489 489 490 490 /// Sets the iterator to the value of the trivial iterator \c e. 491 /// This feature necessitates that each time we 491 /// This feature necessitates that each time we 492 492 /// iterate the arc-set, the iteration order is the same. 493 493 InArcIt(const Graph&, const Arc&) { } … … 500 500 501 501 /// \brief Read write map of the nodes to type \c T. 502 /// 502 /// 503 503 /// ReadWrite map of the nodes to type \c T. 504 504 /// \sa Reference 505 template<class T> 505 template<class T> 506 506 class NodeMap : public ReadWriteMap< Node, T > 507 507 { … … 517 517 ///Assignment operator 518 518 template <typename CMap> 519 NodeMap& operator=(const CMap&) { 519 NodeMap& operator=(const CMap&) { 520 520 checkConcept<ReadMap<Node, T>, CMap>(); 521 return *this; 521 return *this; 522 522 } 523 523 }; … … 527 527 /// Reference map of the directed arcs to type \c T. 528 528 /// \sa Reference 529 template<class T> 529 template<class T> 530 530 class ArcMap : public ReadWriteMap<Arc,T> 531 531 { … … 540 540 ///Assignment operator 541 541 template <typename CMap> 542 ArcMap& operator=(const CMap&) { 542 ArcMap& operator=(const CMap&) { 543 543 checkConcept<ReadMap<Arc, T>, CMap>(); 544 return *this; 544 return *this; 545 545 } 546 546 }; … … 550 550 /// Reference map of the arcs to type \c T. 551 551 /// \sa Reference 552 template<class T> 552 template<class T> 553 553 class EdgeMap : public ReadWriteMap<Edge,T> 554 554 { … … 563 563 ///Assignment operator 564 564 template <typename CMap> 565 EdgeMap& operator=(const CMap&) { 565 EdgeMap& operator=(const CMap&) { 566 566 checkConcept<ReadMap<Edge, T>, CMap>(); 567 return *this; 567 return *this; 568 568 } 569 569 }; … … 574 574 /// will be the given node. 575 575 Arc direct(const Edge&, const Node&) const { 576 576 return INVALID; 577 577 } 578 578 … … 584 584 /// the directed arc is the same when the given bool is true. 585 585 Arc direct(const Edge&, bool) const { 586 586 return INVALID; 587 587 } 588 588 … … 626 626 627 627 /// \brief Returns the id of the node. 628 int id(Node) const { return -1; } 628 int id(Node) const { return -1; } 629 629 630 630 /// \brief Returns the id of the edge. 631 int id(Edge) const { return -1; } 631 int id(Edge) const { return -1; } 632 632 633 633 /// \brief Returns the id of the arc. 634 int id(Arc) const { return -1; } 634 int id(Arc) const { return -1; } 635 635 636 636 /// \brief Returns the node with the given id. 637 637 /// 638 638 /// \pre The argument should be a valid node id in the graph. 639 Node nodeFromId(int) const { return INVALID; } 639 Node nodeFromId(int) const { return INVALID; } 640 640 641 641 /// \brief Returns the edge with the given id. 642 642 /// 643 643 /// \pre The argument should be a valid edge id in the graph. 644 Edge edgeFromId(int) const { return INVALID; } 644 Edge edgeFromId(int) const { return INVALID; } 645 645 646 646 /// \brief Returns the arc with the given id. 647 647 /// 648 648 /// \pre The argument should be a valid arc id in the graph. 649 Arc arcFromId(int) const { return INVALID; } 649 Arc arcFromId(int) const { return INVALID; } 650 650 651 651 /// \brief Returns an upper bound on the node IDs. 652 int maxNodeId() const { return -1; } 652 int maxNodeId() const { return -1; } 653 653 654 654 /// \brief Returns an upper bound on the edge IDs. 655 int maxEdgeId() const { return -1; } 655 int maxEdgeId() const { return -1; } 656 656 657 657 /// \brief Returns an upper bound on the arc IDs. 658 int maxArcId() const { return -1; } 658 int maxArcId() const { return -1; } 659 659 660 660 void first(Node&) const {} … … 684 684 685 685 // Dummy parameter. 686 int maxId(Node) const { return -1; } 686 int maxId(Node) const { return -1; } 687 687 // Dummy parameter. 688 int maxId(Edge) const { return -1; } 688 int maxId(Edge) const { return -1; } 689 689 // Dummy parameter. 690 int maxId(Arc) const { return -1; } 690 int maxId(Arc) const { return -1; } 691 691 692 692 /// \brief Base node of the iterator … … 694 694 /// Returns the base node (the source in this case) of the iterator 695 695 Node baseNode(OutArcIt e) const { 696 696 return source(e); 697 697 } 698 698 /// \brief Running node of the iterator … … 701 701 /// iterator 702 702 Node runningNode(OutArcIt e) const { 703 703 return target(e); 704 704 } 705 705 … … 708 708 /// Returns the base node (the target in this case) of the iterator 709 709 Node baseNode(InArcIt e) const { 710 710 return target(e); 711 711 } 712 712 /// \brief Running node of the iterator … … 715 715 /// iterator 716 716 Node runningNode(InArcIt e) const { 717 717 return source(e); 718 718 } 719 719 … … 722 722 /// Returns the base node of the iterator 723 723 Node baseNode(IncEdgeIt) const { 724 724 return INVALID; 725 725 } 726 726 727 727 /// \brief Running node of the iterator 728 728 /// 729 729 /// Returns the running node of the iterator 730 730 Node runningNode(IncEdgeIt) const { 731 731 return INVALID; 732 732 } 733 733 734 734 template <typename _Graph> 735 735 struct Constraints { 736 737 738 739 740 736 void constraints() { 737 checkConcept<IterableGraphComponent<>, _Graph>(); 738 checkConcept<IDableGraphComponent<>, _Graph>(); 739 checkConcept<MappableGraphComponent<>, _Graph>(); 740 } 741 741 }; 742 742 -
lemon/concepts/graph_components.h
r169 r209 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 50 50 public: 51 51 /// \brief Default constructor. 52 /// 52 /// 53 53 /// \warning The default constructor is not required to set 54 54 /// the item to some well-defined value. So you should consider it … … 67 67 /// \brief Assign operator for nodes. 68 68 /// 69 /// The nodes are assignable. 69 /// The nodes are assignable. 70 70 /// 71 71 GraphItem& operator=(GraphItem const&) { return *this; } … … 93 93 template<typename _GraphItem> 94 94 struct Constraints { 95 96 97 98 99 100 101 102 103 //b = (ia == ib) && (ia != ib) && (ia < ib);104 105 95 void constraints() { 96 _GraphItem i1; 97 _GraphItem i2 = i1; 98 _GraphItem i3 = INVALID; 99 100 i1 = i2 = i3; 101 102 bool b; 103 // b = (ia == ib) && (ia != ib) && (ia < ib); 104 b = (ia == ib) && (ia != ib); 105 b = (ia == INVALID) && (ib != INVALID); 106 106 b = (ia < ib); 107 108 109 110 107 } 108 109 const _GraphItem &ia; 110 const _GraphItem &ib; 111 111 }; 112 112 }; 113 113 114 114 /// \brief An empty base directed graph class. 115 /// 115 /// 116 116 /// This class provides the minimal set of features needed for a 117 117 /// directed graph structure. All digraph concepts have to be … … 123 123 124 124 typedef BaseDigraphComponent Digraph; 125 125 126 126 /// \brief Node class of the digraph. 127 127 /// 128 /// This class represents the Nodes of the digraph. 128 /// This class represents the Nodes of the digraph. 129 129 /// 130 130 typedef GraphItem<'n'> Node; … … 132 132 /// \brief Arc class of the digraph. 133 133 /// 134 /// This class represents the Arcs of the digraph. 134 /// This class represents the Arcs of the digraph. 135 135 /// 136 136 typedef GraphItem<'e'> Arc; … … 157 157 template <typename _Digraph> 158 158 struct Constraints { 159 160 161 162 163 164 165 166 167 168 169 159 typedef typename _Digraph::Node Node; 160 typedef typename _Digraph::Arc Arc; 161 162 void constraints() { 163 checkConcept<GraphItem<'n'>, Node>(); 164 checkConcept<GraphItem<'a'>, Arc>(); 165 { 166 Node n; 167 Arc e(INVALID); 168 n = digraph.source(e); 169 n = digraph.target(e); 170 170 n = digraph.oppositeNode(n, e); 171 } 172 173 174 171 } 172 } 173 174 const _Digraph& digraph; 175 175 }; 176 176 }; 177 177 178 178 /// \brief An empty base undirected graph class. 179 /// 179 /// 180 180 /// This class provides the minimal set of features needed for an 181 181 /// undirected graph structure. All undirected graph concepts have … … 200 200 typedef GraphItem<'u'> Parent; 201 201 /// \brief Default constructor. 202 /// 202 /// 203 203 /// \warning The default constructor is not required to set 204 204 /// the item to some well-defined value. So you should consider it … … 218 218 /// 219 219 /// Besides the core graph item functionality each arc should 220 /// be convertible to the represented edge. 220 /// be convertible to the represented edge. 221 221 Edge(const Arc&) {} 222 222 /// \brief Assign arc to edge. 223 223 /// 224 224 /// Besides the core graph item functionality each arc should 225 /// be convertible to the represented edge. 225 /// be convertible to the represented edge. 226 226 Edge& operator=(const Arc&) { return *this; } 227 227 }; … … 238 238 /// Returns the directed arc from its direction and the 239 239 /// represented edge. 240 Arc direct(const Edge&, bool) const { return INVALID;} 240 Arc direct(const Edge&, bool) const { return INVALID;} 241 241 242 242 /// \brief Returns the directed arc. … … 244 244 /// Returns the directed arc from its source and the 245 245 /// represented edge. 246 Arc direct(const Edge&, const Node&) const { return INVALID;} 246 Arc direct(const Edge&, const Node&) const { return INVALID;} 247 247 248 248 /// \brief Returns the opposite arc. … … 261 261 /// Gives back the other ending of an edge. 262 262 Node v(const Edge&) const { return INVALID;} 263 263 264 264 template <typename _Graph> 265 265 struct Constraints { 266 267 268 269 270 266 typedef typename _Graph::Node Node; 267 typedef typename _Graph::Arc Arc; 268 typedef typename _Graph::Edge Edge; 269 270 void constraints() { 271 271 checkConcept<BaseDigraphComponent, _Graph>(); 272 273 274 275 272 checkConcept<GraphItem<'u'>, Edge>(); 273 { 274 Node n; 275 Edge ue(INVALID); 276 276 Arc e; 277 278 277 n = graph.u(ue); 278 n = graph.v(ue); 279 279 e = graph.direct(ue, true); 280 280 e = graph.direct(ue, n); … … 283 283 bool d = graph.direction(e); 284 284 ignore_unused_variable_warning(d); 285 } 286 287 288 285 } 286 } 287 288 const _Graph& graph; 289 289 }; 290 290 … … 292 292 293 293 /// \brief An empty idable base digraph class. 294 /// 294 /// 295 295 /// This class provides beside the core digraph features 296 296 /// core id functions for the digraph structure. … … 305 305 typedef typename Base::Arc Arc; 306 306 307 /// \brief Gives back an unique integer id for the Node. 308 /// 309 /// Gives back an unique integer id for the Node. 307 /// \brief Gives back an unique integer id for the Node. 308 /// 309 /// Gives back an unique integer id for the Node. 310 310 /// 311 311 int id(const Node&) const { return -1;} … … 315 315 /// Gives back the node by the unique id. 316 316 /// If the digraph does not contain node with the given id 317 /// then the result of the function is undetermined. 317 /// then the result of the function is undetermined. 318 318 Node nodeFromId(int) const { return INVALID;} 319 319 320 /// \brief Gives back an unique integer id for the Arc. 321 /// 322 /// Gives back an unique integer id for the Arc. 320 /// \brief Gives back an unique integer id for the Arc. 321 /// 322 /// Gives back an unique integer id for the Arc. 323 323 /// 324 324 int id(const Arc&) const { return -1;} … … 328 328 /// Gives back the arc by the unique id. 329 329 /// If the digraph does not contain arc with the given id 330 /// then the result of the function is undetermined. 330 /// then the result of the function is undetermined. 331 331 Arc arcFromId(int) const { return INVALID;} 332 332 … … 348 348 struct Constraints { 349 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 350 void constraints() { 351 checkConcept<Base, _Digraph >(); 352 typename _Digraph::Node node; 353 int nid = digraph.id(node); 354 nid = digraph.id(node); 355 node = digraph.nodeFromId(nid); 356 typename _Digraph::Arc arc; 357 int eid = digraph.id(arc); 358 eid = digraph.id(arc); 359 arc = digraph.arcFromId(eid); 360 361 nid = digraph.maxNodeId(); 362 ignore_unused_variable_warning(nid); 363 eid = digraph.maxArcId(); 364 ignore_unused_variable_warning(eid); 365 } 366 367 const _Digraph& digraph; 368 368 }; 369 369 }; 370 370 371 371 /// \brief An empty idable base undirected graph class. 372 /// 372 /// 373 373 /// This class provides beside the core undirected graph features 374 374 /// core id functions for the undirected graph structure. The … … 384 384 using IDableDigraphComponent<_Base>::id; 385 385 386 /// \brief Gives back an unique integer id for the Edge. 387 /// 388 /// Gives back an unique integer id for the Edge. 386 /// \brief Gives back an unique integer id for the Edge. 387 /// 388 /// Gives back an unique integer id for the Edge. 389 389 /// 390 390 int id(const Edge&) const { return -1;} … … 407 407 struct Constraints { 408 408 409 410 411 412 413 414 415 416 417 418 419 420 409 void constraints() { 410 checkConcept<Base, _Graph >(); 411 checkConcept<IDableDigraphComponent<Base>, _Graph >(); 412 typename _Graph::Edge edge; 413 int ueid = graph.id(edge); 414 ueid = graph.id(edge); 415 edge = graph.edgeFromId(ueid); 416 ueid = graph.maxEdgeId(); 417 ignore_unused_variable_warning(ueid); 418 } 419 420 const _Graph& graph; 421 421 }; 422 422 }; … … 451 451 /// \brief Assign operator for items. 452 452 /// 453 /// The items are assignable. 454 /// 455 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 453 /// The items are assignable. 454 /// 455 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 456 456 /// \brief Next item. 457 /// 457 /// 458 458 /// Assign the iterator to the next item. 459 459 /// 460 460 GraphItemIt& operator++() { return *this; } 461 461 /// \brief Equality operator 462 /// 462 /// 463 463 /// Two iterators are equal if and only if they point to the 464 464 /// same object or both are invalid. 465 465 bool operator==(const GraphItemIt&) const { return true;} 466 466 /// \brief Inequality operator 467 /// 467 /// 468 468 /// \sa operator==(Node n) 469 469 /// 470 470 bool operator!=(const GraphItemIt&) const { return true;} 471 471 472 472 template<typename _GraphItemIt> 473 473 struct Constraints { 474 475 _GraphItemIt it1(g); 476 477 478 479 480 481 482 483 484 485 474 void constraints() { 475 _GraphItemIt it1(g); 476 _GraphItemIt it2; 477 478 it2 = ++it1; 479 ++it2 = it1; 480 ++(++it1); 481 482 _Item bi = it1; 483 bi = it2; 484 } 485 _Graph& g; 486 486 }; 487 487 }; … … 490 490 /// 491 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 492 /// base class, the _selector is a additional template parameter. For 493 /// InArcIt you should instantiate it with character 'i' and for 494 494 /// OutArcIt with 'o'. 495 495 template <typename _Graph, 496 497 typename _Base = typename _Graph::Node, 498 496 typename _Item = typename _Graph::Arc, 497 typename _Base = typename _Graph::Node, 498 char _selector = '0'> 499 499 class GraphIncIt : public _Item { 500 500 public: … … 509 509 /// 510 510 GraphIncIt(GraphIncIt const& gi) : _Item(gi) {} 511 /// \brief Sets the iterator to the first arc incoming into or outgoing 511 /// \brief Sets the iterator to the first arc incoming into or outgoing 512 512 /// from the node. 513 513 /// 514 /// Sets the iterator to the first arc incoming into or outgoing 514 /// Sets the iterator to the first arc incoming into or outgoing 515 515 /// from the node. 516 516 /// … … 523 523 /// \brief Assign operator for iterators. 524 524 /// 525 /// The iterators are assignable. 526 /// 527 GraphIncIt& operator=(GraphIncIt const&) { return *this; } 525 /// The iterators are assignable. 526 /// 527 GraphIncIt& operator=(GraphIncIt const&) { return *this; } 528 528 /// \brief Next item. 529 529 /// … … 546 546 template <typename _GraphIncIt> 547 547 struct Constraints { 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 548 void constraints() { 549 checkConcept<GraphItem<_selector>, _GraphIncIt>(); 550 _GraphIncIt it1(graph, node); 551 _GraphIncIt it2; 552 553 it2 = ++it1; 554 ++it2 = it1; 555 ++(++it1); 556 _Item e = it1; 557 e = it2; 558 559 } 560 561 _Item arc; 562 _Base node; 563 _Graph graph; 564 _GraphIncIt it; 565 565 }; 566 566 }; … … 576 576 577 577 public: 578 578 579 579 typedef _Base Base; 580 580 typedef typename Base::Node Node; … … 584 584 585 585 /// \name Base iteration 586 /// 586 /// 587 587 /// This interface provides functions for iteration on digraph items 588 588 /// 589 /// @{ 589 /// @{ 590 590 591 591 /// \brief Gives back the first node in the iterating order. 592 /// 592 /// 593 593 /// Gives back the first node in the iterating order. 594 /// 594 /// 595 595 void first(Node&) const {} 596 596 … … 598 598 /// 599 599 /// Gives back the next node in the iterating order. 600 /// 600 /// 601 601 void next(Node&) const {} 602 602 … … 604 604 /// 605 605 /// Gives back the first arc in the iterating order. 606 /// 606 /// 607 607 void first(Arc&) const {} 608 608 … … 610 610 /// 611 611 /// Gives back the next arc in the iterating order. 612 /// 612 /// 613 613 void next(Arc&) const {} 614 614 … … 618 618 /// 619 619 /// Gives back the first of the arcs point to the given node. 620 /// 620 /// 621 621 void firstIn(Arc&, const Node&) const {} 622 622 … … 630 630 /// \brief Gives back the first of the arcs start from the 631 631 /// given node. 632 /// 632 /// 633 633 /// Gives back the first of the arcs start from the given node. 634 /// 634 /// 635 635 void firstOut(Arc&, const Node&) const {} 636 636 … … 639 639 /// 640 640 /// Gives back the next of the arcs start from the given node. 641 /// 641 /// 642 642 void nextOut(Arc&) const {} 643 643 … … 645 645 646 646 /// \name Class based iteration 647 /// 647 /// 648 648 /// This interface provides functions for iteration on digraph items 649 649 /// … … 700 700 /// @} 701 701 702 template <typename _Digraph> 703 struct Constraints { 704 705 702 template <typename _Digraph> 703 struct Constraints { 704 void constraints() { 705 checkConcept<Base, _Digraph>(); 706 706 707 707 { 708 typename _Digraph::Node node(INVALID); 708 typename _Digraph::Node node(INVALID); 709 709 typename _Digraph::Arc arc(INVALID); 710 710 { … … 724 724 digraph.nextOut(arc); 725 725 } 726 } 726 } 727 727 728 728 { … … 731 731 checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>, 732 732 typename _Digraph::NodeIt >(); 733 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 733 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 734 734 typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>(); 735 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 735 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 736 736 typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>(); 737 737 … … 746 746 } 747 747 } 748 749 750 748 749 const _Digraph& digraph; 750 751 751 }; 752 752 }; … … 766 766 typedef typename Base::Edge Edge; 767 767 768 768 769 769 typedef IterableGraphComponent Graph; 770 770 771 771 /// \name Base iteration 772 /// 772 /// 773 773 /// This interface provides functions for iteration on graph items 774 /// @{ 774 /// @{ 775 775 776 776 using IterableDigraphComponent<_Base>::first; … … 781 781 /// 782 782 /// Gives back the first edge in the iterating order. 783 /// 783 /// 784 784 void first(Edge&) const {} 785 785 … … 788 788 /// 789 789 /// Gives back the next edge in the iterating order. 790 /// 790 /// 791 791 void next(Edge&) const {} 792 792 … … 815 815 816 816 /// \name Class based iteration 817 /// 817 /// 818 818 /// This interface provides functions for iteration on graph items 819 819 /// … … 842 842 /// @} 843 843 844 template <typename _Graph> 845 struct Constraints { 846 847 844 template <typename _Graph> 845 struct Constraints { 846 void constraints() { 847 checkConcept<IterableDigraphComponent<Base>, _Graph>(); 848 848 849 849 { … … 859 859 graph.nextInc(edge, dir); 860 860 } 861 862 } 863 861 862 } 863 864 864 { 865 865 checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>, 866 866 typename _Graph::EdgeIt >(); 867 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 867 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 868 868 typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>(); 869 869 870 870 typename _Graph::Node n; 871 871 typename _Graph::IncEdgeIt ueit(INVALID); … … 874 874 } 875 875 } 876 877 878 876 877 const _Graph& graph; 878 879 879 }; 880 880 }; 881 881 882 882 /// \brief An empty alteration notifier digraph class. 883 /// 883 /// 884 884 /// This class provides beside the core digraph features alteration 885 885 /// notifier interface for the digraph structure. This implements … … 898 898 899 899 /// The node observer registry. 900 typedef AlterationNotifier<AlterableDigraphComponent, Node> 900 typedef AlterationNotifier<AlterableDigraphComponent, Node> 901 901 NodeNotifier; 902 902 /// The arc observer registry. 903 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 903 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 904 904 ArcNotifier; 905 905 906 906 /// \brief Gives back the node alteration notifier. 907 907 /// 908 908 /// Gives back the node alteration notifier. 909 909 NodeNotifier& notifier(Node) const { 910 910 return NodeNotifier(); 911 911 } 912 912 913 913 /// \brief Gives back the arc alteration notifier. 914 914 /// 915 915 /// Gives back the arc alteration notifier. 916 916 ArcNotifier& notifier(Arc) const { 917 917 return ArcNotifier(); 918 918 } 919 919 920 template <typename _Digraph> 921 struct Constraints { 922 923 924 typename _Digraph::NodeNotifier& nn 920 template <typename _Digraph> 921 struct Constraints { 922 void constraints() { 923 checkConcept<Base, _Digraph>(); 924 typename _Digraph::NodeNotifier& nn 925 925 = digraph.notifier(typename _Digraph::Node()); 926 926 927 typename _Digraph::ArcNotifier& en 927 typename _Digraph::ArcNotifier& en 928 928 = digraph.notifier(typename _Digraph::Arc()); 929 929 930 930 ignore_unused_variable_warning(nn); 931 931 ignore_unused_variable_warning(en); 932 933 934 935 936 }; 937 932 } 933 934 const _Digraph& digraph; 935 936 }; 937 938 938 }; 939 939 940 940 /// \brief An empty alteration notifier undirected graph class. 941 /// 941 /// 942 942 /// This class provides beside the core graph features alteration 943 943 /// notifier interface for the graph structure. This implements … … 955 955 956 956 /// The arc observer registry. 957 typedef AlterationNotifier<AlterableGraphComponent, Edge> 957 typedef AlterationNotifier<AlterableGraphComponent, Edge> 958 958 EdgeNotifier; 959 959 960 960 /// \brief Gives back the arc alteration notifier. 961 961 /// 962 962 /// Gives back the arc alteration notifier. 963 963 EdgeNotifier& notifier(Edge) const { 964 964 return EdgeNotifier(); 965 965 } 966 966 967 template <typename _Graph> 968 struct Constraints { 969 970 971 typename _Graph::EdgeNotifier& uen 967 template <typename _Graph> 968 struct Constraints { 969 void constraints() { 970 checkConcept<AlterableGraphComponent<Base>, _Graph>(); 971 typename _Graph::EdgeNotifier& uen 972 972 = graph.notifier(typename _Graph::Edge()); 973 973 ignore_unused_variable_warning(uen); 974 975 976 977 978 }; 979 974 } 975 976 const _Graph& graph; 977 978 }; 979 980 980 }; 981 981 982 982 /// \brief Class describing the concept of graph maps 983 /// 983 /// 984 984 /// This class describes the common interface of the graph maps 985 985 /// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to … … 1010 1010 /// Copy Constructor. 1011 1011 GraphMap(const GraphMap&) : Parent() {} 1012 1012 1013 1013 /// \brief Assign operator. 1014 1014 /// 1015 1015 /// Assign operator. It does not mofify the underlying graph, 1016 1016 /// it just iterates on the current item set and set the map 1017 /// with the value returned by the assigned map. 1017 /// with the value returned by the assigned map. 1018 1018 template <typename CMap> 1019 GraphMap& operator=(const CMap&) { 1019 GraphMap& operator=(const CMap&) { 1020 1020 checkConcept<ReadMap<Key, Value>, CMap>(); 1021 1021 return *this; … … 1024 1024 template<typename _Map> 1025 1025 struct Constraints { 1026 1027 1028 1029 1030 1031 1032 1033 1034 1026 void constraints() { 1027 checkConcept<ReadWriteMap<Key, Value>, _Map >(); 1028 // Construction with a graph parameter 1029 _Map a(g); 1030 // Constructor with a graph and a default value parameter 1031 _Map a2(g,t); 1032 // Copy constructor. 1033 _Map b(c); 1034 1035 1035 ReadMap<Key, Value> cmap; 1036 1036 b = cmap; 1037 1037 1038 1039 1040 1041 1042 1043 1044 1038 ignore_unused_variable_warning(a2); 1039 ignore_unused_variable_warning(b); 1040 } 1041 1042 const _Map &c; 1043 const Graph &g; 1044 const typename GraphMap::Value &t; 1045 1045 }; 1046 1046 … … 1071 1071 typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent; 1072 1072 1073 1074 1075 1076 explicit NodeMap(const MappableDigraphComponent& digraph) 1073 /// \brief Construct a new map. 1074 /// 1075 /// Construct a new map for the digraph. 1076 explicit NodeMap(const MappableDigraphComponent& digraph) 1077 1077 : Parent(digraph) {} 1078 1078 1079 1080 1081 1082 1079 /// \brief Construct a new map with default value. 1080 /// 1081 /// Construct a new map for the digraph and initalise the values. 1082 NodeMap(const MappableDigraphComponent& digraph, const _Value& value) 1083 1083 : Parent(digraph, value) {} 1084 1084 1085 1086 1087 1088 1089 1090 1091 1092 1085 /// \brief Copy constructor. 1086 /// 1087 /// Copy Constructor. 1088 NodeMap(const NodeMap& nm) : Parent(nm) {} 1089 1090 /// \brief Assign operator. 1091 /// 1092 /// Assign operator. 1093 1093 template <typename CMap> 1094 NodeMap& operator=(const CMap&) { 1094 NodeMap& operator=(const CMap&) { 1095 1095 checkConcept<ReadMap<Node, _Value>, CMap>(); 1096 1096 return *this; … … 1108 1108 typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent; 1109 1109 1110 1111 1112 1113 explicit ArcMap(const MappableDigraphComponent& digraph) 1110 /// \brief Construct a new map. 1111 /// 1112 /// Construct a new map for the digraph. 1113 explicit ArcMap(const MappableDigraphComponent& digraph) 1114 1114 : Parent(digraph) {} 1115 1115 1116 1117 1118 1119 1116 /// \brief Construct a new map with default value. 1117 /// 1118 /// Construct a new map for the digraph and initalise the values. 1119 ArcMap(const MappableDigraphComponent& digraph, const _Value& value) 1120 1120 : Parent(digraph, value) {} 1121 1121 1122 1123 1124 1125 1126 1127 1128 1129 1122 /// \brief Copy constructor. 1123 /// 1124 /// Copy Constructor. 1125 ArcMap(const ArcMap& nm) : Parent(nm) {} 1126 1127 /// \brief Assign operator. 1128 /// 1129 /// Assign operator. 1130 1130 template <typename CMap> 1131 ArcMap& operator=(const CMap&) { 1131 ArcMap& operator=(const CMap&) { 1132 1132 checkConcept<ReadMap<Arc, _Value>, CMap>(); 1133 1133 return *this; … … 1140 1140 struct Constraints { 1141 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>, 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 } 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>, 1175 1176 } 1177 1178 1179 1142 struct Dummy { 1143 int value; 1144 Dummy() : value(0) {} 1145 Dummy(int _v) : value(_v) {} 1146 }; 1147 1148 void constraints() { 1149 checkConcept<Base, _Digraph>(); 1150 { // int map test 1151 typedef typename _Digraph::template NodeMap<int> IntNodeMap; 1152 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>, 1153 IntNodeMap >(); 1154 } { // bool map test 1155 typedef typename _Digraph::template NodeMap<bool> BoolNodeMap; 1156 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>, 1157 BoolNodeMap >(); 1158 } { // Dummy map test 1159 typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap; 1160 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>, 1161 DummyNodeMap >(); 1162 } 1163 1164 { // int map test 1165 typedef typename _Digraph::template ArcMap<int> IntArcMap; 1166 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>, 1167 IntArcMap >(); 1168 } { // bool map test 1169 typedef typename _Digraph::template ArcMap<bool> BoolArcMap; 1170 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>, 1171 BoolArcMap >(); 1172 } { // Dummy map test 1173 typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap; 1174 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>, 1175 DummyArcMap >(); 1176 } 1177 } 1178 1179 _Digraph& digraph; 1180 1180 }; 1181 1181 }; … … 1200 1200 /// 1201 1201 template <typename _Value> 1202 class EdgeMap : public GraphMap<Graph, Edge, _Value> { 1202 class EdgeMap : public GraphMap<Graph, Edge, _Value> { 1203 1203 public: 1204 1204 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent; 1205 1205 1206 1207 1208 1209 explicit EdgeMap(const MappableGraphComponent& graph) 1206 /// \brief Construct a new map. 1207 /// 1208 /// Construct a new map for the graph. 1209 explicit EdgeMap(const MappableGraphComponent& graph) 1210 1210 : Parent(graph) {} 1211 1211 1212 1213 1214 1215 1212 /// \brief Construct a new map with default value. 1213 /// 1214 /// Construct a new map for the graph and initalise the values. 1215 EdgeMap(const MappableGraphComponent& graph, const _Value& value) 1216 1216 : Parent(graph, value) {} 1217 1217 1218 1219 1220 1221 1222 1223 1224 1225 1218 /// \brief Copy constructor. 1219 /// 1220 /// Copy Constructor. 1221 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1222 1223 /// \brief Assign operator. 1224 /// 1225 /// Assign operator. 1226 1226 template <typename CMap> 1227 EdgeMap& operator=(const CMap&) { 1227 EdgeMap& operator=(const CMap&) { 1228 1228 checkConcept<ReadMap<Edge, _Value>, CMap>(); 1229 1229 return *this; … … 1236 1236 struct Constraints { 1237 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>, 1258 1259 } 1260 1261 1262 1238 struct Dummy { 1239 int value; 1240 Dummy() : value(0) {} 1241 Dummy(int _v) : value(_v) {} 1242 }; 1243 1244 void constraints() { 1245 checkConcept<MappableGraphComponent<Base>, _Graph>(); 1246 1247 { // int map test 1248 typedef typename _Graph::template EdgeMap<int> IntEdgeMap; 1249 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, 1250 IntEdgeMap >(); 1251 } { // bool map test 1252 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap; 1253 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, 1254 BoolEdgeMap >(); 1255 } { // Dummy map test 1256 typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap; 1257 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>, 1258 DummyEdgeMap >(); 1259 } 1260 } 1261 1262 _Graph& graph; 1263 1263 }; 1264 1264 }; … … 1283 1283 /// 1284 1284 Node addNode() { 1285 1285 return INVALID; 1286 1286 } 1287 1287 1288 1288 /// \brief Adds a new arc connects the given two nodes. 1289 1289 /// 1290 1290 /// Adds a new arc connects the the given two nodes. 1291 1291 Arc addArc(const Node&, const Node&) { 1292 1292 return INVALID; 1293 1293 } 1294 1294 1295 1295 template <typename _Digraph> 1296 1296 struct Constraints { 1297 1297 void constraints() { 1298 1298 checkConcept<Base, _Digraph>(); 1299 1300 1301 1302 1303 1304 1305 1306 1299 typename _Digraph::Node node_a, node_b; 1300 node_a = digraph.addNode(); 1301 node_b = digraph.addNode(); 1302 typename _Digraph::Arc arc; 1303 arc = digraph.addArc(node_a, node_b); 1304 } 1305 1306 _Digraph& digraph; 1307 1307 }; 1308 1308 }; … … 1328 1328 /// 1329 1329 Node addNode() { 1330 1330 return INVALID; 1331 1331 } 1332 1332 1333 1333 /// \brief Adds a new arc connects the given two nodes. 1334 1334 /// 1335 1335 /// Adds a new arc connects the the given two nodes. 1336 1336 Edge addArc(const Node&, const Node&) { 1337 1337 return INVALID; 1338 1338 } 1339 1339 1340 1340 template <typename _Graph> 1341 1341 struct Constraints { 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1342 void constraints() { 1343 checkConcept<Base, _Graph>(); 1344 typename _Graph::Node node_a, node_b; 1345 node_a = graph.addNode(); 1346 node_b = graph.addNode(); 1347 typename _Graph::Edge edge; 1348 edge = graph.addEdge(node_a, node_b); 1349 } 1350 1351 _Graph& graph; 1352 1352 }; 1353 1353 }; 1354 1354 1355 1355 /// \brief An empty erasable digraph class. 1356 /// 1356 /// 1357 1357 /// This class provides beside the core digraph features core erase 1358 1358 /// functions for the digraph structure. The main difference between … … 1369 1369 /// \brief Erase a node from the digraph. 1370 1370 /// 1371 /// Erase a node from the digraph. This function should 1371 /// Erase a node from the digraph. This function should 1372 1372 /// erase all arcs connecting to the node. 1373 void erase(const Node&) {} 1373 void erase(const Node&) {} 1374 1374 1375 1375 /// \brief Erase an arc from the digraph. … … 1381 1381 template <typename _Digraph> 1382 1382 struct Constraints { 1383 1383 void constraints() { 1384 1384 checkConcept<Base, _Digraph>(); 1385 1386 1387 1388 1389 1390 1391 1385 typename _Digraph::Node node; 1386 digraph.erase(node); 1387 typename _Digraph::Arc arc; 1388 digraph.erase(arc); 1389 } 1390 1391 _Digraph& digraph; 1392 1392 }; 1393 1393 }; 1394 1394 1395 1395 /// \brief An empty erasable base undirected graph class. 1396 /// 1396 /// 1397 1397 /// This class provides beside the core undirected graph features 1398 1398 /// core erase functions for the undirceted graph structure. The … … 1411 1411 /// Erase a node from the graph. This function should erase 1412 1412 /// arcs connecting to the node. 1413 void erase(const Node&) {} 1413 void erase(const Node&) {} 1414 1414 1415 1415 /// \brief Erase an arc from the graph. … … 1421 1421 template <typename _Graph> 1422 1422 struct Constraints { 1423 1423 void constraints() { 1424 1424 checkConcept<Base, _Graph>(); 1425 1426 1427 1428 1429 1430 1431 1425 typename _Graph::Node node; 1426 graph.erase(node); 1427 typename _Graph::Edge edge; 1428 graph.erase(edge); 1429 } 1430 1431 _Graph& graph; 1432 1432 }; 1433 1433 }; … … 1449 1449 /// Erase all nodes and arcs from the digraph. 1450 1450 /// 1451 void clear() {} 1451 void clear() {} 1452 1452 1453 1453 template <typename _Digraph> 1454 1454 struct Constraints { 1455 1455 void constraints() { 1456 1456 checkConcept<Base, _Digraph>(); 1457 1458 1459 1460 1457 digraph.clear(); 1458 } 1459 1460 _Digraph digraph; 1461 1461 }; 1462 1462 }; … … 1476 1476 template <typename _Graph> 1477 1477 struct Constraints { 1478 1478 void constraints() { 1479 1479 checkConcept<ClearableGraphComponent<Base>, _Graph>(); 1480 1481 1482 1480 } 1481 1482 _Graph graph; 1483 1483 }; 1484 1484 }; -
lemon/concepts/heap.h
r203 r209 1 /* -*- C++-*-2 * 3 * This file is a part of LEMON, a generic C++ optimization library 1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 53 53 /// the user. 54 54 /// 55 /// The \c ItemIntMap must be initialized in such a way, that it 55 /// The \c ItemIntMap must be initialized in such a way, that it 56 56 /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item. 57 57 enum State { 58 59 60 58 IN_HEAP = 0, 59 PRE_HEAP = -1, 60 POST_HEAP = -2 61 61 }; 62 62 63 63 /// \brief The constructor. 64 64 /// … … 86 86 87 87 /// \brief Inserts an item into the heap with the given priority. 88 /// 89 /// Inserts the given item into the heap with the given priority. 88 /// 89 /// Inserts the given item into the heap with the given priority. 90 90 /// \param i The item to insert. 91 91 /// \param p The priority of the item. … … 113 113 /// 114 114 /// Removes the given item from the heap if it is already stored. 115 /// \param i The item to delete. 115 /// \param i The item to delete. 116 116 void erase(const Item &i) {} 117 117 118 118 /// \brief The priority of an item. 119 119 /// 120 /// Returns the priority of the given item. 120 /// Returns the priority of the given item. 121 121 /// \pre \c i must be in the heap. 122 122 /// \param i The item. … … 134 134 /// \param p The priority. 135 135 void set(const Item &i, const Prio &p) {} 136 136 137 137 /// \brief Decreases the priority of an item to the given value. 138 138 /// … … 175 175 struct Constraints { 176 176 public: 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 177 void constraints() { 178 typedef typename _Heap::Item OwnItem; 179 typedef typename _Heap::Prio OwnPrio; 180 typedef typename _Heap::State OwnState; 181 182 Item item; 183 Prio prio; 184 item=Item(); 185 prio=Prio(); 186 ignore_unused_variable_warning(item); 187 ignore_unused_variable_warning(prio); 188 189 OwnItem own_item; 190 OwnPrio own_prio; 191 OwnState own_state; 192 own_item=Item(); 193 own_prio=Prio(); 194 ignore_unused_variable_warning(own_item); 195 ignore_unused_variable_warning(own_prio); 196 ignore_unused_variable_warning(own_state); 197 198 _Heap heap1(map); 199 _Heap heap2 = heap1; 200 ignore_unused_variable_warning(heap1); 201 ignore_unused_variable_warning(heap2); 202 203 int s = heap.size(); 204 ignore_unused_variable_warning(s); 205 bool e = heap.empty(); 206 ignore_unused_variable_warning(e); 207 208 prio = heap.prio(); 209 item = heap.top(); 210 prio = heap[item]; 211 own_prio = heap.prio(); 212 own_item = heap.top(); 213 own_prio = heap[own_item]; 214 215 heap.push(item, prio); 216 heap.push(own_item, own_prio); 217 heap.pop(); 218 219 heap.set(item, prio); 220 heap.decrease(item, prio); 221 heap.increase(item, prio); 222 heap.set(own_item, own_prio); 223 heap.decrease(own_item, own_prio); 224 heap.increase(own_item, own_prio); 225 226 heap.erase(item); 227 heap.erase(own_item); 228 heap.clear(); 229 230 own_state = heap.state(own_item); 231 heap.state(own_item, own_state); 232 233 own_state = _Heap::PRE_HEAP; 234 own_state = _Heap::IN_HEAP; 235 own_state = _Heap::POST_HEAP; 236 } 237 238 _Heap& heap; 239 ItemIntMap& map; 240 240 }; 241 241 }; -
lemon/concepts/maps.h
r114 r209 1 /* -*- C++-*-2 * 3 * This file is a part of LEMON, a generic C++ optimization library 1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 48 48 49 49 /// Returns the value associated with the given key. 50 Value operator[](const Key &) const { 50 Value operator[](const Key &) const { 51 51 return *static_cast<Value *>(0); 52 52 } … … 54 54 template<typename _ReadMap> 55 55 struct Constraints { 56 57 58 59 60 61 62 63 64 65 66 67 68 69 56 void constraints() { 57 Value val = m[key]; 58 val = m[key]; 59 typename _ReadMap::Value own_val = m[own_key]; 60 own_val = m[own_key]; 61 62 ignore_unused_variable_warning(key); 63 ignore_unused_variable_warning(val); 64 ignore_unused_variable_warning(own_key); 65 ignore_unused_variable_warning(own_val); 66 } 67 const Key& key; 68 const typename _ReadMap::Key& own_key; 69 const _ReadMap& m; 70 70 }; 71 71 … … 94 94 template <typename _WriteMap> 95 95 struct Constraints { 96 97 98 99 100 101 102 103 104 105 106 107 108 109 96 void constraints() { 97 m.set(key, val); 98 m.set(own_key, own_val); 99 100 ignore_unused_variable_warning(key); 101 ignore_unused_variable_warning(val); 102 ignore_unused_variable_warning(own_key); 103 ignore_unused_variable_warning(own_val); 104 } 105 const Key& key; 106 const Value& val; 107 const typename _WriteMap::Key& own_key; 108 const typename _WriteMap::Value& own_val; 109 _WriteMap& m; 110 110 }; 111 111 }; … … 117 117 template<typename K, typename T> 118 118 class ReadWriteMap : public ReadMap<K,T>, 119 119 public WriteMap<K,T> 120 120 { 121 121 public: … … 126 126 127 127 /// Returns the value associated with the given key. 128 Value operator[](const Key &) const { 128 Value operator[](const Key &) const { 129 129 return *static_cast<Value *>(0); 130 130 } … … 135 135 template<typename _ReadWriteMap> 136 136 struct Constraints { 137 138 139 140 137 void constraints() { 138 checkConcept<ReadMap<K, T>, _ReadWriteMap >(); 139 checkConcept<WriteMap<K, T>, _ReadWriteMap >(); 140 } 141 141 }; 142 142 }; … … 165 165 166 166 /// Returns a reference to the value associated with the given key. 167 Reference operator[](const Key &) { 167 Reference operator[](const Key &) { 168 168 return *static_cast<Value *>(0); 169 169 } … … 179 179 template<typename _ReferenceMap> 180 180 struct Constraints { 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 181 void constraints() { 182 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >(); 183 ref = m[key]; 184 m[key] = val; 185 m[key] = ref; 186 m[key] = cref; 187 own_ref = m[own_key]; 188 m[own_key] = own_val; 189 m[own_key] = own_ref; 190 m[own_key] = own_cref; 191 m[key] = m[own_key]; 192 m[own_key] = m[key]; 193 } 194 const Key& key; 195 Value& val; 196 Reference ref; 197 ConstReference cref; 198 const typename _ReferenceMap::Key& own_key; 199 typename _ReferenceMap::Value& own_val; 200 typename _ReferenceMap::Reference own_ref; 201 typename _ReferenceMap::ConstReference own_cref; 202 _ReferenceMap& m; 203 203 }; 204 204 }; -
lemon/concepts/path.h
r157 r209 1 /* -*- C++-*-2 * 3 * This file is a part of LEMON, a generic C++ optimization library 1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 40 40 /// 41 41 /// A skeleton structure for representing directed paths in a 42 /// digraph. 42 /// digraph. 43 43 /// \tparam _Digraph The digraph type in which the path is. 44 44 /// … … 84 84 class ArcIt { 85 85 public: 86 87 88 89 90 91 86 /// Default constructor 87 ArcIt() {} 88 /// Invalid constructor 89 ArcIt(Invalid) {} 90 /// Constructor for first arc 91 ArcIt(const Path &) {} 92 92 93 93 /// Conversion to Arc 94 95 96 97 98 99 100 101 102 103 104 94 operator Arc() const { return INVALID; } 95 96 /// Next arc 97 ArcIt& operator++() {return *this;} 98 99 /// Comparison operator 100 bool operator==(const ArcIt&) const {return true;} 101 /// Comparison operator 102 bool operator!=(const ArcIt&) const {return true;} 103 /// Comparison operator 104 bool operator<(const ArcIt&) const {return false;} 105 105 106 106 }; … … 138 138 139 139 namespace _path_bits { 140 140 141 141 template <typename _Digraph, typename _Path, typename RevPathTag = void> 142 142 struct PathDumperConstraints { … … 163 163 template <typename _Digraph, typename _Path> 164 164 struct PathDumperConstraints< 165 _Digraph, _Path, 165 _Digraph, _Path, 166 166 typename enable_if<typename _Path::RevPathTag, void>::type 167 167 > { … … 185 185 _Path& p; 186 186 }; 187 187 188 188 } 189 189 … … 210 210 /// The paths can be constructed from any path type by a 211 211 /// template constructor or a template assignment operator. 212 /// 212 /// 213 213 template <typename _Digraph> 214 214 class PathDumper { … … 239 239 class ArcIt { 240 240 public: 241 242 243 244 245 246 241 /// Default constructor 242 ArcIt() {} 243 /// Invalid constructor 244 ArcIt(Invalid) {} 245 /// Constructor for first arc 246 ArcIt(const PathDumper&) {} 247 247 248 248 /// Conversion to Arc 249 250 251 252 253 254 255 256 257 258 259 249 operator Arc() const { return INVALID; } 250 251 /// Next arc 252 ArcIt& operator++() {return *this;} 253 254 /// Comparison operator 255 bool operator==(const ArcIt&) const {return true;} 256 /// Comparison operator 257 bool operator!=(const ArcIt&) const {return true;} 258 /// Comparison operator 259 bool operator<(const ArcIt&) const {return false;} 260 260 261 261 }; … … 267 267 class RevArcIt { 268 268 public: 269 270 271 272 273 274 269 /// Default constructor 270 RevArcIt() {} 271 /// Invalid constructor 272 RevArcIt(Invalid) {} 273 /// Constructor for first arc 274 RevArcIt(const PathDumper &) {} 275 275 276 276 /// Conversion to Arc 277 278 279 280 281 282 283 284 285 286 287 277 operator Arc() const { return INVALID; } 278 279 /// Next arc 280 RevArcIt& operator++() {return *this;} 281 282 /// Comparison operator 283 bool operator==(const RevArcIt&) const {return true;} 284 /// Comparison operator 285 bool operator!=(const RevArcIt&) const {return true;} 286 /// Comparison operator 287 bool operator<(const RevArcIt&) const {return false;} 288 288 289 289 };
Note: See TracChangeset
for help on using the changeset viewer.
