Changeset 209:765619b7cbb2 in lemon-main for lemon/concepts/graph.h
- Timestamp:
- 07/13/08 20:51:02 (17 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
-
lemon/concepts/graph.h (modified) (35 diffs)
Legend:
- Unmodified
- Added
- Removed
-
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
Note: See TracChangeset
for help on using the changeset viewer.
