1.1 --- a/src/lemon/concept/graph_component.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,982 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/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