00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00023
00024
00025 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
00026 #define LEMON_CONCEPT_UNDIR_GRAPH_H
00027
00028 #include <lemon/concept/graph_component.h>
00029
00030 namespace lemon {
00031 namespace concept {
00032
00035
00036
00039 template <typename UndirGraph>
00040 class UndirGraphEdge : public UndirGraph::UndirEdge {
00041 typedef typename UndirGraph::UndirEdge UndirEdge;
00042 typedef typename UndirGraph::Node Node;
00043 public:
00044
00046 UndirGraphEdge() {}
00047
00049 UndirGraphEdge(const UndirGraphEdge&) {}
00050
00052 UndirGraphEdge(Invalid) {}
00053
00059 UndirGraphEdge(const UndirGraph &g,
00060 UndirEdge undir_edge, Node n) {
00061 ignore_unused_variable_warning(undir_edge);
00062 ignore_unused_variable_warning(g);
00063 ignore_unused_variable_warning(n);
00064 }
00065
00067 UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
00068
00070 bool operator==(UndirGraphEdge) const { return true; }
00072 bool operator!=(UndirGraphEdge) const { return false; }
00073
00075 bool operator<(UndirGraphEdge) const { return false; }
00076
00077 template <typename Edge>
00078 struct Constraints {
00079 void constraints() {
00080 const_constraints();
00081 }
00082 void const_constraints() const {
00084 UndirEdge ue = e;
00085 ue = e;
00086
00087 Edge e_with_source(graph,ue,n);
00088 ignore_unused_variable_warning(e_with_source);
00089 }
00090 Edge e;
00091 UndirEdge ue;
00092 UndirGraph graph;
00093 Node n;
00094 };
00095 };
00096
00097
00098 struct BaseIterableUndirGraphConcept {
00099
00100 template <typename Graph>
00101 struct Constraints {
00102
00103 typedef typename Graph::UndirEdge UndirEdge;
00104 typedef typename Graph::Edge Edge;
00105 typedef typename Graph::Node Node;
00106
00107 void constraints() {
00108 checkConcept<BaseIterableGraphComponent, Graph>();
00109 checkConcept<GraphItem<>, UndirEdge>();
00110 checkConcept<UndirGraphEdge<Graph>, Edge>();
00111
00112 graph.first(ue);
00113 graph.next(ue);
00114
00115 const_constraints();
00116 }
00117 void const_constraints() {
00118 Node n;
00119 n = graph.target(ue);
00120 n = graph.source(ue);
00121 n = graph.oppositeNode(n0, ue);
00122
00123 bool b;
00124 b = graph.forward(e);
00125 ignore_unused_variable_warning(b);
00126 }
00127
00128 Graph graph;
00129 Edge e;
00130 Node n0;
00131 UndirEdge ue;
00132 };
00133
00134 };
00135
00136
00137 struct IterableUndirGraphConcept {
00138
00139 template <typename Graph>
00140 struct Constraints {
00141 void constraints() {
00144
00145
00146 checkConcept<IterableGraphComponent, Graph> ();
00147
00148 typedef typename Graph::UndirEdge UndirEdge;
00149 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
00150 typedef typename Graph::IncEdgeIt IncEdgeIt;
00151
00152 checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
00153 checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
00154 }
00155 };
00156
00157 };
00158
00159 struct MappableUndirGraphConcept {
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 UndirEdgeMap<int> IntMap;
00174 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
00175 IntMap >();
00176
00177 typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
00178 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
00179 BoolMap >();
00180
00181 typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
00182 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
00183 DummyMap >();
00184 }
00185 };
00186
00187 };
00188
00189 struct ExtendableUndirGraphConcept {
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::UndirEdge uedge;
00199 Graph graph;
00200 };
00201
00202 };
00203
00204 struct ErasableUndirGraphConcept {
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::UndirEdge e;
00215 };
00216
00217 };
00218
00220
00233
00234 class UndirGraph {
00235 public:
00236
00238 typedef GraphNode Node;
00239
00241 typedef GraphItem<'u'> UndirEdge;
00242
00244 #ifndef DOXYGEN
00245 typedef UndirGraphEdge<UndirGraph> Edge;
00246 #else
00247 typedef UndirGraphEdge Edge;
00248 #endif
00249
00251 #ifndef DOXYGEN
00252 typedef GraphIterator<UndirGraph, Node> NodeIt;
00253 #else
00254 typedef GraphIterator NodeIt;
00255 #endif
00256
00258 #ifndef DOXYGEN
00259 typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
00260 #else
00261 typedef GraphIterator UndirEdgeIt;
00262 #endif
00263
00265
00268 #ifndef DOXYGEN
00269 typedef GraphIterator<UndirGraph, Edge> EdgeIt;
00270 #else
00271 typedef GraphIterator EdgeIt;
00272 #endif
00273
00274
00276 #ifndef DOXYGEN
00277 typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
00278 #else
00279 typedef GraphIncIterator IncEdgeIt;
00280 #endif
00281
00283 #ifndef DOXYGEN
00284 typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
00285 #else
00286 typedef GraphIncIterator InEdgeIt;
00287 #endif
00288
00290 #ifndef DOXYGEN
00291 typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
00292 #else
00293 typedef GraphIncIterator OutEdgeIt;
00294 #endif
00295
00297 #ifdef DOXYGEN
00298 typedef GraphMap NodeMap<T>;
00299 #endif
00300
00302 #ifdef DOXYGEN
00303 typedef GraphMap UndirEdgeMap<T>;
00304 #endif
00305
00307 #ifdef DOXYGEN
00308 typedef GraphMap EdgeMap<T>;
00309 #endif
00310
00311 template <typename T>
00312 class NodeMap : public GraphMap<UndirGraph, Node, T> {
00313 typedef GraphMap<UndirGraph, Node, T> Parent;
00314 public:
00315
00316 explicit NodeMap(const UndirGraph &g) : Parent(g) {}
00317 NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
00318 };
00319
00320 template <typename T>
00321 class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
00322 typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
00323 public:
00324
00325 explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
00326 UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
00327 };
00328
00329 template <typename T>
00330 class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
00331 typedef GraphMap<UndirGraph, Edge, T> Parent;
00332 public:
00333
00334 explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
00335 EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
00336 };
00337
00339
00344 bool forward(Edge) const { return true; }
00345
00347
00351 Node oppositeNode(Node, UndirEdge) const { return INVALID; }
00352
00354
00364 Node source(UndirEdge) const { return INVALID; }
00365
00367 Node target(UndirEdge) const { return INVALID; }
00368
00370 Node source(Edge) const { return INVALID; }
00371
00373 Node target(Edge) const { return INVALID; }
00374
00376
00380 void first(Node&) const {}
00382
00386 void next(Node&) const {}
00387
00389
00393 void first(UndirEdge&) const {}
00395
00399 void next(UndirEdge&) const {}
00400
00402
00406 void first(Edge&) const {}
00408
00412 void next(Edge&) const {}
00413
00415
00419 void firstOut(Edge&, Node) const {}
00421
00425 void nextOut(Edge&) const {}
00426
00428
00432 void firstIn(Edge&, Node) const {}
00434
00438 void nextIn(Edge&) const {}
00439
00440
00444 Node baseNode(OutEdgeIt e) const {
00445 return source(e);
00446 }
00451 Node runningNode(OutEdgeIt e) const {
00452 return target(e);
00453 }
00454
00458 Node baseNode(InEdgeIt e) const {
00459 return target(e);
00460 }
00465 Node runningNode(InEdgeIt e) const {
00466 return source(e);
00467 }
00468
00472 Node baseNode(IncEdgeIt e) const {
00473 return INVALID;
00474 }
00478 Node runningNode(IncEdgeIt e) const {
00479 return INVALID;
00480 }
00481
00482
00483 template <typename Graph>
00484 struct Constraints {
00485 void constraints() {
00486 checkConcept<BaseIterableUndirGraphConcept, Graph>();
00487 checkConcept<IterableUndirGraphConcept, Graph>();
00488 checkConcept<MappableUndirGraphConcept, Graph>();
00489 }
00490 };
00491
00492 };
00493
00494 class ExtendableUndirGraph : public UndirGraph {
00495 public:
00496
00497 template <typename Graph>
00498 struct Constraints {
00499 void constraints() {
00500 checkConcept<BaseIterableUndirGraphConcept, Graph>();
00501 checkConcept<IterableUndirGraphConcept, Graph>();
00502 checkConcept<MappableUndirGraphConcept, Graph>();
00503
00504 checkConcept<UndirGraph, Graph>();
00505 checkConcept<ExtendableUndirGraphConcept, Graph>();
00506 checkConcept<ClearableGraphComponent, Graph>();
00507 }
00508 };
00509
00510 };
00511
00512 class ErasableUndirGraph : public ExtendableUndirGraph {
00513 public:
00514
00515 template <typename Graph>
00516 struct Constraints {
00517 void constraints() {
00518 checkConcept<ExtendableUndirGraph, Graph>();
00519 checkConcept<ErasableUndirGraphConcept, Graph>();
00520 }
00521 };
00522
00523 };
00524
00526
00527 }
00528
00529 }
00530
00531 #endif