1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concept/graph_component.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,982 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +///\ingroup graph_concepts
1.21 +///\file
1.22 +///\brief The graph components.
1.23 +
1.24 +
1.25 +#ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
1.26 +#define LEMON_CONCEPT_GRAPH_COMPONENT_H
1.27 +
1.28 +#include <lemon/invalid.h>
1.29 +#include <lemon/concept/maps.h>
1.30 +
1.31 +#include <lemon/bits/alteration_notifier.h>
1.32 +
1.33 +namespace lemon {
1.34 + namespace concept {
1.35 +
1.36 + /// \addtogroup graph_concepts
1.37 + /// @{
1.38 +
1.39 + /**************** Graph iterator concepts ****************/
1.40 +
1.41 + /// Skeleton class for graph Node and Edge types
1.42 +
1.43 + /// This class describes the interface of Node and Edge (and UndirEdge
1.44 + /// in undirected graphs) subtypes of graph types.
1.45 + ///
1.46 + /// \note This class is a template class so that we can use it to
1.47 + /// create graph skeleton classes. The reason for this is than Node
1.48 + /// and Edge types should \em not derive from the same base class.
1.49 + /// For Node you should instantiate it with character 'n' and for Edge
1.50 + /// with 'e'.
1.51 +
1.52 +#ifndef DOXYGEN
1.53 + template <char _selector = '0'>
1.54 +#endif
1.55 + class GraphItem {
1.56 + public:
1.57 + /// Default constructor.
1.58 +
1.59 + /// \warning The default constructor is not required to set
1.60 + /// the item to some well-defined value. So you should consider it
1.61 + /// as uninitialized.
1.62 + GraphItem() {}
1.63 + /// Copy constructor.
1.64 +
1.65 + /// Copy constructor.
1.66 + ///
1.67 + GraphItem(GraphItem const&) {}
1.68 + /// Invalid constructor \& conversion.
1.69 +
1.70 + /// This constructor initializes the item to be invalid.
1.71 + /// \sa Invalid for more details.
1.72 + GraphItem(Invalid) {}
1.73 + /// Assign operator for nodes.
1.74 +
1.75 + /// The nodes are assignable.
1.76 + ///
1.77 + GraphItem& operator=(GraphItem const&) { return *this; }
1.78 + /// Equality operator.
1.79 +
1.80 + /// Two iterators are equal if and only if they represents the
1.81 + /// same node in the graph or both are invalid.
1.82 + bool operator==(GraphItem) const { return false; }
1.83 + /// Inequality operator.
1.84 +
1.85 + /// \sa operator==(const Node& n)
1.86 + ///
1.87 + bool operator!=(GraphItem) const { return false; }
1.88 +
1.89 + /// Artificial ordering operator.
1.90 +
1.91 + /// To allow the use of graph descriptors as key type in std::map or
1.92 + /// similar associative container we require this.
1.93 + ///
1.94 + /// \note This operator only have to define some strict ordering of
1.95 + /// the items; this order has nothing to do with the iteration
1.96 + /// ordering of the items.
1.97 + ///
1.98 + /// \bug This is a technical requirement. Do we really need this?
1.99 + bool operator<(GraphItem) const { return false; }
1.100 +
1.101 + template<typename _GraphItem>
1.102 + struct Constraints {
1.103 + void constraints() {
1.104 + _GraphItem i1;
1.105 + _GraphItem i2 = i1;
1.106 + _GraphItem i3 = INVALID;
1.107 +
1.108 + i1 = i2 = i3;
1.109 +
1.110 + bool b;
1.111 + // b = (ia == ib) && (ia != ib) && (ia < ib);
1.112 + b = (ia == ib) && (ia != ib);
1.113 + b = (ia == INVALID) && (ib != INVALID);
1.114 + // b = (ia < ib);
1.115 + }
1.116 +
1.117 + const _GraphItem &ia;
1.118 + const _GraphItem &ib;
1.119 + };
1.120 + };
1.121 +
1.122 + /// A type describing the concept of graph node
1.123 +
1.124 + /// This is an instantiation of \ref GraphItem which can be used as a
1.125 + /// Node subtype in graph skeleton definitions
1.126 + typedef GraphItem<'n'> GraphNode;
1.127 +
1.128 + /// A type describing the concept of graph edge
1.129 +
1.130 + /// This is an instantiation of \ref GraphItem which can be used as a
1.131 + /// Edge subtype in graph skeleton definitions
1.132 + typedef GraphItem<'e'> GraphEdge;
1.133 +
1.134 +
1.135 + /**************** Basic features of graphs ****************/
1.136 +
1.137 + /// An empty base graph class.
1.138 +
1.139 + /// This class provides the minimal set of features needed for a graph
1.140 + /// structure. All graph concepts have to be conform to this base
1.141 + /// graph.
1.142 + ///
1.143 + /// \bug This is not true. The minimal graph concept is the
1.144 + /// BaseIterableGraphComponent.
1.145 +
1.146 + class BaseGraphComponent {
1.147 + public:
1.148 +
1.149 + typedef BaseGraphComponent Graph;
1.150 +
1.151 + /// Node class of the graph.
1.152 +
1.153 + /// This class represents the Nodes of the graph.
1.154 + ///
1.155 + typedef GraphItem<'n'> Node;
1.156 +
1.157 + /// Edge class of the graph.
1.158 +
1.159 + /// This class represents the Edges of the graph.
1.160 + ///
1.161 + typedef GraphItem<'e'> Edge;
1.162 +
1.163 + ///Gives back the target node of an edge.
1.164 +
1.165 + ///Gives back the target node of an edge.
1.166 + ///
1.167 + Node target(const Edge&) const { return INVALID;}
1.168 +
1.169 + ///Gives back the source node of an edge.
1.170 +
1.171 + ///Gives back the source node of an edge.
1.172 + ///
1.173 + Node source(const Edge&) const { return INVALID;}
1.174 +
1.175 +
1.176 + template <typename _Graph>
1.177 + struct Constraints {
1.178 + typedef typename _Graph::Node Node;
1.179 + typedef typename _Graph::Edge Edge;
1.180 +
1.181 + void constraints() {
1.182 + checkConcept<GraphItem<'n'>, Node>();
1.183 + checkConcept<GraphItem<'e'>, Edge>();
1.184 + {
1.185 + Node n;
1.186 + Edge e;
1.187 + n = graph.source(e);
1.188 + n = graph.target(e);
1.189 + }
1.190 + }
1.191 +
1.192 + const _Graph& graph;
1.193 + };
1.194 + };
1.195 +
1.196 + /// An empty iterable base graph class.
1.197 +
1.198 + /// This class provides beside the core graph features
1.199 + /// core iterable interface for the graph structure.
1.200 + /// Most of the base graphs should be conform to this concept.
1.201 +
1.202 + class BaseIterableGraphComponent : virtual public BaseGraphComponent {
1.203 + public:
1.204 +
1.205 + typedef BaseGraphComponent::Node Node;
1.206 + typedef BaseGraphComponent::Edge Edge;
1.207 +
1.208 + /// Gives back the first Node in the iterating order.
1.209 +
1.210 + /// Gives back the first Node in the iterating order.
1.211 + ///
1.212 + void first(Node&) const {}
1.213 +
1.214 + /// Gives back the next Node in the iterating order.
1.215 +
1.216 + /// Gives back the next Node in the iterating order.
1.217 + ///
1.218 + void next(Node&) const {}
1.219 +
1.220 + /// Gives back the first Edge in the iterating order.
1.221 +
1.222 + /// Gives back the first Edge in the iterating order.
1.223 + ///
1.224 + void first(Edge&) const {}
1.225 + /// Gives back the next Edge in the iterating order.
1.226 +
1.227 + /// Gives back the next Edge in the iterating order.
1.228 + ///
1.229 + void next(Edge&) const {}
1.230 +
1.231 +
1.232 + /// Gives back the first of the Edges point to the given Node.
1.233 +
1.234 + /// Gives back the first of the Edges point to the given Node.
1.235 + ///
1.236 + void firstIn(Edge&, const Node&) const {}
1.237 +
1.238 + /// Gives back the next of the Edges points to the given Node.
1.239 +
1.240 +
1.241 + /// Gives back the next of the Edges points to the given Node.
1.242 + ///
1.243 + void nextIn(Edge&) const {}
1.244 +
1.245 + /// Gives back the first of the Edges start from the given Node.
1.246 +
1.247 + /// Gives back the first of the Edges start from the given Node.
1.248 + ///
1.249 + void firstOut(Edge&, const Node&) const {}
1.250 +
1.251 + /// Gives back the next of the Edges start from the given Node.
1.252 +
1.253 + /// Gives back the next of the Edges start from the given Node.
1.254 + ///
1.255 + void nextOut(Edge&) const {}
1.256 +
1.257 +
1.258 + template <typename _Graph>
1.259 + struct Constraints {
1.260 +
1.261 + void constraints() {
1.262 + checkConcept< BaseGraphComponent, _Graph >();
1.263 + typename _Graph::Node node;
1.264 + typename _Graph::Edge edge;
1.265 + {
1.266 + graph.first(node);
1.267 + graph.next(node);
1.268 + }
1.269 + {
1.270 + graph.first(edge);
1.271 + graph.next(edge);
1.272 + }
1.273 + {
1.274 + graph.firstIn(edge, node);
1.275 + graph.nextIn(edge);
1.276 + }
1.277 + {
1.278 + graph.firstOut(edge, node);
1.279 + graph.nextOut(edge);
1.280 + }
1.281 + }
1.282 +
1.283 + const _Graph& graph;
1.284 + };
1.285 + };
1.286 +
1.287 + /// An empty idable base graph class.
1.288 +
1.289 + /// This class provides beside the core graph features
1.290 + /// core id functions for the graph structure.
1.291 + /// The most of the base graphs should be conform to this concept.
1.292 + /// The id's are unique and immutable.
1.293 + class IDableGraphComponent : virtual public BaseGraphComponent {
1.294 + public:
1.295 +
1.296 + typedef BaseGraphComponent::Node Node;
1.297 + typedef BaseGraphComponent::Edge Edge;
1.298 +
1.299 + /// Gives back an unique integer id for the Node.
1.300 +
1.301 + /// Gives back an unique integer id for the Node.
1.302 + ///
1.303 + int id(const Node&) const { return -1;}
1.304 +
1.305 + /// \brief Gives back the node by the unique id.
1.306 + ///
1.307 + /// Gives back the node by the unique id.
1.308 + /// If the graph does not contain node with the given id
1.309 + /// then the result of the function is undetermined.
1.310 + Node fromId(int , Node) const { return INVALID;}
1.311 +
1.312 + /// \brief Gives back an unique integer id for the Edge.
1.313 + ///
1.314 + /// Gives back an unique integer id for the Edge.
1.315 + ///
1.316 + int id(const Edge&) const { return -1;}
1.317 +
1.318 + /// \brief Gives back the edge by the unique id.
1.319 + ///
1.320 + /// Gives back the edge by the unique id.
1.321 + /// If the graph does not contain edge with the given id
1.322 + /// then the result of the function is undetermined.
1.323 + Edge fromId(int, Edge) const { return INVALID;}
1.324 +
1.325 + template <typename _Graph>
1.326 + struct Constraints {
1.327 +
1.328 + void constraints() {
1.329 + checkConcept< BaseGraphComponent, _Graph >();
1.330 + typename _Graph::Node node;
1.331 + int nid = graph.id(node);
1.332 + nid = graph.id(node);
1.333 + node = graph.fromId(nid, Node());
1.334 + typename _Graph::Edge edge;
1.335 + int eid = graph.id(edge);
1.336 + eid = graph.id(edge);
1.337 + edge = graph.fromId(eid, Edge());
1.338 + }
1.339 +
1.340 + const _Graph& graph;
1.341 + };
1.342 + };
1.343 +
1.344 +
1.345 + /// An empty max-idable base graph class.
1.346 +
1.347 + /// This class provides beside the core graph features
1.348 + /// core max id functions for the graph structure.
1.349 + /// The most of the base graphs should be conform to this concept.
1.350 + /// The id's are unique and immutable.
1.351 + class MaxIDableGraphComponent : virtual public BaseGraphComponent {
1.352 + public:
1.353 +
1.354 + /// Gives back an integer greater or equal to the maximum Node id.
1.355 +
1.356 + /// Gives back an integer greater or equal to the maximum Node id.
1.357 + ///
1.358 + int maxId(Node = INVALID) const { return -1;}
1.359 +
1.360 + /// Gives back an integer greater or equal to the maximum Edge id.
1.361 +
1.362 + /// Gives back an integer greater or equal to the maximum Edge id.
1.363 + ///
1.364 + int maxId(Edge = INVALID) const { return -1;}
1.365 +
1.366 + template <typename _Graph>
1.367 + struct Constraints {
1.368 +
1.369 + void constraints() {
1.370 + checkConcept<BaseGraphComponent, _Graph>();
1.371 + int nid = graph.maxId(typename _Graph::Node());
1.372 + ignore_unused_variable_warning(nid);
1.373 + int eid = graph.maxId(typename _Graph::Edge());
1.374 + ignore_unused_variable_warning(eid);
1.375 + }
1.376 +
1.377 + const _Graph& graph;
1.378 + };
1.379 + };
1.380 +
1.381 + /// An empty extendable base graph class.
1.382 +
1.383 + /// This class provides beside the core graph features
1.384 + /// core graph extend interface for the graph structure.
1.385 + /// The most of the base graphs should be conform to this concept.
1.386 + class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
1.387 + public:
1.388 +
1.389 + typedef BaseGraphComponent::Node Node;
1.390 + typedef BaseGraphComponent::Edge Edge;
1.391 +
1.392 + /// Adds a new Node to the graph.
1.393 +
1.394 + /// Adds a new Node to the graph.
1.395 + ///
1.396 + Node addNode() {
1.397 + return INVALID;
1.398 + }
1.399 +
1.400 + /// Adds a new Edge connects the two Nodes to the graph.
1.401 +
1.402 + /// Adds a new Edge connects the two Nodes to the graph.
1.403 + ///
1.404 + Edge addEdge(const Node&, const Node&) {
1.405 + return INVALID;
1.406 + }
1.407 +
1.408 + template <typename _Graph>
1.409 + struct Constraints {
1.410 + void constraints() {
1.411 + checkConcept<BaseGraphComponent, _Graph >();
1.412 + typename _Graph::Node node_a, node_b;
1.413 + node_a = graph.addNode();
1.414 + typename _Graph::Edge edge;
1.415 + edge = graph.addEdge(node_a, node_b);
1.416 + }
1.417 +
1.418 + _Graph& graph;
1.419 + };
1.420 + };
1.421 +
1.422 + /// An empty erasable base graph class.
1.423 +
1.424 + /// This class provides beside the core graph features
1.425 + /// core erase functions for the graph structure.
1.426 + /// The most of the base graphs should be conform to this concept.
1.427 + class BaseErasableGraphComponent : virtual public BaseGraphComponent {
1.428 + public:
1.429 +
1.430 + typedef BaseGraphComponent::Node Node;
1.431 + typedef BaseGraphComponent::Edge Edge;
1.432 +
1.433 + /// Erase a Node from the graph.
1.434 +
1.435 + /// Erase a Node from the graph. This function should not
1.436 + /// erase edges connecting to the Node.
1.437 + void erase(const Node&) {}
1.438 +
1.439 + /// Erase an Edge from the graph.
1.440 +
1.441 + /// Erase an Edge from the graph.
1.442 + ///
1.443 + void erase(const Edge&) {}
1.444 +
1.445 + template <typename _Graph>
1.446 + struct Constraints {
1.447 + void constraints() {
1.448 + checkConcept<BaseGraphComponent, _Graph>();
1.449 + typename _Graph::Node node;
1.450 + graph.erase(node);
1.451 + typename _Graph::Edge edge;
1.452 + graph.erase(edge);
1.453 + }
1.454 +
1.455 + _Graph& graph;
1.456 + };
1.457 + };
1.458 +
1.459 + /// An empty clearable base graph class.
1.460 +
1.461 + /// This class provides beside the core graph features
1.462 + /// core clear functions for the graph structure.
1.463 + /// The most of the base graphs should be conform to this concept.
1.464 + class ClearableGraphComponent : virtual public BaseGraphComponent {
1.465 + public:
1.466 +
1.467 + /// Erase all the Nodes and Edges from the graph.
1.468 +
1.469 + /// Erase all the Nodes and Edges from the graph.
1.470 + ///
1.471 + void clear() {}
1.472 +
1.473 + template <typename _Graph>
1.474 + struct Constraints {
1.475 + void constraints() {
1.476 + checkConcept<BaseGraphComponent, _Graph>();
1.477 + graph.clear();
1.478 + }
1.479 +
1.480 + _Graph graph;
1.481 + };
1.482 + };
1.483 +
1.484 +
1.485 + /// Skeleton class for graph NodeIt and EdgeIt
1.486 +
1.487 + /// Skeleton class for graph NodeIt and EdgeIt.
1.488 + ///
1.489 + template <typename _Graph, typename _Item>
1.490 + class GraphIterator : public _Item {
1.491 + public:
1.492 + /// \todo Don't we need the Item type as typedef?
1.493 +
1.494 + /// Default constructor.
1.495 +
1.496 + /// @warning The default constructor sets the iterator
1.497 + /// to an undefined value.
1.498 + GraphIterator() {}
1.499 + /// Copy constructor.
1.500 +
1.501 + /// Copy constructor.
1.502 + ///
1.503 + GraphIterator(GraphIterator const&) {}
1.504 + /// Sets the iterator to the first item.
1.505 +
1.506 + /// Sets the iterator to the first item of \c the graph.
1.507 + ///
1.508 + explicit GraphIterator(const _Graph&) {}
1.509 + /// Invalid constructor \& conversion.
1.510 +
1.511 + /// This constructor initializes the item to be invalid.
1.512 + /// \sa Invalid for more details.
1.513 + GraphIterator(Invalid) {}
1.514 + /// Assign operator for items.
1.515 +
1.516 + /// The items are assignable.
1.517 + ///
1.518 + GraphIterator& operator=(GraphIterator const&) { return *this; }
1.519 + /// Next item.
1.520 +
1.521 + /// Assign the iterator to the next item.
1.522 + ///
1.523 + GraphIterator& operator++() { return *this; }
1.524 + // Node operator*() const { return INVALID; }
1.525 + /// Equality operator
1.526 +
1.527 + /// Two iterators are equal if and only if they point to the
1.528 + /// same object or both are invalid.
1.529 + bool operator==(const GraphIterator&) const { return true;}
1.530 + /// Inequality operator
1.531 +
1.532 + /// \sa operator==(Node n)
1.533 + ///
1.534 + bool operator!=(const GraphIterator&) const { return true;}
1.535 +
1.536 + template<typename _GraphIterator>
1.537 + struct Constraints {
1.538 + void constraints() {
1.539 + // checkConcept< Item, _GraphIterator >();
1.540 + _GraphIterator it1(g);
1.541 +
1.542 + /// \todo Do we need NodeIt(Node) kind of constructor?
1.543 + // _GraphIterator it2(bj);
1.544 + _GraphIterator it2;
1.545 +
1.546 + it2 = ++it1;
1.547 + ++it2 = it1;
1.548 + ++(++it1);
1.549 + /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
1.550 + _Item bi = it1;
1.551 + bi = it2;
1.552 + }
1.553 + _Graph& g;
1.554 + };
1.555 + };
1.556 +
1.557 + /// Skeleton class for graph InEdgeIt and OutEdgeIt
1.558 +
1.559 + /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
1.560 + /// base class, the _selector is a additional template parameter. For
1.561 + /// InEdgeIt you should instantiate it with character 'i' and for
1.562 + /// OutEdgeIt with 'o'.
1.563 + /// \todo Is this a good name for this concept?
1.564 + template <typename Graph,
1.565 + typename Edge = typename Graph::Edge,
1.566 + char _selector = '0'>
1.567 + class GraphIncIterator : public Edge {
1.568 + public:
1.569 + /// Default constructor.
1.570 +
1.571 + /// @warning The default constructor sets the iterator
1.572 + /// to an undefined value.
1.573 + GraphIncIterator() {}
1.574 + /// Copy constructor.
1.575 +
1.576 + /// Copy constructor.
1.577 + ///
1.578 + GraphIncIterator(GraphIncIterator const& gi) :Edge(gi) {}
1.579 + /// Sets the iterator to the first edge incoming into or outgoing
1.580 + /// from the node.
1.581 +
1.582 + /// Sets the iterator to the first edge incoming into or outgoing
1.583 + /// from the node.
1.584 + ///
1.585 + explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
1.586 + /// Invalid constructor \& conversion.
1.587 +
1.588 + /// This constructor initializes the item to be invalid.
1.589 + /// \sa Invalid for more details.
1.590 + GraphIncIterator(Invalid) {}
1.591 + /// Assign operator for nodes.
1.592 +
1.593 + /// The nodes are assignable.
1.594 + ///
1.595 + GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }
1.596 + /// Next edge.
1.597 +
1.598 + /// Assign the iterator to the next node.
1.599 + ///
1.600 + GraphIncIterator& operator++() { return *this; }
1.601 +
1.602 + // Node operator*() const { return INVALID; }
1.603 +
1.604 + /// Equality operator
1.605 +
1.606 + /// Two iterators are equal if and only if they point to the
1.607 + /// same object or both are invalid.
1.608 + bool operator==(const GraphIncIterator&) const { return true;}
1.609 +
1.610 + /// Inequality operator
1.611 +
1.612 + /// \sa operator==(Node n)
1.613 + ///
1.614 + bool operator!=(const GraphIncIterator&) const { return true;}
1.615 +
1.616 + template <typename _GraphIncIterator>
1.617 + struct Constraints {
1.618 + typedef typename Graph::Node Node;
1.619 + void constraints() {
1.620 + checkConcept<GraphItem<'e'>, _GraphIncIterator>();
1.621 + _GraphIncIterator it1(graph, node);
1.622 + /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
1.623 + // _GraphIncIterator it2(edge);
1.624 + _GraphIncIterator it2;
1.625 +
1.626 + it2 = ++it1;
1.627 + ++it2 = it1;
1.628 + ++(++it1);
1.629 + Edge e = it1;
1.630 + e = it2;
1.631 +
1.632 + const_constraits();
1.633 + }
1.634 +
1.635 + void const_constraits() {
1.636 + Node n = graph.baseNode(it);
1.637 + n = graph.runningNode(it);
1.638 + }
1.639 +
1.640 + Edge edge;
1.641 + Node node;
1.642 + Graph graph;
1.643 + _GraphIncIterator it;
1.644 + };
1.645 + };
1.646 +
1.647 +
1.648 + /// An empty iterable base graph class.
1.649 +
1.650 + /// This class provides beside the core graph features
1.651 + /// iterator based iterable interface for the graph structure.
1.652 + /// This concept is part of the StaticGraphConcept.
1.653 + class IterableGraphComponent : virtual public BaseGraphComponent {
1.654 +
1.655 + public:
1.656 +
1.657 + typedef IterableGraphComponent Graph;
1.658 +
1.659 + typedef BaseGraphComponent::Node Node;
1.660 + typedef BaseGraphComponent::Edge Edge;
1.661 +
1.662 + /// This iterator goes through each node.
1.663 +
1.664 + /// This iterator goes through each node.
1.665 + ///
1.666 + typedef GraphIterator<Graph, Node> NodeIt;
1.667 + /// This iterator goes through each node.
1.668 +
1.669 + /// This iterator goes through each node.
1.670 + ///
1.671 + typedef GraphIterator<Graph, Edge> EdgeIt;
1.672 + /// This iterator goes trough the incoming edges of a node.
1.673 +
1.674 + /// This iterator goes trough the \e inccoming edges of a certain node
1.675 + /// of a graph.
1.676 + typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
1.677 + /// This iterator goes trough the outgoing edges of a node.
1.678 +
1.679 + /// This iterator goes trough the \e outgoing edges of a certain node
1.680 + /// of a graph.
1.681 + typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
1.682 + };
1.683 +
1.684 + template <typename _Graph>
1.685 + struct Constraints {
1.686 + void constraints() {
1.687 + checkConcept< BaseGraphComponent, _Graph>();
1.688 +
1.689 + checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
1.690 + typename _Graph::EdgeIt >();
1.691 + checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
1.692 + typename _Graph::NodeIt >();
1.693 + checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
1.694 + checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
1.695 + }
1.696 + };
1.697 +
1.698 + /// An empty alteration notifier base graph class.
1.699 +
1.700 + /// This class provides beside the core graph features
1.701 + /// alteration notifier interface for the graph structure.
1.702 + /// This is an observer-notifier pattern. More Obsevers can
1.703 + /// be registered into the notifier and whenever an alteration
1.704 + /// occured in the graph all the observers will notified about it.
1.705 + class AlterableGraphComponent : virtual public BaseGraphComponent {
1.706 + public:
1.707 +
1.708 + /// The edge observer registry.
1.709 + typedef AlterationNotifier<Edge> EdgeNotifier;
1.710 + /// The node observer registry.
1.711 + typedef AlterationNotifier<Node> NodeNotifier;
1.712 +
1.713 + /// \brief Gives back the edge alteration notifier.
1.714 + ///
1.715 + /// Gives back the edge alteration notifier.
1.716 + EdgeNotifier getNotifier(Edge) const {
1.717 + return EdgeNotifier();
1.718 + }
1.719 +
1.720 + /// \brief Gives back the node alteration notifier.
1.721 + ///
1.722 + /// Gives back the node alteration notifier.
1.723 + NodeNotifier getNotifier(Node) const {
1.724 + return NodeNotifier();
1.725 + }
1.726 +
1.727 + };
1.728 +
1.729 +
1.730 + /// Class describing the concept of graph maps
1.731 +
1.732 + /// This class describes the common interface of the graph maps
1.733 + /// (NodeMap, EdgeMap), that is \ref maps-pages "maps" which can be used to
1.734 + /// associate data to graph descriptors (nodes or edges).
1.735 + template <typename Graph, typename Item, typename _Value>
1.736 + class GraphMap : public ReadWriteMap<Item, _Value> {
1.737 + protected:
1.738 + GraphMap() {}
1.739 + public:
1.740 + /// \brief Construct a new map.
1.741 + ///
1.742 + /// Construct a new map for the graph.
1.743 + explicit GraphMap(const Graph&) {}
1.744 + /// \brief Construct a new map with default value.
1.745 + ///
1.746 + /// Construct a new map for the graph and initalise the values.
1.747 + GraphMap(const Graph&, const _Value&) {}
1.748 + /// \brief Copy constructor.
1.749 + ///
1.750 + /// Copy Constructor.
1.751 + GraphMap(const GraphMap& gm) :ReadWriteMap<Item, _Value>(gm) {}
1.752 +
1.753 + /// \brief Assign operator.
1.754 + ///
1.755 + /// Assign operator.
1.756 + GraphMap& operator=(const GraphMap&) { return *this;}
1.757 +
1.758 + template<typename _Map>
1.759 + struct Constraints {
1.760 + void constraints() {
1.761 + checkConcept<ReadWriteMap<Item, _Value>, _Map >();
1.762 + // Construction with a graph parameter
1.763 + _Map a(g);
1.764 + // Constructor with a graph and a default value parameter
1.765 + _Map a2(g,t);
1.766 + // Copy constructor. Do we need it?
1.767 + _Map b=c;
1.768 + // Copy operator. Do we need it?
1.769 + a=b;
1.770 +
1.771 + ignore_unused_variable_warning(a2);
1.772 + }
1.773 +
1.774 + const _Map &c;
1.775 + const Graph &g;
1.776 + const typename GraphMap::Value &t;
1.777 + };
1.778 +
1.779 + };
1.780 +
1.781 + /// An empty mappable base graph class.
1.782 +
1.783 + /// This class provides beside the core graph features
1.784 + /// map interface for the graph structure.
1.785 + /// This concept is part of the StaticGraphConcept.
1.786 + class MappableGraphComponent : virtual public BaseGraphComponent {
1.787 + public:
1.788 +
1.789 + typedef MappableGraphComponent Graph;
1.790 +
1.791 + typedef BaseGraphComponent::Node Node;
1.792 + typedef BaseGraphComponent::Edge Edge;
1.793 +
1.794 + /// ReadWrite map of the nodes.
1.795 +
1.796 + /// ReadWrite map of the nodes.
1.797 + ///
1.798 + template <typename _Value>
1.799 + class NodeMap : public GraphMap<Graph, Node, _Value> {
1.800 + private:
1.801 + NodeMap();
1.802 + public:
1.803 + /// \brief Construct a new map.
1.804 + ///
1.805 + /// Construct a new map for the graph.
1.806 + /// \todo call the right parent class constructor
1.807 + explicit NodeMap(const Graph&) {}
1.808 + /// \brief Construct a new map with default value.
1.809 + ///
1.810 + /// Construct a new map for the graph and initalise the values.
1.811 + NodeMap(const Graph&, const _Value&) {}
1.812 + /// \brief Copy constructor.
1.813 + ///
1.814 + /// Copy Constructor.
1.815 + NodeMap(const NodeMap& nm) : GraphMap<Graph, Node, _Value>(nm) {}
1.816 +
1.817 + /// \brief Assign operator.
1.818 + ///
1.819 + /// Assign operator.
1.820 + NodeMap& operator=(const NodeMap&) { return *this;}
1.821 +
1.822 + };
1.823 +
1.824 + /// ReadWrite map of the edges.
1.825 +
1.826 + /// ReadWrite map of the edges.
1.827 + ///
1.828 + template <typename _Value>
1.829 + class EdgeMap : public GraphMap<Graph, Edge, _Value> {
1.830 + private:
1.831 + EdgeMap();
1.832 + public:
1.833 + /// \brief Construct a new map.
1.834 + ///
1.835 + /// Construct a new map for the graph.
1.836 + /// \todo call the right parent class constructor
1.837 + explicit EdgeMap(const Graph&) {}
1.838 + /// \brief Construct a new map with default value.
1.839 + ///
1.840 + /// Construct a new map for the graph and initalise the values.
1.841 + EdgeMap(const Graph&, const _Value&) {}
1.842 + /// \brief Copy constructor.
1.843 + ///
1.844 + /// Copy Constructor.
1.845 + EdgeMap(const EdgeMap& em) :GraphMap<Graph, Edge, _Value>(em) {}
1.846 +
1.847 + /// \brief Assign operator.
1.848 + ///
1.849 + /// Assign operator.
1.850 + EdgeMap& operator=(const EdgeMap&) { return *this;}
1.851 +
1.852 + };
1.853 +
1.854 + template <typename _Graph>
1.855 + struct Constraints {
1.856 +
1.857 + struct Type {
1.858 + int value;
1.859 + Type() : value(0) {}
1.860 + Type(int _v) : value(_v) {}
1.861 + };
1.862 +
1.863 + void constraints() {
1.864 + checkConcept<BaseGraphComponent, _Graph>();
1.865 + { // int map test
1.866 + typedef typename _Graph::template NodeMap<int> IntNodeMap;
1.867 + checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
1.868 + IntNodeMap >();
1.869 + } { // bool map test
1.870 + typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
1.871 + checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
1.872 + BoolNodeMap >();
1.873 + } { // Type map test
1.874 + typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
1.875 + checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
1.876 + TypeNodeMap >();
1.877 + }
1.878 +
1.879 + { // int map test
1.880 + typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1.881 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1.882 + IntEdgeMap >();
1.883 + } { // bool map test
1.884 + typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1.885 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1.886 + BoolEdgeMap >();
1.887 + } { // Type map test
1.888 + typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
1.889 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>,
1.890 + TypeEdgeMap >();
1.891 + }
1.892 + }
1.893 +
1.894 + _Graph& graph;
1.895 + };
1.896 + };
1.897 +
1.898 + /// \brief An empty extendable extended graph class.
1.899 + ///
1.900 + /// This class provides beside the core graph features
1.901 + /// item addition interface for the graph structure.
1.902 + /// The difference between this class and the
1.903 + /// \c BaseExtendableGraphComponent is that it should
1.904 + /// notify the item alteration observers.
1.905 + class ExtendableGraphComponent : virtual public BaseGraphComponent {
1.906 + public:
1.907 +
1.908 + typedef ExtendableGraphComponent Graph;
1.909 +
1.910 + typedef BaseGraphComponent::Node Node;
1.911 + typedef BaseGraphComponent::Edge Edge;
1.912 +
1.913 + /// \brief Add a node to the graph.
1.914 + ///
1.915 + /// Add a node to the graph and notify the observers.
1.916 + Node addNode() {
1.917 + return INVALID;
1.918 + }
1.919 +
1.920 + /// \brief Add an edge to the graph.
1.921 + ///
1.922 + /// Add an edge to the graph and notify the observers.
1.923 + Edge addEdge(const Node&, const Node&) {
1.924 + return INVALID;
1.925 + }
1.926 +
1.927 + template <typename _Graph>
1.928 + struct Constraints {
1.929 + void constraints() {
1.930 + checkConcept<BaseGraphComponent, _Graph >();
1.931 + typename _Graph::Node node_a, node_b;
1.932 + node_a = graph.addNode();
1.933 + typename _Graph::Edge edge;
1.934 + edge = graph.addEdge(node_a, node_b);
1.935 + }
1.936 + _Graph& graph;
1.937 + };
1.938 + };
1.939 +
1.940 + /// \brief An empty erasable extended graph class.
1.941 + ///
1.942 + /// This class provides beside the core graph features
1.943 + /// item erase interface for the graph structure.
1.944 + /// The difference between this class and the
1.945 + /// \c BaseErasableGraphComponent is that it should
1.946 + /// notify the item alteration observers.
1.947 + class ErasableGraphComponent : virtual public BaseGraphComponent {
1.948 + public:
1.949 +
1.950 + typedef ErasableGraphComponent Graph;
1.951 +
1.952 + typedef BaseGraphComponent::Node Node;
1.953 + typedef BaseGraphComponent::Edge Edge;
1.954 +
1.955 + /// \brief Erase the Node and notify the node alteration observers.
1.956 + ///
1.957 + /// Erase the Node and notify the node alteration observers.
1.958 + void erase(const Node&) {}
1.959 +
1.960 + /// \brief Erase the Edge and notify the edge alteration observers.
1.961 + ///
1.962 + /// Erase the Edge and notify the edge alteration observers.
1.963 + void erase(const Edge&) {}
1.964 +
1.965 + template <typename _Graph>
1.966 + struct Constraints {
1.967 + void constraints() {
1.968 + checkConcept<BaseGraphComponent, _Graph >();
1.969 + typename _Graph::Node node;
1.970 + graph.erase(node);
1.971 + typename _Graph::Edge edge;
1.972 + graph.erase(edge);
1.973 + }
1.974 +
1.975 + _Graph& graph;
1.976 + };
1.977 + };
1.978 +
1.979 + /// @}
1.980 +
1.981 + }
1.982 +
1.983 +}
1.984 +
1.985 +#endif