1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concepts/graph_components.h Tue Oct 24 17:19:16 2006 +0000
1.3 @@ -0,0 +1,2103 @@
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/concepts/maps.h>
1.32 +
1.33 +#include <lemon/bits/alteration_notifier.h>
1.34 +
1.35 +namespace lemon {
1.36 + namespace concepts {
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 + /// \brief Assign edge to undirected edge.
1.225 + ///
1.226 + /// Besides the core graph item functionality each edge should
1.227 + /// be convertible to the represented undirected edge.
1.228 + UEdge& operator=(const Edge&) { return *this; }
1.229 + };
1.230 +
1.231 + /// \brief Returns the direction of the edge.
1.232 + ///
1.233 + /// Returns the direction of the edge. Each edge represents an
1.234 + /// undirected edge with a direction. It gives back the
1.235 + /// direction.
1.236 + bool direction(const Edge&) const { return true; }
1.237 +
1.238 + /// \brief Returns the directed edge.
1.239 + ///
1.240 + /// Returns the directed edge from its direction and the
1.241 + /// represented undirected edge.
1.242 + Edge direct(const UEdge&, bool) const { return INVALID;}
1.243 +
1.244 + /// \brief Returns the directed edge.
1.245 + ///
1.246 + /// Returns the directed edge from its source and the
1.247 + /// represented undirected edge.
1.248 + Edge direct(const UEdge&, const Node&) const { return INVALID;}
1.249 +
1.250 + /// \brief Returns the opposite edge.
1.251 + ///
1.252 + /// Returns the opposite edge. It is the edge representing the
1.253 + /// same undirected edge and has opposite direction.
1.254 + Edge oppositeEdge(const Edge&) const { return INVALID;}
1.255 +
1.256 + /// \brief Gives back the target node of an undirected edge.
1.257 + ///
1.258 + /// Gives back the target node of an undirected edge. The name
1.259 + /// target is a little confusing because the undirected edge
1.260 + /// does not have target but it just means that one of the end
1.261 + /// node.
1.262 + Node target(const UEdge&) const { return INVALID;}
1.263 +
1.264 + /// \brief Gives back the source node of an undirected edge.
1.265 + ///
1.266 + /// Gives back the source node of an undirected edge. The name
1.267 + /// source is a little confusing because the undirected edge
1.268 + /// does not have source but it just means that one of the end
1.269 + /// node.
1.270 + Node source(const UEdge&) const { return INVALID;}
1.271 +
1.272 + template <typename _Graph>
1.273 + struct Constraints {
1.274 + typedef typename _Graph::Node Node;
1.275 + typedef typename _Graph::Edge Edge;
1.276 + typedef typename _Graph::UEdge UEdge;
1.277 +
1.278 + void constraints() {
1.279 + checkConcept<BaseGraphComponent, _Graph>();
1.280 + checkConcept<GraphItem<'u'>, UEdge>();
1.281 + {
1.282 + Node n;
1.283 + UEdge ue(INVALID);
1.284 + Edge e;
1.285 + n = graph.source(ue);
1.286 + n = graph.target(ue);
1.287 + e = graph.direct(ue, true);
1.288 + e = graph.direct(ue, n);
1.289 + e = graph.oppositeEdge(e);
1.290 + ue = e;
1.291 + bool d = graph.direction(e);
1.292 + ignore_unused_variable_warning(d);
1.293 + }
1.294 + }
1.295 +
1.296 + const _Graph& graph;
1.297 + };
1.298 +
1.299 + };
1.300 +
1.301 + /// \brief An empty base bipartite undirected graph class.
1.302 + ///
1.303 + /// This class provides the minimal set of features needed for an
1.304 + /// bipartite undirected graph structure. All bipartite undirected
1.305 + /// graph concepts have to be conform to this base graph. It just
1.306 + /// provides types for nodes, A-nodes, B-nodes, edges and
1.307 + /// undirected edges and functions to get the source and the
1.308 + /// target of the edges and undirected edges, conversion from
1.309 + /// edges to undirected edges and function to get both direction
1.310 + /// of the undirected edges.
1.311 + class BaseBpUGraphComponent : public BaseUGraphComponent {
1.312 + public:
1.313 + typedef BaseUGraphComponent::Node Node;
1.314 + typedef BaseUGraphComponent::Edge Edge;
1.315 + typedef BaseUGraphComponent::UEdge UEdge;
1.316 +
1.317 + /// \brief Helper class for A-nodes.
1.318 + ///
1.319 + /// This class is just a helper class for A-nodes, it is not
1.320 + /// suggested to use it directly. It can be converted easily to
1.321 + /// node and vice versa. The usage of this class is limited
1.322 + /// to use just as template parameters for special map types.
1.323 + class ANode : public Node {
1.324 + public:
1.325 + typedef Node Parent;
1.326 +
1.327 + /// \brief Default constructor.
1.328 + ///
1.329 + /// \warning The default constructor is not required to set
1.330 + /// the item to some well-defined value. So you should consider it
1.331 + /// as uninitialized.
1.332 + ANode() {}
1.333 + /// \brief Copy constructor.
1.334 + ///
1.335 + /// Copy constructor.
1.336 + ///
1.337 + ANode(const ANode &) : Parent() {}
1.338 + /// \brief Invalid constructor \& conversion.
1.339 + ///
1.340 + /// This constructor initializes the item to be invalid.
1.341 + /// \sa Invalid for more details.
1.342 + ANode(Invalid) {}
1.343 + /// \brief Converter from node to A-node.
1.344 + ///
1.345 + /// Besides the core graph item functionality each node should
1.346 + /// be convertible to the represented A-node if it is it possible.
1.347 + ANode(const Node&) {}
1.348 + /// \brief Assign node to A-node.
1.349 + ///
1.350 + /// Besides the core graph item functionality each node should
1.351 + /// be convertible to the represented A-node if it is it possible.
1.352 + ANode& operator=(const Node&) { return *this; }
1.353 + };
1.354 +
1.355 + /// \brief Helper class for B-nodes.
1.356 + ///
1.357 + /// This class is just a helper class for B-nodes, it is not
1.358 + /// suggested to use it directly. It can be converted easily to
1.359 + /// node and vice versa. The usage of this class is limited
1.360 + /// to use just as template parameters for special map types.
1.361 + class BNode : public Node {
1.362 + public:
1.363 + typedef Node Parent;
1.364 +
1.365 + /// \brief Default constructor.
1.366 + ///
1.367 + /// \warning The default constructor is not required to set
1.368 + /// the item to some well-defined value. So you should consider it
1.369 + /// as uninitialized.
1.370 + BNode() {}
1.371 + /// \brief Copy constructor.
1.372 + ///
1.373 + /// Copy constructor.
1.374 + ///
1.375 + BNode(const BNode &) : Parent() {}
1.376 + /// \brief Invalid constructor \& conversion.
1.377 + ///
1.378 + /// This constructor initializes the item to be invalid.
1.379 + /// \sa Invalid for more details.
1.380 + BNode(Invalid) {}
1.381 + /// \brief Converter from node to B-node.
1.382 + ///
1.383 + /// Besides the core graph item functionality each node should
1.384 + /// be convertible to the represented B-node if it is it possible.
1.385 + BNode(const Node&) {}
1.386 + /// \brief Assign node to B-node.
1.387 + ///
1.388 + /// Besides the core graph item functionality each node should
1.389 + /// be convertible to the represented B-node if it is it possible.
1.390 + BNode& operator=(const Node&) { return *this; }
1.391 + };
1.392 +
1.393 + /// \brief Gives back %true when the node is A-node.
1.394 + ///
1.395 + /// Gives back %true when the node is A-node.
1.396 + bool aNode(const Node&) const { return false; }
1.397 +
1.398 + /// \brief Gives back %true when the node is B-node.
1.399 + ///
1.400 + /// Gives back %true when the node is B-node.
1.401 + bool bNode(const Node&) const { return false; }
1.402 +
1.403 + /// \brief Gives back the A-node of the undirected edge.
1.404 + ///
1.405 + /// Gives back the A-node of the undirected edge.
1.406 + Node aNode(const UEdge&) const { return INVALID; }
1.407 +
1.408 + /// \brief Gives back the B-node of the undirected edge.
1.409 + ///
1.410 + /// Gives back the B-node of the undirected edge.
1.411 + Node bNode(const UEdge&) const { return INVALID; }
1.412 +
1.413 + template <typename _Graph>
1.414 + struct Constraints {
1.415 + typedef typename _Graph::Node Node;
1.416 + typedef typename _Graph::ANode ANode;
1.417 + typedef typename _Graph::BNode BNode;
1.418 + typedef typename _Graph::Edge Edge;
1.419 + typedef typename _Graph::UEdge UEdge;
1.420 +
1.421 + void constraints() {
1.422 + checkConcept<BaseUGraphComponent, _Graph>();
1.423 + checkConcept<GraphItem<'a'>, ANode>();
1.424 + checkConcept<GraphItem<'b'>, BNode>();
1.425 + {
1.426 + Node n;
1.427 + UEdge ue(INVALID);
1.428 + bool b;
1.429 + n = graph.aNode(ue);
1.430 + n = graph.bNode(ue);
1.431 + b = graph.aNode(n);
1.432 + b = graph.bNode(n);
1.433 + ANode an;
1.434 + an = n; n = an;
1.435 + BNode bn;
1.436 + bn = n; n = bn;
1.437 + ignore_unused_variable_warning(b);
1.438 + }
1.439 + }
1.440 +
1.441 + const _Graph& graph;
1.442 + };
1.443 +
1.444 + };
1.445 +
1.446 + /// \brief An empty idable base graph class.
1.447 + ///
1.448 + /// This class provides beside the core graph features
1.449 + /// core id functions for the graph structure.
1.450 + /// The most of the base graphs should be conform to this concept.
1.451 + /// The id's are unique and immutable.
1.452 + template <typename _Base = BaseGraphComponent>
1.453 + class IDableGraphComponent : public _Base {
1.454 + public:
1.455 +
1.456 + typedef _Base Base;
1.457 + typedef typename Base::Node Node;
1.458 + typedef typename Base::Edge Edge;
1.459 +
1.460 + /// \brief Gives back an unique integer id for the Node.
1.461 + ///
1.462 + /// Gives back an unique integer id for the Node.
1.463 + ///
1.464 + int id(const Node&) const { return -1;}
1.465 +
1.466 + /// \brief Gives back the node by the unique id.
1.467 + ///
1.468 + /// Gives back the node by the unique id.
1.469 + /// If the graph does not contain node with the given id
1.470 + /// then the result of the function is undetermined.
1.471 + Node nodeFromId(int) const { return INVALID;}
1.472 +
1.473 + /// \brief Gives back an unique integer id for the Edge.
1.474 + ///
1.475 + /// Gives back an unique integer id for the Edge.
1.476 + ///
1.477 + int id(const Edge&) const { return -1;}
1.478 +
1.479 + /// \brief Gives back the edge by the unique id.
1.480 + ///
1.481 + /// Gives back the edge by the unique id.
1.482 + /// If the graph does not contain edge with the given id
1.483 + /// then the result of the function is undetermined.
1.484 + Edge edgeFromId(int) const { return INVALID;}
1.485 +
1.486 + /// \brief Gives back an integer greater or equal to the maximum
1.487 + /// Node id.
1.488 + ///
1.489 + /// Gives back an integer greater or equal to the maximum Node
1.490 + /// id.
1.491 + int maxNodeId() const { return -1;}
1.492 +
1.493 + /// \brief Gives back an integer greater or equal to the maximum
1.494 + /// Edge id.
1.495 + ///
1.496 + /// Gives back an integer greater or equal to the maximum Edge
1.497 + /// id.
1.498 + int maxEdgeId() const { return -1;}
1.499 +
1.500 + template <typename _Graph>
1.501 + struct Constraints {
1.502 +
1.503 + void constraints() {
1.504 + checkConcept<Base, _Graph >();
1.505 + typename _Graph::Node node;
1.506 + int nid = graph.id(node);
1.507 + nid = graph.id(node);
1.508 + node = graph.nodeFromId(nid);
1.509 + typename _Graph::Edge edge;
1.510 + int eid = graph.id(edge);
1.511 + eid = graph.id(edge);
1.512 + edge = graph.edgeFromId(eid);
1.513 +
1.514 + nid = graph.maxNodeId();
1.515 + ignore_unused_variable_warning(nid);
1.516 + eid = graph.maxEdgeId();
1.517 + ignore_unused_variable_warning(eid);
1.518 + }
1.519 +
1.520 + const _Graph& graph;
1.521 + };
1.522 + };
1.523 +
1.524 + /// \brief An empty idable base undirected graph class.
1.525 + ///
1.526 + /// This class provides beside the core undirected graph features
1.527 + /// core id functions for the undirected graph structure. The
1.528 + /// most of the base undirected graphs should be conform to this
1.529 + /// concept. The id's are unique and immutable.
1.530 + template <typename _Base = BaseUGraphComponent>
1.531 + class IDableUGraphComponent : public IDableGraphComponent<_Base> {
1.532 + public:
1.533 +
1.534 + typedef _Base Base;
1.535 + typedef typename Base::UEdge UEdge;
1.536 +
1.537 + using IDableGraphComponent<_Base>::id;
1.538 +
1.539 + /// \brief Gives back an unique integer id for the UEdge.
1.540 + ///
1.541 + /// Gives back an unique integer id for the UEdge.
1.542 + ///
1.543 + int id(const UEdge&) const { return -1;}
1.544 +
1.545 + /// \brief Gives back the undirected edge by the unique id.
1.546 + ///
1.547 + /// Gives back the undirected edge by the unique id. If the
1.548 + /// graph does not contain edge with the given id then the
1.549 + /// result of the function is undetermined.
1.550 + UEdge uEdgeFromId(int) const { return INVALID;}
1.551 +
1.552 + /// \brief Gives back an integer greater or equal to the maximum
1.553 + /// UEdge id.
1.554 + ///
1.555 + /// Gives back an integer greater or equal to the maximum UEdge
1.556 + /// id.
1.557 + int maxUEdgeId() const { return -1;}
1.558 +
1.559 + template <typename _Graph>
1.560 + struct Constraints {
1.561 +
1.562 + void constraints() {
1.563 + checkConcept<Base, _Graph >();
1.564 + checkConcept<IDableGraphComponent<Base>, _Graph >();
1.565 + typename _Graph::UEdge uedge;
1.566 + int ueid = graph.id(uedge);
1.567 + ueid = graph.id(uedge);
1.568 + uedge = graph.uEdgeFromId(ueid);
1.569 + ueid = graph.maxUEdgeId();
1.570 + ignore_unused_variable_warning(ueid);
1.571 + }
1.572 +
1.573 + const _Graph& graph;
1.574 + };
1.575 + };
1.576 +
1.577 + /// \brief An empty idable base bipartite undirected graph class.
1.578 + ///
1.579 + /// This class provides beside the core bipartite undirected graph
1.580 + /// features core id functions for the bipartite undirected graph
1.581 + /// structure. The most of the base undirected graphs should be
1.582 + /// conform to this concept.
1.583 + template <typename _Base = BaseBpUGraphComponent>
1.584 + class IDableBpUGraphComponent : public IDableUGraphComponent<_Base> {
1.585 + public:
1.586 +
1.587 + typedef _Base Base;
1.588 + typedef typename Base::Node Node;
1.589 +
1.590 + using IDableUGraphComponent<_Base>::id;
1.591 +
1.592 + /// \brief Gives back an unique integer id for the ANode.
1.593 + ///
1.594 + /// Gives back an unique integer id for the ANode.
1.595 + ///
1.596 + int aNodeId(const Node&) const { return -1;}
1.597 +
1.598 + /// \brief Gives back the undirected edge by the unique id.
1.599 + ///
1.600 + /// Gives back the undirected edge by the unique id. If the
1.601 + /// graph does not contain edge with the given id then the
1.602 + /// result of the function is undetermined.
1.603 + Node nodeFromANodeId(int) const { return INVALID;}
1.604 +
1.605 + /// \brief Gives back an integer greater or equal to the maximum
1.606 + /// ANode id.
1.607 + ///
1.608 + /// Gives back an integer greater or equal to the maximum ANode
1.609 + /// id.
1.610 + int maxANodeId() const { return -1;}
1.611 +
1.612 + /// \brief Gives back an unique integer id for the BNode.
1.613 + ///
1.614 + /// Gives back an unique integer id for the BNode.
1.615 + ///
1.616 + int bNodeId(const Node&) const { return -1;}
1.617 +
1.618 + /// \brief Gives back the undirected edge by the unique id.
1.619 + ///
1.620 + /// Gives back the undirected edge by the unique id. If the
1.621 + /// graph does not contain edge with the given id then the
1.622 + /// result of the function is undetermined.
1.623 + Node nodeFromBNodeId(int) const { return INVALID;}
1.624 +
1.625 + /// \brief Gives back an integer greater or equal to the maximum
1.626 + /// BNode id.
1.627 + ///
1.628 + /// Gives back an integer greater or equal to the maximum BNode
1.629 + /// id.
1.630 + int maxBNodeId() const { return -1;}
1.631 +
1.632 + template <typename _Graph>
1.633 + struct Constraints {
1.634 +
1.635 + void constraints() {
1.636 + checkConcept<Base, _Graph >();
1.637 + checkConcept<IDableGraphComponent<Base>, _Graph >();
1.638 + typename _Graph::Node node(INVALID);
1.639 + int id;
1.640 + id = graph.aNodeId(node);
1.641 + id = graph.bNodeId(node);
1.642 + node = graph.nodeFromANodeId(id);
1.643 + node = graph.nodeFromBNodeId(id);
1.644 + id = graph.maxANodeId();
1.645 + id = graph.maxBNodeId();
1.646 + }
1.647 +
1.648 + const _Graph& graph;
1.649 + };
1.650 + };
1.651 +
1.652 + /// \brief Skeleton class for graph NodeIt and EdgeIt
1.653 + ///
1.654 + /// Skeleton class for graph NodeIt and EdgeIt.
1.655 + ///
1.656 + template <typename _Graph, typename _Item>
1.657 + class GraphItemIt : public _Item {
1.658 + public:
1.659 + /// \brief Default constructor.
1.660 + ///
1.661 + /// @warning The default constructor sets the iterator
1.662 + /// to an undefined value.
1.663 + GraphItemIt() {}
1.664 + /// \brief Copy constructor.
1.665 + ///
1.666 + /// Copy constructor.
1.667 + ///
1.668 + GraphItemIt(const GraphItemIt& ) {}
1.669 + /// \brief Sets the iterator to the first item.
1.670 + ///
1.671 + /// Sets the iterator to the first item of \c the graph.
1.672 + ///
1.673 + explicit GraphItemIt(const _Graph&) {}
1.674 + /// \brief Invalid constructor \& conversion.
1.675 + ///
1.676 + /// This constructor initializes the item to be invalid.
1.677 + /// \sa Invalid for more details.
1.678 + GraphItemIt(Invalid) {}
1.679 + /// \brief Assign operator for items.
1.680 + ///
1.681 + /// The items are assignable.
1.682 + ///
1.683 + GraphItemIt& operator=(const GraphItemIt&) { return *this; }
1.684 + /// \brief Next item.
1.685 + ///
1.686 + /// Assign the iterator to the next item.
1.687 + ///
1.688 + GraphItemIt& operator++() { return *this; }
1.689 + /// \brief Equality operator
1.690 + ///
1.691 + /// Two iterators are equal if and only if they point to the
1.692 + /// same object or both are invalid.
1.693 + bool operator==(const GraphItemIt&) const { return true;}
1.694 + /// \brief Inequality operator
1.695 + ///
1.696 + /// \sa operator==(Node n)
1.697 + ///
1.698 + bool operator!=(const GraphItemIt&) const { return true;}
1.699 +
1.700 + template<typename _GraphItemIt>
1.701 + struct Constraints {
1.702 + void constraints() {
1.703 + _GraphItemIt it1(g);
1.704 + _GraphItemIt it2;
1.705 +
1.706 + it2 = ++it1;
1.707 + ++it2 = it1;
1.708 + ++(++it1);
1.709 +
1.710 + _Item bi = it1;
1.711 + bi = it2;
1.712 + }
1.713 + _Graph& g;
1.714 + };
1.715 + };
1.716 +
1.717 + /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt
1.718 + ///
1.719 + /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
1.720 + /// base class, the _selector is a additional template parameter. For
1.721 + /// InEdgeIt you should instantiate it with character 'i' and for
1.722 + /// OutEdgeIt with 'o'.
1.723 + template <typename _Graph,
1.724 + typename _Item = typename _Graph::Edge,
1.725 + typename _Base = typename _Graph::Node,
1.726 + char _selector = '0'>
1.727 + class GraphIncIt : public _Item {
1.728 + public:
1.729 + /// \brief Default constructor.
1.730 + ///
1.731 + /// @warning The default constructor sets the iterator
1.732 + /// to an undefined value.
1.733 + GraphIncIt() {}
1.734 + /// \brief Copy constructor.
1.735 + ///
1.736 + /// Copy constructor.
1.737 + ///
1.738 + GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
1.739 + /// \brief Sets the iterator to the first edge incoming into or outgoing
1.740 + /// from the node.
1.741 + ///
1.742 + /// Sets the iterator to the first edge incoming into or outgoing
1.743 + /// from the node.
1.744 + ///
1.745 + explicit GraphIncIt(const _Graph&, const _Base&) {}
1.746 + /// \brief Invalid constructor \& conversion.
1.747 + ///
1.748 + /// This constructor initializes the item to be invalid.
1.749 + /// \sa Invalid for more details.
1.750 + GraphIncIt(Invalid) {}
1.751 + /// \brief Assign operator for iterators.
1.752 + ///
1.753 + /// The iterators are assignable.
1.754 + ///
1.755 + GraphIncIt& operator=(GraphIncIt const&) { return *this; }
1.756 + /// \brief Next item.
1.757 + ///
1.758 + /// Assign the iterator to the next item.
1.759 + ///
1.760 + GraphIncIt& operator++() { return *this; }
1.761 +
1.762 + /// \brief Equality operator
1.763 + ///
1.764 + /// Two iterators are equal if and only if they point to the
1.765 + /// same object or both are invalid.
1.766 + bool operator==(const GraphIncIt&) const { return true;}
1.767 +
1.768 + /// \brief Inequality operator
1.769 + ///
1.770 + /// \sa operator==(Node n)
1.771 + ///
1.772 + bool operator!=(const GraphIncIt&) const { return true;}
1.773 +
1.774 + template <typename _GraphIncIt>
1.775 + struct Constraints {
1.776 + void constraints() {
1.777 + checkConcept<GraphItem<_selector>, _GraphIncIt>();
1.778 + _GraphIncIt it1(graph, node);
1.779 + _GraphIncIt it2;
1.780 +
1.781 + it2 = ++it1;
1.782 + ++it2 = it1;
1.783 + ++(++it1);
1.784 + _Item e = it1;
1.785 + e = it2;
1.786 +
1.787 + }
1.788 +
1.789 + _Item edge;
1.790 + _Base node;
1.791 + _Graph graph;
1.792 + _GraphIncIt it;
1.793 + };
1.794 + };
1.795 +
1.796 +
1.797 + /// \brief An empty iterable graph class.
1.798 + ///
1.799 + /// This class provides beside the core graph features
1.800 + /// iterator based iterable interface for the graph structure.
1.801 + /// This concept is part of the Graph concept.
1.802 + template <typename _Base = BaseGraphComponent>
1.803 + class IterableGraphComponent : public _Base {
1.804 +
1.805 + public:
1.806 +
1.807 + typedef _Base Base;
1.808 + typedef typename Base::Node Node;
1.809 + typedef typename Base::Edge Edge;
1.810 +
1.811 + typedef IterableGraphComponent Graph;
1.812 +
1.813 + /// \name Base iteration
1.814 + ///
1.815 + /// This interface provides functions for iteration on graph items
1.816 + ///
1.817 + /// @{
1.818 +
1.819 + /// \brief Gives back the first node in the iterating order.
1.820 + ///
1.821 + /// Gives back the first node in the iterating order.
1.822 + ///
1.823 + void first(Node&) const {}
1.824 +
1.825 + /// \brief Gives back the next node in the iterating order.
1.826 + ///
1.827 + /// Gives back the next node in the iterating order.
1.828 + ///
1.829 + void next(Node&) const {}
1.830 +
1.831 + /// \brief Gives back the first edge in the iterating order.
1.832 + ///
1.833 + /// Gives back the first edge in the iterating order.
1.834 + ///
1.835 + void first(Edge&) const {}
1.836 +
1.837 + /// \brief Gives back the next edge in the iterating order.
1.838 + ///
1.839 + /// Gives back the next edge in the iterating order.
1.840 + ///
1.841 + void next(Edge&) const {}
1.842 +
1.843 +
1.844 + /// \brief Gives back the first of the edges point to the given
1.845 + /// node.
1.846 + ///
1.847 + /// Gives back the first of the edges point to the given node.
1.848 + ///
1.849 + void firstIn(Edge&, const Node&) const {}
1.850 +
1.851 + /// \brief Gives back the next of the edges points to the given
1.852 + /// node.
1.853 + ///
1.854 + /// Gives back the next of the edges points to the given node.
1.855 + ///
1.856 + void nextIn(Edge&) const {}
1.857 +
1.858 + /// \brief Gives back the first of the edges start from the
1.859 + /// given node.
1.860 + ///
1.861 + /// Gives back the first of the edges start from the given node.
1.862 + ///
1.863 + void firstOut(Edge&, const Node&) const {}
1.864 +
1.865 + /// \brief Gives back the next of the edges start from the given
1.866 + /// node.
1.867 + ///
1.868 + /// Gives back the next of the edges start from the given node.
1.869 + ///
1.870 + void nextOut(Edge&) const {}
1.871 +
1.872 + /// @}
1.873 +
1.874 + /// \name Class based iteration
1.875 + ///
1.876 + /// This interface provides functions for iteration on graph items
1.877 + ///
1.878 + /// @{
1.879 +
1.880 + /// \brief This iterator goes through each node.
1.881 + ///
1.882 + /// This iterator goes through each node.
1.883 + ///
1.884 + typedef GraphItemIt<Graph, Node> NodeIt;
1.885 +
1.886 + /// \brief This iterator goes through each node.
1.887 + ///
1.888 + /// This iterator goes through each node.
1.889 + ///
1.890 + typedef GraphItemIt<Graph, Edge> EdgeIt;
1.891 +
1.892 + /// \brief This iterator goes trough the incoming edges of a node.
1.893 + ///
1.894 + /// This iterator goes trough the \e inccoming edges of a certain node
1.895 + /// of a graph.
1.896 + typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt;
1.897 +
1.898 + /// \brief This iterator goes trough the outgoing edges of a node.
1.899 + ///
1.900 + /// This iterator goes trough the \e outgoing edges of a certain node
1.901 + /// of a graph.
1.902 + typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt;
1.903 +
1.904 + /// \brief The base node of the iterator.
1.905 + ///
1.906 + /// Gives back the base node of the iterator.
1.907 + /// It is always the target of the pointed edge.
1.908 + Node baseNode(const InEdgeIt&) const { return INVALID; }
1.909 +
1.910 + /// \brief The running node of the iterator.
1.911 + ///
1.912 + /// Gives back the running node of the iterator.
1.913 + /// It is always the source of the pointed edge.
1.914 + Node runningNode(const InEdgeIt&) const { return INVALID; }
1.915 +
1.916 + /// \brief The base node of the iterator.
1.917 + ///
1.918 + /// Gives back the base node of the iterator.
1.919 + /// It is always the source of the pointed edge.
1.920 + Node baseNode(const OutEdgeIt&) const { return INVALID; }
1.921 +
1.922 + /// \brief The running node of the iterator.
1.923 + ///
1.924 + /// Gives back the running node of the iterator.
1.925 + /// It is always the target of the pointed edge.
1.926 + Node runningNode(const OutEdgeIt&) const { return INVALID; }
1.927 +
1.928 + /// @}
1.929 +
1.930 + template <typename _Graph>
1.931 + struct Constraints {
1.932 + void constraints() {
1.933 + checkConcept<Base, _Graph>();
1.934 +
1.935 + {
1.936 + typename _Graph::Node node(INVALID);
1.937 + typename _Graph::Edge edge(INVALID);
1.938 + {
1.939 + graph.first(node);
1.940 + graph.next(node);
1.941 + }
1.942 + {
1.943 + graph.first(edge);
1.944 + graph.next(edge);
1.945 + }
1.946 + {
1.947 + graph.firstIn(edge, node);
1.948 + graph.nextIn(edge);
1.949 + }
1.950 + {
1.951 + graph.firstOut(edge, node);
1.952 + graph.nextOut(edge);
1.953 + }
1.954 + }
1.955 +
1.956 + {
1.957 + checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1.958 + typename _Graph::EdgeIt >();
1.959 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
1.960 + typename _Graph::NodeIt >();
1.961 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1.962 + typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
1.963 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1.964 + typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
1.965 +
1.966 + typename _Graph::Node n;
1.967 + typename _Graph::InEdgeIt ieit(INVALID);
1.968 + typename _Graph::OutEdgeIt oeit(INVALID);
1.969 + n = graph.baseNode(ieit);
1.970 + n = graph.runningNode(ieit);
1.971 + n = graph.baseNode(oeit);
1.972 + n = graph.runningNode(oeit);
1.973 + ignore_unused_variable_warning(n);
1.974 + }
1.975 + }
1.976 +
1.977 + const _Graph& graph;
1.978 +
1.979 + };
1.980 + };
1.981 +
1.982 + /// \brief An empty iterable undirected graph class.
1.983 + ///
1.984 + /// This class provides beside the core graph features iterator
1.985 + /// based iterable interface for the undirected graph structure.
1.986 + /// This concept is part of the UGraph concept.
1.987 + template <typename _Base = BaseUGraphComponent>
1.988 + class IterableUGraphComponent : public IterableGraphComponent<_Base> {
1.989 + public:
1.990 +
1.991 + typedef _Base Base;
1.992 + typedef typename Base::Node Node;
1.993 + typedef typename Base::Edge Edge;
1.994 + typedef typename Base::UEdge UEdge;
1.995 +
1.996 +
1.997 + typedef IterableUGraphComponent Graph;
1.998 +
1.999 + /// \name Base iteration
1.1000 + ///
1.1001 + /// This interface provides functions for iteration on graph items
1.1002 + /// @{
1.1003 +
1.1004 + using IterableGraphComponent<_Base>::first;
1.1005 + using IterableGraphComponent<_Base>::next;
1.1006 +
1.1007 + /// \brief Gives back the first undirected edge in the iterating
1.1008 + /// order.
1.1009 + ///
1.1010 + /// Gives back the first undirected edge in the iterating order.
1.1011 + ///
1.1012 + void first(UEdge&) const {}
1.1013 +
1.1014 + /// \brief Gives back the next undirected edge in the iterating
1.1015 + /// order.
1.1016 + ///
1.1017 + /// Gives back the next undirected edge in the iterating order.
1.1018 + ///
1.1019 + void next(UEdge&) const {}
1.1020 +
1.1021 +
1.1022 + /// \brief Gives back the first of the undirected edges from the
1.1023 + /// given node.
1.1024 + ///
1.1025 + /// Gives back the first of the undirected edges from the given
1.1026 + /// node. The bool parameter gives back that direction which
1.1027 + /// gives a good direction of the uedge so the source of the
1.1028 + /// directed edge is the given node.
1.1029 + void firstInc(UEdge&, bool&, const Node&) const {}
1.1030 +
1.1031 + /// \brief Gives back the next of the undirected edges from the
1.1032 + /// given node.
1.1033 + ///
1.1034 + /// Gives back the next of the undirected edges from the given
1.1035 + /// node. The bool parameter should be used as the \c firstInc()
1.1036 + /// use it.
1.1037 + void nextInc(UEdge&, bool&) const {}
1.1038 +
1.1039 + using IterableGraphComponent<_Base>::baseNode;
1.1040 + using IterableGraphComponent<_Base>::runningNode;
1.1041 +
1.1042 + /// @}
1.1043 +
1.1044 + /// \name Class based iteration
1.1045 + ///
1.1046 + /// This interface provides functions for iteration on graph items
1.1047 + ///
1.1048 + /// @{
1.1049 +
1.1050 + /// \brief This iterator goes through each node.
1.1051 + ///
1.1052 + /// This iterator goes through each node.
1.1053 + typedef GraphItemIt<Graph, UEdge> UEdgeIt;
1.1054 + /// \brief This iterator goes trough the incident edges of a
1.1055 + /// node.
1.1056 + ///
1.1057 + /// This iterator goes trough the incident edges of a certain
1.1058 + /// node of a graph.
1.1059 + typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt;
1.1060 + /// \brief The base node of the iterator.
1.1061 + ///
1.1062 + /// Gives back the base node of the iterator.
1.1063 + Node baseNode(const IncEdgeIt&) const { return INVALID; }
1.1064 +
1.1065 + /// \brief The running node of the iterator.
1.1066 + ///
1.1067 + /// Gives back the running node of the iterator.
1.1068 + Node runningNode(const IncEdgeIt&) const { return INVALID; }
1.1069 +
1.1070 + /// @}
1.1071 +
1.1072 + template <typename _Graph>
1.1073 + struct Constraints {
1.1074 + void constraints() {
1.1075 + checkConcept<IterableGraphComponent<Base>, _Graph>();
1.1076 +
1.1077 + {
1.1078 + typename _Graph::Node node(INVALID);
1.1079 + typename _Graph::UEdge uedge(INVALID);
1.1080 + bool dir;
1.1081 + {
1.1082 + graph.first(uedge);
1.1083 + graph.next(uedge);
1.1084 + }
1.1085 + {
1.1086 + graph.firstInc(uedge, dir, node);
1.1087 + graph.nextInc(uedge, dir);
1.1088 + }
1.1089 +
1.1090 + }
1.1091 +
1.1092 + {
1.1093 + checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
1.1094 + typename _Graph::UEdgeIt >();
1.1095 + checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
1.1096 + typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
1.1097 +
1.1098 + typename _Graph::Node n;
1.1099 + typename _Graph::IncEdgeIt ueit(INVALID);
1.1100 + n = graph.baseNode(ueit);
1.1101 + n = graph.runningNode(ueit);
1.1102 + }
1.1103 + }
1.1104 +
1.1105 + const _Graph& graph;
1.1106 +
1.1107 + };
1.1108 + };
1.1109 +
1.1110 + /// \brief An empty iterable bipartite undirected graph class.
1.1111 + ///
1.1112 + /// This class provides beside the core graph features iterator
1.1113 + /// based iterable interface for the bipartite undirected graph
1.1114 + /// structure. This concept is part of the BpUGraph concept.
1.1115 + template <typename _Base = BaseUGraphComponent>
1.1116 + class IterableBpUGraphComponent : public IterableUGraphComponent<_Base> {
1.1117 + public:
1.1118 +
1.1119 + typedef _Base Base;
1.1120 + typedef typename Base::Node Node;
1.1121 + typedef typename Base::UEdge UEdge;
1.1122 +
1.1123 + typedef IterableBpUGraphComponent Graph;
1.1124 +
1.1125 + /// \name Base iteration
1.1126 + ///
1.1127 + /// This interface provides functions for iteration on graph items
1.1128 + /// @{
1.1129 +
1.1130 + using IterableUGraphComponent<_Base>::first;
1.1131 + using IterableUGraphComponent<_Base>::next;
1.1132 +
1.1133 + /// \brief Gives back the first A-node in the iterating order.
1.1134 + ///
1.1135 + /// Gives back the first undirected A-node in the iterating
1.1136 + /// order.
1.1137 + ///
1.1138 + void firstANode(Node&) const {}
1.1139 +
1.1140 + /// \brief Gives back the next A-node in the iterating order.
1.1141 + ///
1.1142 + /// Gives back the next A-node in the iterating order.
1.1143 + ///
1.1144 + void nextANode(Node&) const {}
1.1145 +
1.1146 + /// \brief Gives back the first B-node in the iterating order.
1.1147 + ///
1.1148 + /// Gives back the first undirected B-node in the iterating
1.1149 + /// order.
1.1150 + ///
1.1151 + void firstBNode(Node&) const {}
1.1152 +
1.1153 + /// \brief Gives back the next B-node in the iterating order.
1.1154 + ///
1.1155 + /// Gives back the next B-node in the iterating order.
1.1156 + ///
1.1157 + void nextBNode(Node&) const {}
1.1158 +
1.1159 +
1.1160 + /// \brief Gives back the first of the undirected edges start
1.1161 + /// from the given A-node.
1.1162 + ///
1.1163 + /// Gives back the first of the undirected edges start from the
1.1164 + /// given A-node.
1.1165 + void firstFromANode(UEdge&, const Node&) const {}
1.1166 +
1.1167 + /// \brief Gives back the next of the undirected edges start
1.1168 + /// from the given A-node.
1.1169 + ///
1.1170 + /// Gives back the next of the undirected edges start from the
1.1171 + /// given A-node.
1.1172 + void nextFromANode(UEdge&) const {}
1.1173 +
1.1174 + /// \brief Gives back the first of the undirected edges start
1.1175 + /// from the given B-node.
1.1176 + ///
1.1177 + /// Gives back the first of the undirected edges start from the
1.1178 + /// given B-node.
1.1179 + void firstFromBNode(UEdge&, const Node&) const {}
1.1180 +
1.1181 + /// \brief Gives back the next of the undirected edges start
1.1182 + /// from the given B-node.
1.1183 + ///
1.1184 + /// Gives back the next of the undirected edges start from the
1.1185 + /// given B-node.
1.1186 + void nextFromBNode(UEdge&) const {}
1.1187 +
1.1188 +
1.1189 + /// @}
1.1190 +
1.1191 + /// \name Class based iteration
1.1192 + ///
1.1193 + /// This interface provides functions for iteration on graph items
1.1194 + ///
1.1195 + /// @{
1.1196 +
1.1197 + /// \brief This iterator goes through each A-node.
1.1198 + ///
1.1199 + /// This iterator goes through each A-node.
1.1200 + typedef GraphItemIt<Graph, Node> ANodeIt;
1.1201 +
1.1202 + /// \brief This iterator goes through each B-node.
1.1203 + ///
1.1204 + /// This iterator goes through each B-node.
1.1205 + typedef GraphItemIt<Graph, Node> BNodeIt;
1.1206 +
1.1207 + /// @}
1.1208 +
1.1209 + template <typename _Graph>
1.1210 + struct Constraints {
1.1211 + void constraints() {
1.1212 + checkConcept<IterableUGraphComponent<Base>, _Graph>();
1.1213 +
1.1214 + {
1.1215 + typename _Graph::Node node(INVALID);
1.1216 + typename _Graph::UEdge uedge(INVALID);
1.1217 + graph.firstANode(node);
1.1218 + graph.nextANode(node);
1.1219 + graph.firstBNode(node);
1.1220 + graph.nextBNode(node);
1.1221 +
1.1222 + graph.firstFromANode(uedge, node);
1.1223 + graph.nextFromANode(uedge);
1.1224 + graph.firstFromBNode(uedge, node);
1.1225 + graph.nextFromBNode(uedge);
1.1226 + }
1.1227 + {
1.1228 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
1.1229 + typename _Graph::ANodeIt >();
1.1230 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
1.1231 + typename _Graph::BNodeIt >();
1.1232 + }
1.1233 +
1.1234 + }
1.1235 +
1.1236 + const _Graph& graph;
1.1237 +
1.1238 + };
1.1239 + };
1.1240 +
1.1241 + /// \brief An empty alteration notifier graph class.
1.1242 + ///
1.1243 + /// This class provides beside the core graph features alteration
1.1244 + /// notifier interface for the graph structure. This implements
1.1245 + /// an observer-notifier pattern for each graph item. More
1.1246 + /// obsevers can be registered into the notifier and whenever an
1.1247 + /// alteration occured in the graph all the observers will
1.1248 + /// notified about it.
1.1249 + template <typename _Base = BaseGraphComponent>
1.1250 + class AlterableGraphComponent : public _Base {
1.1251 + public:
1.1252 +
1.1253 + typedef _Base Base;
1.1254 + typedef typename Base::Node Node;
1.1255 + typedef typename Base::Edge Edge;
1.1256 +
1.1257 +
1.1258 + /// The node observer registry.
1.1259 + typedef AlterationNotifier<AlterableGraphComponent, Node>
1.1260 + NodeNotifier;
1.1261 + /// The edge observer registry.
1.1262 + typedef AlterationNotifier<AlterableGraphComponent, Edge>
1.1263 + EdgeNotifier;
1.1264 +
1.1265 + /// \brief Gives back the node alteration notifier.
1.1266 + ///
1.1267 + /// Gives back the node alteration notifier.
1.1268 + NodeNotifier& getNotifier(Node) const {
1.1269 + return NodeNotifier();
1.1270 + }
1.1271 +
1.1272 + /// \brief Gives back the edge alteration notifier.
1.1273 + ///
1.1274 + /// Gives back the edge alteration notifier.
1.1275 + EdgeNotifier& getNotifier(Edge) const {
1.1276 + return EdgeNotifier();
1.1277 + }
1.1278 +
1.1279 + template <typename _Graph>
1.1280 + struct Constraints {
1.1281 + void constraints() {
1.1282 + checkConcept<Base, _Graph>();
1.1283 + typename _Graph::NodeNotifier& nn
1.1284 + = graph.getNotifier(typename _Graph::Node());
1.1285 +
1.1286 + typename _Graph::EdgeNotifier& en
1.1287 + = graph.getNotifier(typename _Graph::Edge());
1.1288 +
1.1289 + ignore_unused_variable_warning(nn);
1.1290 + ignore_unused_variable_warning(en);
1.1291 + }
1.1292 +
1.1293 + const _Graph& graph;
1.1294 +
1.1295 + };
1.1296 +
1.1297 + };
1.1298 +
1.1299 + /// \brief An empty alteration notifier undirected graph class.
1.1300 + ///
1.1301 + /// This class provides beside the core graph features alteration
1.1302 + /// notifier interface for the graph structure. This implements
1.1303 + /// an observer-notifier pattern for each graph item. More
1.1304 + /// obsevers can be registered into the notifier and whenever an
1.1305 + /// alteration occured in the graph all the observers will
1.1306 + /// notified about it.
1.1307 + template <typename _Base = BaseUGraphComponent>
1.1308 + class AlterableUGraphComponent : public AlterableGraphComponent<_Base> {
1.1309 + public:
1.1310 +
1.1311 + typedef _Base Base;
1.1312 + typedef typename Base::UEdge UEdge;
1.1313 +
1.1314 +
1.1315 + /// The edge observer registry.
1.1316 + typedef AlterationNotifier<AlterableUGraphComponent, UEdge>
1.1317 + UEdgeNotifier;
1.1318 +
1.1319 + /// \brief Gives back the edge alteration notifier.
1.1320 + ///
1.1321 + /// Gives back the edge alteration notifier.
1.1322 + UEdgeNotifier& getNotifier(UEdge) const {
1.1323 + return UEdgeNotifier();
1.1324 + }
1.1325 +
1.1326 + template <typename _Graph>
1.1327 + struct Constraints {
1.1328 + void constraints() {
1.1329 + checkConcept<AlterableGraphComponent<Base>, _Graph>();
1.1330 + typename _Graph::UEdgeNotifier& uen
1.1331 + = graph.getNotifier(typename _Graph::UEdge());
1.1332 + ignore_unused_variable_warning(uen);
1.1333 + }
1.1334 +
1.1335 + const _Graph& graph;
1.1336 +
1.1337 + };
1.1338 +
1.1339 + };
1.1340 +
1.1341 + /// \brief An empty alteration notifier bipartite undirected graph
1.1342 + /// class.
1.1343 + ///
1.1344 + /// This class provides beside the core graph features alteration
1.1345 + /// notifier interface for the graph structure. This implements
1.1346 + /// an observer-notifier pattern for each graph item. More
1.1347 + /// obsevers can be registered into the notifier and whenever an
1.1348 + /// alteration occured in the graph all the observers will
1.1349 + /// notified about it.
1.1350 + template <typename _Base = BaseUGraphComponent>
1.1351 + class AlterableBpUGraphComponent : public AlterableUGraphComponent<_Base> {
1.1352 + public:
1.1353 +
1.1354 + typedef _Base Base;
1.1355 + typedef typename Base::ANode ANode;
1.1356 + typedef typename Base::BNode BNode;
1.1357 +
1.1358 +
1.1359 + /// The A-node observer registry.
1.1360 + typedef AlterationNotifier<AlterableBpUGraphComponent, ANode>
1.1361 + ANodeNotifier;
1.1362 +
1.1363 + /// The B-node observer registry.
1.1364 + typedef AlterationNotifier<AlterableBpUGraphComponent, BNode>
1.1365 + BNodeNotifier;
1.1366 +
1.1367 + /// \brief Gives back the A-node alteration notifier.
1.1368 + ///
1.1369 + /// Gives back the A-node alteration notifier.
1.1370 + ANodeNotifier& getNotifier(ANode) const {
1.1371 + return ANodeNotifier();
1.1372 + }
1.1373 +
1.1374 + /// \brief Gives back the B-node alteration notifier.
1.1375 + ///
1.1376 + /// Gives back the B-node alteration notifier.
1.1377 + BNodeNotifier& getNotifier(BNode) const {
1.1378 + return BNodeNotifier();
1.1379 + }
1.1380 +
1.1381 + template <typename _Graph>
1.1382 + struct Constraints {
1.1383 + void constraints() {
1.1384 + checkConcept<AlterableUGraphComponent<Base>, _Graph>();
1.1385 + typename _Graph::ANodeNotifier& ann
1.1386 + = graph.getNotifier(typename _Graph::ANode());
1.1387 + typename _Graph::BNodeNotifier& bnn
1.1388 + = graph.getNotifier(typename _Graph::BNode());
1.1389 + ignore_unused_variable_warning(ann);
1.1390 + ignore_unused_variable_warning(bnn);
1.1391 + }
1.1392 +
1.1393 + const _Graph& graph;
1.1394 +
1.1395 + };
1.1396 +
1.1397 + };
1.1398 +
1.1399 +
1.1400 + /// \brief Class describing the concept of graph maps
1.1401 + ///
1.1402 + /// This class describes the common interface of the graph maps
1.1403 + /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to
1.1404 + /// associate data to graph descriptors (nodes or edges).
1.1405 + template <typename _Graph, typename _Item, typename _Value>
1.1406 + class GraphMap : public ReadWriteMap<_Item, _Value> {
1.1407 + public:
1.1408 +
1.1409 + typedef ReadWriteMap<_Item, _Value> Parent;
1.1410 +
1.1411 + /// The graph type of the map.
1.1412 + typedef _Graph Graph;
1.1413 + /// The key type of the map.
1.1414 + typedef _Item Key;
1.1415 + /// The value type of the map.
1.1416 + typedef _Value Value;
1.1417 +
1.1418 + /// \brief Construct a new map.
1.1419 + ///
1.1420 + /// Construct a new map for the graph.
1.1421 + explicit GraphMap(const Graph&) {}
1.1422 + /// \brief Construct a new map with default value.
1.1423 + ///
1.1424 + /// Construct a new map for the graph and initalise the values.
1.1425 + GraphMap(const Graph&, const Value&) {}
1.1426 + /// \brief Copy constructor.
1.1427 + ///
1.1428 + /// Copy Constructor.
1.1429 + GraphMap(const GraphMap&) : Parent() {}
1.1430 +
1.1431 + /// \brief Assign operator.
1.1432 + ///
1.1433 + /// Assign operator. It does not mofify the underlying graph,
1.1434 + /// it just iterates on the current item set and set the map
1.1435 + /// with the value returned by the assigned map.
1.1436 + template <typename CMap>
1.1437 + GraphMap& operator=(const CMap&) {
1.1438 + checkConcept<ReadMap<Key, Value>, CMap>();
1.1439 + return *this;
1.1440 + }
1.1441 +
1.1442 + template<typename _Map>
1.1443 + struct Constraints {
1.1444 + void constraints() {
1.1445 + checkConcept<ReadWriteMap<Key, Value>, _Map >();
1.1446 + // Construction with a graph parameter
1.1447 + _Map a(g);
1.1448 + // Constructor with a graph and a default value parameter
1.1449 + _Map a2(g,t);
1.1450 + // Copy constructor.
1.1451 + _Map b(c);
1.1452 +
1.1453 + ReadMap<Key, Value> cmap;
1.1454 + b = cmap;
1.1455 +
1.1456 + ignore_unused_variable_warning(a2);
1.1457 + ignore_unused_variable_warning(b);
1.1458 + }
1.1459 +
1.1460 + const _Map &c;
1.1461 + const Graph &g;
1.1462 + const typename GraphMap::Value &t;
1.1463 + };
1.1464 +
1.1465 + };
1.1466 +
1.1467 + /// \brief An empty mappable graph class.
1.1468 + ///
1.1469 + /// This class provides beside the core graph features
1.1470 + /// map interface for the graph structure.
1.1471 + /// This concept is part of the Graph concept.
1.1472 + template <typename _Base = BaseGraphComponent>
1.1473 + class MappableGraphComponent : public _Base {
1.1474 + public:
1.1475 +
1.1476 + typedef _Base Base;
1.1477 + typedef typename Base::Node Node;
1.1478 + typedef typename Base::Edge Edge;
1.1479 +
1.1480 + typedef MappableGraphComponent Graph;
1.1481 +
1.1482 + /// \brief ReadWrite map of the nodes.
1.1483 + ///
1.1484 + /// ReadWrite map of the nodes.
1.1485 + ///
1.1486 + template <typename _Value>
1.1487 + class NodeMap : public GraphMap<Graph, Node, _Value> {
1.1488 + private:
1.1489 + NodeMap();
1.1490 + public:
1.1491 + typedef GraphMap<MappableGraphComponent, Node, _Value> Parent;
1.1492 +
1.1493 + /// \brief Construct a new map.
1.1494 + ///
1.1495 + /// Construct a new map for the graph.
1.1496 + /// \todo call the right parent class constructor
1.1497 + explicit NodeMap(const MappableGraphComponent& graph)
1.1498 + : Parent(graph) {}
1.1499 +
1.1500 + /// \brief Construct a new map with default value.
1.1501 + ///
1.1502 + /// Construct a new map for the graph and initalise the values.
1.1503 + NodeMap(const MappableGraphComponent& graph, const _Value& value)
1.1504 + : Parent(graph, value) {}
1.1505 +
1.1506 + /// \brief Copy constructor.
1.1507 + ///
1.1508 + /// Copy Constructor.
1.1509 + NodeMap(const NodeMap& nm) : Parent(nm) {}
1.1510 +
1.1511 + /// \brief Assign operator.
1.1512 + ///
1.1513 + /// Assign operator.
1.1514 + template <typename CMap>
1.1515 + NodeMap& operator=(const CMap&) {
1.1516 + checkConcept<ReadMap<Node, _Value>, CMap>();
1.1517 + return *this;
1.1518 + }
1.1519 +
1.1520 + };
1.1521 +
1.1522 + /// \brief ReadWrite map of the edges.
1.1523 + ///
1.1524 + /// ReadWrite map of the edges.
1.1525 + ///
1.1526 + template <typename _Value>
1.1527 + class EdgeMap : public GraphMap<Graph, Edge, _Value> {
1.1528 + private:
1.1529 + EdgeMap();
1.1530 + public:
1.1531 + typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
1.1532 +
1.1533 + /// \brief Construct a new map.
1.1534 + ///
1.1535 + /// Construct a new map for the graph.
1.1536 + /// \todo call the right parent class constructor
1.1537 + explicit EdgeMap(const MappableGraphComponent& graph)
1.1538 + : Parent(graph) {}
1.1539 +
1.1540 + /// \brief Construct a new map with default value.
1.1541 + ///
1.1542 + /// Construct a new map for the graph and initalise the values.
1.1543 + EdgeMap(const MappableGraphComponent& graph, const _Value& value)
1.1544 + : Parent(graph, value) {}
1.1545 +
1.1546 + /// \brief Copy constructor.
1.1547 + ///
1.1548 + /// Copy Constructor.
1.1549 + EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1.1550 +
1.1551 + /// \brief Assign operator.
1.1552 + ///
1.1553 + /// Assign operator.
1.1554 + template <typename CMap>
1.1555 + EdgeMap& operator=(const CMap&) {
1.1556 + checkConcept<ReadMap<Edge, _Value>, CMap>();
1.1557 + return *this;
1.1558 + }
1.1559 +
1.1560 + };
1.1561 +
1.1562 +
1.1563 + template <typename _Graph>
1.1564 + struct Constraints {
1.1565 +
1.1566 + struct Dummy {
1.1567 + int value;
1.1568 + Dummy() : value(0) {}
1.1569 + Dummy(int _v) : value(_v) {}
1.1570 + };
1.1571 +
1.1572 + void constraints() {
1.1573 + checkConcept<Base, _Graph>();
1.1574 + { // int map test
1.1575 + typedef typename _Graph::template NodeMap<int> IntNodeMap;
1.1576 + checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
1.1577 + IntNodeMap >();
1.1578 + } { // bool map test
1.1579 + typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
1.1580 + checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
1.1581 + BoolNodeMap >();
1.1582 + } { // Dummy map test
1.1583 + typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap;
1.1584 + checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>,
1.1585 + DummyNodeMap >();
1.1586 + }
1.1587 +
1.1588 + { // int map test
1.1589 + typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1.1590 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1.1591 + IntEdgeMap >();
1.1592 + } { // bool map test
1.1593 + typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1.1594 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1.1595 + BoolEdgeMap >();
1.1596 + } { // Dummy map test
1.1597 + typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1.1598 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1.1599 + DummyEdgeMap >();
1.1600 + }
1.1601 + }
1.1602 +
1.1603 + _Graph& graph;
1.1604 + };
1.1605 + };
1.1606 +
1.1607 + /// \brief An empty mappable base bipartite undirected graph class.
1.1608 + ///
1.1609 + /// This class provides beside the core graph features
1.1610 + /// map interface for the graph structure.
1.1611 + /// This concept is part of the UGraph concept.
1.1612 + template <typename _Base = BaseUGraphComponent>
1.1613 + class MappableUGraphComponent : public MappableGraphComponent<_Base> {
1.1614 + public:
1.1615 +
1.1616 + typedef _Base Base;
1.1617 + typedef typename Base::UEdge UEdge;
1.1618 +
1.1619 + typedef MappableUGraphComponent Graph;
1.1620 +
1.1621 + /// \brief ReadWrite map of the uedges.
1.1622 + ///
1.1623 + /// ReadWrite map of the uedges.
1.1624 + ///
1.1625 + template <typename _Value>
1.1626 + class UEdgeMap : public GraphMap<Graph, UEdge, _Value> {
1.1627 + public:
1.1628 + typedef GraphMap<MappableUGraphComponent, UEdge, _Value> Parent;
1.1629 +
1.1630 + /// \brief Construct a new map.
1.1631 + ///
1.1632 + /// Construct a new map for the graph.
1.1633 + /// \todo call the right parent class constructor
1.1634 + explicit UEdgeMap(const MappableUGraphComponent& graph)
1.1635 + : Parent(graph) {}
1.1636 +
1.1637 + /// \brief Construct a new map with default value.
1.1638 + ///
1.1639 + /// Construct a new map for the graph and initalise the values.
1.1640 + UEdgeMap(const MappableUGraphComponent& graph, const _Value& value)
1.1641 + : Parent(graph, value) {}
1.1642 +
1.1643 + /// \brief Copy constructor.
1.1644 + ///
1.1645 + /// Copy Constructor.
1.1646 + UEdgeMap(const UEdgeMap& nm) : Parent(nm) {}
1.1647 +
1.1648 + /// \brief Assign operator.
1.1649 + ///
1.1650 + /// Assign operator.
1.1651 + template <typename CMap>
1.1652 + UEdgeMap& operator=(const CMap&) {
1.1653 + checkConcept<ReadMap<UEdge, _Value>, CMap>();
1.1654 + return *this;
1.1655 + }
1.1656 +
1.1657 + };
1.1658 +
1.1659 +
1.1660 + template <typename _Graph>
1.1661 + struct Constraints {
1.1662 +
1.1663 + struct Dummy {
1.1664 + int value;
1.1665 + Dummy() : value(0) {}
1.1666 + Dummy(int _v) : value(_v) {}
1.1667 + };
1.1668 +
1.1669 + void constraints() {
1.1670 + checkConcept<MappableGraphComponent<Base>, _Graph>();
1.1671 +
1.1672 + { // int map test
1.1673 + typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap;
1.1674 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>,
1.1675 + IntUEdgeMap >();
1.1676 + } { // bool map test
1.1677 + typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap;
1.1678 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>,
1.1679 + BoolUEdgeMap >();
1.1680 + } { // Dummy map test
1.1681 + typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap;
1.1682 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>,
1.1683 + DummyUEdgeMap >();
1.1684 + }
1.1685 + }
1.1686 +
1.1687 + _Graph& graph;
1.1688 + };
1.1689 + };
1.1690 +
1.1691 + /// \brief An empty mappable base bipartite undirected graph
1.1692 + /// class.
1.1693 + ///
1.1694 + /// This class provides beside the core graph features
1.1695 + /// map interface for the graph structure.
1.1696 + /// This concept is part of the BpUGraph concept.
1.1697 + template <typename _Base = BaseBpUGraphComponent>
1.1698 + class MappableBpUGraphComponent : public MappableUGraphComponent<_Base> {
1.1699 + public:
1.1700 +
1.1701 + typedef _Base Base;
1.1702 + typedef typename Base::Node Node;
1.1703 +
1.1704 + typedef MappableBpUGraphComponent Graph;
1.1705 +
1.1706 + /// \brief ReadWrite map of the A-nodes.
1.1707 + ///
1.1708 + /// ReadWrite map of the A-nodes.
1.1709 + ///
1.1710 + template <typename _Value>
1.1711 + class ANodeMap : public GraphMap<Graph, Node, _Value> {
1.1712 + public:
1.1713 + typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
1.1714 +
1.1715 + /// \brief Construct a new map.
1.1716 + ///
1.1717 + /// Construct a new map for the graph.
1.1718 + /// \todo call the right parent class constructor
1.1719 + explicit ANodeMap(const MappableBpUGraphComponent& graph)
1.1720 + : Parent(graph) {}
1.1721 +
1.1722 + /// \brief Construct a new map with default value.
1.1723 + ///
1.1724 + /// Construct a new map for the graph and initalise the values.
1.1725 + ANodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
1.1726 + : Parent(graph, value) {}
1.1727 +
1.1728 + /// \brief Copy constructor.
1.1729 + ///
1.1730 + /// Copy Constructor.
1.1731 + ANodeMap(const ANodeMap& nm) : Parent(nm) {}
1.1732 +
1.1733 + /// \brief Assign operator.
1.1734 + ///
1.1735 + /// Assign operator.
1.1736 + template <typename CMap>
1.1737 + ANodeMap& operator=(const CMap&) {
1.1738 + checkConcept<ReadMap<Node, _Value>, CMap>();
1.1739 + return *this;
1.1740 + }
1.1741 +
1.1742 + };
1.1743 +
1.1744 + /// \brief ReadWrite map of the B-nodes.
1.1745 + ///
1.1746 + /// ReadWrite map of the A-nodes.
1.1747 + ///
1.1748 + template <typename _Value>
1.1749 + class BNodeMap : public GraphMap<Graph, Node, _Value> {
1.1750 + public:
1.1751 + typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
1.1752 +
1.1753 + /// \brief Construct a new map.
1.1754 + ///
1.1755 + /// Construct a new map for the graph.
1.1756 + /// \todo call the right parent class constructor
1.1757 + explicit BNodeMap(const MappableBpUGraphComponent& graph)
1.1758 + : Parent(graph) {}
1.1759 +
1.1760 + /// \brief Construct a new map with default value.
1.1761 + ///
1.1762 + /// Construct a new map for the graph and initalise the values.
1.1763 + BNodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
1.1764 + : Parent(graph, value) {}
1.1765 +
1.1766 + /// \brief Copy constructor.
1.1767 + ///
1.1768 + /// Copy Constructor.
1.1769 + BNodeMap(const BNodeMap& nm) : Parent(nm) {}
1.1770 +
1.1771 + /// \brief Assign operator.
1.1772 + ///
1.1773 + /// Assign operator.
1.1774 + template <typename CMap>
1.1775 + BNodeMap& operator=(const CMap&) {
1.1776 + checkConcept<ReadMap<Node, _Value>, CMap>();
1.1777 + return *this;
1.1778 + }
1.1779 +
1.1780 + };
1.1781 +
1.1782 +
1.1783 + template <typename _Graph>
1.1784 + struct Constraints {
1.1785 +
1.1786 + struct Dummy {
1.1787 + int value;
1.1788 + Dummy() : value(0) {}
1.1789 + Dummy(int _v) : value(_v) {}
1.1790 + };
1.1791 +
1.1792 + void constraints() {
1.1793 + checkConcept<MappableUGraphComponent<Base>, _Graph>();
1.1794 +
1.1795 + { // int map test
1.1796 + typedef typename _Graph::template ANodeMap<int> IntANodeMap;
1.1797 + checkConcept<GraphMap<_Graph, typename _Graph::ANode, int>,
1.1798 + IntANodeMap >();
1.1799 + } { // bool map test
1.1800 + typedef typename _Graph::template ANodeMap<bool> BoolANodeMap;
1.1801 + checkConcept<GraphMap<_Graph, typename _Graph::ANode, bool>,
1.1802 + BoolANodeMap >();
1.1803 + } { // Dummy map test
1.1804 + typedef typename _Graph::template ANodeMap<Dummy> DummyANodeMap;
1.1805 + checkConcept<GraphMap<_Graph, typename _Graph::ANode, Dummy>,
1.1806 + DummyANodeMap >();
1.1807 + }
1.1808 + }
1.1809 +
1.1810 + _Graph& graph;
1.1811 + };
1.1812 + };
1.1813 +
1.1814 +
1.1815 + /// \brief An empty extendable graph class.
1.1816 + ///
1.1817 + /// This class provides beside the core graph features graph
1.1818 + /// extendable interface for the graph structure. The main
1.1819 + /// difference between the base and this interface is that the
1.1820 + /// graph alterations should handled already on this level.
1.1821 + template <typename _Base = BaseGraphComponent>
1.1822 + class ExtendableGraphComponent : public _Base {
1.1823 + public:
1.1824 + typedef _Base Base;
1.1825 +
1.1826 + typedef typename _Base::Node Node;
1.1827 + typedef typename _Base::Edge Edge;
1.1828 +
1.1829 + /// \brief Adds a new node to the graph.
1.1830 + ///
1.1831 + /// Adds a new node to the graph.
1.1832 + ///
1.1833 + Node addNode() {
1.1834 + return INVALID;
1.1835 + }
1.1836 +
1.1837 + /// \brief Adds a new edge connects the given two nodes.
1.1838 + ///
1.1839 + /// Adds a new edge connects the the given two nodes.
1.1840 + Edge addEdge(const Node&, const Node&) {
1.1841 + return INVALID;
1.1842 + }
1.1843 +
1.1844 + template <typename _Graph>
1.1845 + struct Constraints {
1.1846 + void constraints() {
1.1847 + checkConcept<Base, _Graph>();
1.1848 + typename _Graph::Node node_a, node_b;
1.1849 + node_a = graph.addNode();
1.1850 + node_b = graph.addNode();
1.1851 + typename _Graph::Edge edge;
1.1852 + edge = graph.addEdge(node_a, node_b);
1.1853 + }
1.1854 +
1.1855 + _Graph& graph;
1.1856 + };
1.1857 + };
1.1858 +
1.1859 + /// \brief An empty extendable base undirected graph class.
1.1860 + ///
1.1861 + /// This class provides beside the core undirected graph features
1.1862 + /// core undircted graph extend interface for the graph structure.
1.1863 + /// The main difference between the base and this interface is
1.1864 + /// that the graph alterations should handled already on this
1.1865 + /// level.
1.1866 + template <typename _Base = BaseUGraphComponent>
1.1867 + class ExtendableUGraphComponent : public _Base {
1.1868 + public:
1.1869 +
1.1870 + typedef _Base Base;
1.1871 + typedef typename _Base::Node Node;
1.1872 + typedef typename _Base::UEdge UEdge;
1.1873 +
1.1874 + /// \brief Adds a new node to the graph.
1.1875 + ///
1.1876 + /// Adds a new node to the graph.
1.1877 + ///
1.1878 + Node addNode() {
1.1879 + return INVALID;
1.1880 + }
1.1881 +
1.1882 + /// \brief Adds a new edge connects the given two nodes.
1.1883 + ///
1.1884 + /// Adds a new edge connects the the given two nodes.
1.1885 + UEdge addEdge(const Node&, const Node&) {
1.1886 + return INVALID;
1.1887 + }
1.1888 +
1.1889 + template <typename _Graph>
1.1890 + struct Constraints {
1.1891 + void constraints() {
1.1892 + checkConcept<Base, _Graph>();
1.1893 + typename _Graph::Node node_a, node_b;
1.1894 + node_a = graph.addNode();
1.1895 + node_b = graph.addNode();
1.1896 + typename _Graph::UEdge uedge;
1.1897 + uedge = graph.addUEdge(node_a, node_b);
1.1898 + }
1.1899 +
1.1900 + _Graph& graph;
1.1901 + };
1.1902 + };
1.1903 +
1.1904 + /// \brief An empty extendable base undirected graph class.
1.1905 + ///
1.1906 + /// This class provides beside the core bipartite undirected graph
1.1907 + /// features core undircted graph extend interface for the graph
1.1908 + /// structure. The main difference between the base and this
1.1909 + /// interface is that the graph alterations should handled already
1.1910 + /// on this level.
1.1911 + template <typename _Base = BaseBpUGraphComponent>
1.1912 + class ExtendableBpUGraphComponent
1.1913 + : public ExtendableUGraphComponent<_Base> {
1.1914 +
1.1915 + typedef _Base Base;
1.1916 +
1.1917 + template <typename _Graph>
1.1918 + struct Constraints {
1.1919 + void constraints() {
1.1920 + checkConcept<ExtendableUGraphComponent<Base>, _Graph>();
1.1921 + }
1.1922 + };
1.1923 + };
1.1924 +
1.1925 + /// \brief An empty erasable graph class.
1.1926 + ///
1.1927 + /// This class provides beside the core graph features core erase
1.1928 + /// functions for the graph structure. The main difference between
1.1929 + /// the base and this interface is that the graph alterations
1.1930 + /// should handled already on this level.
1.1931 + template <typename _Base = BaseGraphComponent>
1.1932 + class ErasableGraphComponent : public _Base {
1.1933 + public:
1.1934 +
1.1935 + typedef _Base Base;
1.1936 + typedef typename Base::Node Node;
1.1937 + typedef typename Base::Edge Edge;
1.1938 +
1.1939 + /// \brief Erase a node from the graph.
1.1940 + ///
1.1941 + /// Erase a node from the graph. This function should
1.1942 + /// erase all edges connecting to the node.
1.1943 + void erase(const Node&) {}
1.1944 +
1.1945 + /// \brief Erase an edge from the graph.
1.1946 + ///
1.1947 + /// Erase an edge from the graph.
1.1948 + ///
1.1949 + void erase(const Edge&) {}
1.1950 +
1.1951 + template <typename _Graph>
1.1952 + struct Constraints {
1.1953 + void constraints() {
1.1954 + checkConcept<Base, _Graph>();
1.1955 + typename _Graph::Node node;
1.1956 + graph.erase(node);
1.1957 + typename _Graph::Edge edge;
1.1958 + graph.erase(edge);
1.1959 + }
1.1960 +
1.1961 + _Graph& graph;
1.1962 + };
1.1963 + };
1.1964 +
1.1965 + /// \brief An empty erasable base undirected graph class.
1.1966 + ///
1.1967 + /// This class provides beside the core undirected graph features
1.1968 + /// core erase functions for the undirceted graph structure. The
1.1969 + /// main difference between the base and this interface is that
1.1970 + /// the graph alterations should handled already on this level.
1.1971 + template <typename _Base = BaseUGraphComponent>
1.1972 + class ErasableUGraphComponent : public _Base {
1.1973 + public:
1.1974 +
1.1975 + typedef _Base Base;
1.1976 + typedef typename Base::Node Node;
1.1977 + typedef typename Base::UEdge UEdge;
1.1978 +
1.1979 + /// \brief Erase a node from the graph.
1.1980 + ///
1.1981 + /// Erase a node from the graph. This function should erase
1.1982 + /// edges connecting to the node.
1.1983 + void erase(const Node&) {}
1.1984 +
1.1985 + /// \brief Erase an edge from the graph.
1.1986 + ///
1.1987 + /// Erase an edge from the graph.
1.1988 + ///
1.1989 + void erase(const UEdge&) {}
1.1990 +
1.1991 + template <typename _Graph>
1.1992 + struct Constraints {
1.1993 + void constraints() {
1.1994 + checkConcept<Base, _Graph>();
1.1995 + typename _Graph::Node node;
1.1996 + graph.erase(node);
1.1997 + typename _Graph::Edge edge;
1.1998 + graph.erase(edge);
1.1999 + }
1.2000 +
1.2001 + _Graph& graph;
1.2002 + };
1.2003 + };
1.2004 +
1.2005 + /// \brief An empty erasable base bipartite undirected graph class.
1.2006 + ///
1.2007 + /// This class provides beside the core bipartite undirected graph
1.2008 + /// features core erase functions for the undirceted graph
1.2009 + /// structure. The main difference between the base and this
1.2010 + /// interface is that the graph alterations should handled already
1.2011 + /// on this level.
1.2012 + template <typename _Base = BaseBpUGraphComponent>
1.2013 + class ErasableBpUGraphComponent : public ErasableUGraphComponent<_Base> {
1.2014 + public:
1.2015 +
1.2016 + typedef _Base Base;
1.2017 +
1.2018 + template <typename _Graph>
1.2019 + struct Constraints {
1.2020 + void constraints() {
1.2021 + checkConcept<ErasableUGraphComponent<Base>, _Graph>();
1.2022 + }
1.2023 + };
1.2024 + };
1.2025 +
1.2026 + /// \brief An empty clearable base graph class.
1.2027 + ///
1.2028 + /// This class provides beside the core graph features core clear
1.2029 + /// functions for the graph structure. The main difference between
1.2030 + /// the base and this interface is that the graph alterations
1.2031 + /// should handled already on this level.
1.2032 + template <typename _Base = BaseGraphComponent>
1.2033 + class ClearableGraphComponent : public _Base {
1.2034 + public:
1.2035 +
1.2036 + typedef _Base Base;
1.2037 +
1.2038 + /// \brief Erase all nodes and edges from the graph.
1.2039 + ///
1.2040 + /// Erase all nodes and edges from the graph.
1.2041 + ///
1.2042 + void clear() {}
1.2043 +
1.2044 + template <typename _Graph>
1.2045 + struct Constraints {
1.2046 + void constraints() {
1.2047 + checkConcept<Base, _Graph>();
1.2048 + graph.clear();
1.2049 + }
1.2050 +
1.2051 + _Graph graph;
1.2052 + };
1.2053 + };
1.2054 +
1.2055 + /// \brief An empty clearable base undirected graph class.
1.2056 + ///
1.2057 + /// This class provides beside the core undirected graph features
1.2058 + /// core clear functions for the undirected graph structure. The
1.2059 + /// main difference between the base and this interface is that
1.2060 + /// the graph alterations should handled already on this level.
1.2061 + template <typename _Base = BaseUGraphComponent>
1.2062 + class ClearableUGraphComponent : public ClearableUGraphComponent<_Base> {
1.2063 + public:
1.2064 +
1.2065 + typedef _Base Base;
1.2066 +
1.2067 + template <typename _Graph>
1.2068 + struct Constraints {
1.2069 + void constraints() {
1.2070 + checkConcept<ClearableUGraphComponent<Base>, _Graph>();
1.2071 + }
1.2072 +
1.2073 + _Graph graph;
1.2074 + };
1.2075 + };
1.2076 +
1.2077 + /// \brief An empty clearable base bipartite undirected graph
1.2078 + /// class.
1.2079 + ///
1.2080 + /// This class provides beside the core bipartite undirected graph
1.2081 + /// features core clear functions for the undirected graph
1.2082 + /// structure. The main difference between the base and this
1.2083 + /// interface is that the graph alterations should handled already
1.2084 + /// on this level.
1.2085 + template <typename _Base = BaseUGraphComponent>
1.2086 + class ClearableBpUGraphComponent
1.2087 + : public ClearableBpUGraphComponent<_Base> {
1.2088 + public:
1.2089 +
1.2090 + typedef _Base Base;
1.2091 +
1.2092 + template <typename _Graph>
1.2093 + struct Constraints {
1.2094 + void constraints() {
1.2095 + checkConcept<ClearableBpUGraphComponent<Base>, _Graph>();
1.2096 + }
1.2097 +
1.2098 + };
1.2099 +
1.2100 + };
1.2101 +
1.2102 + }
1.2103 +
1.2104 +}
1.2105 +
1.2106 +#endif