Changeset 1909:2d806130e700 in lemon-0.x for lemon/concept/ugraph.h
- Timestamp:
- 01/26/06 16:42:13 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2484
- File:
-
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
lemon/concept/ugraph.h
r1875 r1909 1 1 /* -*- C++ -*- 2 2 * 3 * lemon/concept/u ndir_graph_component.h - Part of LEMON, a generic3 * lemon/concept/ugraph_component.h - Part of LEMON, a generic 4 4 * C++ optimization library 5 5 * … … 34 34 35 35 // /// Skeleton class which describes an edge with direction in \ref 36 // /// U ndirGraph "undirected graph".37 template <typename U ndirGraph>38 class U ndirGraphEdge : public UndirGraph::UndirEdge {39 typedef typename U ndirGraph::UndirEdge UndirEdge;40 typedef typename U ndirGraph::Node Node;36 // /// UGraph "undirected graph". 37 template <typename UGraph> 38 class UGraphEdge : public UGraph::UEdge { 39 typedef typename UGraph::UEdge UEdge; 40 typedef typename UGraph::Node Node; 41 41 public: 42 42 43 43 /// \e 44 U ndirGraphEdge() {}44 UGraphEdge() {} 45 45 46 46 /// \e 47 U ndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {}47 UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {} 48 48 49 49 /// \e 50 U ndirGraphEdge(Invalid) {}50 UGraphEdge(Invalid) {} 51 51 52 52 /// \brief Directed edge from undirected edge and a source node. … … 55 55 /// 56 56 /// \note You have to specify the graph for this constructor. 57 U ndirGraphEdge(const UndirGraph &g,58 U ndirEdge undir_edge, Node n) {59 ignore_unused_variable_warning(u ndir_edge);57 UGraphEdge(const UGraph &g, 58 UEdge u_edge, Node n) { 59 ignore_unused_variable_warning(u_edge); 60 60 ignore_unused_variable_warning(g); 61 61 ignore_unused_variable_warning(n); … … 63 63 64 64 /// \e 65 U ndirGraphEdge& operator=(UndirGraphEdge) { return *this; }65 UGraphEdge& operator=(UGraphEdge) { return *this; } 66 66 67 67 /// \e 68 bool operator==(U ndirGraphEdge) const { return true; }68 bool operator==(UGraphEdge) const { return true; } 69 69 /// \e 70 bool operator!=(U ndirGraphEdge) const { return false; }70 bool operator!=(UGraphEdge) const { return false; } 71 71 72 72 /// \e 73 bool operator<(U ndirGraphEdge) const { return false; }73 bool operator<(UGraphEdge) const { return false; } 74 74 75 75 template <typename Edge> … … 80 80 void const_constraints() const { 81 81 /// \bug This should be is_base_and_derived ... 82 U ndirEdge ue = e;82 UEdge ue = e; 83 83 ue = e; 84 84 … … 87 87 } 88 88 Edge e; 89 U ndirEdge ue;90 U ndirGraph graph;89 UEdge ue; 90 UGraph graph; 91 91 Node n; 92 92 }; … … 94 94 95 95 96 struct BaseIterableU ndirGraphConcept {96 struct BaseIterableUGraphConcept { 97 97 98 98 template <typename Graph> 99 99 struct Constraints { 100 100 101 typedef typename Graph::U ndirEdge UndirEdge;101 typedef typename Graph::UEdge UEdge; 102 102 typedef typename Graph::Edge Edge; 103 103 typedef typename Graph::Node Node; … … 105 105 void constraints() { 106 106 checkConcept<BaseIterableGraphComponent, Graph>(); 107 checkConcept<GraphItem<>, U ndirEdge>();108 //checkConcept<U ndirGraphEdge<Graph>, Edge>();107 checkConcept<GraphItem<>, UEdge>(); 108 //checkConcept<UGraphEdge<Graph>, Edge>(); 109 109 110 110 graph.first(ue); … … 121 121 bool b; 122 122 b = graph.direction(e); 123 Edge e = graph.direct(U ndirEdge(), true);124 e = graph.direct(U ndirEdge(), n);123 Edge e = graph.direct(UEdge(), true); 124 e = graph.direct(UEdge(), n); 125 125 126 126 ignore_unused_variable_warning(b); … … 130 130 Edge e; 131 131 Node n0; 132 U ndirEdge ue;132 UEdge ue; 133 133 }; 134 134 … … 136 136 137 137 138 struct IterableU ndirGraphConcept {138 struct IterableUGraphConcept { 139 139 140 140 template <typename Graph> … … 143 143 /// \todo we don't need the iterable component to be base iterable 144 144 /// Don't we really??? 145 //checkConcept< BaseIterableU ndirGraphConcept, Graph > ();145 //checkConcept< BaseIterableUGraphConcept, Graph > (); 146 146 147 147 checkConcept<IterableGraphComponent, Graph> (); 148 148 149 typedef typename Graph::U ndirEdge UndirEdge;150 typedef typename Graph::U ndirEdgeIt UndirEdgeIt;149 typedef typename Graph::UEdge UEdge; 150 typedef typename Graph::UEdgeIt UEdgeIt; 151 151 typedef typename Graph::IncEdgeIt IncEdgeIt; 152 152 153 checkConcept<GraphIterator<Graph, U ndirEdge>, UndirEdgeIt>();154 checkConcept<GraphIncIterator<Graph, U ndirEdge>, IncEdgeIt>();153 checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>(); 154 checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>(); 155 155 } 156 156 }; … … 158 158 }; 159 159 160 struct MappableU ndirGraphConcept {160 struct MappableUGraphConcept { 161 161 162 162 template <typename Graph> … … 172 172 checkConcept<MappableGraphComponent, Graph>(); 173 173 174 typedef typename Graph::template U ndirEdgeMap<int> IntMap;175 checkConcept<GraphMap<Graph, typename Graph::U ndirEdge, int>,174 typedef typename Graph::template UEdgeMap<int> IntMap; 175 checkConcept<GraphMap<Graph, typename Graph::UEdge, int>, 176 176 IntMap >(); 177 177 178 typedef typename Graph::template U ndirEdgeMap<bool> BoolMap;179 checkConcept<GraphMap<Graph, typename Graph::U ndirEdge, bool>,178 typedef typename Graph::template UEdgeMap<bool> BoolMap; 179 checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>, 180 180 BoolMap >(); 181 181 182 typedef typename Graph::template U ndirEdgeMap<Dummy> DummyMap;183 checkConcept<GraphMap<Graph, typename Graph::U ndirEdge, Dummy>,182 typedef typename Graph::template UEdgeMap<Dummy> DummyMap; 183 checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>, 184 184 DummyMap >(); 185 185 } … … 188 188 }; 189 189 190 struct ExtendableU ndirGraphConcept {190 struct ExtendableUGraphConcept { 191 191 192 192 template <typename Graph> … … 197 197 } 198 198 typename Graph::Node node_a, node_b; 199 typename Graph::U ndirEdge uedge;199 typename Graph::UEdge uedge; 200 200 Graph graph; 201 201 }; … … 203 203 }; 204 204 205 struct ErasableU ndirGraphConcept {205 struct ErasableUGraphConcept { 206 206 207 207 template <typename Graph> … … 213 213 Graph graph; 214 214 typename Graph::Node n; 215 typename Graph::U ndirEdge e;215 typename Graph::UEdge e; 216 216 }; 217 217 … … 234 234 /// In LEMON undirected graphs also fulfill the concept of directed 235 235 /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For 236 /// explanation of this and more see also the page \ref u ndir_graphs,236 /// explanation of this and more see also the page \ref ugraphs, 237 237 /// a tutorial about undirected graphs. 238 238 /// … … 241 241 /// to the StaticGraph concept. 242 242 243 class U ndirGraph {243 class UGraph { 244 244 public: 245 245 ///\e … … 247 247 ///\todo undocumented 248 248 /// 249 typedef True U ndirTag;249 typedef True UTag; 250 250 251 251 /// \brief The base type of node iterators, … … 330 330 /// Sets the iterator to the first node of \c g. 331 331 /// 332 NodeIt(const U ndirGraph&) { }332 NodeIt(const UGraph&) { } 333 333 /// Node -> NodeIt conversion. 334 334 … … 337 337 /// This feature necessitates that each time we 338 338 /// iterate the edge-set, the iteration order is the same. 339 NodeIt(const U ndirGraph&, const Node&) { }339 NodeIt(const UGraph&, const Node&) { } 340 340 /// Next node. 341 341 … … 350 350 /// The base type of the undirected edge iterators. 351 351 /// 352 class U ndirEdge {352 class UEdge { 353 353 public: 354 354 /// Default constructor … … 356 356 /// @warning The default constructor sets the iterator 357 357 /// to an undefined value. 358 U ndirEdge() { }359 /// Copy constructor. 360 361 /// Copy constructor. 362 /// 363 U ndirEdge(const UndirEdge&) { }364 /// Initialize the iterator to be invalid. 365 366 /// Initialize the iterator to be invalid. 367 /// 368 U ndirEdge(Invalid) { }358 UEdge() { } 359 /// Copy constructor. 360 361 /// Copy constructor. 362 /// 363 UEdge(const UEdge&) { } 364 /// Initialize the iterator to be invalid. 365 366 /// Initialize the iterator to be invalid. 367 /// 368 UEdge(Invalid) { } 369 369 /// Equality operator 370 370 371 371 /// Two iterators are equal if and only if they point to the 372 372 /// same object or both are invalid. 373 bool operator==(U ndirEdge) const { return true; }373 bool operator==(UEdge) const { return true; } 374 374 /// Inequality operator 375 375 376 /// \sa operator==(U ndirEdge n)377 /// 378 bool operator!=(U ndirEdge) const { return true; }376 /// \sa operator==(UEdge n) 377 /// 378 bool operator!=(UEdge) const { return true; } 379 379 380 380 /// Artificial ordering operator. … … 388 388 /// 389 389 /// \bug This is a technical requirement. Do we really need this? 390 bool operator<(U ndirEdge) const { return false; }390 bool operator<(UEdge) const { return false; } 391 391 }; 392 392 … … 398 398 /// \code 399 399 /// int count=0; 400 /// for(Graph::U ndirEdgeIt e(g); e!=INVALID; ++e) ++count;400 /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count; 401 401 /// \endcode 402 class U ndirEdgeIt : public UndirEdge {402 class UEdgeIt : public UEdge { 403 403 public: 404 404 /// Default constructor … … 406 406 /// @warning The default constructor sets the iterator 407 407 /// to an undefined value. 408 U ndirEdgeIt() { }409 /// Copy constructor. 410 411 /// Copy constructor. 412 /// 413 U ndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }414 /// Initialize the iterator to be invalid. 415 416 /// Initialize the iterator to be invalid. 417 /// 418 U ndirEdgeIt(Invalid) { }408 UEdgeIt() { } 409 /// Copy constructor. 410 411 /// Copy constructor. 412 /// 413 UEdgeIt(const UEdgeIt& e) : UEdge(e) { } 414 /// Initialize the iterator to be invalid. 415 416 /// Initialize the iterator to be invalid. 417 /// 418 UEdgeIt(Invalid) { } 419 419 /// This constructor sets the iterator to the first undirected edge. 420 420 421 421 /// This constructor sets the iterator to the first undirected edge. 422 U ndirEdgeIt(const UndirGraph&) { }423 /// U ndirEdge -> UndirEdgeIt conversion422 UEdgeIt(const UGraph&) { } 423 /// UEdge -> UEdgeIt conversion 424 424 425 425 /// Sets the iterator to the value of the trivial iterator. … … 427 427 /// iterate the undirected edge-set, the iteration order is the 428 428 /// same. 429 U ndirEdgeIt(const UndirGraph&, const UndirEdge&) { }429 UEdgeIt(const UGraph&, const UEdge&) { } 430 430 /// Next undirected edge 431 431 432 432 /// Assign the iterator to the next undirected edge. 433 U ndirEdgeIt& operator++() { return *this; }433 UEdgeIt& operator++() { return *this; } 434 434 }; 435 435 … … 448 448 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 449 449 /// \endcode 450 class IncEdgeIt : public U ndirEdge {450 class IncEdgeIt : public UEdge { 451 451 public: 452 452 /// Default constructor … … 459 459 /// Copy constructor. 460 460 /// 461 IncEdgeIt(const IncEdgeIt& e) : U ndirEdge(e) { }461 IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { } 462 462 /// Initialize the iterator to be invalid. 463 463 … … 469 469 /// This constructor set the iterator to the first incident edge of 470 470 /// the node. 471 IncEdgeIt(const U ndirGraph&, const Node&) { }472 /// U ndirEdge -> IncEdgeIt conversion471 IncEdgeIt(const UGraph&, const Node&) { } 472 /// UEdge -> IncEdgeIt conversion 473 473 474 474 /// Sets the iterator to the value of the trivial iterator \c e. 475 475 /// This feature necessitates that each time we 476 476 /// iterate the edge-set, the iteration order is the same. 477 IncEdgeIt(const U ndirGraph&, const UndirEdge&) { }477 IncEdgeIt(const UGraph&, const UEdge&) { } 478 478 /// Next incident edge 479 479 … … 487 487 /// The directed edge type. It can be converted to the 488 488 /// undirected edge. 489 class Edge : public U ndirEdge {489 class Edge : public UEdge { 490 490 public: 491 491 /// Default constructor … … 498 498 /// Copy constructor. 499 499 /// 500 Edge(const Edge& e) : U ndirEdge(e) { }500 Edge(const Edge& e) : UEdge(e) { } 501 501 /// Initialize the iterator to be invalid. 502 502 … … 558 558 /// This constructor sets the iterator to the first edge of \c g. 559 559 ///@param g the graph 560 EdgeIt(const U ndirGraph &g) { ignore_unused_variable_warning(g); }560 EdgeIt(const UGraph &g) { ignore_unused_variable_warning(g); } 561 561 /// Edge -> EdgeIt conversion 562 562 … … 564 564 /// This feature necessitates that each time we 565 565 /// iterate the edge-set, the iteration order is the same. 566 EdgeIt(const U ndirGraph&, const Edge&) { }566 EdgeIt(const UGraph&, const Edge&) { } 567 567 ///Next edge 568 568 … … 606 606 ///@param n the node 607 607 ///@param g the graph 608 OutEdgeIt(const U ndirGraph& n, const Node& g) {608 OutEdgeIt(const UGraph& n, const Node& g) { 609 609 ignore_unused_variable_warning(n); 610 610 ignore_unused_variable_warning(g); … … 615 615 /// This feature necessitates that each time we 616 616 /// iterate the edge-set, the iteration order is the same. 617 OutEdgeIt(const U ndirGraph&, const Edge&) { }617 OutEdgeIt(const UGraph&, const Edge&) { } 618 618 ///Next outgoing edge 619 619 … … 658 658 ///@param n the node 659 659 ///@param g the graph 660 InEdgeIt(const U ndirGraph& g, const Node& n) {660 InEdgeIt(const UGraph& g, const Node& n) { 661 661 ignore_unused_variable_warning(n); 662 662 ignore_unused_variable_warning(g); … … 667 667 /// This feature necessitates that each time we 668 668 /// iterate the edge-set, the iteration order is the same. 669 InEdgeIt(const U ndirGraph&, const Edge&) { }669 InEdgeIt(const UGraph&, const Edge&) { } 670 670 /// Next incoming edge 671 671 … … 688 688 689 689 ///\e 690 NodeMap(const U ndirGraph&) { }690 NodeMap(const UGraph&) { } 691 691 ///\e 692 NodeMap(const U ndirGraph&, T) { }692 NodeMap(const UGraph&, T) { } 693 693 694 694 ///Copy constructor … … 712 712 713 713 ///\e 714 EdgeMap(const U ndirGraph&) { }714 EdgeMap(const UGraph&) { } 715 715 ///\e 716 EdgeMap(const U ndirGraph&, T) { }716 EdgeMap(const UGraph&, T) { } 717 717 ///Copy constructor 718 718 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { } … … 726 726 /// Reference map of the edges to type \c T. 727 727 /// \sa Reference 728 /// \warning Making maps that can handle bool type (U ndirEdgeMap<bool>)728 /// \warning Making maps that can handle bool type (UEdgeMap<bool>) 729 729 /// needs some extra attention! 730 730 /// \todo Wrong documentation 731 731 template<class T> 732 class U ndirEdgeMap : public ReadWriteMap<UndirEdge,T>732 class UEdgeMap : public ReadWriteMap<UEdge,T> 733 733 { 734 734 public: 735 735 736 736 ///\e 737 U ndirEdgeMap(const UndirGraph&) { }737 UEdgeMap(const UGraph&) { } 738 738 ///\e 739 U ndirEdgeMap(const UndirGraph&, T) { }739 UEdgeMap(const UGraph&, T) { } 740 740 ///Copy constructor 741 U ndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {}741 UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {} 742 742 ///Assignment operator 743 U ndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }743 UEdgeMap &operator=(const UEdgeMap&) { return *this; } 744 744 // \todo fix this concept 745 745 }; … … 749 749 /// Direct the given undirected edge. The returned edge source 750 750 /// will be the given edge. 751 Edge direct(const U ndirEdge&, const Node&) const {751 Edge direct(const UEdge&, const Node&) const { 752 752 return INVALID; 753 753 } … … 758 758 /// will be the source of the undirected edge if the given bool 759 759 /// is true. 760 Edge direct(const U ndirEdge&, bool) const {760 Edge direct(const UEdge&, bool) const { 761 761 return INVALID; 762 762 } … … 776 776 /// 777 777 /// \return the opposite of the given Node on the given Edge 778 Node oppositeNode(Node, U ndirEdge) const { return INVALID; }778 Node oppositeNode(Node, UEdge) const { return INVALID; } 779 779 780 780 /// \brief First node of the undirected edge. 781 781 /// 782 /// \return the first node of the given U ndirEdge.783 /// 784 /// Naturally u ndirectected edges don't have direction and thus782 /// \return the first node of the given UEdge. 783 /// 784 /// Naturally uectected edges don't have direction and thus 785 785 /// don't have source and target node. But we use these two methods 786 786 /// to query the two endnodes of the edge. The direction of the edge … … 789 789 /// of the directed versions of the edges. 790 790 /// \sa direction 791 Node source(U ndirEdge) const { return INVALID; }791 Node source(UEdge) const { return INVALID; } 792 792 793 793 /// \brief Second node of the undirected edge. 794 Node target(U ndirEdge) const { return INVALID; }794 Node target(UEdge) const { return INVALID; } 795 795 796 796 /// \brief Source node of the directed edge. … … 818 818 // /// developpers_interface "Developpers' interface", so it shouldn't 819 819 // /// be used in an end-user program. 820 void first(U ndirEdge&) const {}820 void first(UEdge&) const {} 821 821 // /// \brief Next undirected edge of the graph 822 822 // /// … … 824 824 // /// developpers_interface "Developpers' interface", so it shouldn't 825 825 // /// be used in an end-user program. 826 void next(U ndirEdge&) const {}826 void next(UEdge&) const {} 827 827 828 828 // /// \brief First directed edge of the graph … … 911 911 struct Constraints { 912 912 void constraints() { 913 checkConcept<BaseIterableU ndirGraphConcept, Graph>();914 checkConcept<IterableU ndirGraphConcept, Graph>();915 checkConcept<MappableU ndirGraphConcept, Graph>();913 checkConcept<BaseIterableUGraphConcept, Graph>(); 914 checkConcept<IterableUGraphConcept, Graph>(); 915 checkConcept<MappableUGraphConcept, Graph>(); 916 916 } 917 917 }; … … 921 921 /// \brief An empty non-static undirected graph class. 922 922 /// 923 /// This class provides everything that \ref U ndirGraph does.923 /// This class provides everything that \ref UGraph does. 924 924 /// Additionally it enables building graphs from scratch. 925 class ExtendableU ndirGraph : public UndirGraph {925 class ExtendableUGraph : public UGraph { 926 926 public: 927 927 … … 936 936 /// Add a new undirected edge to the graph. 937 937 /// \return the new edge. 938 U ndirEdge addEdge(const Node& from, const Node& to);938 UEdge addEdge(const Node& from, const Node& to); 939 939 940 940 /// \brief Resets the graph. … … 947 947 struct Constraints { 948 948 void constraints() { 949 checkConcept<BaseIterableU ndirGraphConcept, Graph>();950 checkConcept<IterableU ndirGraphConcept, Graph>();951 checkConcept<MappableU ndirGraphConcept, Graph>();952 953 checkConcept<U ndirGraph, Graph>();954 checkConcept<ExtendableU ndirGraphConcept, Graph>();949 checkConcept<BaseIterableUGraphConcept, Graph>(); 950 checkConcept<IterableUGraphConcept, Graph>(); 951 checkConcept<MappableUGraphConcept, Graph>(); 952 953 checkConcept<UGraph, Graph>(); 954 checkConcept<ExtendableUGraphConcept, Graph>(); 955 955 checkConcept<ClearableGraphComponent, Graph>(); 956 956 } … … 961 961 /// \brief An empty erasable undirected graph class. 962 962 /// 963 /// This class is an extension of \ref ExtendableU ndirGraph. It makes it963 /// This class is an extension of \ref ExtendableUGraph. It makes it 964 964 /// possible to erase undirected edges or nodes. 965 class ErasableU ndirGraph : public ExtendableUndirGraph {965 class ErasableUGraph : public ExtendableUGraph { 966 966 public: 967 967 … … 975 975 /// Deletes an undirected edge. 976 976 /// 977 void erase(U ndirEdge) { }977 void erase(UEdge) { } 978 978 979 979 template <typename Graph> 980 980 struct Constraints { 981 981 void constraints() { 982 checkConcept<ExtendableU ndirGraph, Graph>();983 checkConcept<ErasableU ndirGraphConcept, Graph>();982 checkConcept<ExtendableUGraph, Graph>(); 983 checkConcept<ErasableUGraphConcept, Graph>(); 984 984 } 985 985 };
Note: See TracChangeset
for help on using the changeset viewer.