00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_CONCEPT_GRAPH_H
00018 #define LEMON_CONCEPT_GRAPH_H
00019
00023
00024 #include <lemon/invalid.h>
00025 #include <lemon/concept/maps.h>
00026 #include <lemon/concept_check.h>
00027 #include <lemon/concept/graph_component.h>
00028
00029 namespace lemon {
00030 namespace concept {
00031
00032
00035
00036
00037
00038
00042 class _StaticGraph
00043 : virtual public BaseGraphComponent,
00044 public IterableGraphComponent, public MappableGraphComponent {
00045 public:
00046 typedef BaseGraphComponent::Node Node;
00047 typedef BaseGraphComponent::Edge Edge;
00048
00049 template <typename _Graph>
00050 struct Constraints {
00051 void constraints() {
00052 checkConcept<IterableGraphComponent, _Graph>();
00053 checkConcept<MappableGraphComponent, _Graph>();
00054 }
00055 };
00056 };
00057
00061 class _ExtendableGraph
00062 : virtual public BaseGraphComponent, public _StaticGraph,
00063 public ExtendableGraphComponent, public ClearableGraphComponent {
00064 public:
00065 typedef BaseGraphComponent::Node Node;
00066 typedef BaseGraphComponent::Edge Edge;
00067
00068 template <typename _Graph>
00069 struct Constraints {
00070 void constraints() {
00071 checkConcept<_StaticGraph, _Graph >();
00072 checkConcept<ExtendableGraphComponent, _Graph >();
00073 checkConcept<ClearableGraphComponent, _Graph >();
00074 }
00075 };
00076 };
00077
00081 class _ErasableGraph
00082 : virtual public BaseGraphComponent, public _ExtendableGraph,
00083 public ErasableGraphComponent {
00084 public:
00085 typedef BaseGraphComponent::Node Node;
00086 typedef BaseGraphComponent::Edge Edge;
00087
00088 template <typename _Graph>
00089 struct Constraints {
00090 void constraints() {
00091 checkConcept<_ExtendableGraph, _Graph >();
00092 checkConcept<ErasableGraphComponent, _Graph >();
00093 }
00094 };
00095 };
00096
00098
00115 class StaticGraph
00116 {
00117 public:
00119
00122 StaticGraph() { }
00124
00125
00126
00127
00128
00131
00136 class Node {
00137 public:
00139
00142 Node() { }
00144
00147 Node(const Node&) { }
00148
00150
00153 Node(Invalid) { }
00155
00158 bool operator==(Node) const { return true; }
00159
00161
00164 bool operator!=(Node) const { return true; }
00165
00166 };
00167
00169
00177 class NodeIt : public Node {
00178 public:
00180
00183 NodeIt() { }
00185
00188 NodeIt(const NodeIt&) { }
00190
00193 NodeIt(Invalid) { }
00195
00198 NodeIt(const StaticGraph& g) { }
00200
00205 NodeIt(const StaticGraph& g, const Node& n) { }
00207
00210 NodeIt& operator++() { return *this; }
00211 };
00212
00213
00215
00218 class Edge {
00219 public:
00221
00224 Edge() { }
00226
00229 Edge(const Edge&) { }
00231
00234 Edge(Invalid) { }
00236
00239 bool operator==(Edge) const { return true; }
00241
00244 bool operator!=(Edge) const { return true; }
00245 };
00246
00248
00258
00259 class OutEdgeIt : public Edge {
00260 public:
00262
00265 OutEdgeIt() { }
00267
00270 OutEdgeIt(const OutEdgeIt&) { }
00272
00275 OutEdgeIt(Invalid) { }
00277
00282 OutEdgeIt(const StaticGraph& g, const Node& n) { }
00284
00288 OutEdgeIt(const StaticGraph& g, const Edge& e) { }
00290
00293 OutEdgeIt& operator++() { return *this; }
00294 };
00295
00297
00307
00308 class InEdgeIt : public Edge {
00309 public:
00311
00314 InEdgeIt() { }
00316
00319 InEdgeIt(const InEdgeIt&) { }
00321
00324 InEdgeIt(Invalid) { }
00326
00331 InEdgeIt(const StaticGraph& g, const Node& n) { }
00333
00337 InEdgeIt(const StaticGraph& g, const Edge& n) { }
00339
00342 InEdgeIt& operator++() { return *this; }
00343 };
00345
00353 class EdgeIt : public Edge {
00354 public:
00356
00359 EdgeIt() { }
00361
00364 EdgeIt(const EdgeIt&) { }
00366
00369 EdgeIt(Invalid) { }
00371
00375 EdgeIt(const StaticGraph& g) { }
00377
00381 EdgeIt(const StaticGraph&, const Edge&) { }
00383
00386 EdgeIt& operator++() { return *this; }
00387 };
00389
00392 Node target(Edge) const { return INVALID; }
00394
00397 Node source(Edge) const { return INVALID; }
00399
00405 template<class T>
00406 class NodeMap : public ReadWriteMap< Node, T >
00407 {
00408 public:
00409
00411 NodeMap(const StaticGraph&) { }
00413 NodeMap(const StaticGraph&, T) { }
00414
00416 NodeMap(const NodeMap&) { }
00418 NodeMap& operator=(const NodeMap&) { return *this; }
00419
00420 };
00421
00423
00429 template<class T>
00430 class EdgeMap : public ReadWriteMap<Edge,T>
00431 {
00432 public:
00433
00435 EdgeMap(const StaticGraph&) { }
00437 EdgeMap(const StaticGraph&, T) { }
00439 EdgeMap(const EdgeMap&) { }
00441 EdgeMap& operator=(const EdgeMap&) { return *this; }
00442
00443 };
00444
00445 template <typename _Graph>
00446 struct Constraints : public _StaticGraph::Constraints<_Graph> {};
00447
00448 };
00449
00451
00455 class ExtendableGraph : public StaticGraph
00456 {
00457 public:
00459
00462 ExtendableGraph() { }
00464
00467 Node addNode() { return INVALID; }
00469
00473 Edge addEdge(Node s, Node t) { return INVALID; }
00474
00476
00480 void clear() { }
00481
00482 template <typename _Graph>
00483 struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
00484
00485 };
00486
00488
00491 class ErasableGraph : public ExtendableGraph
00492 {
00493 public:
00495
00498 ErasableGraph() { }
00500
00503 void erase(Node n) { }
00505
00508 void erase(Edge e) { }
00509
00510 template <typename _Graph>
00511 struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
00512
00513 };
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576 }
00577 }
00578
00579
00580
00581 #endif // LEMON_CONCEPT_GRAPH_H