00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00022
00023
00024 #ifndef LEMON_CONCEPT_UGRAPH_H
00025 #define LEMON_CONCEPT_UGRAPH_H
00026
00027 #include <lemon/concept/graph_component.h>
00028 #include <lemon/concept/graph.h>
00029 #include <lemon/utility.h>
00030
00031 namespace lemon {
00032 namespace concept {
00033
00034
00035
00036 template <typename UGraph>
00037 class UGraphEdge : public UGraph::UEdge {
00038 typedef typename UGraph::UEdge UEdge;
00039 typedef typename UGraph::Node Node;
00040 public:
00041
00043 UGraphEdge() {}
00044
00046 UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
00047
00049 UGraphEdge(Invalid) {}
00050
00056 UGraphEdge(const UGraph &g,
00057 UEdge u_edge, Node n) {
00058 ignore_unused_variable_warning(u_edge);
00059 ignore_unused_variable_warning(g);
00060 ignore_unused_variable_warning(n);
00061 }
00062
00064 UGraphEdge& operator=(UGraphEdge) { return *this; }
00065
00067 bool operator==(UGraphEdge) const { return true; }
00069 bool operator!=(UGraphEdge) const { return false; }
00070
00072 bool operator<(UGraphEdge) const { return false; }
00073
00074 template <typename Edge>
00075 struct Constraints {
00076 void constraints() {
00077 const_constraints();
00078 }
00079 void const_constraints() const {
00081 UEdge ue = e;
00082 ue = e;
00083
00084 Edge e_with_source(graph,ue,n);
00085 ignore_unused_variable_warning(e_with_source);
00086 }
00087 Edge e;
00088 UEdge ue;
00089 UGraph graph;
00090 Node n;
00091 };
00092 };
00093
00094
00095 struct BaseIterableUGraphConcept {
00096
00097 template <typename Graph>
00098 struct Constraints {
00099
00100 typedef typename Graph::UEdge UEdge;
00101 typedef typename Graph::Edge Edge;
00102 typedef typename Graph::Node Node;
00103
00104 void constraints() {
00105 checkConcept<BaseIterableGraphComponent, Graph>();
00106 checkConcept<GraphItem<>, UEdge>();
00107
00108
00109 graph.first(ue);
00110 graph.next(ue);
00111
00112 const_constraints();
00113 }
00114 void const_constraints() {
00115 Node n;
00116 n = graph.target(ue);
00117 n = graph.source(ue);
00118 n = graph.oppositeNode(n0, ue);
00119
00120 bool b;
00121 b = graph.direction(e);
00122 Edge e = graph.direct(UEdge(), true);
00123 e = graph.direct(UEdge(), n);
00124
00125 ignore_unused_variable_warning(b);
00126 }
00127
00128 Graph graph;
00129 Edge e;
00130 Node n0;
00131 UEdge ue;
00132 };
00133
00134 };
00135
00136
00137 struct IterableUGraphConcept {
00138
00139 template <typename Graph>
00140 struct Constraints {
00141 void constraints() {
00144
00145
00146 checkConcept<IterableGraphComponent, Graph> ();
00147
00148 typedef typename Graph::UEdge UEdge;
00149 typedef typename Graph::UEdgeIt UEdgeIt;
00150 typedef typename Graph::IncEdgeIt IncEdgeIt;
00151
00152 checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
00153 checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
00154 }
00155 };
00156
00157 };
00158
00159 struct MappableUGraphConcept {
00160
00161 template <typename Graph>
00162 struct Constraints {
00163
00164 struct Dummy {
00165 int value;
00166 Dummy() : value(0) {}
00167 Dummy(int _v) : value(_v) {}
00168 };
00169
00170 void constraints() {
00171 checkConcept<MappableGraphComponent, Graph>();
00172
00173 typedef typename Graph::template UEdgeMap<int> IntMap;
00174 checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
00175 IntMap >();
00176
00177 typedef typename Graph::template UEdgeMap<bool> BoolMap;
00178 checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
00179 BoolMap >();
00180
00181 typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
00182 checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
00183 DummyMap >();
00184 }
00185 };
00186
00187 };
00188
00189 struct ExtendableUGraphConcept {
00190
00191 template <typename Graph>
00192 struct Constraints {
00193 void constraints() {
00194 node_a = graph.addNode();
00195 uedge = graph.addEdge(node_a, node_b);
00196 }
00197 typename Graph::Node node_a, node_b;
00198 typename Graph::UEdge uedge;
00199 Graph graph;
00200 };
00201
00202 };
00203
00204 struct ErasableUGraphConcept {
00205
00206 template <typename Graph>
00207 struct Constraints {
00208 void constraints() {
00209 graph.erase(n);
00210 graph.erase(e);
00211 }
00212 Graph graph;
00213 typename Graph::Node n;
00214 typename Graph::UEdge e;
00215 };
00216
00217 };
00218
00221
00222
00224
00241
00242 class UGraph {
00243 public:
00245
00248 typedef True UTag;
00249
00257 class Node {
00258 public:
00260
00263 Node() { }
00265
00268 Node(const Node&) { }
00269
00271
00274 Node(Invalid) { }
00276
00279 bool operator==(Node) const { return true; }
00280
00282
00285 bool operator!=(Node) const { return true; }
00286
00288
00297 bool operator<(Node) const { return false; }
00298
00299 };
00300
00302
00310 class NodeIt : public Node {
00311 public:
00313
00316 NodeIt() { }
00318
00321 NodeIt(const NodeIt& n) : Node(n) { }
00323
00326 NodeIt(Invalid) { }
00328
00331 NodeIt(const UGraph&) { }
00333
00338 NodeIt(const UGraph&, const Node&) { }
00340
00343 NodeIt& operator++() { return *this; }
00344 };
00345
00346
00348
00351 class UEdge {
00352 public:
00354
00357 UEdge() { }
00359
00362 UEdge(const UEdge&) { }
00364
00367 UEdge(Invalid) { }
00369
00372 bool operator==(UEdge) const { return true; }
00374
00377 bool operator!=(UEdge) const { return true; }
00378
00380
00389 bool operator<(UEdge) const { return false; }
00390 };
00391
00393
00401 class UEdgeIt : public UEdge {
00402 public:
00404
00407 UEdgeIt() { }
00409
00412 UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
00414
00417 UEdgeIt(Invalid) { }
00419
00421 UEdgeIt(const UGraph&) { }
00423
00428 UEdgeIt(const UGraph&, const UEdge&) { }
00430
00432 UEdgeIt& operator++() { return *this; }
00433 };
00434
00449 class IncEdgeIt : public UEdge {
00450 public:
00452
00455 IncEdgeIt() { }
00457
00460 IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { }
00462
00465 IncEdgeIt(Invalid) { }
00467
00470 IncEdgeIt(const UGraph&, const Node&) { }
00472
00476 IncEdgeIt(const UGraph&, const UEdge&) { }
00478
00481 IncEdgeIt& operator++() { return *this; }
00482 };
00483
00485
00488 class Edge : public UEdge {
00489 public:
00491
00494 Edge() { }
00496
00499 Edge(const Edge& e) : UEdge(e) { }
00501
00504 Edge(Invalid) { }
00506
00509 bool operator==(Edge) const { return true; }
00511
00514 bool operator!=(Edge) const { return true; }
00515
00517
00526 bool operator<(Edge) const { return false; }
00527
00528 };
00530
00538 class EdgeIt : public Edge {
00539 public:
00541
00544 EdgeIt() { }
00546
00549 EdgeIt(const EdgeIt& e) : Edge(e) { }
00551
00554 EdgeIt(Invalid) { }
00556
00559 EdgeIt(const UGraph &g) { ignore_unused_variable_warning(g); }
00561
00565 EdgeIt(const UGraph&, const Edge&) { }
00567
00569 EdgeIt& operator++() { return *this; }
00570 };
00571
00573
00583
00584 class OutEdgeIt : public Edge {
00585 public:
00587
00590 OutEdgeIt() { }
00592
00595 OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
00597
00600 OutEdgeIt(Invalid) { }
00602
00607 OutEdgeIt(const UGraph& n, const Node& g) {
00608 ignore_unused_variable_warning(n);
00609 ignore_unused_variable_warning(g);
00610 }
00612
00616 OutEdgeIt(const UGraph&, const Edge&) { }
00618
00621 OutEdgeIt& operator++() { return *this; }
00622 };
00623
00625
00635
00636 class InEdgeIt : public Edge {
00637 public:
00639
00642 InEdgeIt() { }
00644
00647 InEdgeIt(const InEdgeIt& e) : Edge(e) { }
00649
00652 InEdgeIt(Invalid) { }
00654
00659 InEdgeIt(const UGraph& g, const Node& n) {
00660 ignore_unused_variable_warning(n);
00661 ignore_unused_variable_warning(g);
00662 }
00664
00668 InEdgeIt(const UGraph&, const Edge&) { }
00670
00673 InEdgeIt& operator++() { return *this; }
00674 };
00675
00683 template<class T>
00684 class NodeMap : public ReadWriteMap< Node, T >
00685 {
00686 public:
00687
00689 NodeMap(const UGraph&) { }
00691 NodeMap(const UGraph&, T) { }
00692
00694 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
00696 NodeMap& operator=(const NodeMap&) { return *this; }
00697
00698 };
00699
00707 template<class T>
00708 class EdgeMap : public ReadWriteMap<Edge,T>
00709 {
00710 public:
00711
00713 EdgeMap(const UGraph&) { }
00715 EdgeMap(const UGraph&, T) { }
00717 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
00719 EdgeMap& operator=(const EdgeMap&) { return *this; }
00720
00721 };
00722
00724
00730 template<class T>
00731 class UEdgeMap : public ReadWriteMap<UEdge,T>
00732 {
00733 public:
00734
00736 UEdgeMap(const UGraph&) { }
00738 UEdgeMap(const UGraph&, T) { }
00740 UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
00742 UEdgeMap &operator=(const UEdgeMap&) { return *this; }
00743
00744 };
00745
00750 Edge direct(const UEdge&, const Node&) const {
00751 return INVALID;
00752 }
00753
00759 Edge direct(const UEdge&, bool) const {
00760 return INVALID;
00761 }
00762
00767 bool direction(Edge) const { return true; }
00768
00772 Edge oppositeEdge(Edge) const { return INVALID; }
00773
00777 Node oppositeNode(Node, UEdge) const { return INVALID; }
00778
00790 Node source(UEdge) const { return INVALID; }
00791
00793 Node target(UEdge) const { return INVALID; }
00794
00796 Node source(Edge) const { return INVALID; }
00797
00799 Node target(Edge) const { return INVALID; }
00800
00801
00802
00803
00804
00805
00806 void first(Node&) const {}
00807
00808
00809
00810
00811
00812 void next(Node&) const {}
00813
00814
00815
00816
00817
00818
00819 void first(UEdge&) const {}
00820
00821
00822
00823
00824
00825 void next(UEdge&) const {}
00826
00827
00828
00829
00830
00831
00832 void first(Edge&) const {}
00833
00834
00835
00836
00837
00838 void next(Edge&) const {}
00839
00840
00841
00842
00843
00844
00845 void firstOut(Edge&, Node) const {}
00846
00847
00848
00849
00850
00851 void nextOut(Edge&) const {}
00852
00853
00854
00855
00856
00857
00858 void firstIn(Edge&, Node) const {}
00859
00860
00861
00862
00863
00864 void nextIn(Edge&) const {}
00865
00866
00870 Node baseNode(OutEdgeIt e) const {
00871 return source(e);
00872 }
00877 Node runningNode(OutEdgeIt e) const {
00878 return target(e);
00879 }
00880
00884 Node baseNode(InEdgeIt e) const {
00885 return target(e);
00886 }
00891 Node runningNode(InEdgeIt e) const {
00892 return source(e);
00893 }
00894
00898 Node baseNode(IncEdgeIt) const {
00899 return INVALID;
00900 }
00901
00905 Node runningNode(IncEdgeIt) const {
00906 return INVALID;
00907 }
00908
00909 template <typename Graph>
00910 struct Constraints {
00911 void constraints() {
00912 checkConcept<BaseIterableUGraphConcept, Graph>();
00913 checkConcept<IterableUGraphConcept, Graph>();
00914 checkConcept<MappableUGraphConcept, Graph>();
00915 }
00916 };
00917
00918 };
00919
00924 class ExtendableUGraph : public UGraph {
00925 public:
00926
00931 Node addNode();
00932
00937 UEdge addEdge(const Node& from, const Node& to);
00938
00943 void clear() { }
00944
00945 template <typename Graph>
00946 struct Constraints {
00947 void constraints() {
00948 checkConcept<BaseIterableUGraphConcept, Graph>();
00949 checkConcept<IterableUGraphConcept, Graph>();
00950 checkConcept<MappableUGraphConcept, Graph>();
00951
00952 checkConcept<UGraph, Graph>();
00953 checkConcept<ExtendableUGraphConcept, Graph>();
00954 checkConcept<ClearableGraphComponent, Graph>();
00955 }
00956 };
00957
00958 };
00959
00964 class ErasableUGraph : public ExtendableUGraph {
00965 public:
00966
00971 void erase(Node) { }
00976 void erase(UEdge) { }
00977
00978 template <typename Graph>
00979 struct Constraints {
00980 void constraints() {
00981 checkConcept<ExtendableUGraph, Graph>();
00982 checkConcept<ErasableUGraphConcept, Graph>();
00983 }
00984 };
00985
00986 };
00987
00989
00990 }
00991
00992 }
00993
00994 #endif