1.1 --- a/src/lemon/concept/graph_component.h Sat Nov 13 17:47:44 2004 +0000
1.2 +++ b/src/lemon/concept/graph_component.h Sat Nov 13 21:37:54 2004 +0000
1.3 @@ -37,90 +37,64 @@
1.4 /// base class, this is a template. For Node you should instantiate it
1.5 /// with character 'n' and for Edge with 'e'.
1.6
1.7 - template<char Ch>
1.8 + template<char _selector>
1.9 class GraphItem {
1.10 public:
1.11 + /// Default constructor.
1.12 +
1.13 + /// @warning The default constructor sets the item
1.14 + /// to an undefined value.
1.15 GraphItem() {}
1.16 + /// Copy constructor.
1.17 +
1.18 + /// Copy constructor.
1.19 + ///
1.20 + GraphItem(GraphItem const&) {}
1.21 + /// Invalid constructor \& conversion.
1.22 +
1.23 + /// This constructor initializes the item to be invalid.
1.24 + /// \sa Invalid for more details.
1.25 GraphItem(Invalid) {}
1.26 + /// Assign operator for nodes.
1.27
1.28 - // We explicitely list these:
1.29 - GraphItem(GraphItem const&) {}
1.30 + /// The nodes are assignable.
1.31 + ///
1.32 GraphItem& operator=(GraphItem const&) { return *this; }
1.33 -
1.34 + /// Equality operator.
1.35 +
1.36 + /// Two iterators are equal if and only if they represents the
1.37 + /// same node in the graph or both are invalid.
1.38 bool operator==(GraphItem) const { return false; }
1.39 + /// Inequality operator.
1.40 +
1.41 + /// \sa operator==(const Node& n)
1.42 + ///
1.43 bool operator!=(GraphItem) const { return false; }
1.44
1.45 // Technical requirement. Do we really need this?
1.46 - bool operator<(GraphItem) const { return false; }
1.47 + // bool operator<(GraphItem) const { return false; }
1.48 +
1.49 +
1.50 + template<typename _GraphItem>
1.51 + struct Constraints {
1.52 + void constraints() {
1.53 + _GraphItem i1;
1.54 + _GraphItem i2 = i1;
1.55 + _GraphItem i3 = INVALID;
1.56 +
1.57 + i1 = i2 = i3;
1.58 +
1.59 + bool b;
1.60 + // b = (ia == ib) && (ia != ib) && (ia < ib);
1.61 + b = (ia == ib) && (ia != ib);
1.62 + b = (ia == INVALID) && (ib != INVALID);
1.63 + }
1.64 +
1.65 + const _GraphItem &ia;
1.66 + const _GraphItem &ib;
1.67 + };
1.68 };
1.69
1.70 -
1.71 - template<typename GI>
1.72 - struct GraphItemConcept {
1.73 - void constraints() {
1.74 - GI i1;
1.75 - GI i2 = i1;
1.76 - GI i3 = INVALID;
1.77 -
1.78 - i1 = i2 = i3;
1.79 -
1.80 - bool b;
1.81 - b = (ia == ib) && (ia != ib) && (ia < ib);
1.82 - b = (ia == INVALID) && (ib != INVALID);
1.83 - }
1.84 -
1.85 - const GI &ia;
1.86 - const GI &ib;
1.87 - };
1.88 -
1.89 -
1.90 - template<typename Iter, typename Graph, typename BaseItem>
1.91 - struct GraphIteratorConcept {
1.92 - void constraints() {
1.93 - function_requires< GraphItemConcept<Iter> >();
1.94 - Iter it1(g);
1.95 -
1.96 - /// \todo Do we need NodeIt(Node) kind of constructor?
1.97 - // Iter it2(bj);
1.98 - Iter it2;
1.99 -
1.100 - it2 = ++it1;
1.101 - ++it2 = it1;
1.102 - ++(++it1);
1.103 - /// \bug This should be: is_base_and_derived<BaseItem, Iter>
1.104 - BaseItem bi = it1;
1.105 - bi = it2;
1.106 - }
1.107 -
1.108 - BaseItem bj;
1.109 - Graph g;
1.110 - };
1.111 -
1.112 - template<typename Iter, typename Graph>
1.113 - struct GraphIncIteratorConcept {
1.114 - typedef typename Graph::Node Node;
1.115 - typedef typename Graph::Edge Edge;
1.116 - void constraints() {
1.117 - function_requires< GraphItemConcept<Iter> >();
1.118 - Iter it1(graph, node);
1.119 - /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
1.120 - // Iter it2(edge);
1.121 - Iter it2;
1.122 -
1.123 - it2 = ++it1;
1.124 - ++it2 = it1;
1.125 - ++(++it1);
1.126 - Edge e = it1;
1.127 - e = it2;
1.128 - }
1.129 -
1.130 - Edge edge;
1.131 - Node node;
1.132 - Graph graph;
1.133 - };
1.134 -
1.135 -
1.136 -
1.137 /// An empty base graph class.
1.138
1.139 /// This class provides the minimal set of features needed for a graph
1.140 @@ -139,108 +113,13 @@
1.141
1.142 /// This class represents the Nodes of the graph.
1.143 ///
1.144 - class Node {
1.145 - public:
1.146 -
1.147 - /// Default constructor.
1.148 -
1.149 - /// @warning The default constructor sets the iterator
1.150 - /// to an undefined value.
1.151 -
1.152 - Node() {}
1.153 - /// Copy constructor.
1.154 -
1.155 - /// Copy constructor.
1.156 - ///
1.157 - Node(const Node&) {}
1.158 -
1.159 - /// Invalid constructor \& conversion.
1.160 -
1.161 - /// This constructor initializes the iterator to be invalid.
1.162 - /// \sa Invalid for more details.
1.163 - Node(Invalid) {}
1.164 -
1.165 -
1.166 - /// Assign operator for nodes.
1.167 -
1.168 - /// The nodes are assignable.
1.169 - ///
1.170 - Node& operator=(const Node&) { return *this;}
1.171 -
1.172 - /// Equality operator.
1.173 -
1.174 - /// Two iterators are equal if and only if they represents the
1.175 - /// same node in the graph or both are invalid.
1.176 - bool operator==(const Node&) const { return true;}
1.177 -
1.178 -
1.179 - /// Inequality operator.
1.180 -
1.181 - /// \sa operator==(const Node& n)
1.182 - ///
1.183 - bool operator!=(const Node&) const { return true;}
1.184 -
1.185 - /// Comparison operator.
1.186 -
1.187 - /// This is a strict ordering between the nodes.
1.188 - ///
1.189 - /// This ordering can be different from the iterating order of nodes.
1.190 - /// \todo Possibly we don't need it.
1.191 - bool operator<(const Node&) const { return true;}
1.192 - };
1.193 + typedef GraphItem<'n'> Node;
1.194
1.195 /// Edge class of the graph.
1.196
1.197 /// This class represents the Edges of the graph.
1.198 ///
1.199 - class Edge {
1.200 - public:
1.201 -
1.202 - /// Default constructor.
1.203 -
1.204 - /// @warning The default constructor sets the iterator
1.205 - /// to an undefined value.
1.206 -
1.207 - Edge() {}
1.208 - /// Copy constructor.
1.209 -
1.210 - /// Copy constructor.
1.211 - ///
1.212 - Edge(const Edge&) {}
1.213 -
1.214 - /// Invalid constructor \& conversion.
1.215 -
1.216 - /// This constructor initializes the iterator to be invalid.
1.217 - /// \sa Invalid for more details.
1.218 - Edge(Invalid) {}
1.219 -
1.220 - /// Assign operator for edges.
1.221 -
1.222 - /// The edges are assignable.
1.223 - ///
1.224 - Edge& operator=(const Edge&) { return *this;}
1.225 -
1.226 - /// Equality operator.
1.227 -
1.228 - /// Two iterators are equal if and only if they represents the
1.229 - /// same edge in the graph or both are invalid.
1.230 - bool operator==(const Edge&) const { return true;}
1.231 -
1.232 -
1.233 - /// Inequality operator.
1.234 -
1.235 - /// \sa operator==(const Edge& n)
1.236 - ///
1.237 - bool operator!=(const Edge&) const { return true;}
1.238 -
1.239 - /// Comparison operator.
1.240 -
1.241 - /// This is a strict ordering between the edges.
1.242 - ///
1.243 - /// This ordering can be different from the iterating order of edges.
1.244 - /// \todo Possibly we don't need it.
1.245 - bool operator<(const Edge&) const { return true;}
1.246 - };
1.247 + typedef GraphItem<'e'> Edge;
1.248
1.249 ///Gives back the target node of an edge.
1.250
1.251 @@ -253,31 +132,26 @@
1.252 ///Gives back the source node of an edge.
1.253 ///
1.254 Node source(const Edge&) const { return INVALID;}
1.255 - };
1.256
1.257
1.258 - /// Concept check structure for BaseGraph.
1.259 -
1.260 - /// Concept check structure for BaseGraph.
1.261 - ///
1.262 -
1.263 - template <typename Graph>
1.264 - struct BaseGraphComponentConcept {
1.265 - typedef typename Graph::Node Node;
1.266 - typedef typename Graph::Edge Edge;
1.267 + template <typename _Graph>
1.268 + struct Constraints {
1.269 + typedef typename _Graph::Node Node;
1.270 + typedef typename _Graph::Edge Edge;
1.271
1.272 - void constraints() {
1.273 - function_requires< GraphItemConcept<Node> >();
1.274 - function_requires< GraphItemConcept<Edge> >();
1.275 - {
1.276 - Node n;
1.277 - Edge e;
1.278 - n = graph.source(e);
1.279 - n = graph.target(e);
1.280 - }
1.281 - }
1.282 + void constraints() {
1.283 + checkConcept<GraphItem<'n'>, Node>();
1.284 + checkConcept<GraphItem<'e'>, Edge>();
1.285 + {
1.286 + Node n;
1.287 + Edge e;
1.288 + n = graph.source(e);
1.289 + n = graph.target(e);
1.290 + }
1.291 + }
1.292
1.293 - const Graph& graph;
1.294 + const _Graph& graph;
1.295 + };
1.296 };
1.297
1.298 /// An empty iterable base graph class.
1.299 @@ -340,39 +214,35 @@
1.300 /// Gives back the next of the Edges start from the given Node.
1.301 ///
1.302 void nextOut(Edge&) const {}
1.303 - };
1.304
1.305
1.306 - /// Concept check structure for IterableBaseGraph.
1.307 + template <typename _Graph>
1.308 + struct Constraints {
1.309 +
1.310 + void constraints() {
1.311 + checkConcept< BaseGraphComponent, _Graph >();
1.312 + typename _Graph::Node node;
1.313 + typename _Graph::Edge edge;
1.314 + {
1.315 + graph.first(node);
1.316 + graph.next(node);
1.317 + }
1.318 + {
1.319 + graph.first(edge);
1.320 + graph.next(edge);
1.321 + }
1.322 + {
1.323 + graph.firstIn(edge, node);
1.324 + graph.nextIn(edge);
1.325 + }
1.326 + {
1.327 + graph.firstOut(edge, node);
1.328 + graph.nextOut(edge);
1.329 + }
1.330 + }
1.331
1.332 - /// Concept check structure for IterableBaseGraph.
1.333 - ///
1.334 - template <typename Graph>
1.335 - struct BaseIterableGraphComponentConcept {
1.336 -
1.337 - void constraints() {
1.338 - function_requires< BaseGraphComponentConcept<Graph> >();
1.339 - typename Graph::Node node;
1.340 - typename Graph::Edge edge;
1.341 - {
1.342 - graph.first(node);
1.343 - graph.next(node);
1.344 - }
1.345 - {
1.346 - graph.first(edge);
1.347 - graph.next(edge);
1.348 - }
1.349 - {
1.350 - graph.firstIn(edge, node);
1.351 - graph.nextIn(edge);
1.352 - }
1.353 - {
1.354 - graph.firstOut(edge, node);
1.355 - graph.nextOut(edge);
1.356 - }
1.357 - }
1.358 -
1.359 - const Graph& graph;
1.360 + const _Graph& graph;
1.361 + };
1.362 };
1.363
1.364 /// An empty idable base graph class.
1.365 @@ -381,7 +251,6 @@
1.366 /// core id functions for the graph structure.
1.367 /// The most of the base graphs should be conform to this concept.
1.368 /// The id's are unique and immutable.
1.369 -
1.370 class IDableGraphComponent : virtual public BaseGraphComponent {
1.371 public:
1.372
1.373 @@ -399,27 +268,22 @@
1.374 /// Gives back an unique integer id for the Edge.
1.375 ///
1.376 int id(const Edge&) const { return -1;}
1.377 - };
1.378
1.379 + template <typename _Graph>
1.380 + struct Constraints {
1.381
1.382 - /// Concept check structure for IdableBaseGraph.
1.383 + void constraints() {
1.384 + checkConcept< BaseGraphComponent, _Graph >();
1.385 + typename _Graph::Node node;
1.386 + int nid = graph.id(node);
1.387 + nid = graph.id(node);
1.388 + typename _Graph::Edge edge;
1.389 + int eid = graph.id(edge);
1.390 + eid = graph.id(edge);
1.391 + }
1.392
1.393 - /// Concept check structure for IdableBaseGraph.
1.394 - ///
1.395 - template <typename Graph>
1.396 - struct IDableGraphComponentConcept {
1.397 -
1.398 - void constraints() {
1.399 - function_requires< BaseGraphComponentConcept<Graph> >();
1.400 - typename Graph::Node node;
1.401 - int nid = graph.id(node);
1.402 - nid = graph.id(node);
1.403 - typename Graph::Edge edge;
1.404 - int eid = graph.id(edge);
1.405 - eid = graph.id(edge);
1.406 - }
1.407 -
1.408 - const Graph& graph;
1.409 + const _Graph& graph;
1.410 + };
1.411 };
1.412
1.413
1.414 @@ -443,24 +307,20 @@
1.415 /// Gives back an integer greater or equal to the maximum Edge id.
1.416 ///
1.417 int maxId(Edge = INVALID) const { return -1;}
1.418 - };
1.419
1.420 - /// Concept check structure for MaxIdableBaseGraph.
1.421 + template <typename _Graph>
1.422 + struct Constraints {
1.423
1.424 - /// Concept check structure for MaxIdableBaseGraph.
1.425 - ///
1.426 - template <typename Graph>
1.427 - struct MaxIDableGraphComponentConcept {
1.428 -
1.429 - void constraints() {
1.430 - function_requires< BaseGraphComponentConcept<Graph> >();
1.431 - int nid = graph.maxId(typename Graph::Node());
1.432 - ignore_unused_variable_warning(nid);
1.433 - int eid = graph.maxId(typename Graph::Edge());
1.434 - ignore_unused_variable_warning(eid);
1.435 - }
1.436 -
1.437 - const Graph& graph;
1.438 + void constraints() {
1.439 + checkConcept<BaseGraphComponent, _Graph>();
1.440 + int nid = graph.maxId(typename _Graph::Node());
1.441 + ignore_unused_variable_warning(nid);
1.442 + int eid = graph.maxId(typename _Graph::Edge());
1.443 + ignore_unused_variable_warning(eid);
1.444 + }
1.445 +
1.446 + const _Graph& graph;
1.447 + };
1.448 };
1.449
1.450 /// An empty extendable base graph class.
1.451 @@ -490,23 +350,18 @@
1.452 return INVALID;
1.453 }
1.454
1.455 - };
1.456 + template <typename _Graph>
1.457 + struct Constraints {
1.458 + void constraints() {
1.459 + checkConcept<BaseGraphComponent, _Graph >();
1.460 + typename _Graph::Node node_a, node_b;
1.461 + node_a = graph.addNode();
1.462 + typename _Graph::Edge edge;
1.463 + edge = graph.addEdge(node_a, node_b);
1.464 + }
1.465
1.466 - /// Concept check structure for ExtendableBaseGraph.
1.467 -
1.468 - /// Concept check structure for ExtendableBaseGraph.
1.469 - ///
1.470 - template <typename Graph>
1.471 - struct BaseExtendableGraphComponentConcept {
1.472 - void constraints() {
1.473 - function_requires< BaseGraphComponentConcept<Graph> >();
1.474 - typename Graph::Node node_a, node_b;
1.475 - node_a = graph.addNode();
1.476 - typename Graph::Edge edge;
1.477 - edge = graph.addEdge(node_a, node_b);
1.478 - }
1.479 -
1.480 - Graph& graph;
1.481 + _Graph& graph;
1.482 + };
1.483 };
1.484
1.485 /// An empty erasable base graph class.
1.486 @@ -532,23 +387,18 @@
1.487 ///
1.488 void erase(const Edge&) {}
1.489
1.490 - };
1.491 + template <typename _Graph>
1.492 + struct Constraints {
1.493 + void constraints() {
1.494 + checkConcept<BaseGraphComponent, _Graph>();
1.495 + typename _Graph::Node node;
1.496 + graph.erase(node);
1.497 + typename _Graph::Edge edge;
1.498 + graph.erase(edge);
1.499 + }
1.500
1.501 - /// Concept check structure for ErasableBaseGraph.
1.502 -
1.503 - /// Concept check structure for ErasableBaseGraph.
1.504 - ///
1.505 - template <typename Graph>
1.506 - struct BaseErasableGraphComponentConcept {
1.507 - void constraints() {
1.508 - function_requires< BaseGraphComponentConcept<Graph> >();
1.509 - typename Graph::Node node;
1.510 - graph.erase(node);
1.511 - typename Graph::Edge edge;
1.512 - graph.erase(edge);
1.513 - }
1.514 -
1.515 - Graph& graph;
1.516 + _Graph& graph;
1.517 + };
1.518 };
1.519
1.520 /// An empty clearable base graph class.
1.521 @@ -564,25 +414,172 @@
1.522 /// Erase all the Nodes and Edges from the graph.
1.523 ///
1.524 void clear() {}
1.525 +
1.526 + template <typename _Graph>
1.527 + struct Constraints {
1.528 + void constraints() {
1.529 + checkConcept< BaseGraphComponent, _Graph>();
1.530 + graph.clear();
1.531 + }
1.532 +
1.533 + _Graph& graph;
1.534 + };
1.535 };
1.536
1.537 - /// Concept check function for ErasableBaseGraph.
1.538
1.539 - /// Concept check function for ErasableBaseGraph.
1.540 + /// Skeleton class for graph NodeIt and EdgeIt
1.541 +
1.542 + /// Skeleton class for graph NodeIt and EdgeIt.
1.543 ///
1.544 - template <typename Graph>
1.545 - struct BaseClearableGraphComponentConcept {
1.546 - void constraints() {
1.547 - function_requires< BaseGraphComponentConcept<Graph> >();
1.548 - graph.clear();
1.549 - }
1.550 + template <typename _Graph, typename _Item>
1.551 + class GraphIterator : public _Item {
1.552 + public:
1.553 + /// \todo Don't we need the Item type as typedef?
1.554
1.555 - Graph& graph;
1.556 + /// Default constructor.
1.557 +
1.558 + /// @warning The default constructor sets the iterator
1.559 + /// to an undefined value.
1.560 + GraphIterator() {}
1.561 + /// Copy constructor.
1.562 +
1.563 + /// Copy constructor.
1.564 + ///
1.565 + GraphIterator(GraphIterator const&) {}
1.566 + /// Sets the iterator to the first item.
1.567 +
1.568 + /// Sets the iterator to the first item of \c the graph.
1.569 + ///
1.570 + explicit GraphIterator(const _Graph&) {}
1.571 + /// Invalid constructor \& conversion.
1.572 +
1.573 + /// This constructor initializes the item to be invalid.
1.574 + /// \sa Invalid for more details.
1.575 + GraphIterator(Invalid) {}
1.576 + /// Assign operator for items.
1.577 +
1.578 + /// The items are assignable.
1.579 + ///
1.580 + GraphIterator& operator=(GraphIterator const&) { return *this; }
1.581 + /// Next item.
1.582 +
1.583 + /// Assign the iterator to the next item.
1.584 + ///
1.585 + GraphIterator& operator++() { return *this; }
1.586 + // Node operator*() const { return INVALID; }
1.587 + /// Equality operator
1.588 +
1.589 + /// Two iterators are equal if and only if they point to the
1.590 + /// same object or both are invalid.
1.591 + bool operator==(const GraphIterator&) const { return true;}
1.592 + /// Inequality operator
1.593 +
1.594 + /// \sa operator==(Node n)
1.595 + ///
1.596 + bool operator!=(const GraphIterator&) const { return true;}
1.597 +
1.598 + template<typename _GraphIterator>
1.599 + struct Constraints {
1.600 + void constraints() {
1.601 + // checkConcept< Item, _GraphIterator >();
1.602 + _GraphIterator it1(g);
1.603 +
1.604 + /// \todo Do we need NodeIt(Node) kind of constructor?
1.605 + // _GraphIterator it2(bj);
1.606 + _GraphIterator it2;
1.607 +
1.608 + it2 = ++it1;
1.609 + ++it2 = it1;
1.610 + ++(++it1);
1.611 + /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
1.612 + _Item bi = it1;
1.613 + bi = it2;
1.614 + }
1.615 + _Graph& g;
1.616 + };
1.617 };
1.618
1.619 + /// Skeleton class for graph InEdgeIt and OutEdgeIt
1.620
1.621 - class IterableGraphComponent :
1.622 - virtual public BaseIterableGraphComponent {
1.623 + /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
1.624 + /// base class, the _selector is a additional template parameter. For
1.625 + /// InEdgeIt you should instantiate it with character 'i' and for
1.626 + /// OutEdgeIt with 'o'.
1.627 + /// \todo check the name of the concept GraphIncEdgeIterator
1.628 + template <typename _Graph, char _selector>
1.629 + class GraphIncEdgeIterator : public _Graph::Edge {
1.630 + public:
1.631 + /// Default constructor.
1.632 +
1.633 + /// @warning The default constructor sets the iterator
1.634 + /// to an undefined value.
1.635 + GraphIncEdgeIterator() {}
1.636 + /// Copy constructor.
1.637 +
1.638 + /// Copy constructor.
1.639 + ///
1.640 + GraphIncEdgeIterator(GraphIncEdgeIterator const&) {}
1.641 + /// Sets the iterator to the first edge incoming into or outgoing from the node.
1.642 +
1.643 + /// Sets the iterator to the first edge incoming into or outgoing from the node.
1.644 + ///
1.645 + explicit GraphIncEdgeIterator(const _Graph&, const typename _Graph::Node&) {}
1.646 + /// Invalid constructor \& conversion.
1.647 +
1.648 + /// This constructor initializes the item to be invalid.
1.649 + /// \sa Invalid for more details.
1.650 + GraphIncEdgeIterator(Invalid) {}
1.651 + /// Assign operator for nodes.
1.652 +
1.653 + /// The nodes are assignable.
1.654 + ///
1.655 + GraphIncEdgeIterator& operator=(GraphIncEdgeIterator const&) { return *this; }
1.656 + /// Next edge.
1.657 +
1.658 + /// Assign the iterator to the next node.
1.659 + ///
1.660 + GraphIncEdgeIterator& operator++() { return *this; }
1.661 + // Node operator*() const { return INVALID; }
1.662 + /// Equality operator
1.663 +
1.664 + /// Two iterators are equal if and only if they point to the
1.665 + /// same object or both are invalid.
1.666 + bool operator==(const GraphIncEdgeIterator&) const { return true;}
1.667 + /// Inequality operator
1.668 +
1.669 + /// \sa operator==(Node n)
1.670 + ///
1.671 + bool operator!=(const GraphIncEdgeIterator&) const { return true;}
1.672 +
1.673 + template <typename _GraphIncEdgeIterator>
1.674 + struct Constraints {
1.675 + typedef typename _Graph::Node Node;
1.676 + typedef typename _Graph::Edge Edge;
1.677 + void constraints() {
1.678 + checkConcept<GraphItem<'e'>, _GraphIncEdgeIterator>();
1.679 + _GraphIncEdgeIterator it1(graph, node);
1.680 + /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
1.681 + // _GraphIncEdgeIterator it2(edge);
1.682 + _GraphIncEdgeIterator it2;
1.683 +
1.684 + it2 = ++it1;
1.685 + ++it2 = it1;
1.686 + ++(++it1);
1.687 + Edge e = it1;
1.688 + e = it2;
1.689 + }
1.690 +
1.691 + Edge& edge;
1.692 + Node& node;
1.693 + _Graph& graph;
1.694 + };
1.695 + };
1.696 + /// An empty iterable base graph class.
1.697 +
1.698 + /// This class provides beside the core graph features
1.699 + /// iterator based iterable interface for the graph structure.
1.700 + /// This concept is part of the StaticGraphConcept.
1.701 + class IterableGraphComponent : virtual public BaseGraphComponent {
1.702
1.703 public:
1.704
1.705 @@ -591,84 +588,80 @@
1.706 typedef BaseGraphComponent::Node Node;
1.707 typedef BaseGraphComponent::Edge Edge;
1.708
1.709 - class NodeIt : public Node {
1.710 - public:
1.711 - NodeIt() {}
1.712 - NodeIt(Invalid) {}
1.713 - // explicit NodeIt(Node) {}
1.714 - explicit NodeIt(const Graph&) {}
1.715 + /// This iterator goes through each node.
1.716
1.717 - NodeIt& operator++() { return *this; }
1.718 - // Node operator*() const { return INVALID; }
1.719 + /// This iterator goes through each node.
1.720 + ///
1.721 + typedef GraphIterator<Graph, Node> NodeIt;
1.722 + /// This iterator goes through each node.
1.723
1.724 - bool operator==(const NodeIt&) const { return true;}
1.725 - bool operator!=(const NodeIt&) const { return true;}
1.726 - };
1.727 + /// This iterator goes through each node.
1.728 + ///
1.729 + typedef GraphIterator<Graph, Edge> EdgeIt;
1.730 + /// This iterator goes trough the incoming edges of a node.
1.731
1.732 - class EdgeIt : public Edge {
1.733 - public:
1.734 - EdgeIt() {}
1.735 - EdgeIt(Invalid) {}
1.736 - // explicit EdgeIt(Edge) {}
1.737 - explicit EdgeIt(const Graph&) {}
1.738 + /// This iterator goes trough the \e inccoming edges of a certain node
1.739 + /// of a graph.
1.740 + typedef GraphIncEdgeIterator<Graph, 'i'> InEdgeIt;
1.741 + /// This iterator goes trough the outgoing edges of a node.
1.742
1.743 - EdgeIt& operator++() { return *this; }
1.744 - // Edge operator*() const { return INVALID; }
1.745 + /// This iterator goes trough the \e outgoing edges of a certain node
1.746 + /// of a graph.
1.747 + typedef GraphIncEdgeIterator<Graph, 'o'> OutEdgeIt;
1.748 + };
1.749 +
1.750 + template <typename _Graph>
1.751 + struct Constraints {
1.752 + void constraints() {
1.753 + checkConcept< BaseGraphComponent, _Graph>();
1.754
1.755 - bool operator==(const EdgeIt&) const { return true;}
1.756 - bool operator!=(const EdgeIt&) const { return true;}
1.757 - };
1.758 + checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
1.759 + checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
1.760 + checkConcept<GraphIncEdgeIterator<_Graph, 'i'>, typename _Graph::InEdgeIt >();
1.761 + checkConcept<GraphIncEdgeIterator<_Graph, 'o'>, typename _Graph::OutEdgeIt >();
1.762 + }
1.763 + };
1.764
1.765 - class InEdgeIt : public Edge {
1.766 - public:
1.767 - InEdgeIt() {}
1.768 - InEdgeIt(Invalid) {}
1.769 - // explicit InEdgeIt(Edge) {}
1.770 - explicit InEdgeIt(const Graph&, const Node&) {}
1.771
1.772 - InEdgeIt& operator++() { return *this; }
1.773 - // Edge operator*() const { return INVALID; }
1.774 + template <typename Graph, typename Item, typename _Value>
1.775 + class GraphMap : public ReadWriteMap<Item, _Value> {
1.776 + protected:
1.777 + GraphMap() {}
1.778 + public:
1.779 + explicit GraphMap(const Graph&) {}
1.780 + GraphMap(const Graph&, const _Value&) {}
1.781 + GraphMap(const GraphMap&) {}
1.782 +
1.783 + GraphMap& operator=(const GraphMap&) { return *this;}
1.784
1.785 - bool operator==(const InEdgeIt&) const { return true;}
1.786 - bool operator!=(const InEdgeIt&) const { return true;}
1.787 - };
1.788 + template<typename _Map>
1.789 + struct Constraints {
1.790 + void constraints() {
1.791 + checkConcept<ReadWriteMap<Item, _Value>, _Map >();
1.792 + // Construction with a graph parameter
1.793 + _Map a(g);
1.794 + // Constructor with a graph and a default value parameter
1.795 + _Map a2(g,t);
1.796 + // Copy constructor. Do we need it?
1.797 + _Map b=c;
1.798 + // Copy operator. Do we need it?
1.799 + a=b;
1.800
1.801 - class OutEdgeIt : public Edge {
1.802 - public:
1.803 - OutEdgeIt() {}
1.804 - OutEdgeIt(Invalid) {}
1.805 - // explicit OutEdgeIt(Edge) {}
1.806 - explicit OutEdgeIt(const Graph&, const Node&) {}
1.807 + ignore_unused_variable_warning(a2);
1.808 + }
1.809
1.810 - OutEdgeIt& operator++() { return *this; }
1.811 - // Edge operator*() const { return INVALID; }
1.812 -
1.813 - bool operator==(const OutEdgeIt&) const { return true;}
1.814 - bool operator!=(const OutEdgeIt&) const { return true;}
1.815 + const _Map &c;
1.816 + const Graph &g;
1.817 + const typename GraphMap::Value &t;
1.818 };
1.819
1.820 };
1.821 -
1.822 - template <typename Graph>
1.823 - struct IterableGraphComponentConcept {
1.824 - void constraints() {
1.825 - function_requires< BaseIterableGraphComponentConcept<Graph> >();
1.826
1.827 - typedef typename Graph::Node Node;
1.828 - typedef typename Graph::NodeIt NodeIt;
1.829 - typedef typename Graph::Edge Edge;
1.830 - typedef typename Graph::EdgeIt EdgeIt;
1.831 - typedef typename Graph::InEdgeIt InEdgeIt;
1.832 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.833 + /// An empty mappable base graph class.
1.834
1.835 - function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
1.836 - function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
1.837 - function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
1.838 - function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
1.839 - }
1.840 - };
1.841 -
1.842 -
1.843 + /// This class provides beside the core graph features
1.844 + /// map interface for the graph structure.
1.845 + /// This concept is part of the StaticGraphConcept.
1.846 class MappableGraphComponent : virtual public BaseGraphComponent {
1.847 public:
1.848
1.849 @@ -677,65 +670,78 @@
1.850 typedef BaseGraphComponent::Node Node;
1.851 typedef BaseGraphComponent::Edge Edge;
1.852
1.853 + /// ReadWrite map of the nodes.
1.854 +
1.855 + /// ReadWrite map of the nodes.
1.856 + ///
1.857 template <typename _Value>
1.858 - class NodeMap : public ReferenceMap<Node, _Value> {
1.859 + class NodeMap : public GraphMap<Graph, Node, _Value> {
1.860 + private:
1.861 + NodeMap();
1.862 public:
1.863 - NodeMap(const Graph&) {}
1.864 + // \todo call the right parent class constructor
1.865 + explicit NodeMap(const Graph&) {}
1.866 NodeMap(const Graph&, const _Value&) {}
1.867 NodeMap(const NodeMap&) {}
1.868
1.869 NodeMap& operator=(const NodeMap&) { return *this;}
1.870 -
1.871 +
1.872 };
1.873
1.874 + /// ReadWrite map of the edges.
1.875 +
1.876 + /// ReadWrite map of the edges.
1.877 + ///
1.878 template <typename _Value>
1.879 - class EdgeMap : public ReferenceMap<Edge, _Value> {
1.880 + class EdgeMap : public GraphMap<Graph, Edge, _Value> {
1.881 + private:
1.882 + EdgeMap();
1.883 public:
1.884 - EdgeMap(const Graph&) {}
1.885 + // \todo call the right parent class constructor
1.886 + explicit EdgeMap(const Graph&) {}
1.887 EdgeMap(const Graph&, const _Value&) {}
1.888 EdgeMap(const EdgeMap&) {}
1.889
1.890 EdgeMap& operator=(const EdgeMap&) { return *this;}
1.891 -
1.892 +
1.893 };
1.894
1.895 - };
1.896 + template <typename _Graph>
1.897 + struct Constraints {
1.898
1.899 - template <typename Graph>
1.900 - struct MappableGraphComponentConcept {
1.901 + struct Type {
1.902 + int value;
1.903 + Type() : value(0) {}
1.904 + Type(int _v) : value(_v) {}
1.905 + };
1.906
1.907 - struct Type {
1.908 - int value;
1.909 - Type() : value(0) {}
1.910 - Type(int _v) : value(_v) {}
1.911 + void constraints() {
1.912 + checkConcept<BaseGraphComponent, _Graph>();
1.913 + { // int map test
1.914 + typedef typename _Graph::template NodeMap<int> IntNodeMap;
1.915 + checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, IntNodeMap >();
1.916 + } { // bool map test
1.917 + typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
1.918 + checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>, BoolNodeMap >();
1.919 + } { // Type map test
1.920 + typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
1.921 + checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>, TypeNodeMap >();
1.922 + }
1.923 +
1.924 + { // int map test
1.925 + typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1.926 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, IntEdgeMap >();
1.927 + } { // bool map test
1.928 + typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1.929 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, BoolEdgeMap >();
1.930 + } { // Type map test
1.931 + typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
1.932 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, TypeEdgeMap >();
1.933 + }
1.934 + }
1.935 +
1.936 + _Graph& graph;
1.937 };
1.938 -
1.939 - void constraints() {
1.940 - function_requires< BaseGraphComponentConcept<Graph> >();
1.941 - { // int map test
1.942 - typedef typename Graph::template NodeMap<int> IntNodeMap;
1.943 - function_requires<GraphMapConcept<IntNodeMap,Graph> >();
1.944 - } { // bool map test
1.945 - typedef typename Graph::template NodeMap<bool> BoolNodeMap;
1.946 - function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
1.947 - } { // Type map test
1.948 - typedef typename Graph::template NodeMap<Type> TypeNodeMap;
1.949 - function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
1.950 - }
1.951 -
1.952 - { // int map test
1.953 - typedef typename Graph::template EdgeMap<int> IntEdgeMap;
1.954 - function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
1.955 - } { // bool map test
1.956 - typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
1.957 - function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
1.958 - } { // Type map test
1.959 - typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
1.960 - function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
1.961 - }
1.962 - }
1.963 -
1.964 - Graph& graph;
1.965 };
1.966
1.967
1.968 @@ -755,20 +761,18 @@
1.969 return INVALID;
1.970 }
1.971
1.972 + template <typename _Graph>
1.973 + struct Constraints {
1.974 + void constraints() {
1.975 + checkConcept<BaseGraphComponent, _Graph >();
1.976 + typename _Graph::Node node_a, node_b;
1.977 + node_a = graph.addNode();
1.978 + typename _Graph::Edge edge;
1.979 + edge = graph.addEdge(node_a, node_b);
1.980 + }
1.981 + _Graph& graph;
1.982 + };
1.983 };
1.984 -
1.985 - template <typename Graph>
1.986 - struct ExtendableGraphComponentConcept {
1.987 - void constraints() {
1.988 - function_requires< BaseGraphComponentConcept<Graph> >();
1.989 - typename Graph::Node node_a, node_b;
1.990 - node_a = graph.addNode();
1.991 - typename Graph::Edge edge;
1.992 - edge = graph.addEdge(node_a, node_b);
1.993 - }
1.994 - Graph& graph;
1.995 - };
1.996 -
1.997 class ErasableGraphComponent : virtual public BaseGraphComponent {
1.998 public:
1.999
1.1000 @@ -780,19 +784,18 @@
1.1001 void erase(const Node&) {}
1.1002 void erase(const Edge&) {}
1.1003
1.1004 - };
1.1005 + template <typename _Graph>
1.1006 + struct Constraints {
1.1007 + void constraints() {
1.1008 + checkConcept<BaseGraphComponent, _Graph >();
1.1009 + typename _Graph::Node node;
1.1010 + graph.erase(node);
1.1011 + typename _Graph::Edge edge;
1.1012 + graph.erase(edge);
1.1013 + }
1.1014
1.1015 - template <typename Graph>
1.1016 - struct ErasableGraphComponentConcept {
1.1017 - void constraints() {
1.1018 - function_requires< BaseGraphComponentConcept<Graph> >();
1.1019 - typename Graph::Node node;
1.1020 - graph.erase(node);
1.1021 - typename Graph::Edge edge;
1.1022 - graph.erase(edge);
1.1023 - }
1.1024 -
1.1025 - Graph& graph;
1.1026 + _Graph& graph;
1.1027 + };
1.1028 };
1.1029
1.1030 class ClearableGraphComponent : virtual public BaseGraphComponent {
1.1031 @@ -805,15 +808,15 @@
1.1032
1.1033 void clear() {}
1.1034
1.1035 - };
1.1036
1.1037 - template <typename Graph>
1.1038 - struct ClearableGraphComponentConcept {
1.1039 - void constraints() {
1.1040 - function_requires< BaseGraphComponentConcept<Graph> >();
1.1041 - graph.clear();
1.1042 - }
1.1043 - Graph& graph;
1.1044 + template <typename _Graph>
1.1045 + struct ClearableGraphComponentConcept {
1.1046 + void constraints() {
1.1047 + checkConcept< BaseGraphComponent, _Graph >();
1.1048 + graph.clear();
1.1049 + }
1.1050 + _Graph& graph;
1.1051 + };
1.1052 };
1.1053
1.1054 }