00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00020
00021
00022 #ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
00023 #define LEMON_CONCEPT_GRAPH_COMPONENT_H
00024
00025 #include <lemon/invalid.h>
00026 #include <lemon/concept/maps.h>
00027
00028 #include <lemon/alteration_notifier.h>
00029
00030 namespace lemon {
00031 namespace concept {
00032
00035
00036
00037
00039
00048
00049 #ifndef DOXYGEN
00050 template <char _selector = '0'>
00051 #endif
00052 class GraphItem {
00053 public:
00055
00059 GraphItem() {}
00061
00064 GraphItem(GraphItem const&) {}
00066
00069 GraphItem(Invalid) {}
00071
00074 GraphItem& operator=(GraphItem const&) { return *this; }
00076
00079 bool operator==(GraphItem) const { return false; }
00081
00084 bool operator!=(GraphItem) const { return false; }
00085
00087
00096 bool operator<(GraphItem) const { return false; }
00097
00098 template<typename _GraphItem>
00099 struct Constraints {
00100 void constraints() {
00101 _GraphItem i1;
00102 _GraphItem i2 = i1;
00103 _GraphItem i3 = INVALID;
00104
00105 i1 = i2 = i3;
00106
00107 bool b;
00108
00109 b = (ia == ib) && (ia != ib);
00110 b = (ia == INVALID) && (ib != INVALID);
00111
00112 }
00113
00114 const _GraphItem &ia;
00115 const _GraphItem &ib;
00116 };
00117 };
00118
00120
00123 typedef GraphItem<'n'> GraphNode;
00124
00126
00129 typedef GraphItem<'e'> GraphEdge;
00130
00131
00132
00133
00135
00142
00143 class BaseGraphComponent {
00144 public:
00145
00146 typedef BaseGraphComponent Graph;
00147
00149
00152 typedef GraphItem<'n'> Node;
00153
00155
00158 typedef GraphItem<'e'> Edge;
00159
00161
00164 Node target(const Edge&) const { return INVALID;}
00165
00167
00170 Node source(const Edge&) const { return INVALID;}
00171
00172
00173 template <typename _Graph>
00174 struct Constraints {
00175 typedef typename _Graph::Node Node;
00176 typedef typename _Graph::Edge Edge;
00177
00178 void constraints() {
00179 checkConcept<GraphItem<'n'>, Node>();
00180 checkConcept<GraphItem<'e'>, Edge>();
00181 {
00182 Node n;
00183 Edge e;
00184 n = graph.source(e);
00185 n = graph.target(e);
00186 }
00187 }
00188
00189 const _Graph& graph;
00190 };
00191 };
00192
00194
00198
00199 class BaseIterableGraphComponent : virtual public BaseGraphComponent {
00200 public:
00201
00202 typedef BaseGraphComponent::Node Node;
00203 typedef BaseGraphComponent::Edge Edge;
00204
00206
00209 void first(Node&) const {}
00210
00212
00215 void next(Node&) const {}
00216
00218
00221 void first(Edge&) const {}
00223
00226 void next(Edge&) const {}
00227
00228
00230
00233 void firstIn(Edge&, const Node&) const {}
00234
00236
00237
00240 void nextIn(Edge&) const {}
00241
00243
00246 void firstOut(Edge&, const Node&) const {}
00247
00249
00252 void nextOut(Edge&) const {}
00253
00254
00255 template <typename _Graph>
00256 struct Constraints {
00257
00258 void constraints() {
00259 checkConcept< BaseGraphComponent, _Graph >();
00260 typename _Graph::Node node;
00261 typename _Graph::Edge edge;
00262 {
00263 graph.first(node);
00264 graph.next(node);
00265 }
00266 {
00267 graph.first(edge);
00268 graph.next(edge);
00269 }
00270 {
00271 graph.firstIn(edge, node);
00272 graph.nextIn(edge);
00273 }
00274 {
00275 graph.firstOut(edge, node);
00276 graph.nextOut(edge);
00277 }
00278 }
00279
00280 const _Graph& graph;
00281 };
00282 };
00283
00285
00290 class IDableGraphComponent : virtual public BaseGraphComponent {
00291 public:
00292
00293 typedef BaseGraphComponent::Node Node;
00294 typedef BaseGraphComponent::Edge Edge;
00295
00297
00300 int id(const Node&) const { return -1;}
00301
00307 Node fromId(int id, Node) const { return INVALID;}
00308
00313 int id(const Edge&) const { return -1;}
00314
00320 Edge fromId(int id, Edge) const { return INVALID;}
00321
00322 template <typename _Graph>
00323 struct Constraints {
00324
00325 void constraints() {
00326 checkConcept< BaseGraphComponent, _Graph >();
00327 typename _Graph::Node node;
00328 int nid = graph.id(node);
00329 nid = graph.id(node);
00330 node = graph.fromId(nid, Node());
00331 typename _Graph::Edge edge;
00332 int eid = graph.id(edge);
00333 eid = graph.id(edge);
00334 edge = graph.fromId(eid, Edge());
00335 }
00336
00337 const _Graph& graph;
00338 };
00339 };
00340
00341
00343
00348 class MaxIDableGraphComponent : virtual public BaseGraphComponent {
00349 public:
00350
00352
00355 int maxId(Node = INVALID) const { return -1;}
00356
00358
00361 int maxId(Edge = INVALID) const { return -1;}
00362
00363 template <typename _Graph>
00364 struct Constraints {
00365
00366 void constraints() {
00367 checkConcept<BaseGraphComponent, _Graph>();
00368 int nid = graph.maxId(typename _Graph::Node());
00369 ignore_unused_variable_warning(nid);
00370 int eid = graph.maxId(typename _Graph::Edge());
00371 ignore_unused_variable_warning(eid);
00372 }
00373
00374 const _Graph& graph;
00375 };
00376 };
00377
00379
00383 class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
00384 public:
00385
00386 typedef BaseGraphComponent::Node Node;
00387 typedef BaseGraphComponent::Edge Edge;
00388
00390
00393 Node addNode() {
00394 return INVALID;
00395 }
00396
00398
00401 Edge addEdge(const Node& from, const Node& to) {
00402 return INVALID;
00403 }
00404
00405 template <typename _Graph>
00406 struct Constraints {
00407 void constraints() {
00408 checkConcept<BaseGraphComponent, _Graph >();
00409 typename _Graph::Node node_a, node_b;
00410 node_a = graph.addNode();
00411 typename _Graph::Edge edge;
00412 edge = graph.addEdge(node_a, node_b);
00413 }
00414
00415 _Graph& graph;
00416 };
00417 };
00418
00420
00424 class BaseErasableGraphComponent : virtual public BaseGraphComponent {
00425 public:
00426
00427 typedef BaseGraphComponent::Node Node;
00428 typedef BaseGraphComponent::Edge Edge;
00429
00431
00434 void erase(const Node&) {}
00435
00437
00440 void erase(const Edge&) {}
00441
00442 template <typename _Graph>
00443 struct Constraints {
00444 void constraints() {
00445 checkConcept<BaseGraphComponent, _Graph>();
00446 typename _Graph::Node node;
00447 graph.erase(node);
00448 typename _Graph::Edge edge;
00449 graph.erase(edge);
00450 }
00451
00452 _Graph& graph;
00453 };
00454 };
00455
00457
00461 class ClearableGraphComponent : virtual public BaseGraphComponent {
00462 public:
00463
00465
00468 void clear() {}
00469
00470 template <typename _Graph>
00471 struct Constraints {
00472 void constraints() {
00473 checkConcept<BaseGraphComponent, _Graph>();
00474 graph.clear();
00475 }
00476
00477 _Graph graph;
00478 };
00479 };
00480
00481
00483
00486 template <typename _Graph, typename _Item>
00487 class GraphIterator : public _Item {
00488 public:
00490
00492
00495 GraphIterator() {}
00497
00500 GraphIterator(GraphIterator const&) {}
00502
00505 explicit GraphIterator(const _Graph&) {}
00507
00510 GraphIterator(Invalid) {}
00512
00515 GraphIterator& operator=(GraphIterator const&) { return *this; }
00517
00520 GraphIterator& operator++() { return *this; }
00521
00523
00526 bool operator==(const GraphIterator&) const { return true;}
00528
00531 bool operator!=(const GraphIterator&) const { return true;}
00532
00533 template<typename _GraphIterator>
00534 struct Constraints {
00535 void constraints() {
00536
00537 _GraphIterator it1(g);
00538
00540
00541 _GraphIterator it2;
00542
00543 it2 = ++it1;
00544 ++it2 = it1;
00545 ++(++it1);
00547 _Item bi = it1;
00548 bi = it2;
00549 }
00550 _Graph& g;
00551 };
00552 };
00553
00555
00561 template <typename Graph,
00562 typename Edge = typename Graph::Edge,
00563 char _selector = '0'>
00564 class GraphIncIterator : public Edge {
00565 public:
00567
00570 GraphIncIterator() {}
00572
00575 GraphIncIterator(GraphIncIterator const&) {}
00578
00582 explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
00584
00587 GraphIncIterator(Invalid) {}
00589
00592 GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }
00594
00597 GraphIncIterator& operator++() { return *this; }
00598
00599
00600
00602
00605 bool operator==(const GraphIncIterator&) const { return true;}
00606
00608
00611 bool operator!=(const GraphIncIterator&) const { return true;}
00612
00613 template <typename _GraphIncIterator>
00614 struct Constraints {
00615 typedef typename Graph::Node Node;
00616 void constraints() {
00617 checkConcept<GraphItem<'e'>, _GraphIncIterator>();
00618 _GraphIncIterator it1(graph, node);
00620
00621 _GraphIncIterator it2;
00622
00623 it2 = ++it1;
00624 ++it2 = it1;
00625 ++(++it1);
00626 Edge e = it1;
00627 e = it2;
00628
00629 const_constraits();
00630 }
00631
00632 void const_constraits() {
00633 Node n = graph.baseNode(it);
00634 n = graph.runningNode(it);
00635 }
00636
00637 Edge edge;
00638 Node node;
00639 Graph graph;
00640 _GraphIncIterator it;
00641 };
00642 };
00643
00644
00646
00650 class IterableGraphComponent : virtual public BaseGraphComponent {
00651
00652 public:
00653
00654 typedef IterableGraphComponent Graph;
00655
00656 typedef BaseGraphComponent::Node Node;
00657 typedef BaseGraphComponent::Edge Edge;
00658
00660
00663 typedef GraphIterator<Graph, Node> NodeIt;
00665
00668 typedef GraphIterator<Graph, Edge> EdgeIt;
00670
00673 typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
00675
00678 typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
00679 };
00680
00681 template <typename _Graph>
00682 struct Constraints {
00683 void constraints() {
00684 checkConcept< BaseGraphComponent, _Graph>();
00685
00686 checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
00687 typename _Graph::EdgeIt >();
00688 checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
00689 typename _Graph::NodeIt >();
00690 checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
00691 checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
00692 }
00693 };
00694
00696
00702 class AlterableGraphComponent : virtual public BaseGraphComponent {
00703 public:
00704
00706 typedef AlterationNotifier<Edge> EdgeNotifier;
00708 typedef AlterationNotifier<Node> NodeNotifier;
00709
00713 EdgeNotifier getNotifier(Edge) const {
00714 return EdgeNotifier();
00715 }
00716
00720 NodeNotifier getNotifier(Node) const {
00721 return NodeNotifier();
00722 }
00723
00724 };
00725
00726
00728
00732 template <typename Graph, typename Item, typename _Value>
00733 class GraphMap : public ReadWriteMap<Item, _Value> {
00734 protected:
00735 GraphMap() {}
00736 public:
00740 explicit GraphMap(const Graph&) {}
00744 GraphMap(const Graph&, const _Value&) {}
00748 GraphMap(const GraphMap&) {}
00749
00753 GraphMap& operator=(const GraphMap&) { return *this;}
00754
00755 template<typename _Map>
00756 struct Constraints {
00757 void constraints() {
00758 checkConcept<ReadWriteMap<Item, _Value>, _Map >();
00759
00760 _Map a(g);
00761
00762 _Map a2(g,t);
00763
00764 _Map b=c;
00765
00766 a=b;
00767
00768 ignore_unused_variable_warning(a2);
00769 }
00770
00771 const _Map &c;
00772 const Graph &g;
00773 const typename GraphMap::Value &t;
00774 };
00775
00776 };
00777
00779
00783 class MappableGraphComponent : virtual public BaseGraphComponent {
00784 public:
00785
00786 typedef MappableGraphComponent Graph;
00787
00788 typedef BaseGraphComponent::Node Node;
00789 typedef BaseGraphComponent::Edge Edge;
00790
00792
00795 template <typename _Value>
00796 class NodeMap : public GraphMap<Graph, Node, _Value> {
00797 private:
00798 NodeMap();
00799 public:
00804 explicit NodeMap(const Graph&) {}
00808 NodeMap(const Graph&, const _Value&) {}
00812 NodeMap(const NodeMap&) {}
00813
00817 NodeMap& operator=(const NodeMap&) { return *this;}
00818
00819 };
00820
00822
00825 template <typename _Value>
00826 class EdgeMap : public GraphMap<Graph, Edge, _Value> {
00827 private:
00828 EdgeMap();
00829 public:
00834 explicit EdgeMap(const Graph&) {}
00838 EdgeMap(const Graph&, const _Value&) {}
00842 EdgeMap(const EdgeMap&) {}
00843
00847 EdgeMap& operator=(const EdgeMap&) { return *this;}
00848
00849 };
00850
00851 template <typename _Graph>
00852 struct Constraints {
00853
00854 struct Type {
00855 int value;
00856 Type() : value(0) {}
00857 Type(int _v) : value(_v) {}
00858 };
00859
00860 void constraints() {
00861 checkConcept<BaseGraphComponent, _Graph>();
00862 {
00863 typedef typename _Graph::template NodeMap<int> IntNodeMap;
00864 checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
00865 IntNodeMap >();
00866 } {
00867 typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
00868 checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
00869 BoolNodeMap >();
00870 } {
00871 typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
00872 checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
00873 TypeNodeMap >();
00874 }
00875
00876 {
00877 typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
00878 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
00879 IntEdgeMap >();
00880 } {
00881 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
00882 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
00883 BoolEdgeMap >();
00884 } {
00885 typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
00886 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>,
00887 TypeEdgeMap >();
00888 }
00889 }
00890
00891 _Graph& graph;
00892 };
00893 };
00894
00902 class ExtendableGraphComponent : virtual public BaseGraphComponent {
00903 public:
00904
00905 typedef ExtendableGraphComponent Graph;
00906
00907 typedef BaseGraphComponent::Node Node;
00908 typedef BaseGraphComponent::Edge Edge;
00909
00913 Node addNode() {
00914 return INVALID;
00915 }
00916
00920 Edge addEdge(const Node& from, const Node& to) {
00921 return INVALID;
00922 }
00923
00924 template <typename _Graph>
00925 struct Constraints {
00926 void constraints() {
00927 checkConcept<BaseGraphComponent, _Graph >();
00928 typename _Graph::Node node_a, node_b;
00929 node_a = graph.addNode();
00930 typename _Graph::Edge edge;
00931 edge = graph.addEdge(node_a, node_b);
00932 }
00933 _Graph& graph;
00934 };
00935 };
00936
00944 class ErasableGraphComponent : virtual public BaseGraphComponent {
00945 public:
00946
00947 typedef ErasableGraphComponent Graph;
00948
00949 typedef BaseGraphComponent::Node Node;
00950 typedef BaseGraphComponent::Edge Edge;
00951
00955 void erase(const Node&) {}
00956
00960 void erase(const Edge&) {}
00961
00962 template <typename _Graph>
00963 struct Constraints {
00964 void constraints() {
00965 checkConcept<BaseGraphComponent, _Graph >();
00966 typename _Graph::Node node;
00967 graph.erase(node);
00968 typename _Graph::Edge edge;
00969 graph.erase(edge);
00970 }
00971
00972 _Graph& graph;
00973 };
00974 };
00975
00977
00978 }
00979
00980 }
00981
00982 #endif