00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00022
00023
00024 #ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
00025 #define LEMON_CONCEPT_GRAPH_COMPONENT_H
00026
00027 #include <lemon/invalid.h>
00028 #include <lemon/concept/maps.h>
00029
00030 #include <lemon/bits/alteration_notifier.h>
00031
00032 namespace lemon {
00033 namespace concept {
00034
00035
00036
00038
00047
00048 #ifndef DOXYGEN
00049 template <char _selector = '0'>
00050 #endif
00051 class GraphItem {
00052 public:
00054
00058 GraphItem() {}
00060
00063 GraphItem(GraphItem const&) {}
00065
00068 GraphItem(Invalid) {}
00070
00073 GraphItem& operator=(GraphItem const&) { return *this; }
00075
00078 bool operator==(GraphItem) const { return false; }
00080
00083 bool operator!=(GraphItem) const { return false; }
00084
00086
00095 bool operator<(GraphItem) const { return false; }
00096
00097 template<typename _GraphItem>
00098 struct Constraints {
00099 void constraints() {
00100 _GraphItem i1;
00101 _GraphItem i2 = i1;
00102 _GraphItem i3 = INVALID;
00103
00104 i1 = i2 = i3;
00105
00106 bool b;
00107
00108 b = (ia == ib) && (ia != ib);
00109 b = (ia == INVALID) && (ib != INVALID);
00110
00111 }
00112
00113 const _GraphItem &ia;
00114 const _GraphItem &ib;
00115 };
00116 };
00117
00119
00122 typedef GraphItem<'n'> GraphNode;
00123
00125
00128 typedef GraphItem<'e'> GraphEdge;
00129
00130
00131
00132
00134
00141
00142 class BaseGraphComponent {
00143 public:
00144
00145 typedef BaseGraphComponent Graph;
00146
00148
00151 typedef GraphItem<'n'> Node;
00152
00154
00157 typedef GraphItem<'e'> Edge;
00158
00160
00163 Node target(const Edge&) const { return INVALID;}
00164
00166
00169 Node source(const Edge&) const { return INVALID;}
00170
00171
00172 template <typename _Graph>
00173 struct Constraints {
00174 typedef typename _Graph::Node Node;
00175 typedef typename _Graph::Edge Edge;
00176
00177 void constraints() {
00178 checkConcept<GraphItem<'n'>, Node>();
00179 checkConcept<GraphItem<'e'>, Edge>();
00180 {
00181 Node n;
00182 Edge e(INVALID);
00183 n = graph.source(e);
00184 n = graph.target(e);
00185 }
00186 }
00187
00188 const _Graph& graph;
00189 };
00190 };
00191
00193
00197
00198 class BaseIterableGraphComponent : virtual public BaseGraphComponent {
00199 public:
00200
00201 typedef BaseGraphComponent::Node Node;
00202 typedef BaseGraphComponent::Edge Edge;
00203
00205
00208 void first(Node&) const {}
00209
00211
00214 void next(Node&) const {}
00215
00217
00220 void first(Edge&) const {}
00222
00225 void next(Edge&) const {}
00226
00227
00229
00232 void firstIn(Edge&, const Node&) const {}
00233
00235
00236
00239 void nextIn(Edge&) const {}
00240
00242
00245 void firstOut(Edge&, const Node&) const {}
00246
00248
00251 void nextOut(Edge&) const {}
00252
00253
00254 template <typename _Graph>
00255 struct Constraints {
00256
00257 void constraints() {
00258 checkConcept< BaseGraphComponent, _Graph >();
00259 typename _Graph::Node node;
00260 typename _Graph::Edge edge;
00261 {
00262 graph.first(node);
00263 graph.next(node);
00264 }
00265 {
00266 graph.first(edge);
00267 graph.next(edge);
00268 }
00269 {
00270 graph.firstIn(edge, node);
00271 graph.nextIn(edge);
00272 }
00273 {
00274 graph.firstOut(edge, node);
00275 graph.nextOut(edge);
00276 }
00277 }
00278
00279 const _Graph& graph;
00280 };
00281 };
00282
00284
00289 class IDableGraphComponent : virtual public BaseGraphComponent {
00290 public:
00291
00292 typedef BaseGraphComponent::Node Node;
00293 typedef BaseGraphComponent::Edge Edge;
00294
00296
00299 int id(const Node&) const { return -1;}
00300
00306 Node fromId(int , Node) const { return INVALID;}
00307
00312 int id(const Edge&) const { return -1;}
00313
00319 Edge fromId(int, Edge) const { return INVALID;}
00320
00321 template <typename _Graph>
00322 struct Constraints {
00323
00324 void constraints() {
00325 checkConcept< BaseGraphComponent, _Graph >();
00326 typename _Graph::Node node;
00327 int nid = graph.id(node);
00328 nid = graph.id(node);
00329 node = graph.fromId(nid, Node());
00330 typename _Graph::Edge edge;
00331 int eid = graph.id(edge);
00332 eid = graph.id(edge);
00333 edge = graph.fromId(eid, Edge());
00334 }
00335
00336 const _Graph& graph;
00337 };
00338 };
00339
00340
00342
00347 class MaxIDableGraphComponent : virtual public BaseGraphComponent {
00348 public:
00349
00351
00354 int maxId(Node = INVALID) const { return -1;}
00355
00357
00360 int maxId(Edge = INVALID) const { return -1;}
00361
00362 template <typename _Graph>
00363 struct Constraints {
00364
00365 void constraints() {
00366 checkConcept<BaseGraphComponent, _Graph>();
00367 int nid = graph.maxId(typename _Graph::Node());
00368 ignore_unused_variable_warning(nid);
00369 int eid = graph.maxId(typename _Graph::Edge());
00370 ignore_unused_variable_warning(eid);
00371 }
00372
00373 const _Graph& graph;
00374 };
00375 };
00376
00378
00382 class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
00383 public:
00384
00385 typedef BaseGraphComponent::Node Node;
00386 typedef BaseGraphComponent::Edge Edge;
00387
00389
00392 Node addNode() {
00393 return INVALID;
00394 }
00395
00397
00400 Edge addEdge(const Node&, const Node&) {
00401 return INVALID;
00402 }
00403
00404 template <typename _Graph>
00405 struct Constraints {
00406 void constraints() {
00407 checkConcept<BaseGraphComponent, _Graph >();
00408 typename _Graph::Node node_a, node_b;
00409 node_a = graph.addNode();
00410 node_b = 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& gi) :Edge(gi) {}
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
00684 Node baseNode(const InEdgeIt&) const { return INVALID; }
00685
00690 Node runningNode(const InEdgeIt&) const { return INVALID; }
00691
00696 Node baseNode(const OutEdgeIt&) const { return INVALID; }
00697
00702 Node runningNode(const OutEdgeIt&) const { return INVALID; }
00703
00708 Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
00709
00710
00711 template <typename _Graph>
00712 struct Constraints {
00713 void constraints() {
00714 checkConcept< BaseGraphComponent, _Graph>();
00715
00716 checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
00717 typename _Graph::EdgeIt >();
00718 checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
00719 typename _Graph::NodeIt >();
00720 checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt>();
00721 checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt>();
00722
00723 typename _Graph::Node n(INVALID);
00724 typename _Graph::Edge e(INVALID);
00725 n = graph.oppositeNode(n, e);
00726 }
00727
00728 const _Graph& graph;
00729
00730 };
00731 };
00732
00734
00740 class AlterableGraphComponent : virtual public BaseGraphComponent {
00741 public:
00742
00744 typedef AlterationNotifier<Edge> EdgeNotifier;
00746 typedef AlterationNotifier<Node> NodeNotifier;
00747
00751 EdgeNotifier getNotifier(Edge) const {
00752 return EdgeNotifier();
00753 }
00754
00758 NodeNotifier getNotifier(Node) const {
00759 return NodeNotifier();
00760 }
00761
00762 };
00763
00764
00766
00770 template <typename Graph, typename Item, typename _Value>
00771 class GraphMap : public ReadWriteMap<Item, _Value> {
00772 protected:
00773 GraphMap() {}
00774 public:
00778 explicit GraphMap(const Graph&) {}
00782 GraphMap(const Graph&, const _Value&) {}
00786 GraphMap(const GraphMap& gm) :ReadWriteMap<Item, _Value>(gm) {}
00787
00791 GraphMap& operator=(const GraphMap&) { return *this;}
00792
00793 template<typename _Map>
00794 struct Constraints {
00795 void constraints() {
00796 checkConcept<ReadWriteMap<Item, _Value>, _Map >();
00797
00798 _Map a(g);
00799
00800 _Map a2(g,t);
00801
00802 _Map b=c;
00803
00804 ignore_unused_variable_warning(a2);
00805 }
00806
00807 const _Map &c;
00808 const Graph &g;
00809 const typename GraphMap::Value &t;
00810 };
00811
00812 };
00813
00815
00819 class MappableGraphComponent : virtual public BaseGraphComponent {
00820 public:
00821
00822 typedef MappableGraphComponent Graph;
00823
00824 typedef BaseGraphComponent::Node Node;
00825 typedef BaseGraphComponent::Edge Edge;
00826
00828
00831 template <typename _Value>
00832 class NodeMap : public GraphMap<Graph, Node, _Value> {
00833 private:
00834 NodeMap();
00835 public:
00840 explicit NodeMap(const Graph&) {}
00844 NodeMap(const Graph&, const _Value&) {}
00848 NodeMap(const NodeMap& nm) : GraphMap<Graph, Node, _Value>(nm) {}
00849
00853 NodeMap& operator=(const NodeMap&) { return *this;}
00854
00855 };
00856
00858
00861 template <typename _Value>
00862 class EdgeMap : public GraphMap<Graph, Edge, _Value> {
00863 private:
00864 EdgeMap();
00865 public:
00870 explicit EdgeMap(const Graph&) {}
00874 EdgeMap(const Graph&, const _Value&) {}
00878 EdgeMap(const EdgeMap& em) :GraphMap<Graph, Edge, _Value>(em) {}
00879
00883 EdgeMap& operator=(const EdgeMap&) { return *this;}
00884
00885 };
00886
00887 template <typename _Graph>
00888 struct Constraints {
00889
00890 struct Type {
00891 int value;
00892 Type() : value(0) {}
00893 Type(int _v) : value(_v) {}
00894 };
00895
00896 void constraints() {
00897 checkConcept<BaseGraphComponent, _Graph>();
00898 {
00899 typedef typename _Graph::template NodeMap<int> IntNodeMap;
00900 checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
00901 IntNodeMap >();
00902 } {
00903 typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
00904 checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
00905 BoolNodeMap >();
00906 } {
00907 typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
00908 checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
00909 TypeNodeMap >();
00910 }
00911
00912 {
00913 typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
00914 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
00915 IntEdgeMap >();
00916 } {
00917 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
00918 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
00919 BoolEdgeMap >();
00920 } {
00921 typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
00922 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>,
00923 TypeEdgeMap >();
00924 }
00925 }
00926
00927 _Graph& graph;
00928 };
00929 };
00930
00938 class ExtendableGraphComponent : virtual public BaseGraphComponent {
00939 public:
00940
00941 typedef ExtendableGraphComponent Graph;
00942
00943 typedef BaseGraphComponent::Node Node;
00944 typedef BaseGraphComponent::Edge Edge;
00945
00949 Node addNode() {
00950 return INVALID;
00951 }
00952
00956 Edge addEdge(const Node&, const Node&) {
00957 return INVALID;
00958 }
00959
00960 template <typename _Graph>
00961 struct Constraints {
00962 void constraints() {
00963 checkConcept<BaseGraphComponent, _Graph >();
00964 typename _Graph::Node node_a, node_b;
00965 node_a = graph.addNode();
00966 node_b = graph.addNode();
00967 typename _Graph::Edge edge;
00968 edge = graph.addEdge(node_a, node_b);
00969 }
00970 _Graph& graph;
00971 };
00972 };
00973
00981 class ErasableGraphComponent : virtual public BaseGraphComponent {
00982 public:
00983
00984 typedef ErasableGraphComponent Graph;
00985
00986 typedef BaseGraphComponent::Node Node;
00987 typedef BaseGraphComponent::Edge Edge;
00988
00992 void erase(const Node&) {}
00993
00997 void erase(const Edge&) {}
00998
00999 template <typename _Graph>
01000 struct Constraints {
01001 void constraints() {
01002 checkConcept<BaseGraphComponent, _Graph >();
01003 typename _Graph::Node node;
01004 graph.erase(node);
01005 typename _Graph::Edge edge;
01006 graph.erase(edge);
01007 }
01008
01009 _Graph& graph;
01010 };
01011 };
01012
01013 }
01014
01015 }
01016
01017 #endif