1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concept/graph_components.h Tue Jul 11 15:42:15 2006 +0000
1.3 @@ -0,0 +1,1720 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\ingroup graph_concepts
1.23 +///\file
1.24 +///\brief The concept of the graph components.
1.25 +
1.26 +
1.27 +#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
1.28 +#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
1.29 +
1.30 +#include <lemon/bits/invalid.h>
1.31 +#include <lemon/concept/maps.h>
1.32 +
1.33 +#include <lemon/bits/alteration_notifier.h>
1.34 +
1.35 +namespace lemon {
1.36 + namespace concept {
1.37 +
1.38 + /// \brief Skeleton class for graph Node and Edge types
1.39 + ///
1.40 + /// This class describes the interface of Node and Edge (and UEdge
1.41 + /// in undirected graphs) subtypes of graph types.
1.42 + ///
1.43 + /// \note This class is a template class so that we can use it to
1.44 + /// create graph skeleton classes. The reason for this is than Node
1.45 + /// and Edge types should \em not derive from the same base class.
1.46 + /// For Node you should instantiate it with character 'n' and for Edge
1.47 + /// with 'e'.
1.48 +
1.49 +#ifndef DOXYGEN
1.50 + template <char _selector = '0'>
1.51 +#endif
1.52 + class GraphItem {
1.53 + public:
1.54 + /// \brief Default constructor.
1.55 + ///
1.56 + /// \warning The default constructor is not required to set
1.57 + /// the item to some well-defined value. So you should consider it
1.58 + /// as uninitialized.
1.59 + GraphItem() {}
1.60 + /// \brief Copy constructor.
1.61 + ///
1.62 + /// Copy constructor.
1.63 + ///
1.64 + GraphItem(const GraphItem &) {}
1.65 + /// \brief Invalid constructor \& conversion.
1.66 + ///
1.67 + /// This constructor initializes the item to be invalid.
1.68 + /// \sa Invalid for more details.
1.69 + GraphItem(Invalid) {}
1.70 + /// \brief Assign operator for nodes.
1.71 + ///
1.72 + /// The nodes are assignable.
1.73 + ///
1.74 + GraphItem& operator=(GraphItem const&) { return *this; }
1.75 + /// \brief Equality operator.
1.76 + ///
1.77 + /// Two iterators are equal if and only if they represents the
1.78 + /// same node in the graph or both are invalid.
1.79 + bool operator==(GraphItem) const { return false; }
1.80 + /// \brief Inequality operator.
1.81 + ///
1.82 + /// \sa operator==(const Node& n)
1.83 + ///
1.84 + bool operator!=(GraphItem) const { return false; }
1.85 +
1.86 + /// \brief Artificial ordering operator.
1.87 + ///
1.88 + /// To allow the use of graph descriptors as key type in std::map or
1.89 + /// similar associative container we require this.
1.90 + ///
1.91 + /// \note This operator only have to define some strict ordering of
1.92 + /// the items; this order has nothing to do with the iteration
1.93 + /// ordering of the items.
1.94 + bool operator<(GraphItem) const { return false; }
1.95 +
1.96 + template<typename _GraphItem>
1.97 + struct Constraints {
1.98 + void constraints() {
1.99 + _GraphItem i1;
1.100 + _GraphItem i2 = i1;
1.101 + _GraphItem i3 = INVALID;
1.102 +
1.103 + i1 = i2 = i3;
1.104 +
1.105 + bool b;
1.106 + // b = (ia == ib) && (ia != ib) && (ia < ib);
1.107 + b = (ia == ib) && (ia != ib);
1.108 + b = (ia == INVALID) && (ib != INVALID);
1.109 + b = (ia < ib);
1.110 + }
1.111 +
1.112 + const _GraphItem &ia;
1.113 + const _GraphItem &ib;
1.114 + };
1.115 + };
1.116 +
1.117 + /// \brief An empty base graph class.
1.118 + ///
1.119 + /// This class provides the minimal set of features needed for a graph
1.120 + /// structure. All graph concepts have to be conform to this base
1.121 + /// graph. It just provides types for nodes and edges and functions to
1.122 + /// get the source and the target of the edges.
1.123 + class BaseGraphComponent {
1.124 + public:
1.125 +
1.126 + typedef BaseGraphComponent Graph;
1.127 +
1.128 + /// \brief Node class of the graph.
1.129 + ///
1.130 + /// This class represents the Nodes of the graph.
1.131 + ///
1.132 + typedef GraphItem<'n'> Node;
1.133 +
1.134 + /// \brief Edge class of the graph.
1.135 + ///
1.136 + /// This class represents the Edges of the graph.
1.137 + ///
1.138 + typedef GraphItem<'e'> Edge;
1.139 +
1.140 + /// \brief Gives back the target node of an edge.
1.141 + ///
1.142 + /// Gives back the target node of an edge.
1.143 + ///
1.144 + Node target(const Edge&) const { return INVALID;}
1.145 +
1.146 + /// \brief Gives back the source node of an edge.
1.147 + ///
1.148 + /// Gives back the source node of an edge.
1.149 + ///
1.150 + Node source(const Edge&) const { return INVALID;}
1.151 +
1.152 + /// \brief Gives back the opposite node on the given edge.
1.153 + ///
1.154 + /// Gives back the opposite node on the given edge.
1.155 + Node oppositeNode(const Node&, const Edge&) const {
1.156 + return INVALID;
1.157 + }
1.158 +
1.159 + template <typename _Graph>
1.160 + struct Constraints {
1.161 + typedef typename _Graph::Node Node;
1.162 + typedef typename _Graph::Edge Edge;
1.163 +
1.164 + void constraints() {
1.165 + checkConcept<GraphItem<'n'>, Node>();
1.166 + checkConcept<GraphItem<'e'>, Edge>();
1.167 + {
1.168 + Node n;
1.169 + Edge e(INVALID);
1.170 + n = graph.source(e);
1.171 + n = graph.target(e);
1.172 + n = graph.oppositeNode(n, e);
1.173 + }
1.174 + }
1.175 +
1.176 + const _Graph& graph;
1.177 + };
1.178 + };
1.179 +
1.180 + /// \brief An empty base undirected graph class.
1.181 + ///
1.182 + /// This class provides the minimal set of features needed for an
1.183 + /// undirected graph structure. All undirected graph concepts have
1.184 + /// to be conform to this base graph. It just provides types for
1.185 + /// nodes, edges and undirected edges and functions to get the
1.186 + /// source and the target of the edges and undirected edges,
1.187 + /// conversion from edges to undirected edges and function to get
1.188 + /// both direction of the undirected edges.
1.189 + class BaseUGraphComponent : public BaseGraphComponent {
1.190 + public:
1.191 + typedef BaseGraphComponent::Node Node;
1.192 + typedef BaseGraphComponent::Edge Edge;
1.193 + /// \brief Undirected edge class of the graph.
1.194 + ///
1.195 + /// This class represents the undirected edges of the graph.
1.196 + /// The undirected graphs can be used as a directed graph which
1.197 + /// for each edge contains the opposite edge too so the graph is
1.198 + /// bidirected. The undirected edge represents two opposite
1.199 + /// directed edges.
1.200 + class UEdge : public GraphItem<'u'> {
1.201 + public:
1.202 + typedef GraphItem<'u'> Parent;
1.203 + /// \brief Default constructor.
1.204 + ///
1.205 + /// \warning The default constructor is not required to set
1.206 + /// the item to some well-defined value. So you should consider it
1.207 + /// as uninitialized.
1.208 + UEdge() {}
1.209 + /// \brief Copy constructor.
1.210 + ///
1.211 + /// Copy constructor.
1.212 + ///
1.213 + UEdge(const UEdge &) : Parent() {}
1.214 + /// \brief Invalid constructor \& conversion.
1.215 + ///
1.216 + /// This constructor initializes the item to be invalid.
1.217 + /// \sa Invalid for more details.
1.218 + UEdge(Invalid) {}
1.219 + /// \brief Converter from edge to undirected edge.
1.220 + ///
1.221 + /// Besides the core graph item functionality each edge should
1.222 + /// be convertible to the represented undirected edge.
1.223 + UEdge(const Edge&) {}
1.224 + };
1.225 +
1.226 + /// \brief Returns the direction of the edge.
1.227 + ///
1.228 + /// Returns the direction of the edge. Each edge represents an
1.229 + /// undirected edge with a direction. It gives back the
1.230 + /// direction.
1.231 + bool direction(const Edge&) const { return true; }
1.232 +
1.233 + /// \brief Returns the directed edge.
1.234 + ///
1.235 + /// Returns the directed edge from its direction and the
1.236 + /// represented undirected edge.
1.237 + Edge direct(const UEdge&, bool) const { return INVALID;}
1.238 +
1.239 + /// \brief Returns the directed edge.
1.240 + ///
1.241 + /// Returns the directed edge from its source and the
1.242 + /// represented undirected edge.
1.243 + Edge direct(const UEdge&, const Node&) const { return INVALID;}
1.244 +
1.245 + /// \brief Returns the opposite edge.
1.246 + ///
1.247 + /// Returns the opposite edge. It is the edge representing the
1.248 + /// same undirected edge and has opposite direction.
1.249 + Edge oppositeEdge(const Edge&) const { return INVALID;}
1.250 +
1.251 + /// \brief Gives back the target node of an undirected edge.
1.252 + ///
1.253 + /// Gives back the target node of an undirected edge. The name
1.254 + /// target is a little confusing because the undirected edge
1.255 + /// does not have target but it just means that one of the end
1.256 + /// node.
1.257 + Node target(const UEdge&) const { return INVALID;}
1.258 +
1.259 + /// \brief Gives back the source node of an undirected edge.
1.260 + ///
1.261 + /// Gives back the source node of an undirected edge. The name
1.262 + /// source is a little confusing because the undirected edge
1.263 + /// does not have source but it just means that one of the end
1.264 + /// node.
1.265 + Node source(const UEdge&) const { return INVALID;}
1.266 +
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 + typedef typename _Graph::UEdge UEdge;
1.272 +
1.273 + void constraints() {
1.274 + checkConcept<BaseGraphComponent, _Graph>();
1.275 + checkConcept<GraphItem<'u'>, UEdge>();
1.276 + {
1.277 + Node n;
1.278 + UEdge ue(INVALID);
1.279 + Edge e;
1.280 + n = graph.source(ue);
1.281 + n = graph.target(ue);
1.282 + e = graph.direct(ue, true);
1.283 + e = graph.direct(ue, n);
1.284 + e = graph.oppositeEdge(e);
1.285 + ue = e;
1.286 + bool d = graph.direction(e);
1.287 + ignore_unused_variable_warning(d);
1.288 + }
1.289 + }
1.290 +
1.291 + const _Graph& graph;
1.292 + };
1.293 +
1.294 + };
1.295 +
1.296 + /// \brief An empty iterable base graph class.
1.297 + ///
1.298 + /// This class provides beside the core graph features
1.299 + /// core iterable interface for the graph structure.
1.300 + /// Most of the base graphs should be conform to this concept.
1.301 + template <typename _Base = BaseGraphComponent>
1.302 + class BaseIterableGraphComponent : public _Base {
1.303 + public:
1.304 +
1.305 + typedef _Base Base;
1.306 + typedef typename Base::Node Node;
1.307 + typedef typename Base::Edge Edge;
1.308 +
1.309 + /// \brief Gives back the first node in the iterating order.
1.310 + ///
1.311 + /// Gives back the first node in the iterating order.
1.312 + ///
1.313 + void first(Node&) const {}
1.314 +
1.315 + /// \brief Gives back the next node in the iterating order.
1.316 + ///
1.317 + /// Gives back the next node in the iterating order.
1.318 + ///
1.319 + void next(Node&) const {}
1.320 +
1.321 + /// \brief Gives back the first edge in the iterating order.
1.322 + ///
1.323 + /// Gives back the first edge in the iterating order.
1.324 + ///
1.325 + void first(Edge&) const {}
1.326 +
1.327 + /// \brief Gives back the next edge in the iterating order.
1.328 + ///
1.329 + /// Gives back the next edge in the iterating order.
1.330 + ///
1.331 + void next(Edge&) const {}
1.332 +
1.333 +
1.334 + /// \brief Gives back the first of the edges point to the given
1.335 + /// node.
1.336 + ///
1.337 + /// Gives back the first of the edges point to the given node.
1.338 + ///
1.339 + void firstIn(Edge&, const Node&) const {}
1.340 +
1.341 + /// \brief Gives back the next of the edges points to the given
1.342 + /// node.
1.343 + ///
1.344 + /// Gives back the next of the edges points to the given node.
1.345 + ///
1.346 + void nextIn(Edge&) const {}
1.347 +
1.348 + /// \brief Gives back the first of the edges start from the
1.349 + /// given node.
1.350 + ///
1.351 + /// Gives back the first of the edges start from the given node.
1.352 + ///
1.353 + void firstOut(Edge&, const Node&) const {}
1.354 +
1.355 + /// \brief Gives back the next of the edges start from the given
1.356 + /// node.
1.357 + ///
1.358 + /// Gives back the next of the edges start from the given node.
1.359 + ///
1.360 + void nextOut(Edge&) const {}
1.361 +
1.362 +
1.363 + template <typename _Graph>
1.364 + struct Constraints {
1.365 +
1.366 + void constraints() {
1.367 + checkConcept< BaseGraphComponent, _Graph >();
1.368 + typename _Graph::Node node;
1.369 + typename _Graph::Edge edge;
1.370 + {
1.371 + graph.first(node);
1.372 + graph.next(node);
1.373 + }
1.374 + {
1.375 + graph.first(edge);
1.376 + graph.next(edge);
1.377 + }
1.378 + {
1.379 + graph.firstIn(edge, node);
1.380 + graph.nextIn(edge);
1.381 + }
1.382 + {
1.383 + graph.firstOut(edge, node);
1.384 + graph.nextOut(edge);
1.385 + }
1.386 + }
1.387 +
1.388 + const _Graph& graph;
1.389 + };
1.390 + };
1.391 +
1.392 + /// \brief An empty iterable base undirected graph class.
1.393 + ///
1.394 + /// This class provides beside the core undirceted graph features
1.395 + /// core iterable interface for the undirected graph structure.
1.396 + /// Most of the base undirected graphs should be conform to this
1.397 + /// concept.
1.398 + template <typename _Base = BaseUGraphComponent>
1.399 + class BaseIterableUGraphComponent
1.400 + : public BaseIterableGraphComponent<_Base> {
1.401 + public:
1.402 +
1.403 + typedef _Base Base;
1.404 + typedef typename Base::UEdge UEdge;
1.405 + typedef typename Base::Node Node;
1.406 +
1.407 + using BaseIterableGraphComponent<_Base>::first;
1.408 + using BaseIterableGraphComponent<_Base>::next;
1.409 +
1.410 + /// \brief Gives back the first undirected edge in the iterating
1.411 + /// order.
1.412 + ///
1.413 + /// Gives back the first undirected edge in the iterating order.
1.414 + ///
1.415 + void first(UEdge&) const {}
1.416 +
1.417 + /// \brief Gives back the next undirected edge in the iterating
1.418 + /// order.
1.419 + ///
1.420 + /// Gives back the next undirected edge in the iterating order.
1.421 + ///
1.422 + void next(UEdge&) const {}
1.423 +
1.424 +
1.425 + /// \brief Gives back the first of the undirected edges from the
1.426 + /// given node.
1.427 + ///
1.428 + /// Gives back the first of the undirected edges from the given
1.429 + /// node. The bool parameter gives back that direction which
1.430 + /// gives a good direction of the uedge so the source of the
1.431 + /// directed edge is the given node.
1.432 + void firstInc(UEdge&, bool&, const Node&) const {}
1.433 +
1.434 + /// \brief Gives back the next of the undirected edges from the
1.435 + /// given node.
1.436 + ///
1.437 + /// Gives back the next of the undirected edges from the given
1.438 + /// node. The bool parameter should be used as the \c firstInc()
1.439 + /// use it.
1.440 + void nextInc(UEdge&, bool&) const {}
1.441 +
1.442 + template <typename _Graph>
1.443 + struct Constraints {
1.444 +
1.445 + void constraints() {
1.446 + checkConcept<Base, _Graph >();
1.447 + checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
1.448 + typename _Graph::Node node;
1.449 + typename _Graph::UEdge uedge;
1.450 + bool dir;
1.451 + {
1.452 + graph.first(uedge);
1.453 + graph.next(uedge);
1.454 + }
1.455 + {
1.456 + graph.firstInc(uedge, dir, node);
1.457 + graph.nextInc(uedge, dir);
1.458 + }
1.459 + }
1.460 +
1.461 + const _Graph& graph;
1.462 + };
1.463 + };
1.464 +
1.465 + /// \brief An empty idable base graph class.
1.466 + ///
1.467 + /// This class provides beside the core graph features
1.468 + /// core id functions for the graph structure.
1.469 + /// The most of the base graphs should be conform to this concept.
1.470 + /// The id's are unique and immutable.
1.471 + template <typename _Base = BaseGraphComponent>
1.472 + class IDableGraphComponent : public _Base {
1.473 + public:
1.474 +
1.475 + typedef _Base Base;
1.476 + typedef typename Base::Node Node;
1.477 + typedef typename Base::Edge Edge;
1.478 +
1.479 + /// \brief Gives back an unique integer id for the Node.
1.480 + ///
1.481 + /// Gives back an unique integer id for the Node.
1.482 + ///
1.483 + int id(const Node&) const { return -1;}
1.484 +
1.485 + /// \brief Gives back the node by the unique id.
1.486 + ///
1.487 + /// Gives back the node by the unique id.
1.488 + /// If the graph does not contain node with the given id
1.489 + /// then the result of the function is undetermined.
1.490 + Node nodeFromId(int) const { return INVALID;}
1.491 +
1.492 + /// \brief Gives back an unique integer id for the Edge.
1.493 + ///
1.494 + /// Gives back an unique integer id for the Edge.
1.495 + ///
1.496 + int id(const Edge&) const { return -1;}
1.497 +
1.498 + /// \brief Gives back the edge by the unique id.
1.499 + ///
1.500 + /// Gives back the edge by the unique id.
1.501 + /// If the graph does not contain edge with the given id
1.502 + /// then the result of the function is undetermined.
1.503 + Edge edgeFromId(int) const { return INVALID;}
1.504 +
1.505 + /// \brief Gives back an integer greater or equal to the maximum
1.506 + /// Node id.
1.507 + ///
1.508 + /// Gives back an integer greater or equal to the maximum Node
1.509 + /// id.
1.510 + int maxNodeId() const { return -1;}
1.511 +
1.512 + /// \brief Gives back an integer greater or equal to the maximum
1.513 + /// Edge id.
1.514 + ///
1.515 + /// Gives back an integer greater or equal to the maximum Edge
1.516 + /// id.
1.517 + int maxEdgeId() const { return -1;}
1.518 +
1.519 + template <typename _Graph>
1.520 + struct Constraints {
1.521 +
1.522 + void constraints() {
1.523 + checkConcept< BaseGraphComponent, _Graph >();
1.524 + typename _Graph::Node node;
1.525 + int nid = graph.id(node);
1.526 + nid = graph.id(node);
1.527 + node = graph.nodeFromId(nid);
1.528 + typename _Graph::Edge edge;
1.529 + int eid = graph.id(edge);
1.530 + eid = graph.id(edge);
1.531 + edge = graph.edgeFromId(eid);
1.532 +
1.533 + nid = graph.maxNodeId();
1.534 + ignore_unused_variable_warning(nid);
1.535 + eid = graph.maxEdgeId();
1.536 + ignore_unused_variable_warning(eid);
1.537 + }
1.538 +
1.539 + const _Graph& graph;
1.540 + };
1.541 + };
1.542 +
1.543 + /// \brief An empty idable base undirected graph class.
1.544 + ///
1.545 + /// This class provides beside the core undirected graph features
1.546 + /// core id functions for the undirected graph structure. The
1.547 + /// most of the base undirected graphs should be conform to this
1.548 + /// concept. The id's are unique and immutable.
1.549 + template <typename _Base = BaseUGraphComponent>
1.550 + class IDableUGraphComponent : public IDableGraphComponent<_Base> {
1.551 + public:
1.552 +
1.553 + typedef _Base Base;
1.554 + typedef typename Base::UEdge UEdge;
1.555 +
1.556 + using IDableGraphComponent<_Base>::id;
1.557 +
1.558 + /// \brief Gives back an unique integer id for the UEdge.
1.559 + ///
1.560 + /// Gives back an unique integer id for the UEdge.
1.561 + ///
1.562 + int id(const UEdge&) const { return -1;}
1.563 +
1.564 + /// \brief Gives back the undirected edge by the unique id.
1.565 + ///
1.566 + /// Gives back the undirected edge by the unique id. If the
1.567 + /// graph does not contain edge with the given id then the
1.568 + /// result of the function is undetermined.
1.569 + UEdge uEdgeFromId(int) const { return INVALID;}
1.570 +
1.571 + /// \brief Gives back an integer greater or equal to the maximum
1.572 + /// UEdge id.
1.573 + ///
1.574 + /// Gives back an integer greater or equal to the maximum UEdge
1.575 + /// id.
1.576 + int maxUEdgeId() const { return -1;}
1.577 +
1.578 + template <typename _Graph>
1.579 + struct Constraints {
1.580 +
1.581 + void constraints() {
1.582 + checkConcept<Base, _Graph >();
1.583 + checkConcept<IDableGraphComponent<Base>, _Graph >();
1.584 + typename _Graph::UEdge uedge;
1.585 + int ueid = graph.id(uedge);
1.586 + ueid = graph.id(uedge);
1.587 + uedge = graph.uEdgeFromId(ueid);
1.588 + ueid = graph.maxUEdgeId();
1.589 + ignore_unused_variable_warning(ueid);
1.590 + }
1.591 +
1.592 + const _Graph& graph;
1.593 + };
1.594 + };
1.595 +
1.596 + /// \brief An empty extendable base graph class.
1.597 + ///
1.598 + /// This class provides beside the core graph features
1.599 + /// core graph extend interface for the graph structure.
1.600 + /// The most of the base graphs should be conform to this concept.
1.601 + template <typename _Base = BaseGraphComponent>
1.602 + class BaseExtendableGraphComponent : public _Base {
1.603 + public:
1.604 +
1.605 + typedef typename _Base::Node Node;
1.606 + typedef typename _Base::Edge Edge;
1.607 +
1.608 + /// \brief Adds a new node to the graph.
1.609 + ///
1.610 + /// Adds a new node to the graph.
1.611 + ///
1.612 + Node addNode() {
1.613 + return INVALID;
1.614 + }
1.615 +
1.616 + /// \brief Adds a new edge connects the given two nodes.
1.617 + ///
1.618 + /// Adds a new edge connects the the given two nodes.
1.619 + Edge addEdge(const Node&, const Node&) {
1.620 + return INVALID;
1.621 + }
1.622 +
1.623 + template <typename _Graph>
1.624 + struct Constraints {
1.625 + void constraints() {
1.626 + typename _Graph::Node node_a, node_b;
1.627 + node_a = graph.addNode();
1.628 + node_b = graph.addNode();
1.629 + typename _Graph::Edge edge;
1.630 + edge = graph.addEdge(node_a, node_b);
1.631 + }
1.632 +
1.633 + _Graph& graph;
1.634 + };
1.635 + };
1.636 +
1.637 + /// \brief An empty extendable base undirected graph class.
1.638 + ///
1.639 + /// This class provides beside the core undirected graph features
1.640 + /// core undircted graph extend interface for the graph structure.
1.641 + /// The most of the base graphs should be conform to this concept.
1.642 + template <typename _Base = BaseUGraphComponent>
1.643 + class BaseExtendableUGraphComponent : public _Base {
1.644 + public:
1.645 +
1.646 + typedef typename _Base::Node Node;
1.647 + typedef typename _Base::UEdge UEdge;
1.648 +
1.649 + /// \brief Adds a new node to the graph.
1.650 + ///
1.651 + /// Adds a new node to the graph.
1.652 + ///
1.653 + Node addNode() {
1.654 + return INVALID;
1.655 + }
1.656 +
1.657 + /// \brief Adds a new edge connects the given two nodes.
1.658 + ///
1.659 + /// Adds a new edge connects the the given two nodes.
1.660 + UEdge addEdge(const Node&, const Node&) {
1.661 + return INVALID;
1.662 + }
1.663 +
1.664 + template <typename _Graph>
1.665 + struct Constraints {
1.666 + void constraints() {
1.667 + typename _Graph::Node node_a, node_b;
1.668 + node_a = graph.addNode();
1.669 + node_b = graph.addNode();
1.670 + typename _Graph::UEdge uedge;
1.671 + uedge = graph.addUEdge(node_a, node_b);
1.672 + }
1.673 +
1.674 + _Graph& graph;
1.675 + };
1.676 + };
1.677 +
1.678 + /// \brief An empty erasable base graph class.
1.679 + ///
1.680 + /// This class provides beside the core graph features
1.681 + /// core erase functions for the graph structure.
1.682 + /// The most of the base graphs should be conform to this concept.
1.683 + template <typename _Base = BaseGraphComponent>
1.684 + class BaseErasableGraphComponent : public _Base {
1.685 + public:
1.686 +
1.687 + typedef _Base Base;
1.688 + typedef typename Base::Node Node;
1.689 + typedef typename Base::Edge Edge;
1.690 +
1.691 + /// \brief Erase a node from the graph.
1.692 + ///
1.693 + /// Erase a node from the graph. This function should not
1.694 + /// erase edges connecting to the Node.
1.695 + void erase(const Node&) {}
1.696 +
1.697 + /// \brief Erase an edge from the graph.
1.698 + ///
1.699 + /// Erase an edge from the graph.
1.700 + ///
1.701 + void erase(const Edge&) {}
1.702 +
1.703 + template <typename _Graph>
1.704 + struct Constraints {
1.705 + void constraints() {
1.706 + typename _Graph::Node node;
1.707 + graph.erase(node);
1.708 + typename _Graph::Edge edge;
1.709 + graph.erase(edge);
1.710 + }
1.711 +
1.712 + _Graph& graph;
1.713 + };
1.714 + };
1.715 +
1.716 + /// \brief An empty erasable base undirected graph class.
1.717 + ///
1.718 + /// This class provides beside the core undirected graph features
1.719 + /// core erase functions for the undirceted graph structure.
1.720 + template <typename _Base = BaseUGraphComponent>
1.721 + class BaseErasableUGraphComponent : public _Base {
1.722 + public:
1.723 +
1.724 + typedef _Base Base;
1.725 + typedef typename Base::Node Node;
1.726 + typedef typename Base::UEdge UEdge;
1.727 +
1.728 + /// \brief Erase a node from the graph.
1.729 + ///
1.730 + /// Erase a node from the graph. This function should not
1.731 + /// erase edges connecting to the Node.
1.732 + void erase(const Node&) {}
1.733 +
1.734 + /// \brief Erase an edge from the graph.
1.735 + ///
1.736 + /// Erase an edge from the graph.
1.737 + ///
1.738 + void erase(const UEdge&) {}
1.739 +
1.740 + template <typename _Graph>
1.741 + struct Constraints {
1.742 + void constraints() {
1.743 + typename _Graph::Node node;
1.744 + graph.erase(node);
1.745 + typename _Graph::Edge edge;
1.746 + graph.erase(edge);
1.747 + }
1.748 +
1.749 + _Graph& graph;
1.750 + };
1.751 + };
1.752 +
1.753 + /// \brief An empty clearable base graph class.
1.754 + ///
1.755 + /// This class provides beside the core graph features
1.756 + /// core clear functions for the graph structure.
1.757 + /// The most of the base graphs should be conform to this concept.
1.758 + template <typename _Base = BaseGraphComponent>
1.759 + class BaseClearableGraphComponent : public _Base {
1.760 + public:
1.761 +
1.762 + /// \brief Erase all the nodes and edges from the graph.
1.763 + ///
1.764 + /// Erase all the nodes and edges from the graph.
1.765 + ///
1.766 + void clear() {}
1.767 +
1.768 + template <typename _Graph>
1.769 + struct Constraints {
1.770 + void constraints() {
1.771 + graph.clear();
1.772 + }
1.773 +
1.774 + _Graph graph;
1.775 + };
1.776 + };
1.777 +
1.778 + /// \brief An empty clearable base undirected graph class.
1.779 + ///
1.780 + /// This class provides beside the core undirected graph features
1.781 + /// core clear functions for the undirected graph structure.
1.782 + /// The most of the base graphs should be conform to this concept.
1.783 + template <typename _Base = BaseUGraphComponent>
1.784 + class BaseClearableUGraphComponent : public _Base {
1.785 + public:
1.786 +
1.787 + /// \brief Erase all the nodes and undirected edges from the graph.
1.788 + ///
1.789 + /// Erase all the nodes and undirected edges from the graph.
1.790 + ///
1.791 + void clear() {}
1.792 +
1.793 + template <typename _Graph>
1.794 + struct Constraints {
1.795 + void constraints() {
1.796 + graph.clear();
1.797 + }
1.798 +
1.799 + _Graph graph;
1.800 + };
1.801 + };
1.802 +
1.803 +
1.804 + /// \brief Skeleton class for graph NodeIt and EdgeIt
1.805 + ///
1.806 + /// Skeleton class for graph NodeIt and EdgeIt.
1.807 + ///
1.808 + template <typename _Graph, typename _Item>
1.809 + class GraphItemIt : public _Item {
1.810 + public:
1.811 + /// \brief Default constructor.
1.812 + ///
1.813 + /// @warning The default constructor sets the iterator
1.814 + /// to an undefined value.
1.815 + GraphItemIt() {}
1.816 + /// \brief Copy constructor.
1.817 + ///
1.818 + /// Copy constructor.
1.819 + ///
1.820 + GraphItemIt(const GraphItemIt& ) {}
1.821 + /// \brief Sets the iterator to the first item.
1.822 + ///
1.823 + /// Sets the iterator to the first item of \c the graph.
1.824 + ///
1.825 + explicit GraphItemIt(const _Graph&) {}
1.826 + /// \brief Invalid constructor \& conversion.
1.827 + ///
1.828 + /// This constructor initializes the item to be invalid.
1.829 + /// \sa Invalid for more details.
1.830 + GraphItemIt(Invalid) {}
1.831 + /// \brief Assign operator for items.
1.832 + ///
1.833 + /// The items are assignable.
1.834 + ///
1.835 + GraphItemIt& operator=(const GraphItemIt&) { return *this; }
1.836 + /// \brief Next item.
1.837 + ///
1.838 + /// Assign the iterator to the next item.
1.839 + ///
1.840 + GraphItemIt& operator++() { return *this; }
1.841 + /// \brief Equality operator
1.842 + ///
1.843 + /// Two iterators are equal if and only if they point to the
1.844 + /// same object or both are invalid.
1.845 + bool operator==(const GraphItemIt&) const { return true;}
1.846 + /// \brief Inequality operator
1.847 + ///
1.848 + /// \sa operator==(Node n)
1.849 + ///
1.850 + bool operator!=(const GraphItemIt&) const { return true;}
1.851 +
1.852 + template<typename _GraphItemIt>
1.853 + struct Constraints {
1.854 + void constraints() {
1.855 + _GraphItemIt it1(g);
1.856 + _GraphItemIt it2;
1.857 +
1.858 + it2 = ++it1;
1.859 + ++it2 = it1;
1.860 + ++(++it1);
1.861 +
1.862 + _Item bi = it1;
1.863 + bi = it2;
1.864 + }
1.865 + _Graph& g;
1.866 + };
1.867 + };
1.868 +
1.869 + /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt
1.870 + ///
1.871 + /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
1.872 + /// base class, the _selector is a additional template parameter. For
1.873 + /// InEdgeIt you should instantiate it with character 'i' and for
1.874 + /// OutEdgeIt with 'o'.
1.875 + template <typename _Graph,
1.876 + typename _Item = typename _Graph::Edge,
1.877 + typename _Base = typename _Graph::Node,
1.878 + char _selector = '0'>
1.879 + class GraphIncIt : public _Item {
1.880 + public:
1.881 + /// \brief Default constructor.
1.882 + ///
1.883 + /// @warning The default constructor sets the iterator
1.884 + /// to an undefined value.
1.885 + GraphIncIt() {}
1.886 + /// \brief Copy constructor.
1.887 + ///
1.888 + /// Copy constructor.
1.889 + ///
1.890 + GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
1.891 + /// \brief Sets the iterator to the first edge incoming into or outgoing
1.892 + /// from the node.
1.893 + ///
1.894 + /// Sets the iterator to the first edge incoming into or outgoing
1.895 + /// from the node.
1.896 + ///
1.897 + explicit GraphIncIt(const _Graph&, const _Base&) {}
1.898 + /// \brief Invalid constructor \& conversion.
1.899 + ///
1.900 + /// This constructor initializes the item to be invalid.
1.901 + /// \sa Invalid for more details.
1.902 + GraphIncIt(Invalid) {}
1.903 + /// \brief Assign operator for iterators.
1.904 + ///
1.905 + /// The iterators are assignable.
1.906 + ///
1.907 + GraphIncIt& operator=(GraphIncIt const&) { return *this; }
1.908 + /// \brief Next item.
1.909 + ///
1.910 + /// Assign the iterator to the next item.
1.911 + ///
1.912 + GraphIncIt& operator++() { return *this; }
1.913 +
1.914 + /// \brief Equality operator
1.915 + ///
1.916 + /// Two iterators are equal if and only if they point to the
1.917 + /// same object or both are invalid.
1.918 + bool operator==(const GraphIncIt&) const { return true;}
1.919 +
1.920 + /// \brief Inequality operator
1.921 + ///
1.922 + /// \sa operator==(Node n)
1.923 + ///
1.924 + bool operator!=(const GraphIncIt&) const { return true;}
1.925 +
1.926 + template <typename _GraphIncIt>
1.927 + struct Constraints {
1.928 + void constraints() {
1.929 + checkConcept<GraphItem<_selector>, _GraphIncIt>();
1.930 + _GraphIncIt it1(graph, node);
1.931 + _GraphIncIt it2;
1.932 +
1.933 + it2 = ++it1;
1.934 + ++it2 = it1;
1.935 + ++(++it1);
1.936 + _Item e = it1;
1.937 + e = it2;
1.938 +
1.939 + }
1.940 +
1.941 + _Item edge;
1.942 + _Base node;
1.943 + _Graph graph;
1.944 + _GraphIncIt it;
1.945 + };
1.946 + };
1.947 +
1.948 +
1.949 + /// \brief An empty iterable graph class.
1.950 + ///
1.951 + /// This class provides beside the core graph features
1.952 + /// iterator based iterable interface for the graph structure.
1.953 + /// This concept is part of the GraphConcept.
1.954 + template <typename _Base = BaseGraphComponent>
1.955 + class IterableGraphComponent : public _Base {
1.956 +
1.957 + public:
1.958 +
1.959 + typedef _Base Base;
1.960 + typedef typename Base::Node Node;
1.961 + typedef typename Base::Edge Edge;
1.962 +
1.963 + typedef IterableGraphComponent Graph;
1.964 +
1.965 +
1.966 + /// \brief This iterator goes through each node.
1.967 + ///
1.968 + /// This iterator goes through each node.
1.969 + ///
1.970 + typedef GraphItemIt<Graph, Node> NodeIt;
1.971 +
1.972 + /// \brief This iterator goes through each node.
1.973 + ///
1.974 + /// This iterator goes through each node.
1.975 + ///
1.976 + typedef GraphItemIt<Graph, Edge> EdgeIt;
1.977 +
1.978 + /// \brief This iterator goes trough the incoming edges of a node.
1.979 + ///
1.980 + /// This iterator goes trough the \e inccoming edges of a certain node
1.981 + /// of a graph.
1.982 + typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt;
1.983 +
1.984 + /// \brief This iterator goes trough the outgoing edges of a node.
1.985 + ///
1.986 + /// This iterator goes trough the \e outgoing edges of a certain node
1.987 + /// of a graph.
1.988 + typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt;
1.989 +
1.990 + /// \brief The base node of the iterator.
1.991 + ///
1.992 + /// Gives back the base node of the iterator.
1.993 + /// It is always the target of the pointed edge.
1.994 + Node baseNode(const InEdgeIt&) const { return INVALID; }
1.995 +
1.996 + /// \brief The running node of the iterator.
1.997 + ///
1.998 + /// Gives back the running node of the iterator.
1.999 + /// It is always the source of the pointed edge.
1.1000 + Node runningNode(const InEdgeIt&) const { return INVALID; }
1.1001 +
1.1002 + /// \brief The base node of the iterator.
1.1003 + ///
1.1004 + /// Gives back the base node of the iterator.
1.1005 + /// It is always the source of the pointed edge.
1.1006 + Node baseNode(const OutEdgeIt&) const { return INVALID; }
1.1007 +
1.1008 + /// \brief The running node of the iterator.
1.1009 + ///
1.1010 + /// Gives back the running node of the iterator.
1.1011 + /// It is always the target of the pointed edge.
1.1012 + Node runningNode(const OutEdgeIt&) const { return INVALID; }
1.1013 +
1.1014 + /// \brief The opposite node on the given edge.
1.1015 + ///
1.1016 + /// Gives back the opposite on the given edge.
1.1017 + /// \todo It should not be here.
1.1018 + Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
1.1019 +
1.1020 +
1.1021 + template <typename _Graph>
1.1022 + struct Constraints {
1.1023 + void constraints() {
1.1024 + checkConcept<Base, _Graph>();
1.1025 +
1.1026 + checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1.1027 + typename _Graph::EdgeIt >();
1.1028 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
1.1029 + typename _Graph::NodeIt >();
1.1030 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1.1031 + typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
1.1032 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1.1033 + typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
1.1034 +
1.1035 + typename _Graph::Node n;
1.1036 + typename _Graph::InEdgeIt ieit(INVALID);
1.1037 + typename _Graph::OutEdgeIt oeit(INVALID);
1.1038 + n = graph.baseNode(ieit);
1.1039 + n = graph.runningNode(ieit);
1.1040 + n = graph.baseNode(oeit);
1.1041 + n = graph.runningNode(oeit);
1.1042 + ignore_unused_variable_warning(n);
1.1043 + }
1.1044 +
1.1045 + const _Graph& graph;
1.1046 +
1.1047 + };
1.1048 + };
1.1049 +
1.1050 + /// \brief An empty iterable undirected graph class.
1.1051 + ///
1.1052 + /// This class provides beside the core graph features iterator
1.1053 + /// based iterable interface for the undirected graph structure.
1.1054 + /// This concept is part of the GraphConcept.
1.1055 + template <typename _Base = BaseUGraphComponent>
1.1056 + class IterableUGraphComponent : public IterableGraphComponent<_Base> {
1.1057 + public:
1.1058 +
1.1059 + typedef _Base Base;
1.1060 + typedef typename Base::Node Node;
1.1061 + typedef typename Base::Edge Edge;
1.1062 + typedef typename Base::UEdge UEdge;
1.1063 +
1.1064 +
1.1065 + typedef IterableUGraphComponent Graph;
1.1066 + using IterableGraphComponent<_Base>::baseNode;
1.1067 + using IterableGraphComponent<_Base>::runningNode;
1.1068 +
1.1069 +
1.1070 + /// \brief This iterator goes through each node.
1.1071 + ///
1.1072 + /// This iterator goes through each node.
1.1073 + typedef GraphItemIt<Graph, UEdge> UEdgeIt;
1.1074 + /// \brief This iterator goes trough the incident edges of a
1.1075 + /// node.
1.1076 + ///
1.1077 + /// This iterator goes trough the incident edges of a certain
1.1078 + /// node of a graph.
1.1079 + typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt;
1.1080 + /// \brief The base node of the iterator.
1.1081 + ///
1.1082 + /// Gives back the base node of the iterator.
1.1083 + Node baseNode(const IncEdgeIt&) const { return INVALID; }
1.1084 +
1.1085 + /// \brief The running node of the iterator.
1.1086 + ///
1.1087 + /// Gives back the running node of the iterator.
1.1088 + Node runningNode(const IncEdgeIt&) const { return INVALID; }
1.1089 +
1.1090 + template <typename _Graph>
1.1091 + struct Constraints {
1.1092 + void constraints() {
1.1093 + checkConcept<Base, _Graph>();
1.1094 + checkConcept<IterableGraphComponent<Base>, _Graph>();
1.1095 +
1.1096 + checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
1.1097 + typename _Graph::UEdgeIt >();
1.1098 + checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
1.1099 + typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
1.1100 +
1.1101 + typename _Graph::Node n;
1.1102 + typename _Graph::IncEdgeIt ueit(INVALID);
1.1103 + n = graph.baseNode(ueit);
1.1104 + n = graph.runningNode(ueit);
1.1105 + }
1.1106 +
1.1107 + const _Graph& graph;
1.1108 +
1.1109 + };
1.1110 + };
1.1111 +
1.1112 + /// \brief An empty alteration notifier graph class.
1.1113 + ///
1.1114 + /// This class provides beside the core graph features alteration
1.1115 + /// notifier interface for the graph structure. This implements
1.1116 + /// an observer-notifier pattern for each graph item. More
1.1117 + /// obsevers can be registered into the notifier and whenever an
1.1118 + /// alteration occured in the graph all the observers will
1.1119 + /// notified about it.
1.1120 + template <typename _Base = BaseGraphComponent>
1.1121 + class AlterableGraphComponent : public _Base {
1.1122 + public:
1.1123 +
1.1124 + typedef _Base Base;
1.1125 + typedef typename Base::Node Node;
1.1126 + typedef typename Base::Edge Edge;
1.1127 +
1.1128 +
1.1129 + /// The node observer registry.
1.1130 + typedef AlterationNotifier<AlterableGraphComponent, Node>
1.1131 + NodeNotifier;
1.1132 + /// The edge observer registry.
1.1133 + typedef AlterationNotifier<AlterableGraphComponent, Edge>
1.1134 + EdgeNotifier;
1.1135 +
1.1136 + /// \brief Gives back the node alteration notifier.
1.1137 + ///
1.1138 + /// Gives back the node alteration notifier.
1.1139 + NodeNotifier& getNotifier(Node) const {
1.1140 + return NodeNotifier();
1.1141 + }
1.1142 +
1.1143 + /// \brief Gives back the edge alteration notifier.
1.1144 + ///
1.1145 + /// Gives back the edge alteration notifier.
1.1146 + EdgeNotifier& getNotifier(Edge) const {
1.1147 + return EdgeNotifier();
1.1148 + }
1.1149 +
1.1150 + template <typename _Graph>
1.1151 + struct Constraints {
1.1152 + void constraints() {
1.1153 + checkConcept<Base, _Graph>();
1.1154 + typename _Graph::NodeNotifier& nn
1.1155 + = graph.getNotifier(typename _Graph::Node());
1.1156 +
1.1157 + typename _Graph::EdgeNotifier& en
1.1158 + = graph.getNotifier(typename _Graph::Edge());
1.1159 +
1.1160 + ignore_unused_variable_warning(nn);
1.1161 + ignore_unused_variable_warning(en);
1.1162 + }
1.1163 +
1.1164 + const _Graph& graph;
1.1165 +
1.1166 + };
1.1167 +
1.1168 + };
1.1169 +
1.1170 + /// \brief An empty alteration notifier undirected graph class.
1.1171 + ///
1.1172 + /// This class provides beside the core graph features alteration
1.1173 + /// notifier interface for the graph structure. This implements
1.1174 + /// an observer-notifier pattern for each graph item. More
1.1175 + /// obsevers can be registered into the notifier and whenever an
1.1176 + /// alteration occured in the graph all the observers will
1.1177 + /// notified about it.
1.1178 + template <typename _Base = BaseUGraphComponent>
1.1179 + class AlterableUGraphComponent : public AlterableGraphComponent<_Base> {
1.1180 + public:
1.1181 +
1.1182 + typedef _Base Base;
1.1183 + typedef typename Base::UEdge UEdge;
1.1184 +
1.1185 +
1.1186 + /// The edge observer registry.
1.1187 + typedef AlterationNotifier<AlterableUGraphComponent, UEdge>
1.1188 + UEdgeNotifier;
1.1189 +
1.1190 + /// \brief Gives back the edge alteration notifier.
1.1191 + ///
1.1192 + /// Gives back the edge alteration notifier.
1.1193 + UEdgeNotifier& getNotifier(UEdge) const {
1.1194 + return UEdgeNotifier();
1.1195 + }
1.1196 +
1.1197 + template <typename _Graph>
1.1198 + struct Constraints {
1.1199 + void constraints() {
1.1200 + checkConcept<Base, _Graph>();
1.1201 + checkConcept<AlterableGraphComponent, _Graph>();
1.1202 + typename _Graph::UEdgeNotifier& uen
1.1203 + = graph.getNotifier(typename _Graph::UEdge());
1.1204 + ignore_unused_variable_warning(uen);
1.1205 + }
1.1206 +
1.1207 + const _Graph& graph;
1.1208 +
1.1209 + };
1.1210 +
1.1211 + };
1.1212 +
1.1213 +
1.1214 + /// \brief Class describing the concept of graph maps
1.1215 + ///
1.1216 + /// This class describes the common interface of the graph maps
1.1217 + /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to
1.1218 + /// associate data to graph descriptors (nodes or edges).
1.1219 + template <typename _Graph, typename _Item, typename _Value>
1.1220 + class GraphMap : public ReadWriteMap<_Item, _Value> {
1.1221 + public:
1.1222 +
1.1223 + typedef ReadWriteMap<_Item, _Value> Parent;
1.1224 +
1.1225 + /// The graph type of the map.
1.1226 + typedef _Graph Graph;
1.1227 + /// The key type of the map.
1.1228 + typedef _Item Key;
1.1229 + /// The value type of the map.
1.1230 + typedef _Value Value;
1.1231 +
1.1232 + /// \brief Construct a new map.
1.1233 + ///
1.1234 + /// Construct a new map for the graph.
1.1235 + explicit GraphMap(const Graph&) {}
1.1236 + /// \brief Construct a new map with default value.
1.1237 + ///
1.1238 + /// Construct a new map for the graph and initalise the values.
1.1239 + GraphMap(const Graph&, const Value&) {}
1.1240 + /// \brief Copy constructor.
1.1241 + ///
1.1242 + /// Copy Constructor.
1.1243 + GraphMap(const GraphMap&) : Parent() {}
1.1244 +
1.1245 + /// \brief Assign operator.
1.1246 + ///
1.1247 + /// Assign operator. It does not mofify the underlying graph,
1.1248 + /// it just iterates on the current item set and set the map
1.1249 + /// with the value returned by the assigned map.
1.1250 + template <typename CMap>
1.1251 + GraphMap& operator=(const CMap&) {
1.1252 + checkConcept<ReadMap<Key, Value>, CMap>();
1.1253 + return *this;
1.1254 + }
1.1255 +
1.1256 + template<typename _Map>
1.1257 + struct Constraints {
1.1258 + void constraints() {
1.1259 + checkConcept<ReadWriteMap<Key, Value>, _Map >();
1.1260 + // Construction with a graph parameter
1.1261 + _Map a(g);
1.1262 + // Constructor with a graph and a default value parameter
1.1263 + _Map a2(g,t);
1.1264 + // Copy constructor.
1.1265 + _Map b(c);
1.1266 +
1.1267 + ReadMap<Key, Value> cmap;
1.1268 + b = cmap;
1.1269 +
1.1270 + ignore_unused_variable_warning(a2);
1.1271 + ignore_unused_variable_warning(b);
1.1272 + }
1.1273 +
1.1274 + const _Map &c;
1.1275 + const Graph &g;
1.1276 + const typename GraphMap::Value &t;
1.1277 + };
1.1278 +
1.1279 + };
1.1280 +
1.1281 + /// \brief An empty mappable graph class.
1.1282 + ///
1.1283 + /// This class provides beside the core graph features
1.1284 + /// map interface for the graph structure.
1.1285 + /// This concept is part of the Graph concept.
1.1286 + template <typename _Base = BaseGraphComponent>
1.1287 + class MappableGraphComponent : public _Base {
1.1288 + public:
1.1289 +
1.1290 + typedef _Base Base;
1.1291 + typedef typename Base::Node Node;
1.1292 + typedef typename Base::Edge Edge;
1.1293 +
1.1294 + typedef MappableGraphComponent Graph;
1.1295 +
1.1296 + /// \brief ReadWrite map of the nodes.
1.1297 + ///
1.1298 + /// ReadWrite map of the nodes.
1.1299 + ///
1.1300 + template <typename Value>
1.1301 + class NodeMap : public GraphMap<Graph, Node, Value> {
1.1302 + private:
1.1303 + NodeMap();
1.1304 + public:
1.1305 + typedef GraphMap<Graph, Node, Value> Parent;
1.1306 +
1.1307 + /// \brief Construct a new map.
1.1308 + ///
1.1309 + /// Construct a new map for the graph.
1.1310 + /// \todo call the right parent class constructor
1.1311 + explicit NodeMap(const Graph& graph) : Parent(graph) {}
1.1312 +
1.1313 + /// \brief Construct a new map with default value.
1.1314 + ///
1.1315 + /// Construct a new map for the graph and initalise the values.
1.1316 + NodeMap(const Graph& graph, const Value& value)
1.1317 + : Parent(graph, value) {}
1.1318 +
1.1319 + /// \brief Copy constructor.
1.1320 + ///
1.1321 + /// Copy Constructor.
1.1322 + NodeMap(const NodeMap& nm) : Parent(nm) {}
1.1323 +
1.1324 + /// \brief Assign operator.
1.1325 + ///
1.1326 + /// Assign operator.
1.1327 + template <typename CMap>
1.1328 + NodeMap& operator=(const CMap&) {
1.1329 + checkConcept<ReadMap<Node, Value>, CMap>();
1.1330 + return *this;
1.1331 + }
1.1332 +
1.1333 + };
1.1334 +
1.1335 + /// \brief ReadWrite map of the edges.
1.1336 + ///
1.1337 + /// ReadWrite map of the edges.
1.1338 + ///
1.1339 + template <typename Value>
1.1340 + class EdgeMap : public GraphMap<Graph, Edge, Value> {
1.1341 + private:
1.1342 + EdgeMap();
1.1343 + public:
1.1344 + typedef GraphMap<Graph, Edge, Value> Parent;
1.1345 +
1.1346 + /// \brief Construct a new map.
1.1347 + ///
1.1348 + /// Construct a new map for the graph.
1.1349 + /// \todo call the right parent class constructor
1.1350 + explicit EdgeMap(const Graph& graph) : Parent(graph) {}
1.1351 +
1.1352 + /// \brief Construct a new map with default value.
1.1353 + ///
1.1354 + /// Construct a new map for the graph and initalise the values.
1.1355 + EdgeMap(const Graph& graph, const Value& value)
1.1356 + : Parent(graph, value) {}
1.1357 +
1.1358 + /// \brief Copy constructor.
1.1359 + ///
1.1360 + /// Copy Constructor.
1.1361 + EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1.1362 +
1.1363 + /// \brief Assign operator.
1.1364 + ///
1.1365 + /// Assign operator.
1.1366 + template <typename CMap>
1.1367 + EdgeMap& operator=(const CMap&) {
1.1368 + checkConcept<ReadMap<Edge, Value>, CMap>();
1.1369 + return *this;
1.1370 + }
1.1371 +
1.1372 + };
1.1373 +
1.1374 +
1.1375 + template <typename _Graph>
1.1376 + struct Constraints {
1.1377 +
1.1378 + struct Dummy {
1.1379 + int value;
1.1380 + Dummy() : value(0) {}
1.1381 + Dummy(int _v) : value(_v) {}
1.1382 + };
1.1383 +
1.1384 + void constraints() {
1.1385 + checkConcept<Base, _Graph>();
1.1386 + { // int map test
1.1387 + typedef typename _Graph::template NodeMap<int> IntNodeMap;
1.1388 + checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
1.1389 + IntNodeMap >();
1.1390 + } { // bool map test
1.1391 + typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
1.1392 + checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
1.1393 + BoolNodeMap >();
1.1394 + } { // Dummy map test
1.1395 + typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap;
1.1396 + checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>,
1.1397 + DummyNodeMap >();
1.1398 + }
1.1399 +
1.1400 + { // int map test
1.1401 + typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1.1402 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1.1403 + IntEdgeMap >();
1.1404 + } { // bool map test
1.1405 + typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1.1406 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1.1407 + BoolEdgeMap >();
1.1408 + } { // Dummy map test
1.1409 + typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1.1410 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1.1411 + DummyEdgeMap >();
1.1412 + }
1.1413 + }
1.1414 +
1.1415 + _Graph& graph;
1.1416 + };
1.1417 + };
1.1418 +
1.1419 + /// \brief An empty mappable base graph class.
1.1420 + ///
1.1421 + /// This class provides beside the core graph features
1.1422 + /// map interface for the graph structure.
1.1423 + /// This concept is part of the UGraph concept.
1.1424 + template <typename _Base = BaseUGraphComponent>
1.1425 + class MappableUGraphComponent : public MappableGraphComponent<_Base> {
1.1426 + public:
1.1427 +
1.1428 + typedef _Base Base;
1.1429 + typedef typename Base::UEdge UEdge;
1.1430 +
1.1431 + typedef MappableUGraphComponent Graph;
1.1432 +
1.1433 + /// \brief ReadWrite map of the uedges.
1.1434 + ///
1.1435 + /// ReadWrite map of the uedges.
1.1436 + ///
1.1437 + template <typename Value>
1.1438 + class UEdgeMap : public GraphMap<Graph, UEdge, Value> {
1.1439 + public:
1.1440 + typedef GraphMap<Graph, UEdge, Value> Parent;
1.1441 +
1.1442 + /// \brief Construct a new map.
1.1443 + ///
1.1444 + /// Construct a new map for the graph.
1.1445 + /// \todo call the right parent class constructor
1.1446 + explicit UEdgeMap(const Graph& graph) : Parent(graph) {}
1.1447 +
1.1448 + /// \brief Construct a new map with default value.
1.1449 + ///
1.1450 + /// Construct a new map for the graph and initalise the values.
1.1451 + UEdgeMap(const Graph& graph, const Value& value)
1.1452 + : Parent(graph, value) {}
1.1453 +
1.1454 + /// \brief Copy constructor.
1.1455 + ///
1.1456 + /// Copy Constructor.
1.1457 + UEdgeMap(const UEdgeMap& nm) : Parent(nm) {}
1.1458 +
1.1459 + /// \brief Assign operator.
1.1460 + ///
1.1461 + /// Assign operator.
1.1462 + template <typename CMap>
1.1463 + UEdgeMap& operator=(const CMap&) {
1.1464 + checkConcept<ReadMap<UEdge, Value>, CMap>();
1.1465 + return *this;
1.1466 + }
1.1467 +
1.1468 + };
1.1469 +
1.1470 +
1.1471 + template <typename _Graph>
1.1472 + struct Constraints {
1.1473 +
1.1474 + struct Dummy {
1.1475 + int value;
1.1476 + Dummy() : value(0) {}
1.1477 + Dummy(int _v) : value(_v) {}
1.1478 + };
1.1479 +
1.1480 + void constraints() {
1.1481 + checkConcept<Base, _Graph>();
1.1482 + checkConcept<MappableGraphComponent<Base>, _Graph>();
1.1483 +
1.1484 + { // int map test
1.1485 + typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap;
1.1486 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>,
1.1487 + IntUEdgeMap >();
1.1488 + } { // bool map test
1.1489 + typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap;
1.1490 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>,
1.1491 + BoolUEdgeMap >();
1.1492 + } { // Dummy map test
1.1493 + typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap;
1.1494 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>,
1.1495 + DummyUEdgeMap >();
1.1496 + }
1.1497 + }
1.1498 +
1.1499 + _Graph& graph;
1.1500 + };
1.1501 + };
1.1502 +
1.1503 +
1.1504 + /// \brief An empty extendable graph class.
1.1505 + ///
1.1506 + /// This class provides beside the core graph features graph
1.1507 + /// extendable interface for the graph structure. The main
1.1508 + /// difference between the base and this interface is that the
1.1509 + /// graph alterations should handled already on this level.
1.1510 + template <typename _Base = BaseGraphComponent>
1.1511 + class ExtendableGraphComponent : public _Base {
1.1512 + public:
1.1513 +
1.1514 + typedef typename _Base::Node Node;
1.1515 + typedef typename _Base::Edge Edge;
1.1516 +
1.1517 + /// \brief Adds a new node to the graph.
1.1518 + ///
1.1519 + /// Adds a new node to the graph.
1.1520 + ///
1.1521 + Node addNode() {
1.1522 + return INVALID;
1.1523 + }
1.1524 +
1.1525 + /// \brief Adds a new edge connects the given two nodes.
1.1526 + ///
1.1527 + /// Adds a new edge connects the the given two nodes.
1.1528 + Edge addEdge(const Node&, const Node&) {
1.1529 + return INVALID;
1.1530 + }
1.1531 +
1.1532 + template <typename _Graph>
1.1533 + struct Constraints {
1.1534 + void constraints() {
1.1535 + typename _Graph::Node node_a, node_b;
1.1536 + node_a = graph.addNode();
1.1537 + node_b = graph.addNode();
1.1538 + typename _Graph::Edge edge;
1.1539 + edge = graph.addEdge(node_a, node_b);
1.1540 + }
1.1541 +
1.1542 + _Graph& graph;
1.1543 + };
1.1544 + };
1.1545 +
1.1546 + /// \brief An empty extendable base undirected graph class.
1.1547 + ///
1.1548 + /// This class provides beside the core undirected graph features
1.1549 + /// core undircted graph extend interface for the graph structure.
1.1550 + /// The main difference between the base and this interface is
1.1551 + /// that the graph alterations should handled already on this
1.1552 + /// level.
1.1553 + template <typename _Base = BaseUGraphComponent>
1.1554 + class ExtendableUGraphComponent : public _Base {
1.1555 + public:
1.1556 +
1.1557 + typedef typename _Base::Node Node;
1.1558 + typedef typename _Base::UEdge UEdge;
1.1559 +
1.1560 + /// \brief Adds a new node to the graph.
1.1561 + ///
1.1562 + /// Adds a new node to the graph.
1.1563 + ///
1.1564 + Node addNode() {
1.1565 + return INVALID;
1.1566 + }
1.1567 +
1.1568 + /// \brief Adds a new edge connects the given two nodes.
1.1569 + ///
1.1570 + /// Adds a new edge connects the the given two nodes.
1.1571 + UEdge addEdge(const Node&, const Node&) {
1.1572 + return INVALID;
1.1573 + }
1.1574 +
1.1575 + template <typename _Graph>
1.1576 + struct Constraints {
1.1577 + void constraints() {
1.1578 + typename _Graph::Node node_a, node_b;
1.1579 + node_a = graph.addNode();
1.1580 + node_b = graph.addNode();
1.1581 + typename _Graph::UEdge uedge;
1.1582 + uedge = graph.addUEdge(node_a, node_b);
1.1583 + }
1.1584 +
1.1585 + _Graph& graph;
1.1586 + };
1.1587 + };
1.1588 +
1.1589 + /// \brief An empty erasable graph class.
1.1590 + ///
1.1591 + /// This class provides beside the core graph features core erase
1.1592 + /// functions for the graph structure. The main difference between
1.1593 + /// the base and this interface is that the graph alterations
1.1594 + /// should handled already on this level.
1.1595 + template <typename _Base = BaseGraphComponent>
1.1596 + class ErasableGraphComponent : public _Base {
1.1597 + public:
1.1598 +
1.1599 + typedef _Base Base;
1.1600 + typedef typename Base::Node Node;
1.1601 + typedef typename Base::Edge Edge;
1.1602 +
1.1603 + /// \brief Erase a node from the graph.
1.1604 + ///
1.1605 + /// Erase a node from the graph. This function should
1.1606 + /// erase all edges connecting to the node.
1.1607 + void erase(const Node&) {}
1.1608 +
1.1609 + /// \brief Erase an edge from the graph.
1.1610 + ///
1.1611 + /// Erase an edge from the graph.
1.1612 + ///
1.1613 + void erase(const Edge&) {}
1.1614 +
1.1615 + template <typename _Graph>
1.1616 + struct Constraints {
1.1617 + void constraints() {
1.1618 + typename _Graph::Node node;
1.1619 + graph.erase(node);
1.1620 + typename _Graph::Edge edge;
1.1621 + graph.erase(edge);
1.1622 + }
1.1623 +
1.1624 + _Graph& graph;
1.1625 + };
1.1626 + };
1.1627 +
1.1628 + /// \brief An empty erasable base undirected graph class.
1.1629 + ///
1.1630 + /// This class provides beside the core undirected graph features
1.1631 + /// core erase functions for the undirceted graph structure. The
1.1632 + /// main difference between the base and this interface is that
1.1633 + /// the graph alterations should handled already on this level.
1.1634 + template <typename _Base = BaseUGraphComponent>
1.1635 + class ErasableUGraphComponent : public _Base {
1.1636 + public:
1.1637 +
1.1638 + typedef _Base Base;
1.1639 + typedef typename Base::Node Node;
1.1640 + typedef typename Base::UEdge UEdge;
1.1641 +
1.1642 + /// \brief Erase a node from the graph.
1.1643 + ///
1.1644 + /// Erase a node from the graph. This function should erase
1.1645 + /// edges connecting to the node.
1.1646 + void erase(const Node&) {}
1.1647 +
1.1648 + /// \brief Erase an edge from the graph.
1.1649 + ///
1.1650 + /// Erase an edge from the graph.
1.1651 + ///
1.1652 + void erase(const UEdge&) {}
1.1653 +
1.1654 + template <typename _Graph>
1.1655 + struct Constraints {
1.1656 + void constraints() {
1.1657 + typename _Graph::Node node;
1.1658 + graph.erase(node);
1.1659 + typename _Graph::Edge edge;
1.1660 + graph.erase(edge);
1.1661 + }
1.1662 +
1.1663 + _Graph& graph;
1.1664 + };
1.1665 + };
1.1666 +
1.1667 + /// \brief An empty clearable base graph class.
1.1668 + ///
1.1669 + /// This class provides beside the core graph features core clear
1.1670 + /// functions for the graph structure. The main difference between
1.1671 + /// the base and this interface is that the graph alterations
1.1672 + /// should handled already on this level.
1.1673 + template <typename _Base = BaseGraphComponent>
1.1674 + class ClearableGraphComponent : public _Base {
1.1675 + public:
1.1676 +
1.1677 + /// \brief Erase all nodes and edges from the graph.
1.1678 + ///
1.1679 + /// Erase all nodes and edges from the graph.
1.1680 + ///
1.1681 + void clear() {}
1.1682 +
1.1683 + template <typename _Graph>
1.1684 + struct Constraints {
1.1685 + void constraints() {
1.1686 + graph.clear();
1.1687 + }
1.1688 +
1.1689 + _Graph graph;
1.1690 + };
1.1691 + };
1.1692 +
1.1693 + /// \brief An empty clearable base undirected graph class.
1.1694 + ///
1.1695 + /// This class provides beside the core undirected graph features
1.1696 + /// core clear functions for the undirected graph structure. The
1.1697 + /// main difference between the base and this interface is that
1.1698 + /// the graph alterations should handled already on this level.
1.1699 + template <typename _Base = BaseUGraphComponent>
1.1700 + class ClearableUGraphComponent : public _Base {
1.1701 + public:
1.1702 +
1.1703 + /// \brief Erase all nodes and undirected edges from the graph.
1.1704 + ///
1.1705 + /// Erase all nodes and undirected edges from the graph.
1.1706 + ///
1.1707 + void clear() {}
1.1708 +
1.1709 + template <typename _Graph>
1.1710 + struct Constraints {
1.1711 + void constraints() {
1.1712 + graph.clear();
1.1713 + }
1.1714 +
1.1715 + _Graph graph;
1.1716 + };
1.1717 + };
1.1718 +
1.1719 + }
1.1720 +
1.1721 +}
1.1722 +
1.1723 +#endif