1.1 --- a/src/lemon/concept/graph_component.h Thu Nov 04 21:28:55 2004 +0000
1.2 +++ b/src/lemon/concept/graph_component.h Thu Nov 04 22:04:51 2004 +0000
1.3 @@ -28,10 +28,107 @@
1.4 namespace lemon {
1.5 namespace concept {
1.6
1.7 +
1.8 + /**************** Graph iterator concepts ****************/
1.9 +
1.10 + /// Skeleton class for graph Node and Edge
1.11 +
1.12 + /// \note Because Node and Edge are forbidden to inherit from the same
1.13 + /// base class, this is a template. For Node you shoul instantiate it
1.14 + /// with character 'n' and for Edge with 'e'.
1.15 +
1.16 + template<char Ch>
1.17 + class GraphItem {
1.18 + public:
1.19 + GraphItem() {}
1.20 + GraphItem(Invalid) {}
1.21 +
1.22 + // We explicitely list these:
1.23 + GraphItem(GraphItem const&) {}
1.24 + GraphItem& operator=(GraphItem const&) { return *this; }
1.25 +
1.26 + bool operator==(GraphItem) const { return false; }
1.27 + bool operator!=(GraphItem) const { return false; }
1.28 +
1.29 + // Technical requirement. Do we really need this?
1.30 + bool operator<(GraphItem) const { return false; }
1.31 + };
1.32 +
1.33 +
1.34 + template<typename GI>
1.35 + struct GraphItemConcept {
1.36 + void constraints() {
1.37 + GI i1;
1.38 + GI i2 = i1;
1.39 + GI i3 = INVALID;
1.40 +
1.41 + i1 = i2 = i3;
1.42 +
1.43 + bool b;
1.44 + b = (ia == ib) && (ia != ib) && (ia < ib);
1.45 + b = (ia == INVALID) && (ib != INVALID);
1.46 + }
1.47 +
1.48 + const GI &ia;
1.49 + const GI &ib;
1.50 + };
1.51 +
1.52 +
1.53 + template<typename Iter, typename Graph, typename BaseItem>
1.54 + struct GraphIteratorConcept {
1.55 + void constraints() {
1.56 + function_requires< GraphItemConcept<Iter> >();
1.57 + Iter it1(g);
1.58 +
1.59 + /// \todo Do we need NodeIt(Node) kind of constructor?
1.60 + // Iter it2(bj);
1.61 + Iter it2;
1.62 +
1.63 + it2 = ++it1;
1.64 + ++it2 = it1;
1.65 + ++(++it1);
1.66 + /// \bug This should be: is_base_and_derived<BaseItem, Iter>
1.67 + BaseItem bi = it1;
1.68 + bi = it2;
1.69 + }
1.70 +
1.71 + BaseItem bj;
1.72 + Graph g;
1.73 + };
1.74 +
1.75 + template<typename Iter, typename Graph>
1.76 + struct GraphIncIteratorConcept {
1.77 + typedef typename Graph::Node Node;
1.78 + typedef typename Graph::Edge Edge;
1.79 + void constraints() {
1.80 + function_requires< GraphItemConcept<Iter> >();
1.81 + Iter it1(graph, node);
1.82 + /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
1.83 + // Iter it2(edge);
1.84 + Iter it2;
1.85 +
1.86 + it2 = ++it1;
1.87 + ++it2 = it1;
1.88 + ++(++it1);
1.89 + Edge e = it1;
1.90 + e = it2;
1.91 + }
1.92 +
1.93 + Edge edge;
1.94 + Node node;
1.95 + Graph graph;
1.96 + };
1.97 +
1.98 +
1.99 +
1.100 /// An empty base graph class.
1.101
1.102 - /// This class provides the most minimal features of a graph structure.
1.103 - /// All the graph concepts have to be conform to this base graph.
1.104 + /// This class provides the minimal set of features needed for a graph
1.105 + /// structure. All graph concepts have to be conform to this base
1.106 + /// graph.
1.107 + ///
1.108 + /// \bug This is not true. The minimal graph concept is the
1.109 + /// BaseIterableGraphComponent.
1.110
1.111 class BaseGraphComponent {
1.112 public:
1.113 @@ -70,14 +167,14 @@
1.114
1.115 /// Two iterators are equal if and only if they represents the
1.116 /// same node in the graph or both are invalid.
1.117 - bool operator==(const Node&) { return true;}
1.118 + bool operator==(const Node&) const { return true;}
1.119
1.120
1.121 /// Inequality operator.
1.122
1.123 /// \sa operator==(const Node& n)
1.124 ///
1.125 - bool operator!=(const Node&) { return true;}
1.126 + bool operator!=(const Node&) const { return true;}
1.127
1.128 /// Comparison operator.
1.129
1.130 @@ -85,7 +182,7 @@
1.131 ///
1.132 /// This ordering can be different from the iterating order of nodes.
1.133 /// \todo Possibly we don't need it.
1.134 - bool operator<(const Node&) { return true;}
1.135 + bool operator<(const Node&) const { return true;}
1.136 };
1.137
1.138 /// Edge class of the graph.
1.139 @@ -120,14 +217,14 @@
1.140
1.141 /// Two iterators are equal if and only if they represents the
1.142 /// same edge in the graph or both are invalid.
1.143 - bool operator==(const Edge&) { return true;}
1.144 + bool operator==(const Edge&) const { return true;}
1.145
1.146
1.147 /// Inequality operator.
1.148
1.149 /// \sa operator==(const Edge& n)
1.150 ///
1.151 - bool operator!=(const Edge&) { return true;}
1.152 + bool operator!=(const Edge&) const { return true;}
1.153
1.154 /// Comparison operator.
1.155
1.156 @@ -135,7 +232,7 @@
1.157 ///
1.158 /// This ordering can be different from the iterating order of edges.
1.159 /// \todo Possibly we don't need it.
1.160 - bool operator<(const Edge&) { return true;}
1.161 + bool operator<(const Edge&) const { return true;}
1.162 };
1.163
1.164 ///Gives back the head node of an edge.
1.165 @@ -151,6 +248,7 @@
1.166 Node tail(const Edge&) const { return INVALID;}
1.167 };
1.168
1.169 +
1.170 /// Concept check structure for BaseGraph.
1.171
1.172 /// Concept check structure for BaseGraph.
1.173 @@ -162,24 +260,8 @@
1.174 typedef typename Graph::Edge Edge;
1.175
1.176 void constraints() {
1.177 - {
1.178 - Node ni;
1.179 - Node nj(ni);
1.180 - Node nk(INVALID);
1.181 - ni = nj;
1.182 - bool b; b = true;
1.183 - b = (ni == INVALID); b = (ni != INVALID);
1.184 - b = (ni==nj); b = (ni != nj); b=( ni < nj);
1.185 - }
1.186 - {
1.187 - Edge ei;
1.188 - Edge ej(ei);
1.189 - Edge ek(INVALID);
1.190 - ei = ej;
1.191 - bool b; b = true;
1.192 - b = (ei == INVALID); b = (ei != INVALID);
1.193 - b = (ei==ej); b = (ei != ej); b=( ei < ej);
1.194 - }
1.195 + function_requires< GraphItemConcept<Node> >();
1.196 + function_requires< GraphItemConcept<Edge> >();
1.197 {
1.198 const Graph& const_graph = graph;
1.199 Node n;
1.200 @@ -262,29 +344,29 @@
1.201 template <typename Graph>
1.202 struct BaseIterableGraphComponentConcept {
1.203
1.204 - void constraints() {
1.205 - const Graph& const_graph = graph;
1.206 + void constraints() {
1.207 + function_requires< BaseGraphComponentConcept<Graph> >();
1.208 typename Graph::Node node;
1.209 typename Graph::Edge edge;
1.210 {
1.211 - const_graph.first(node);
1.212 - const_graph.next(node);
1.213 + graph.first(node);
1.214 + graph.next(node);
1.215 }
1.216 {
1.217 - const_graph.first(edge);
1.218 - const_graph.next(edge);
1.219 + graph.first(edge);
1.220 + graph.next(edge);
1.221 }
1.222 {
1.223 - const_graph.firstIn(edge, node);
1.224 - const_graph.nextIn(edge);
1.225 + graph.firstIn(edge, node);
1.226 + graph.nextIn(edge);
1.227 }
1.228 {
1.229 - const_graph.firstOut(edge, node);
1.230 - const_graph.nextOut(edge);
1.231 + graph.firstOut(edge, node);
1.232 + graph.nextOut(edge);
1.233 }
1.234 }
1.235
1.236 - Graph& graph;
1.237 + const Graph& graph;
1.238 };
1.239
1.240 /// An empty idable base graph class.
1.241 @@ -322,16 +404,16 @@
1.242 struct IDableGraphComponentConcept {
1.243
1.244 void constraints() {
1.245 - const Graph& const_graph = graph;
1.246 + function_requires< BaseGraphComponentConcept<Graph> >();
1.247 typename Graph::Node node;
1.248 - int nid = const_graph.id(node);
1.249 - nid = const_graph.id(node);
1.250 + int nid = graph.id(node);
1.251 + nid = graph.id(node);
1.252 typename Graph::Edge edge;
1.253 - int eid = const_graph.id(edge);
1.254 - eid = const_graph.id(edge);
1.255 + int eid = graph.id(edge);
1.256 + eid = graph.id(edge);
1.257 }
1.258
1.259 - Graph& graph;
1.260 + const Graph& graph;
1.261 };
1.262
1.263
1.264 @@ -365,14 +447,14 @@
1.265 struct MaxIDableGraphComponentConcept {
1.266
1.267 void constraints() {
1.268 - const Graph& const_graph = graph;
1.269 - int nid = const_graph.maxEdgeId();
1.270 + function_requires< BaseGraphComponentConcept<Graph> >();
1.271 + int nid = graph.maxEdgeId();
1.272 ignore_unused_variable_warning(nid);
1.273 - int eid = const_graph.maxNodeId();
1.274 + int eid = graph.maxNodeId();
1.275 ignore_unused_variable_warning(eid);
1.276 }
1.277
1.278 - Graph& graph;
1.279 + const Graph& graph;
1.280 };
1.281
1.282 /// An empty extendable base graph class.
1.283 @@ -411,6 +493,7 @@
1.284 template <typename Graph>
1.285 struct BaseExtendableGraphComponentConcept {
1.286 void constraints() {
1.287 + function_requires< BaseGraphComponentConcept<Graph> >();
1.288 typename Graph::Node node_a, node_b;
1.289 node_a = graph.addNode();
1.290 typename Graph::Edge edge;
1.291 @@ -452,6 +535,7 @@
1.292 template <typename Graph>
1.293 struct BaseErasableGraphComponentConcept {
1.294 void constraints() {
1.295 + function_requires< BaseGraphComponentConcept<Graph> >();
1.296 typename Graph::Node node;
1.297 graph.erase(node);
1.298 typename Graph::Edge edge;
1.299 @@ -483,6 +567,7 @@
1.300 template <typename Graph>
1.301 struct BaseClearableGraphComponentConcept {
1.302 void constraints() {
1.303 + function_requires< BaseGraphComponentConcept<Graph> >();
1.304 graph.clear();
1.305 }
1.306
1.307 @@ -490,7 +575,8 @@
1.308 };
1.309
1.310
1.311 - class IterableGraphComponent : virtual public BaseGraphComponent {
1.312 + class IterableGraphComponent :
1.313 + virtual public BaseIterableGraphComponent {
1.314
1.315 public:
1.316
1.317 @@ -503,52 +589,56 @@
1.318 public:
1.319 NodeIt() {}
1.320 NodeIt(Invalid) {}
1.321 - NodeIt(const Graph&) {}
1.322 + // explicit NodeIt(Node) {}
1.323 + explicit NodeIt(const Graph&) {}
1.324
1.325 NodeIt& operator++() { return *this; }
1.326 // Node operator*() const { return INVALID; }
1.327
1.328 - bool operator==(const NodeIt&) { return true;}
1.329 - bool operator!=(const NodeIt&) { return true;}
1.330 + bool operator==(const NodeIt&) const { return true;}
1.331 + bool operator!=(const NodeIt&) const { return true;}
1.332 };
1.333
1.334 class EdgeIt : public Edge {
1.335 public:
1.336 EdgeIt() {}
1.337 EdgeIt(Invalid) {}
1.338 - EdgeIt(const Graph&) {}
1.339 + // explicit EdgeIt(Edge) {}
1.340 + explicit EdgeIt(const Graph&) {}
1.341
1.342 EdgeIt& operator++() { return *this; }
1.343 // Edge operator*() const { return INVALID; }
1.344
1.345 - bool operator==(const EdgeIt&) { return true;}
1.346 - bool operator!=(const EdgeIt&) { return true;}
1.347 + bool operator==(const EdgeIt&) const { return true;}
1.348 + bool operator!=(const EdgeIt&) const { return true;}
1.349 };
1.350
1.351 class InEdgeIt : public Edge {
1.352 public:
1.353 InEdgeIt() {}
1.354 InEdgeIt(Invalid) {}
1.355 - InEdgeIt(const Graph&, const Node&) {}
1.356 + // explicit InEdgeIt(Edge) {}
1.357 + explicit InEdgeIt(const Graph&, const Node&) {}
1.358
1.359 InEdgeIt& operator++() { return *this; }
1.360 // Edge operator*() const { return INVALID; }
1.361
1.362 - bool operator==(const InEdgeIt&) { return true;}
1.363 - bool operator!=(const InEdgeIt&) { return true;}
1.364 + bool operator==(const InEdgeIt&) const { return true;}
1.365 + bool operator!=(const InEdgeIt&) const { return true;}
1.366 };
1.367
1.368 class OutEdgeIt : public Edge {
1.369 public:
1.370 OutEdgeIt() {}
1.371 OutEdgeIt(Invalid) {}
1.372 - OutEdgeIt(const Graph&, const Node&) {}
1.373 + // explicit OutEdgeIt(Edge) {}
1.374 + explicit OutEdgeIt(const Graph&, const Node&) {}
1.375
1.376 OutEdgeIt& operator++() { return *this; }
1.377 // Edge operator*() const { return INVALID; }
1.378
1.379 - bool operator==(const OutEdgeIt&) { return true;}
1.380 - bool operator!=(const OutEdgeIt&) { return true;}
1.381 + bool operator==(const OutEdgeIt&) const { return true;}
1.382 + bool operator!=(const OutEdgeIt&) const { return true;}
1.383 };
1.384
1.385 };
1.386 @@ -557,7 +647,8 @@
1.387 struct IterableGraphComponentConcept {
1.388
1.389 void constraints() {
1.390 -
1.391 + function_requires< BaseIterableGraphComponentConcept<Graph> >();
1.392 +
1.393 typedef typename Graph::Node Node;
1.394 typedef typename Graph::NodeIt NodeIt;
1.395 typedef typename Graph::Edge Edge;
1.396 @@ -565,68 +656,10 @@
1.397 typedef typename Graph::InEdgeIt InEdgeIt;
1.398 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.399
1.400 - {
1.401 - NodeIt it;
1.402 - NodeIt jt(it);
1.403 - NodeIt kt(INVALID);
1.404 - NodeIt lt(graph);
1.405 - it = jt;
1.406 - jt = ++it;
1.407 - bool b;
1.408 - b = (it == INVALID);
1.409 - b = (it != INVALID);
1.410 - b = (it == jt);
1.411 - b = (it != jt);
1.412 - Node node = it;
1.413 - node = it;
1.414 - }
1.415 - {
1.416 - EdgeIt it;
1.417 - EdgeIt jt(it);
1.418 - EdgeIt kt(INVALID);
1.419 - EdgeIt lt(graph);
1.420 - it = jt;
1.421 - jt = ++it;
1.422 - bool b;
1.423 - b = (it == INVALID);
1.424 - b = (it != INVALID);
1.425 - b = (it == jt);
1.426 - b = (it != jt);
1.427 - Edge edge = it;
1.428 - edge = it;
1.429 - }
1.430 - {
1.431 - InEdgeIt it;
1.432 - InEdgeIt jt(it);
1.433 - InEdgeIt kt(INVALID);
1.434 - Node node;
1.435 - InEdgeIt lt(graph, node);
1.436 - it = jt;
1.437 - jt = ++it;
1.438 - bool b;
1.439 - b = (it == INVALID);
1.440 - b = (it != INVALID);
1.441 - b = (it == jt);
1.442 - b = (it != jt);
1.443 - Edge edge = it;
1.444 - edge = it;
1.445 - }
1.446 - {
1.447 - OutEdgeIt it;
1.448 - OutEdgeIt jt(it);
1.449 - OutEdgeIt kt(INVALID);
1.450 - Node node;
1.451 - OutEdgeIt lt(graph, node);
1.452 - it = jt;
1.453 - jt = ++it;
1.454 - bool b;
1.455 - b = (it == INVALID);
1.456 - b = (it != INVALID);
1.457 - b = (it == jt);
1.458 - b = (it != jt);
1.459 - Edge edge = it;
1.460 - edge = it;
1.461 - }
1.462 + function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
1.463 + function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
1.464 + function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
1.465 + function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
1.466 }
1.467 Graph& graph;
1.468 };
1.469 @@ -636,11 +669,11 @@
1.470
1.471 typedef IdMappableGraphComponent Graph;
1.472
1.473 + public:
1.474 +
1.475 typedef BaseGraphComponent::Node Node;
1.476 typedef BaseGraphComponent::Edge Edge;
1.477
1.478 - public:
1.479 -
1.480 class NodeIdMap : public ReadMap<Node, int> {
1.481 public:
1.482 NodeIdMap(const Graph&) {}
1.483 @@ -658,6 +691,7 @@
1.484 template <typename Graph>
1.485 struct IdMappableGraphComponentConcept {
1.486 void constraints() {
1.487 + function_requires< BaseGraphComponentConcept<Graph> >();
1.488 {
1.489 typedef typename Graph::EdgeIdMap EdgeIdMap;
1.490 function_requires<ReadMapConcept<EdgeIdMap> >();
1.491 @@ -719,6 +753,7 @@
1.492 };
1.493
1.494 void constraints() {
1.495 + function_requires< BaseGraphComponentConcept<Graph> >();
1.496 { // int map test
1.497 typedef typename Graph::template NodeMap<int> IntNodeMap;
1.498 function_requires<GraphMapConcept<IntNodeMap,Graph> >();
1.499 @@ -767,6 +802,7 @@
1.500 template <typename Graph>
1.501 struct ExtendableGraphComponentConcept {
1.502 void constraints() {
1.503 + function_requires< BaseGraphComponentConcept<Graph> >();
1.504 typename Graph::Node node_a, node_b;
1.505 node_a = graph.addNode();
1.506 typename Graph::Edge edge;
1.507 @@ -791,6 +827,7 @@
1.508 template <typename Graph>
1.509 struct ErasableGraphComponentConcept {
1.510 void constraints() {
1.511 + function_requires< BaseGraphComponentConcept<Graph> >();
1.512 typename Graph::Node node;
1.513 graph.erase(node);
1.514 typename Graph::Edge edge;
1.515 @@ -815,6 +852,7 @@
1.516 template <typename Graph>
1.517 struct ClearableGraphComponentConcept {
1.518 void constraints() {
1.519 + function_requires< BaseGraphComponentConcept<Graph> >();
1.520 graph.clear();
1.521 }
1.522 Graph& graph;