1.1 --- a/lemon/Makefile.am Tue Jul 11 14:42:06 2006 +0000
1.2 +++ b/lemon/Makefile.am Tue Jul 11 15:42:15 2006 +0000
1.3 @@ -114,7 +114,7 @@
1.4 lemon/concept_check.h \
1.5 lemon/concept/bpugraph.h \
1.6 lemon/concept/graph.h \
1.7 - lemon/concept/graph_component.h \
1.8 + lemon/concept/graph_components.h \
1.9 lemon/concept/heap.h \
1.10 lemon/concept/maps.h \
1.11 lemon/concept/matrix_maps.h \
2.1 --- a/lemon/concept/bpugraph.h Tue Jul 11 14:42:06 2006 +0000
2.2 +++ b/lemon/concept/bpugraph.h Tue Jul 11 15:42:15 2006 +0000
2.3 @@ -24,7 +24,7 @@
2.4 #ifndef LEMON_CONCEPT_BPUGRAPH_H
2.5 #define LEMON_CONCEPT_BPUGRAPH_H
2.6
2.7 -#include <lemon/concept/graph_component.h>
2.8 +#include <lemon/concept/graph_components.h>
2.9
2.10 #include <lemon/concept/graph.h>
2.11 #include <lemon/concept/ugraph.h>
3.1 --- a/lemon/concept/graph.h Tue Jul 11 14:42:06 2006 +0000
3.2 +++ b/lemon/concept/graph.h Tue Jul 11 15:42:15 2006 +0000
3.3 @@ -27,7 +27,7 @@
3.4 #include <lemon/bits/utility.h>
3.5 #include <lemon/concept/maps.h>
3.6 #include <lemon/concept_check.h>
3.7 -#include <lemon/concept/graph_component.h>
3.8 +#include <lemon/concept/graph_components.h>
3.9
3.10 namespace lemon {
3.11 namespace concept {
4.1 --- a/lemon/concept/graph_component.h Tue Jul 11 14:42:06 2006 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,1720 +0,0 @@
4.4 -/* -*- C++ -*-
4.5 - *
4.6 - * This file is a part of LEMON, a generic C++ optimization library
4.7 - *
4.8 - * Copyright (C) 2003-2006
4.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 - *
4.12 - * Permission to use, modify and distribute this software is granted
4.13 - * provided that this copyright notice appears in all copies. For
4.14 - * precise terms see the accompanying LICENSE file.
4.15 - *
4.16 - * This software is provided "AS IS" with no warranty of any kind,
4.17 - * express or implied, and with no claim as to its suitability for any
4.18 - * purpose.
4.19 - *
4.20 - */
4.21 -
4.22 -///\ingroup graph_concepts
4.23 -///\file
4.24 -///\brief The graph components.
4.25 -
4.26 -
4.27 -#ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
4.28 -#define LEMON_CONCEPT_GRAPH_COMPONENT_H
4.29 -
4.30 -#include <lemon/bits/invalid.h>
4.31 -#include <lemon/concept/maps.h>
4.32 -
4.33 -#include <lemon/bits/alteration_notifier.h>
4.34 -
4.35 -namespace lemon {
4.36 - namespace concept {
4.37 -
4.38 - /// \brief Skeleton class for graph Node and Edge types
4.39 - ///
4.40 - /// This class describes the interface of Node and Edge (and UEdge
4.41 - /// in undirected graphs) subtypes of graph types.
4.42 - ///
4.43 - /// \note This class is a template class so that we can use it to
4.44 - /// create graph skeleton classes. The reason for this is than Node
4.45 - /// and Edge types should \em not derive from the same base class.
4.46 - /// For Node you should instantiate it with character 'n' and for Edge
4.47 - /// with 'e'.
4.48 -
4.49 -#ifndef DOXYGEN
4.50 - template <char _selector = '0'>
4.51 -#endif
4.52 - class GraphItem {
4.53 - public:
4.54 - /// \brief Default constructor.
4.55 - ///
4.56 - /// \warning The default constructor is not required to set
4.57 - /// the item to some well-defined value. So you should consider it
4.58 - /// as uninitialized.
4.59 - GraphItem() {}
4.60 - /// \brief Copy constructor.
4.61 - ///
4.62 - /// Copy constructor.
4.63 - ///
4.64 - GraphItem(const GraphItem &) {}
4.65 - /// \brief Invalid constructor \& conversion.
4.66 - ///
4.67 - /// This constructor initializes the item to be invalid.
4.68 - /// \sa Invalid for more details.
4.69 - GraphItem(Invalid) {}
4.70 - /// \brief Assign operator for nodes.
4.71 - ///
4.72 - /// The nodes are assignable.
4.73 - ///
4.74 - GraphItem& operator=(GraphItem const&) { return *this; }
4.75 - /// \brief Equality operator.
4.76 - ///
4.77 - /// Two iterators are equal if and only if they represents the
4.78 - /// same node in the graph or both are invalid.
4.79 - bool operator==(GraphItem) const { return false; }
4.80 - /// \brief Inequality operator.
4.81 - ///
4.82 - /// \sa operator==(const Node& n)
4.83 - ///
4.84 - bool operator!=(GraphItem) const { return false; }
4.85 -
4.86 - /// \brief Artificial ordering operator.
4.87 - ///
4.88 - /// To allow the use of graph descriptors as key type in std::map or
4.89 - /// similar associative container we require this.
4.90 - ///
4.91 - /// \note This operator only have to define some strict ordering of
4.92 - /// the items; this order has nothing to do with the iteration
4.93 - /// ordering of the items.
4.94 - bool operator<(GraphItem) const { return false; }
4.95 -
4.96 - template<typename _GraphItem>
4.97 - struct Constraints {
4.98 - void constraints() {
4.99 - _GraphItem i1;
4.100 - _GraphItem i2 = i1;
4.101 - _GraphItem i3 = INVALID;
4.102 -
4.103 - i1 = i2 = i3;
4.104 -
4.105 - bool b;
4.106 - // b = (ia == ib) && (ia != ib) && (ia < ib);
4.107 - b = (ia == ib) && (ia != ib);
4.108 - b = (ia == INVALID) && (ib != INVALID);
4.109 - b = (ia < ib);
4.110 - }
4.111 -
4.112 - const _GraphItem &ia;
4.113 - const _GraphItem &ib;
4.114 - };
4.115 - };
4.116 -
4.117 - /// \brief An empty base graph class.
4.118 - ///
4.119 - /// This class provides the minimal set of features needed for a graph
4.120 - /// structure. All graph concepts have to be conform to this base
4.121 - /// graph. It just provides types for nodes and edges and functions to
4.122 - /// get the source and the target of the edges.
4.123 - class BaseGraphComponent {
4.124 - public:
4.125 -
4.126 - typedef BaseGraphComponent Graph;
4.127 -
4.128 - /// \brief Node class of the graph.
4.129 - ///
4.130 - /// This class represents the Nodes of the graph.
4.131 - ///
4.132 - typedef GraphItem<'n'> Node;
4.133 -
4.134 - /// \brief Edge class of the graph.
4.135 - ///
4.136 - /// This class represents the Edges of the graph.
4.137 - ///
4.138 - typedef GraphItem<'e'> Edge;
4.139 -
4.140 - /// \brief Gives back the target node of an edge.
4.141 - ///
4.142 - /// Gives back the target node of an edge.
4.143 - ///
4.144 - Node target(const Edge&) const { return INVALID;}
4.145 -
4.146 - /// \brief Gives back the source node of an edge.
4.147 - ///
4.148 - /// Gives back the source node of an edge.
4.149 - ///
4.150 - Node source(const Edge&) const { return INVALID;}
4.151 -
4.152 - /// \brief Gives back the opposite node on the given edge.
4.153 - ///
4.154 - /// Gives back the opposite node on the given edge.
4.155 - Node oppositeNode(const Node&, const Edge&) const {
4.156 - return INVALID;
4.157 - }
4.158 -
4.159 - template <typename _Graph>
4.160 - struct Constraints {
4.161 - typedef typename _Graph::Node Node;
4.162 - typedef typename _Graph::Edge Edge;
4.163 -
4.164 - void constraints() {
4.165 - checkConcept<GraphItem<'n'>, Node>();
4.166 - checkConcept<GraphItem<'e'>, Edge>();
4.167 - {
4.168 - Node n;
4.169 - Edge e(INVALID);
4.170 - n = graph.source(e);
4.171 - n = graph.target(e);
4.172 - n = graph.oppositeNode(n, e);
4.173 - }
4.174 - }
4.175 -
4.176 - const _Graph& graph;
4.177 - };
4.178 - };
4.179 -
4.180 - /// \brief An empty base undirected graph class.
4.181 - ///
4.182 - /// This class provides the minimal set of features needed for an
4.183 - /// undirected graph structure. All undirected graph concepts have
4.184 - /// to be conform to this base graph. It just provides types for
4.185 - /// nodes, edges and undirected edges and functions to get the
4.186 - /// source and the target of the edges and undirected edges,
4.187 - /// conversion from edges to undirected edges and function to get
4.188 - /// both direction of the undirected edges.
4.189 - class BaseUGraphComponent : public BaseGraphComponent {
4.190 - public:
4.191 - typedef BaseGraphComponent::Node Node;
4.192 - typedef BaseGraphComponent::Edge Edge;
4.193 - /// \brief Undirected edge class of the graph.
4.194 - ///
4.195 - /// This class represents the undirected edges of the graph.
4.196 - /// The undirected graphs can be used as a directed graph which
4.197 - /// for each edge contains the opposite edge too so the graph is
4.198 - /// bidirected. The undirected edge represents two opposite
4.199 - /// directed edges.
4.200 - class UEdge : public GraphItem<'u'> {
4.201 - public:
4.202 - typedef GraphItem<'u'> Parent;
4.203 - /// \brief Default constructor.
4.204 - ///
4.205 - /// \warning The default constructor is not required to set
4.206 - /// the item to some well-defined value. So you should consider it
4.207 - /// as uninitialized.
4.208 - UEdge() {}
4.209 - /// \brief Copy constructor.
4.210 - ///
4.211 - /// Copy constructor.
4.212 - ///
4.213 - UEdge(const UEdge &) : Parent() {}
4.214 - /// \brief Invalid constructor \& conversion.
4.215 - ///
4.216 - /// This constructor initializes the item to be invalid.
4.217 - /// \sa Invalid for more details.
4.218 - UEdge(Invalid) {}
4.219 - /// \brief Converter from edge to undirected edge.
4.220 - ///
4.221 - /// Besides the core graph item functionality each edge should
4.222 - /// be convertible to the represented undirected edge.
4.223 - UEdge(const Edge&) {}
4.224 - };
4.225 -
4.226 - /// \brief Returns the direction of the edge.
4.227 - ///
4.228 - /// Returns the direction of the edge. Each edge represents an
4.229 - /// undirected edge with a direction. It gives back the
4.230 - /// direction.
4.231 - bool direction(const Edge&) const { return true; }
4.232 -
4.233 - /// \brief Returns the directed edge.
4.234 - ///
4.235 - /// Returns the directed edge from its direction and the
4.236 - /// represented undirected edge.
4.237 - Edge direct(const UEdge&, bool) const { return INVALID;}
4.238 -
4.239 - /// \brief Returns the directed edge.
4.240 - ///
4.241 - /// Returns the directed edge from its source and the
4.242 - /// represented undirected edge.
4.243 - Edge direct(const UEdge&, const Node&) const { return INVALID;}
4.244 -
4.245 - /// \brief Returns the opposite edge.
4.246 - ///
4.247 - /// Returns the opposite edge. It is the edge representing the
4.248 - /// same undirected edge and has opposite direction.
4.249 - Edge oppositeEdge(const Edge&) const { return INVALID;}
4.250 -
4.251 - /// \brief Gives back the target node of an undirected edge.
4.252 - ///
4.253 - /// Gives back the target node of an undirected edge. The name
4.254 - /// target is a little confusing because the undirected edge
4.255 - /// does not have target but it just means that one of the end
4.256 - /// node.
4.257 - Node target(const UEdge&) const { return INVALID;}
4.258 -
4.259 - /// \brief Gives back the source node of an undirected edge.
4.260 - ///
4.261 - /// Gives back the source node of an undirected edge. The name
4.262 - /// source is a little confusing because the undirected edge
4.263 - /// does not have source but it just means that one of the end
4.264 - /// node.
4.265 - Node source(const UEdge&) const { return INVALID;}
4.266 -
4.267 - template <typename _Graph>
4.268 - struct Constraints {
4.269 - typedef typename _Graph::Node Node;
4.270 - typedef typename _Graph::Edge Edge;
4.271 - typedef typename _Graph::UEdge UEdge;
4.272 -
4.273 - void constraints() {
4.274 - checkConcept<BaseGraphComponent, _Graph>();
4.275 - checkConcept<GraphItem<'u'>, UEdge>();
4.276 - {
4.277 - Node n;
4.278 - UEdge ue(INVALID);
4.279 - Edge e;
4.280 - n = graph.source(ue);
4.281 - n = graph.target(ue);
4.282 - e = graph.direct(ue, true);
4.283 - e = graph.direct(ue, n);
4.284 - e = graph.oppositeEdge(e);
4.285 - ue = e;
4.286 - bool d = graph.direction(e);
4.287 - ignore_unused_variable_warning(d);
4.288 - }
4.289 - }
4.290 -
4.291 - const _Graph& graph;
4.292 - };
4.293 -
4.294 - };
4.295 -
4.296 - /// \brief An empty iterable base graph class.
4.297 - ///
4.298 - /// This class provides beside the core graph features
4.299 - /// core iterable interface for the graph structure.
4.300 - /// Most of the base graphs should be conform to this concept.
4.301 - template <typename _Base = BaseGraphComponent>
4.302 - class BaseIterableGraphComponent : public _Base {
4.303 - public:
4.304 -
4.305 - typedef _Base Base;
4.306 - typedef typename Base::Node Node;
4.307 - typedef typename Base::Edge Edge;
4.308 -
4.309 - /// \brief Gives back the first node in the iterating order.
4.310 - ///
4.311 - /// Gives back the first node in the iterating order.
4.312 - ///
4.313 - void first(Node&) const {}
4.314 -
4.315 - /// \brief Gives back the next node in the iterating order.
4.316 - ///
4.317 - /// Gives back the next node in the iterating order.
4.318 - ///
4.319 - void next(Node&) const {}
4.320 -
4.321 - /// \brief Gives back the first edge in the iterating order.
4.322 - ///
4.323 - /// Gives back the first edge in the iterating order.
4.324 - ///
4.325 - void first(Edge&) const {}
4.326 -
4.327 - /// \brief Gives back the next edge in the iterating order.
4.328 - ///
4.329 - /// Gives back the next edge in the iterating order.
4.330 - ///
4.331 - void next(Edge&) const {}
4.332 -
4.333 -
4.334 - /// \brief Gives back the first of the edges point to the given
4.335 - /// node.
4.336 - ///
4.337 - /// Gives back the first of the edges point to the given node.
4.338 - ///
4.339 - void firstIn(Edge&, const Node&) const {}
4.340 -
4.341 - /// \brief Gives back the next of the edges points to the given
4.342 - /// node.
4.343 - ///
4.344 - /// Gives back the next of the edges points to the given node.
4.345 - ///
4.346 - void nextIn(Edge&) const {}
4.347 -
4.348 - /// \brief Gives back the first of the edges start from the
4.349 - /// given node.
4.350 - ///
4.351 - /// Gives back the first of the edges start from the given node.
4.352 - ///
4.353 - void firstOut(Edge&, const Node&) const {}
4.354 -
4.355 - /// \brief Gives back the next of the edges start from the given
4.356 - /// node.
4.357 - ///
4.358 - /// Gives back the next of the edges start from the given node.
4.359 - ///
4.360 - void nextOut(Edge&) const {}
4.361 -
4.362 -
4.363 - template <typename _Graph>
4.364 - struct Constraints {
4.365 -
4.366 - void constraints() {
4.367 - checkConcept< BaseGraphComponent, _Graph >();
4.368 - typename _Graph::Node node;
4.369 - typename _Graph::Edge edge;
4.370 - {
4.371 - graph.first(node);
4.372 - graph.next(node);
4.373 - }
4.374 - {
4.375 - graph.first(edge);
4.376 - graph.next(edge);
4.377 - }
4.378 - {
4.379 - graph.firstIn(edge, node);
4.380 - graph.nextIn(edge);
4.381 - }
4.382 - {
4.383 - graph.firstOut(edge, node);
4.384 - graph.nextOut(edge);
4.385 - }
4.386 - }
4.387 -
4.388 - const _Graph& graph;
4.389 - };
4.390 - };
4.391 -
4.392 - /// \brief An empty iterable base undirected graph class.
4.393 - ///
4.394 - /// This class provides beside the core undirceted graph features
4.395 - /// core iterable interface for the undirected graph structure.
4.396 - /// Most of the base undirected graphs should be conform to this
4.397 - /// concept.
4.398 - template <typename _Base = BaseUGraphComponent>
4.399 - class BaseIterableUGraphComponent
4.400 - : public BaseIterableGraphComponent<_Base> {
4.401 - public:
4.402 -
4.403 - typedef _Base Base;
4.404 - typedef typename Base::UEdge UEdge;
4.405 - typedef typename Base::Node Node;
4.406 -
4.407 - using BaseIterableGraphComponent<_Base>::first;
4.408 - using BaseIterableGraphComponent<_Base>::next;
4.409 -
4.410 - /// \brief Gives back the first undirected edge in the iterating
4.411 - /// order.
4.412 - ///
4.413 - /// Gives back the first undirected edge in the iterating order.
4.414 - ///
4.415 - void first(UEdge&) const {}
4.416 -
4.417 - /// \brief Gives back the next undirected edge in the iterating
4.418 - /// order.
4.419 - ///
4.420 - /// Gives back the next undirected edge in the iterating order.
4.421 - ///
4.422 - void next(UEdge&) const {}
4.423 -
4.424 -
4.425 - /// \brief Gives back the first of the undirected edges from the
4.426 - /// given node.
4.427 - ///
4.428 - /// Gives back the first of the undirected edges from the given
4.429 - /// node. The bool parameter gives back that direction which
4.430 - /// gives a good direction of the uedge so the source of the
4.431 - /// directed edge is the given node.
4.432 - void firstInc(UEdge&, bool&, const Node&) const {}
4.433 -
4.434 - /// \brief Gives back the next of the undirected edges from the
4.435 - /// given node.
4.436 - ///
4.437 - /// Gives back the next of the undirected edges from the given
4.438 - /// node. The bool parameter should be used as the \c firstInc()
4.439 - /// use it.
4.440 - void nextInc(UEdge&, bool&) const {}
4.441 -
4.442 - template <typename _Graph>
4.443 - struct Constraints {
4.444 -
4.445 - void constraints() {
4.446 - checkConcept<Base, _Graph >();
4.447 - checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
4.448 - typename _Graph::Node node;
4.449 - typename _Graph::UEdge uedge;
4.450 - bool dir;
4.451 - {
4.452 - graph.first(uedge);
4.453 - graph.next(uedge);
4.454 - }
4.455 - {
4.456 - graph.firstInc(uedge, dir, node);
4.457 - graph.nextInc(uedge, dir);
4.458 - }
4.459 - }
4.460 -
4.461 - const _Graph& graph;
4.462 - };
4.463 - };
4.464 -
4.465 - /// \brief An empty idable base graph class.
4.466 - ///
4.467 - /// This class provides beside the core graph features
4.468 - /// core id functions for the graph structure.
4.469 - /// The most of the base graphs should be conform to this concept.
4.470 - /// The id's are unique and immutable.
4.471 - template <typename _Base = BaseGraphComponent>
4.472 - class IDableGraphComponent : public _Base {
4.473 - public:
4.474 -
4.475 - typedef _Base Base;
4.476 - typedef typename Base::Node Node;
4.477 - typedef typename Base::Edge Edge;
4.478 -
4.479 - /// \brief Gives back an unique integer id for the Node.
4.480 - ///
4.481 - /// Gives back an unique integer id for the Node.
4.482 - ///
4.483 - int id(const Node&) const { return -1;}
4.484 -
4.485 - /// \brief Gives back the node by the unique id.
4.486 - ///
4.487 - /// Gives back the node by the unique id.
4.488 - /// If the graph does not contain node with the given id
4.489 - /// then the result of the function is undetermined.
4.490 - Node nodeFromId(int) const { return INVALID;}
4.491 -
4.492 - /// \brief Gives back an unique integer id for the Edge.
4.493 - ///
4.494 - /// Gives back an unique integer id for the Edge.
4.495 - ///
4.496 - int id(const Edge&) const { return -1;}
4.497 -
4.498 - /// \brief Gives back the edge by the unique id.
4.499 - ///
4.500 - /// Gives back the edge by the unique id.
4.501 - /// If the graph does not contain edge with the given id
4.502 - /// then the result of the function is undetermined.
4.503 - Edge edgeFromId(int) const { return INVALID;}
4.504 -
4.505 - /// \brief Gives back an integer greater or equal to the maximum
4.506 - /// Node id.
4.507 - ///
4.508 - /// Gives back an integer greater or equal to the maximum Node
4.509 - /// id.
4.510 - int maxNodeId() const { return -1;}
4.511 -
4.512 - /// \brief Gives back an integer greater or equal to the maximum
4.513 - /// Edge id.
4.514 - ///
4.515 - /// Gives back an integer greater or equal to the maximum Edge
4.516 - /// id.
4.517 - int maxEdgeId() const { return -1;}
4.518 -
4.519 - template <typename _Graph>
4.520 - struct Constraints {
4.521 -
4.522 - void constraints() {
4.523 - checkConcept< BaseGraphComponent, _Graph >();
4.524 - typename _Graph::Node node;
4.525 - int nid = graph.id(node);
4.526 - nid = graph.id(node);
4.527 - node = graph.nodeFromId(nid);
4.528 - typename _Graph::Edge edge;
4.529 - int eid = graph.id(edge);
4.530 - eid = graph.id(edge);
4.531 - edge = graph.edgeFromId(eid);
4.532 -
4.533 - nid = graph.maxNodeId();
4.534 - ignore_unused_variable_warning(nid);
4.535 - eid = graph.maxEdgeId();
4.536 - ignore_unused_variable_warning(eid);
4.537 - }
4.538 -
4.539 - const _Graph& graph;
4.540 - };
4.541 - };
4.542 -
4.543 - /// \brief An empty idable base undirected graph class.
4.544 - ///
4.545 - /// This class provides beside the core undirected graph features
4.546 - /// core id functions for the undirected graph structure. The
4.547 - /// most of the base undirected graphs should be conform to this
4.548 - /// concept. The id's are unique and immutable.
4.549 - template <typename _Base = BaseUGraphComponent>
4.550 - class IDableUGraphComponent : public IDableGraphComponent<_Base> {
4.551 - public:
4.552 -
4.553 - typedef _Base Base;
4.554 - typedef typename Base::UEdge UEdge;
4.555 -
4.556 - using IDableGraphComponent<_Base>::id;
4.557 -
4.558 - /// \brief Gives back an unique integer id for the UEdge.
4.559 - ///
4.560 - /// Gives back an unique integer id for the UEdge.
4.561 - ///
4.562 - int id(const UEdge&) const { return -1;}
4.563 -
4.564 - /// \brief Gives back the undirected edge by the unique id.
4.565 - ///
4.566 - /// Gives back the undirected edge by the unique id. If the
4.567 - /// graph does not contain edge with the given id then the
4.568 - /// result of the function is undetermined.
4.569 - UEdge uEdgeFromId(int) const { return INVALID;}
4.570 -
4.571 - /// \brief Gives back an integer greater or equal to the maximum
4.572 - /// UEdge id.
4.573 - ///
4.574 - /// Gives back an integer greater or equal to the maximum UEdge
4.575 - /// id.
4.576 - int maxUEdgeId() const { return -1;}
4.577 -
4.578 - template <typename _Graph>
4.579 - struct Constraints {
4.580 -
4.581 - void constraints() {
4.582 - checkConcept<Base, _Graph >();
4.583 - checkConcept<IDableGraphComponent<Base>, _Graph >();
4.584 - typename _Graph::UEdge uedge;
4.585 - int ueid = graph.id(uedge);
4.586 - ueid = graph.id(uedge);
4.587 - uedge = graph.uEdgeFromId(ueid);
4.588 - ueid = graph.maxUEdgeId();
4.589 - ignore_unused_variable_warning(ueid);
4.590 - }
4.591 -
4.592 - const _Graph& graph;
4.593 - };
4.594 - };
4.595 -
4.596 - /// \brief An empty extendable base graph class.
4.597 - ///
4.598 - /// This class provides beside the core graph features
4.599 - /// core graph extend interface for the graph structure.
4.600 - /// The most of the base graphs should be conform to this concept.
4.601 - template <typename _Base = BaseGraphComponent>
4.602 - class BaseExtendableGraphComponent : public _Base {
4.603 - public:
4.604 -
4.605 - typedef typename _Base::Node Node;
4.606 - typedef typename _Base::Edge Edge;
4.607 -
4.608 - /// \brief Adds a new node to the graph.
4.609 - ///
4.610 - /// Adds a new node to the graph.
4.611 - ///
4.612 - Node addNode() {
4.613 - return INVALID;
4.614 - }
4.615 -
4.616 - /// \brief Adds a new edge connects the given two nodes.
4.617 - ///
4.618 - /// Adds a new edge connects the the given two nodes.
4.619 - Edge addEdge(const Node&, const Node&) {
4.620 - return INVALID;
4.621 - }
4.622 -
4.623 - template <typename _Graph>
4.624 - struct Constraints {
4.625 - void constraints() {
4.626 - typename _Graph::Node node_a, node_b;
4.627 - node_a = graph.addNode();
4.628 - node_b = graph.addNode();
4.629 - typename _Graph::Edge edge;
4.630 - edge = graph.addEdge(node_a, node_b);
4.631 - }
4.632 -
4.633 - _Graph& graph;
4.634 - };
4.635 - };
4.636 -
4.637 - /// \brief An empty extendable base undirected graph class.
4.638 - ///
4.639 - /// This class provides beside the core undirected graph features
4.640 - /// core undircted graph extend interface for the graph structure.
4.641 - /// The most of the base graphs should be conform to this concept.
4.642 - template <typename _Base = BaseUGraphComponent>
4.643 - class BaseExtendableUGraphComponent : public _Base {
4.644 - public:
4.645 -
4.646 - typedef typename _Base::Node Node;
4.647 - typedef typename _Base::UEdge UEdge;
4.648 -
4.649 - /// \brief Adds a new node to the graph.
4.650 - ///
4.651 - /// Adds a new node to the graph.
4.652 - ///
4.653 - Node addNode() {
4.654 - return INVALID;
4.655 - }
4.656 -
4.657 - /// \brief Adds a new edge connects the given two nodes.
4.658 - ///
4.659 - /// Adds a new edge connects the the given two nodes.
4.660 - UEdge addEdge(const Node&, const Node&) {
4.661 - return INVALID;
4.662 - }
4.663 -
4.664 - template <typename _Graph>
4.665 - struct Constraints {
4.666 - void constraints() {
4.667 - typename _Graph::Node node_a, node_b;
4.668 - node_a = graph.addNode();
4.669 - node_b = graph.addNode();
4.670 - typename _Graph::UEdge uedge;
4.671 - uedge = graph.addUEdge(node_a, node_b);
4.672 - }
4.673 -
4.674 - _Graph& graph;
4.675 - };
4.676 - };
4.677 -
4.678 - /// \brief An empty erasable base graph class.
4.679 - ///
4.680 - /// This class provides beside the core graph features
4.681 - /// core erase functions for the graph structure.
4.682 - /// The most of the base graphs should be conform to this concept.
4.683 - template <typename _Base = BaseGraphComponent>
4.684 - class BaseErasableGraphComponent : public _Base {
4.685 - public:
4.686 -
4.687 - typedef _Base Base;
4.688 - typedef typename Base::Node Node;
4.689 - typedef typename Base::Edge Edge;
4.690 -
4.691 - /// \brief Erase a node from the graph.
4.692 - ///
4.693 - /// Erase a node from the graph. This function should not
4.694 - /// erase edges connecting to the Node.
4.695 - void erase(const Node&) {}
4.696 -
4.697 - /// \brief Erase an edge from the graph.
4.698 - ///
4.699 - /// Erase an edge from the graph.
4.700 - ///
4.701 - void erase(const Edge&) {}
4.702 -
4.703 - template <typename _Graph>
4.704 - struct Constraints {
4.705 - void constraints() {
4.706 - typename _Graph::Node node;
4.707 - graph.erase(node);
4.708 - typename _Graph::Edge edge;
4.709 - graph.erase(edge);
4.710 - }
4.711 -
4.712 - _Graph& graph;
4.713 - };
4.714 - };
4.715 -
4.716 - /// \brief An empty erasable base undirected graph class.
4.717 - ///
4.718 - /// This class provides beside the core undirected graph features
4.719 - /// core erase functions for the undirceted graph structure.
4.720 - template <typename _Base = BaseUGraphComponent>
4.721 - class BaseErasableUGraphComponent : public _Base {
4.722 - public:
4.723 -
4.724 - typedef _Base Base;
4.725 - typedef typename Base::Node Node;
4.726 - typedef typename Base::UEdge UEdge;
4.727 -
4.728 - /// \brief Erase a node from the graph.
4.729 - ///
4.730 - /// Erase a node from the graph. This function should not
4.731 - /// erase edges connecting to the Node.
4.732 - void erase(const Node&) {}
4.733 -
4.734 - /// \brief Erase an edge from the graph.
4.735 - ///
4.736 - /// Erase an edge from the graph.
4.737 - ///
4.738 - void erase(const UEdge&) {}
4.739 -
4.740 - template <typename _Graph>
4.741 - struct Constraints {
4.742 - void constraints() {
4.743 - typename _Graph::Node node;
4.744 - graph.erase(node);
4.745 - typename _Graph::Edge edge;
4.746 - graph.erase(edge);
4.747 - }
4.748 -
4.749 - _Graph& graph;
4.750 - };
4.751 - };
4.752 -
4.753 - /// \brief An empty clearable base graph class.
4.754 - ///
4.755 - /// This class provides beside the core graph features
4.756 - /// core clear functions for the graph structure.
4.757 - /// The most of the base graphs should be conform to this concept.
4.758 - template <typename _Base = BaseGraphComponent>
4.759 - class BaseClearableGraphComponent : public _Base {
4.760 - public:
4.761 -
4.762 - /// \brief Erase all the nodes and edges from the graph.
4.763 - ///
4.764 - /// Erase all the nodes and edges from the graph.
4.765 - ///
4.766 - void clear() {}
4.767 -
4.768 - template <typename _Graph>
4.769 - struct Constraints {
4.770 - void constraints() {
4.771 - graph.clear();
4.772 - }
4.773 -
4.774 - _Graph graph;
4.775 - };
4.776 - };
4.777 -
4.778 - /// \brief An empty clearable base undirected graph class.
4.779 - ///
4.780 - /// This class provides beside the core undirected graph features
4.781 - /// core clear functions for the undirected graph structure.
4.782 - /// The most of the base graphs should be conform to this concept.
4.783 - template <typename _Base = BaseUGraphComponent>
4.784 - class BaseClearableUGraphComponent : public _Base {
4.785 - public:
4.786 -
4.787 - /// \brief Erase all the nodes and undirected edges from the graph.
4.788 - ///
4.789 - /// Erase all the nodes and undirected edges from the graph.
4.790 - ///
4.791 - void clear() {}
4.792 -
4.793 - template <typename _Graph>
4.794 - struct Constraints {
4.795 - void constraints() {
4.796 - graph.clear();
4.797 - }
4.798 -
4.799 - _Graph graph;
4.800 - };
4.801 - };
4.802 -
4.803 -
4.804 - /// \brief Skeleton class for graph NodeIt and EdgeIt
4.805 - ///
4.806 - /// Skeleton class for graph NodeIt and EdgeIt.
4.807 - ///
4.808 - template <typename _Graph, typename _Item>
4.809 - class GraphItemIt : public _Item {
4.810 - public:
4.811 - /// \brief Default constructor.
4.812 - ///
4.813 - /// @warning The default constructor sets the iterator
4.814 - /// to an undefined value.
4.815 - GraphItemIt() {}
4.816 - /// \brief Copy constructor.
4.817 - ///
4.818 - /// Copy constructor.
4.819 - ///
4.820 - GraphItemIt(const GraphItemIt& ) {}
4.821 - /// \brief Sets the iterator to the first item.
4.822 - ///
4.823 - /// Sets the iterator to the first item of \c the graph.
4.824 - ///
4.825 - explicit GraphItemIt(const _Graph&) {}
4.826 - /// \brief Invalid constructor \& conversion.
4.827 - ///
4.828 - /// This constructor initializes the item to be invalid.
4.829 - /// \sa Invalid for more details.
4.830 - GraphItemIt(Invalid) {}
4.831 - /// \brief Assign operator for items.
4.832 - ///
4.833 - /// The items are assignable.
4.834 - ///
4.835 - GraphItemIt& operator=(const GraphItemIt&) { return *this; }
4.836 - /// \brief Next item.
4.837 - ///
4.838 - /// Assign the iterator to the next item.
4.839 - ///
4.840 - GraphItemIt& operator++() { return *this; }
4.841 - /// \brief Equality operator
4.842 - ///
4.843 - /// Two iterators are equal if and only if they point to the
4.844 - /// same object or both are invalid.
4.845 - bool operator==(const GraphItemIt&) const { return true;}
4.846 - /// \brief Inequality operator
4.847 - ///
4.848 - /// \sa operator==(Node n)
4.849 - ///
4.850 - bool operator!=(const GraphItemIt&) const { return true;}
4.851 -
4.852 - template<typename _GraphItemIt>
4.853 - struct Constraints {
4.854 - void constraints() {
4.855 - _GraphItemIt it1(g);
4.856 - _GraphItemIt it2;
4.857 -
4.858 - it2 = ++it1;
4.859 - ++it2 = it1;
4.860 - ++(++it1);
4.861 -
4.862 - _Item bi = it1;
4.863 - bi = it2;
4.864 - }
4.865 - _Graph& g;
4.866 - };
4.867 - };
4.868 -
4.869 - /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt
4.870 - ///
4.871 - /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
4.872 - /// base class, the _selector is a additional template parameter. For
4.873 - /// InEdgeIt you should instantiate it with character 'i' and for
4.874 - /// OutEdgeIt with 'o'.
4.875 - template <typename _Graph,
4.876 - typename _Item = typename _Graph::Edge,
4.877 - typename _Base = typename _Graph::Node,
4.878 - char _selector = '0'>
4.879 - class GraphIncIt : public _Item {
4.880 - public:
4.881 - /// \brief Default constructor.
4.882 - ///
4.883 - /// @warning The default constructor sets the iterator
4.884 - /// to an undefined value.
4.885 - GraphIncIt() {}
4.886 - /// \brief Copy constructor.
4.887 - ///
4.888 - /// Copy constructor.
4.889 - ///
4.890 - GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
4.891 - /// \brief Sets the iterator to the first edge incoming into or outgoing
4.892 - /// from the node.
4.893 - ///
4.894 - /// Sets the iterator to the first edge incoming into or outgoing
4.895 - /// from the node.
4.896 - ///
4.897 - explicit GraphIncIt(const _Graph&, const _Base&) {}
4.898 - /// \brief Invalid constructor \& conversion.
4.899 - ///
4.900 - /// This constructor initializes the item to be invalid.
4.901 - /// \sa Invalid for more details.
4.902 - GraphIncIt(Invalid) {}
4.903 - /// \brief Assign operator for iterators.
4.904 - ///
4.905 - /// The iterators are assignable.
4.906 - ///
4.907 - GraphIncIt& operator=(GraphIncIt const&) { return *this; }
4.908 - /// \brief Next item.
4.909 - ///
4.910 - /// Assign the iterator to the next item.
4.911 - ///
4.912 - GraphIncIt& operator++() { return *this; }
4.913 -
4.914 - /// \brief Equality operator
4.915 - ///
4.916 - /// Two iterators are equal if and only if they point to the
4.917 - /// same object or both are invalid.
4.918 - bool operator==(const GraphIncIt&) const { return true;}
4.919 -
4.920 - /// \brief Inequality operator
4.921 - ///
4.922 - /// \sa operator==(Node n)
4.923 - ///
4.924 - bool operator!=(const GraphIncIt&) const { return true;}
4.925 -
4.926 - template <typename _GraphIncIt>
4.927 - struct Constraints {
4.928 - void constraints() {
4.929 - checkConcept<GraphItem<_selector>, _GraphIncIt>();
4.930 - _GraphIncIt it1(graph, node);
4.931 - _GraphIncIt it2;
4.932 -
4.933 - it2 = ++it1;
4.934 - ++it2 = it1;
4.935 - ++(++it1);
4.936 - _Item e = it1;
4.937 - e = it2;
4.938 -
4.939 - }
4.940 -
4.941 - _Item edge;
4.942 - _Base node;
4.943 - _Graph graph;
4.944 - _GraphIncIt it;
4.945 - };
4.946 - };
4.947 -
4.948 -
4.949 - /// \brief An empty iterable graph class.
4.950 - ///
4.951 - /// This class provides beside the core graph features
4.952 - /// iterator based iterable interface for the graph structure.
4.953 - /// This concept is part of the GraphConcept.
4.954 - template <typename _Base = BaseGraphComponent>
4.955 - class IterableGraphComponent : public _Base {
4.956 -
4.957 - public:
4.958 -
4.959 - typedef _Base Base;
4.960 - typedef typename Base::Node Node;
4.961 - typedef typename Base::Edge Edge;
4.962 -
4.963 - typedef IterableGraphComponent Graph;
4.964 -
4.965 -
4.966 - /// \brief This iterator goes through each node.
4.967 - ///
4.968 - /// This iterator goes through each node.
4.969 - ///
4.970 - typedef GraphItemIt<Graph, Node> NodeIt;
4.971 -
4.972 - /// \brief This iterator goes through each node.
4.973 - ///
4.974 - /// This iterator goes through each node.
4.975 - ///
4.976 - typedef GraphItemIt<Graph, Edge> EdgeIt;
4.977 -
4.978 - /// \brief This iterator goes trough the incoming edges of a node.
4.979 - ///
4.980 - /// This iterator goes trough the \e inccoming edges of a certain node
4.981 - /// of a graph.
4.982 - typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt;
4.983 -
4.984 - /// \brief This iterator goes trough the outgoing edges of a node.
4.985 - ///
4.986 - /// This iterator goes trough the \e outgoing edges of a certain node
4.987 - /// of a graph.
4.988 - typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt;
4.989 -
4.990 - /// \brief The base node of the iterator.
4.991 - ///
4.992 - /// Gives back the base node of the iterator.
4.993 - /// It is always the target of the pointed edge.
4.994 - Node baseNode(const InEdgeIt&) const { return INVALID; }
4.995 -
4.996 - /// \brief The running node of the iterator.
4.997 - ///
4.998 - /// Gives back the running node of the iterator.
4.999 - /// It is always the source of the pointed edge.
4.1000 - Node runningNode(const InEdgeIt&) const { return INVALID; }
4.1001 -
4.1002 - /// \brief The base node of the iterator.
4.1003 - ///
4.1004 - /// Gives back the base node of the iterator.
4.1005 - /// It is always the source of the pointed edge.
4.1006 - Node baseNode(const OutEdgeIt&) const { return INVALID; }
4.1007 -
4.1008 - /// \brief The running node of the iterator.
4.1009 - ///
4.1010 - /// Gives back the running node of the iterator.
4.1011 - /// It is always the target of the pointed edge.
4.1012 - Node runningNode(const OutEdgeIt&) const { return INVALID; }
4.1013 -
4.1014 - /// \brief The opposite node on the given edge.
4.1015 - ///
4.1016 - /// Gives back the opposite on the given edge.
4.1017 - /// \todo It should not be here.
4.1018 - Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
4.1019 -
4.1020 -
4.1021 - template <typename _Graph>
4.1022 - struct Constraints {
4.1023 - void constraints() {
4.1024 - checkConcept<Base, _Graph>();
4.1025 -
4.1026 - checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
4.1027 - typename _Graph::EdgeIt >();
4.1028 - checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
4.1029 - typename _Graph::NodeIt >();
4.1030 - checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
4.1031 - typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
4.1032 - checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
4.1033 - typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
4.1034 -
4.1035 - typename _Graph::Node n;
4.1036 - typename _Graph::InEdgeIt ieit(INVALID);
4.1037 - typename _Graph::OutEdgeIt oeit(INVALID);
4.1038 - n = graph.baseNode(ieit);
4.1039 - n = graph.runningNode(ieit);
4.1040 - n = graph.baseNode(oeit);
4.1041 - n = graph.runningNode(oeit);
4.1042 - ignore_unused_variable_warning(n);
4.1043 - }
4.1044 -
4.1045 - const _Graph& graph;
4.1046 -
4.1047 - };
4.1048 - };
4.1049 -
4.1050 - /// \brief An empty iterable undirected graph class.
4.1051 - ///
4.1052 - /// This class provides beside the core graph features iterator
4.1053 - /// based iterable interface for the undirected graph structure.
4.1054 - /// This concept is part of the GraphConcept.
4.1055 - template <typename _Base = BaseUGraphComponent>
4.1056 - class IterableUGraphComponent : public IterableGraphComponent<_Base> {
4.1057 - public:
4.1058 -
4.1059 - typedef _Base Base;
4.1060 - typedef typename Base::Node Node;
4.1061 - typedef typename Base::Edge Edge;
4.1062 - typedef typename Base::UEdge UEdge;
4.1063 -
4.1064 -
4.1065 - typedef IterableUGraphComponent Graph;
4.1066 - using IterableGraphComponent<_Base>::baseNode;
4.1067 - using IterableGraphComponent<_Base>::runningNode;
4.1068 -
4.1069 -
4.1070 - /// \brief This iterator goes through each node.
4.1071 - ///
4.1072 - /// This iterator goes through each node.
4.1073 - typedef GraphItemIt<Graph, UEdge> UEdgeIt;
4.1074 - /// \brief This iterator goes trough the incident edges of a
4.1075 - /// node.
4.1076 - ///
4.1077 - /// This iterator goes trough the incident edges of a certain
4.1078 - /// node of a graph.
4.1079 - typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt;
4.1080 - /// \brief The base node of the iterator.
4.1081 - ///
4.1082 - /// Gives back the base node of the iterator.
4.1083 - Node baseNode(const IncEdgeIt&) const { return INVALID; }
4.1084 -
4.1085 - /// \brief The running node of the iterator.
4.1086 - ///
4.1087 - /// Gives back the running node of the iterator.
4.1088 - Node runningNode(const IncEdgeIt&) const { return INVALID; }
4.1089 -
4.1090 - template <typename _Graph>
4.1091 - struct Constraints {
4.1092 - void constraints() {
4.1093 - checkConcept<Base, _Graph>();
4.1094 - checkConcept<IterableGraphComponent<Base>, _Graph>();
4.1095 -
4.1096 - checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
4.1097 - typename _Graph::UEdgeIt >();
4.1098 - checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
4.1099 - typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
4.1100 -
4.1101 - typename _Graph::Node n;
4.1102 - typename _Graph::IncEdgeIt ueit(INVALID);
4.1103 - n = graph.baseNode(ueit);
4.1104 - n = graph.runningNode(ueit);
4.1105 - }
4.1106 -
4.1107 - const _Graph& graph;
4.1108 -
4.1109 - };
4.1110 - };
4.1111 -
4.1112 - /// \brief An empty alteration notifier graph class.
4.1113 - ///
4.1114 - /// This class provides beside the core graph features alteration
4.1115 - /// notifier interface for the graph structure. This implements
4.1116 - /// an observer-notifier pattern for each graph item. More
4.1117 - /// obsevers can be registered into the notifier and whenever an
4.1118 - /// alteration occured in the graph all the observers will
4.1119 - /// notified about it.
4.1120 - template <typename _Base = BaseGraphComponent>
4.1121 - class AlterableGraphComponent : public _Base {
4.1122 - public:
4.1123 -
4.1124 - typedef _Base Base;
4.1125 - typedef typename Base::Node Node;
4.1126 - typedef typename Base::Edge Edge;
4.1127 -
4.1128 -
4.1129 - /// The node observer registry.
4.1130 - typedef AlterationNotifier<AlterableGraphComponent, Node>
4.1131 - NodeNotifier;
4.1132 - /// The edge observer registry.
4.1133 - typedef AlterationNotifier<AlterableGraphComponent, Edge>
4.1134 - EdgeNotifier;
4.1135 -
4.1136 - /// \brief Gives back the node alteration notifier.
4.1137 - ///
4.1138 - /// Gives back the node alteration notifier.
4.1139 - NodeNotifier& getNotifier(Node) const {
4.1140 - return NodeNotifier();
4.1141 - }
4.1142 -
4.1143 - /// \brief Gives back the edge alteration notifier.
4.1144 - ///
4.1145 - /// Gives back the edge alteration notifier.
4.1146 - EdgeNotifier& getNotifier(Edge) const {
4.1147 - return EdgeNotifier();
4.1148 - }
4.1149 -
4.1150 - template <typename _Graph>
4.1151 - struct Constraints {
4.1152 - void constraints() {
4.1153 - checkConcept<Base, _Graph>();
4.1154 - typename _Graph::NodeNotifier& nn
4.1155 - = graph.getNotifier(typename _Graph::Node());
4.1156 -
4.1157 - typename _Graph::EdgeNotifier& en
4.1158 - = graph.getNotifier(typename _Graph::Edge());
4.1159 -
4.1160 - ignore_unused_variable_warning(nn);
4.1161 - ignore_unused_variable_warning(en);
4.1162 - }
4.1163 -
4.1164 - const _Graph& graph;
4.1165 -
4.1166 - };
4.1167 -
4.1168 - };
4.1169 -
4.1170 - /// \brief An empty alteration notifier undirected graph class.
4.1171 - ///
4.1172 - /// This class provides beside the core graph features alteration
4.1173 - /// notifier interface for the graph structure. This implements
4.1174 - /// an observer-notifier pattern for each graph item. More
4.1175 - /// obsevers can be registered into the notifier and whenever an
4.1176 - /// alteration occured in the graph all the observers will
4.1177 - /// notified about it.
4.1178 - template <typename _Base = BaseUGraphComponent>
4.1179 - class AlterableUGraphComponent : public AlterableGraphComponent<_Base> {
4.1180 - public:
4.1181 -
4.1182 - typedef _Base Base;
4.1183 - typedef typename Base::UEdge UEdge;
4.1184 -
4.1185 -
4.1186 - /// The edge observer registry.
4.1187 - typedef AlterationNotifier<AlterableUGraphComponent, UEdge>
4.1188 - UEdgeNotifier;
4.1189 -
4.1190 - /// \brief Gives back the edge alteration notifier.
4.1191 - ///
4.1192 - /// Gives back the edge alteration notifier.
4.1193 - UEdgeNotifier& getNotifier(UEdge) const {
4.1194 - return UEdgeNotifier();
4.1195 - }
4.1196 -
4.1197 - template <typename _Graph>
4.1198 - struct Constraints {
4.1199 - void constraints() {
4.1200 - checkConcept<Base, _Graph>();
4.1201 - checkConcept<AlterableGraphComponent, _Graph>();
4.1202 - typename _Graph::UEdgeNotifier& uen
4.1203 - = graph.getNotifier(typename _Graph::UEdge());
4.1204 - ignore_unused_variable_warning(uen);
4.1205 - }
4.1206 -
4.1207 - const _Graph& graph;
4.1208 -
4.1209 - };
4.1210 -
4.1211 - };
4.1212 -
4.1213 -
4.1214 - /// \brief Class describing the concept of graph maps
4.1215 - ///
4.1216 - /// This class describes the common interface of the graph maps
4.1217 - /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to
4.1218 - /// associate data to graph descriptors (nodes or edges).
4.1219 - template <typename _Graph, typename _Item, typename _Value>
4.1220 - class GraphMap : public ReadWriteMap<_Item, _Value> {
4.1221 - public:
4.1222 -
4.1223 - typedef ReadWriteMap<_Item, _Value> Parent;
4.1224 -
4.1225 - /// The graph type of the map.
4.1226 - typedef _Graph Graph;
4.1227 - /// The key type of the map.
4.1228 - typedef _Item Key;
4.1229 - /// The value type of the map.
4.1230 - typedef _Value Value;
4.1231 -
4.1232 - /// \brief Construct a new map.
4.1233 - ///
4.1234 - /// Construct a new map for the graph.
4.1235 - explicit GraphMap(const Graph&) {}
4.1236 - /// \brief Construct a new map with default value.
4.1237 - ///
4.1238 - /// Construct a new map for the graph and initalise the values.
4.1239 - GraphMap(const Graph&, const Value&) {}
4.1240 - /// \brief Copy constructor.
4.1241 - ///
4.1242 - /// Copy Constructor.
4.1243 - GraphMap(const GraphMap&) : Parent() {}
4.1244 -
4.1245 - /// \brief Assign operator.
4.1246 - ///
4.1247 - /// Assign operator. It does not mofify the underlying graph,
4.1248 - /// it just iterates on the current item set and set the map
4.1249 - /// with the value returned by the assigned map.
4.1250 - template <typename CMap>
4.1251 - GraphMap& operator=(const CMap&) {
4.1252 - checkConcept<ReadMap<Key, Value>, CMap>();
4.1253 - return *this;
4.1254 - }
4.1255 -
4.1256 - template<typename _Map>
4.1257 - struct Constraints {
4.1258 - void constraints() {
4.1259 - checkConcept<ReadWriteMap<Key, Value>, _Map >();
4.1260 - // Construction with a graph parameter
4.1261 - _Map a(g);
4.1262 - // Constructor with a graph and a default value parameter
4.1263 - _Map a2(g,t);
4.1264 - // Copy constructor.
4.1265 - _Map b(c);
4.1266 -
4.1267 - ReadMap<Key, Value> cmap;
4.1268 - b = cmap;
4.1269 -
4.1270 - ignore_unused_variable_warning(a2);
4.1271 - ignore_unused_variable_warning(b);
4.1272 - }
4.1273 -
4.1274 - const _Map &c;
4.1275 - const Graph &g;
4.1276 - const typename GraphMap::Value &t;
4.1277 - };
4.1278 -
4.1279 - };
4.1280 -
4.1281 - /// \brief An empty mappable graph class.
4.1282 - ///
4.1283 - /// This class provides beside the core graph features
4.1284 - /// map interface for the graph structure.
4.1285 - /// This concept is part of the Graph concept.
4.1286 - template <typename _Base = BaseGraphComponent>
4.1287 - class MappableGraphComponent : public _Base {
4.1288 - public:
4.1289 -
4.1290 - typedef _Base Base;
4.1291 - typedef typename Base::Node Node;
4.1292 - typedef typename Base::Edge Edge;
4.1293 -
4.1294 - typedef MappableGraphComponent Graph;
4.1295 -
4.1296 - /// \brief ReadWrite map of the nodes.
4.1297 - ///
4.1298 - /// ReadWrite map of the nodes.
4.1299 - ///
4.1300 - template <typename Value>
4.1301 - class NodeMap : public GraphMap<Graph, Node, Value> {
4.1302 - private:
4.1303 - NodeMap();
4.1304 - public:
4.1305 - typedef GraphMap<Graph, Node, Value> Parent;
4.1306 -
4.1307 - /// \brief Construct a new map.
4.1308 - ///
4.1309 - /// Construct a new map for the graph.
4.1310 - /// \todo call the right parent class constructor
4.1311 - explicit NodeMap(const Graph& graph) : Parent(graph) {}
4.1312 -
4.1313 - /// \brief Construct a new map with default value.
4.1314 - ///
4.1315 - /// Construct a new map for the graph and initalise the values.
4.1316 - NodeMap(const Graph& graph, const Value& value)
4.1317 - : Parent(graph, value) {}
4.1318 -
4.1319 - /// \brief Copy constructor.
4.1320 - ///
4.1321 - /// Copy Constructor.
4.1322 - NodeMap(const NodeMap& nm) : Parent(nm) {}
4.1323 -
4.1324 - /// \brief Assign operator.
4.1325 - ///
4.1326 - /// Assign operator.
4.1327 - template <typename CMap>
4.1328 - NodeMap& operator=(const CMap&) {
4.1329 - checkConcept<ReadMap<Node, Value>, CMap>();
4.1330 - return *this;
4.1331 - }
4.1332 -
4.1333 - };
4.1334 -
4.1335 - /// \brief ReadWrite map of the edges.
4.1336 - ///
4.1337 - /// ReadWrite map of the edges.
4.1338 - ///
4.1339 - template <typename Value>
4.1340 - class EdgeMap : public GraphMap<Graph, Edge, Value> {
4.1341 - private:
4.1342 - EdgeMap();
4.1343 - public:
4.1344 - typedef GraphMap<Graph, Edge, Value> Parent;
4.1345 -
4.1346 - /// \brief Construct a new map.
4.1347 - ///
4.1348 - /// Construct a new map for the graph.
4.1349 - /// \todo call the right parent class constructor
4.1350 - explicit EdgeMap(const Graph& graph) : Parent(graph) {}
4.1351 -
4.1352 - /// \brief Construct a new map with default value.
4.1353 - ///
4.1354 - /// Construct a new map for the graph and initalise the values.
4.1355 - EdgeMap(const Graph& graph, const Value& value)
4.1356 - : Parent(graph, value) {}
4.1357 -
4.1358 - /// \brief Copy constructor.
4.1359 - ///
4.1360 - /// Copy Constructor.
4.1361 - EdgeMap(const EdgeMap& nm) : Parent(nm) {}
4.1362 -
4.1363 - /// \brief Assign operator.
4.1364 - ///
4.1365 - /// Assign operator.
4.1366 - template <typename CMap>
4.1367 - EdgeMap& operator=(const CMap&) {
4.1368 - checkConcept<ReadMap<Edge, Value>, CMap>();
4.1369 - return *this;
4.1370 - }
4.1371 -
4.1372 - };
4.1373 -
4.1374 -
4.1375 - template <typename _Graph>
4.1376 - struct Constraints {
4.1377 -
4.1378 - struct Dummy {
4.1379 - int value;
4.1380 - Dummy() : value(0) {}
4.1381 - Dummy(int _v) : value(_v) {}
4.1382 - };
4.1383 -
4.1384 - void constraints() {
4.1385 - checkConcept<Base, _Graph>();
4.1386 - { // int map test
4.1387 - typedef typename _Graph::template NodeMap<int> IntNodeMap;
4.1388 - checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
4.1389 - IntNodeMap >();
4.1390 - } { // bool map test
4.1391 - typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
4.1392 - checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
4.1393 - BoolNodeMap >();
4.1394 - } { // Dummy map test
4.1395 - typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap;
4.1396 - checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>,
4.1397 - DummyNodeMap >();
4.1398 - }
4.1399 -
4.1400 - { // int map test
4.1401 - typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
4.1402 - checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
4.1403 - IntEdgeMap >();
4.1404 - } { // bool map test
4.1405 - typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
4.1406 - checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
4.1407 - BoolEdgeMap >();
4.1408 - } { // Dummy map test
4.1409 - typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
4.1410 - checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
4.1411 - DummyEdgeMap >();
4.1412 - }
4.1413 - }
4.1414 -
4.1415 - _Graph& graph;
4.1416 - };
4.1417 - };
4.1418 -
4.1419 - /// \brief An empty mappable base graph class.
4.1420 - ///
4.1421 - /// This class provides beside the core graph features
4.1422 - /// map interface for the graph structure.
4.1423 - /// This concept is part of the UGraph concept.
4.1424 - template <typename _Base = BaseUGraphComponent>
4.1425 - class MappableUGraphComponent : public MappableGraphComponent<_Base> {
4.1426 - public:
4.1427 -
4.1428 - typedef _Base Base;
4.1429 - typedef typename Base::UEdge UEdge;
4.1430 -
4.1431 - typedef MappableUGraphComponent Graph;
4.1432 -
4.1433 - /// \brief ReadWrite map of the uedges.
4.1434 - ///
4.1435 - /// ReadWrite map of the uedges.
4.1436 - ///
4.1437 - template <typename Value>
4.1438 - class UEdgeMap : public GraphMap<Graph, UEdge, Value> {
4.1439 - public:
4.1440 - typedef GraphMap<Graph, UEdge, Value> Parent;
4.1441 -
4.1442 - /// \brief Construct a new map.
4.1443 - ///
4.1444 - /// Construct a new map for the graph.
4.1445 - /// \todo call the right parent class constructor
4.1446 - explicit UEdgeMap(const Graph& graph) : Parent(graph) {}
4.1447 -
4.1448 - /// \brief Construct a new map with default value.
4.1449 - ///
4.1450 - /// Construct a new map for the graph and initalise the values.
4.1451 - UEdgeMap(const Graph& graph, const Value& value)
4.1452 - : Parent(graph, value) {}
4.1453 -
4.1454 - /// \brief Copy constructor.
4.1455 - ///
4.1456 - /// Copy Constructor.
4.1457 - UEdgeMap(const UEdgeMap& nm) : Parent(nm) {}
4.1458 -
4.1459 - /// \brief Assign operator.
4.1460 - ///
4.1461 - /// Assign operator.
4.1462 - template <typename CMap>
4.1463 - UEdgeMap& operator=(const CMap&) {
4.1464 - checkConcept<ReadMap<UEdge, Value>, CMap>();
4.1465 - return *this;
4.1466 - }
4.1467 -
4.1468 - };
4.1469 -
4.1470 -
4.1471 - template <typename _Graph>
4.1472 - struct Constraints {
4.1473 -
4.1474 - struct Dummy {
4.1475 - int value;
4.1476 - Dummy() : value(0) {}
4.1477 - Dummy(int _v) : value(_v) {}
4.1478 - };
4.1479 -
4.1480 - void constraints() {
4.1481 - checkConcept<Base, _Graph>();
4.1482 - checkConcept<MappableGraphComponent<Base>, _Graph>();
4.1483 -
4.1484 - { // int map test
4.1485 - typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap;
4.1486 - checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>,
4.1487 - IntUEdgeMap >();
4.1488 - } { // bool map test
4.1489 - typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap;
4.1490 - checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>,
4.1491 - BoolUEdgeMap >();
4.1492 - } { // Dummy map test
4.1493 - typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap;
4.1494 - checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>,
4.1495 - DummyUEdgeMap >();
4.1496 - }
4.1497 - }
4.1498 -
4.1499 - _Graph& graph;
4.1500 - };
4.1501 - };
4.1502 -
4.1503 -
4.1504 - /// \brief An empty extendable graph class.
4.1505 - ///
4.1506 - /// This class provides beside the core graph features graph
4.1507 - /// extendable interface for the graph structure. The main
4.1508 - /// difference between the base and this interface is that the
4.1509 - /// graph alterations should handled already on this level.
4.1510 - template <typename _Base = BaseGraphComponent>
4.1511 - class ExtendableGraphComponent : public _Base {
4.1512 - public:
4.1513 -
4.1514 - typedef typename _Base::Node Node;
4.1515 - typedef typename _Base::Edge Edge;
4.1516 -
4.1517 - /// \brief Adds a new node to the graph.
4.1518 - ///
4.1519 - /// Adds a new node to the graph.
4.1520 - ///
4.1521 - Node addNode() {
4.1522 - return INVALID;
4.1523 - }
4.1524 -
4.1525 - /// \brief Adds a new edge connects the given two nodes.
4.1526 - ///
4.1527 - /// Adds a new edge connects the the given two nodes.
4.1528 - Edge addEdge(const Node&, const Node&) {
4.1529 - return INVALID;
4.1530 - }
4.1531 -
4.1532 - template <typename _Graph>
4.1533 - struct Constraints {
4.1534 - void constraints() {
4.1535 - typename _Graph::Node node_a, node_b;
4.1536 - node_a = graph.addNode();
4.1537 - node_b = graph.addNode();
4.1538 - typename _Graph::Edge edge;
4.1539 - edge = graph.addEdge(node_a, node_b);
4.1540 - }
4.1541 -
4.1542 - _Graph& graph;
4.1543 - };
4.1544 - };
4.1545 -
4.1546 - /// \brief An empty extendable base undirected graph class.
4.1547 - ///
4.1548 - /// This class provides beside the core undirected graph features
4.1549 - /// core undircted graph extend interface for the graph structure.
4.1550 - /// The main difference between the base and this interface is
4.1551 - /// that the graph alterations should handled already on this
4.1552 - /// level.
4.1553 - template <typename _Base = BaseUGraphComponent>
4.1554 - class ExtendableUGraphComponent : public _Base {
4.1555 - public:
4.1556 -
4.1557 - typedef typename _Base::Node Node;
4.1558 - typedef typename _Base::UEdge UEdge;
4.1559 -
4.1560 - /// \brief Adds a new node to the graph.
4.1561 - ///
4.1562 - /// Adds a new node to the graph.
4.1563 - ///
4.1564 - Node addNode() {
4.1565 - return INVALID;
4.1566 - }
4.1567 -
4.1568 - /// \brief Adds a new edge connects the given two nodes.
4.1569 - ///
4.1570 - /// Adds a new edge connects the the given two nodes.
4.1571 - UEdge addEdge(const Node&, const Node&) {
4.1572 - return INVALID;
4.1573 - }
4.1574 -
4.1575 - template <typename _Graph>
4.1576 - struct Constraints {
4.1577 - void constraints() {
4.1578 - typename _Graph::Node node_a, node_b;
4.1579 - node_a = graph.addNode();
4.1580 - node_b = graph.addNode();
4.1581 - typename _Graph::UEdge uedge;
4.1582 - uedge = graph.addUEdge(node_a, node_b);
4.1583 - }
4.1584 -
4.1585 - _Graph& graph;
4.1586 - };
4.1587 - };
4.1588 -
4.1589 - /// \brief An empty erasable graph class.
4.1590 - ///
4.1591 - /// This class provides beside the core graph features core erase
4.1592 - /// functions for the graph structure. The main difference between
4.1593 - /// the base and this interface is that the graph alterations
4.1594 - /// should handled already on this level.
4.1595 - template <typename _Base = BaseGraphComponent>
4.1596 - class ErasableGraphComponent : public _Base {
4.1597 - public:
4.1598 -
4.1599 - typedef _Base Base;
4.1600 - typedef typename Base::Node Node;
4.1601 - typedef typename Base::Edge Edge;
4.1602 -
4.1603 - /// \brief Erase a node from the graph.
4.1604 - ///
4.1605 - /// Erase a node from the graph. This function should
4.1606 - /// erase all edges connecting to the node.
4.1607 - void erase(const Node&) {}
4.1608 -
4.1609 - /// \brief Erase an edge from the graph.
4.1610 - ///
4.1611 - /// Erase an edge from the graph.
4.1612 - ///
4.1613 - void erase(const Edge&) {}
4.1614 -
4.1615 - template <typename _Graph>
4.1616 - struct Constraints {
4.1617 - void constraints() {
4.1618 - typename _Graph::Node node;
4.1619 - graph.erase(node);
4.1620 - typename _Graph::Edge edge;
4.1621 - graph.erase(edge);
4.1622 - }
4.1623 -
4.1624 - _Graph& graph;
4.1625 - };
4.1626 - };
4.1627 -
4.1628 - /// \brief An empty erasable base undirected graph class.
4.1629 - ///
4.1630 - /// This class provides beside the core undirected graph features
4.1631 - /// core erase functions for the undirceted graph structure. The
4.1632 - /// main difference between the base and this interface is that
4.1633 - /// the graph alterations should handled already on this level.
4.1634 - template <typename _Base = BaseUGraphComponent>
4.1635 - class ErasableUGraphComponent : public _Base {
4.1636 - public:
4.1637 -
4.1638 - typedef _Base Base;
4.1639 - typedef typename Base::Node Node;
4.1640 - typedef typename Base::UEdge UEdge;
4.1641 -
4.1642 - /// \brief Erase a node from the graph.
4.1643 - ///
4.1644 - /// Erase a node from the graph. This function should erase
4.1645 - /// edges connecting to the node.
4.1646 - void erase(const Node&) {}
4.1647 -
4.1648 - /// \brief Erase an edge from the graph.
4.1649 - ///
4.1650 - /// Erase an edge from the graph.
4.1651 - ///
4.1652 - void erase(const UEdge&) {}
4.1653 -
4.1654 - template <typename _Graph>
4.1655 - struct Constraints {
4.1656 - void constraints() {
4.1657 - typename _Graph::Node node;
4.1658 - graph.erase(node);
4.1659 - typename _Graph::Edge edge;
4.1660 - graph.erase(edge);
4.1661 - }
4.1662 -
4.1663 - _Graph& graph;
4.1664 - };
4.1665 - };
4.1666 -
4.1667 - /// \brief An empty clearable base graph class.
4.1668 - ///
4.1669 - /// This class provides beside the core graph features core clear
4.1670 - /// functions for the graph structure. The main difference between
4.1671 - /// the base and this interface is that the graph alterations
4.1672 - /// should handled already on this level.
4.1673 - template <typename _Base = BaseGraphComponent>
4.1674 - class ClearableGraphComponent : public _Base {
4.1675 - public:
4.1676 -
4.1677 - /// \brief Erase all nodes and edges from the graph.
4.1678 - ///
4.1679 - /// Erase all nodes and edges from the graph.
4.1680 - ///
4.1681 - void clear() {}
4.1682 -
4.1683 - template <typename _Graph>
4.1684 - struct Constraints {
4.1685 - void constraints() {
4.1686 - graph.clear();
4.1687 - }
4.1688 -
4.1689 - _Graph graph;
4.1690 - };
4.1691 - };
4.1692 -
4.1693 - /// \brief An empty clearable base undirected graph class.
4.1694 - ///
4.1695 - /// This class provides beside the core undirected graph features
4.1696 - /// core clear functions for the undirected graph structure. The
4.1697 - /// main difference between the base and this interface is that
4.1698 - /// the graph alterations should handled already on this level.
4.1699 - template <typename _Base = BaseUGraphComponent>
4.1700 - class ClearableUGraphComponent : public _Base {
4.1701 - public:
4.1702 -
4.1703 - /// \brief Erase all nodes and undirected edges from the graph.
4.1704 - ///
4.1705 - /// Erase all nodes and undirected edges from the graph.
4.1706 - ///
4.1707 - void clear() {}
4.1708 -
4.1709 - template <typename _Graph>
4.1710 - struct Constraints {
4.1711 - void constraints() {
4.1712 - graph.clear();
4.1713 - }
4.1714 -
4.1715 - _Graph graph;
4.1716 - };
4.1717 - };
4.1718 -
4.1719 - }
4.1720 -
4.1721 -}
4.1722 -
4.1723 -#endif
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/concept/graph_components.h Tue Jul 11 15:42:15 2006 +0000
5.3 @@ -0,0 +1,1720 @@
5.4 +/* -*- C++ -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library
5.7 + *
5.8 + * Copyright (C) 2003-2006
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +///\ingroup graph_concepts
5.23 +///\file
5.24 +///\brief The concept of the graph components.
5.25 +
5.26 +
5.27 +#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
5.28 +#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
5.29 +
5.30 +#include <lemon/bits/invalid.h>
5.31 +#include <lemon/concept/maps.h>
5.32 +
5.33 +#include <lemon/bits/alteration_notifier.h>
5.34 +
5.35 +namespace lemon {
5.36 + namespace concept {
5.37 +
5.38 + /// \brief Skeleton class for graph Node and Edge types
5.39 + ///
5.40 + /// This class describes the interface of Node and Edge (and UEdge
5.41 + /// in undirected graphs) subtypes of graph types.
5.42 + ///
5.43 + /// \note This class is a template class so that we can use it to
5.44 + /// create graph skeleton classes. The reason for this is than Node
5.45 + /// and Edge types should \em not derive from the same base class.
5.46 + /// For Node you should instantiate it with character 'n' and for Edge
5.47 + /// with 'e'.
5.48 +
5.49 +#ifndef DOXYGEN
5.50 + template <char _selector = '0'>
5.51 +#endif
5.52 + class GraphItem {
5.53 + public:
5.54 + /// \brief Default constructor.
5.55 + ///
5.56 + /// \warning The default constructor is not required to set
5.57 + /// the item to some well-defined value. So you should consider it
5.58 + /// as uninitialized.
5.59 + GraphItem() {}
5.60 + /// \brief Copy constructor.
5.61 + ///
5.62 + /// Copy constructor.
5.63 + ///
5.64 + GraphItem(const GraphItem &) {}
5.65 + /// \brief Invalid constructor \& conversion.
5.66 + ///
5.67 + /// This constructor initializes the item to be invalid.
5.68 + /// \sa Invalid for more details.
5.69 + GraphItem(Invalid) {}
5.70 + /// \brief Assign operator for nodes.
5.71 + ///
5.72 + /// The nodes are assignable.
5.73 + ///
5.74 + GraphItem& operator=(GraphItem const&) { return *this; }
5.75 + /// \brief Equality operator.
5.76 + ///
5.77 + /// Two iterators are equal if and only if they represents the
5.78 + /// same node in the graph or both are invalid.
5.79 + bool operator==(GraphItem) const { return false; }
5.80 + /// \brief Inequality operator.
5.81 + ///
5.82 + /// \sa operator==(const Node& n)
5.83 + ///
5.84 + bool operator!=(GraphItem) const { return false; }
5.85 +
5.86 + /// \brief Artificial ordering operator.
5.87 + ///
5.88 + /// To allow the use of graph descriptors as key type in std::map or
5.89 + /// similar associative container we require this.
5.90 + ///
5.91 + /// \note This operator only have to define some strict ordering of
5.92 + /// the items; this order has nothing to do with the iteration
5.93 + /// ordering of the items.
5.94 + bool operator<(GraphItem) const { return false; }
5.95 +
5.96 + template<typename _GraphItem>
5.97 + struct Constraints {
5.98 + void constraints() {
5.99 + _GraphItem i1;
5.100 + _GraphItem i2 = i1;
5.101 + _GraphItem i3 = INVALID;
5.102 +
5.103 + i1 = i2 = i3;
5.104 +
5.105 + bool b;
5.106 + // b = (ia == ib) && (ia != ib) && (ia < ib);
5.107 + b = (ia == ib) && (ia != ib);
5.108 + b = (ia == INVALID) && (ib != INVALID);
5.109 + b = (ia < ib);
5.110 + }
5.111 +
5.112 + const _GraphItem &ia;
5.113 + const _GraphItem &ib;
5.114 + };
5.115 + };
5.116 +
5.117 + /// \brief An empty base graph class.
5.118 + ///
5.119 + /// This class provides the minimal set of features needed for a graph
5.120 + /// structure. All graph concepts have to be conform to this base
5.121 + /// graph. It just provides types for nodes and edges and functions to
5.122 + /// get the source and the target of the edges.
5.123 + class BaseGraphComponent {
5.124 + public:
5.125 +
5.126 + typedef BaseGraphComponent Graph;
5.127 +
5.128 + /// \brief Node class of the graph.
5.129 + ///
5.130 + /// This class represents the Nodes of the graph.
5.131 + ///
5.132 + typedef GraphItem<'n'> Node;
5.133 +
5.134 + /// \brief Edge class of the graph.
5.135 + ///
5.136 + /// This class represents the Edges of the graph.
5.137 + ///
5.138 + typedef GraphItem<'e'> Edge;
5.139 +
5.140 + /// \brief Gives back the target node of an edge.
5.141 + ///
5.142 + /// Gives back the target node of an edge.
5.143 + ///
5.144 + Node target(const Edge&) const { return INVALID;}
5.145 +
5.146 + /// \brief Gives back the source node of an edge.
5.147 + ///
5.148 + /// Gives back the source node of an edge.
5.149 + ///
5.150 + Node source(const Edge&) const { return INVALID;}
5.151 +
5.152 + /// \brief Gives back the opposite node on the given edge.
5.153 + ///
5.154 + /// Gives back the opposite node on the given edge.
5.155 + Node oppositeNode(const Node&, const Edge&) const {
5.156 + return INVALID;
5.157 + }
5.158 +
5.159 + template <typename _Graph>
5.160 + struct Constraints {
5.161 + typedef typename _Graph::Node Node;
5.162 + typedef typename _Graph::Edge Edge;
5.163 +
5.164 + void constraints() {
5.165 + checkConcept<GraphItem<'n'>, Node>();
5.166 + checkConcept<GraphItem<'e'>, Edge>();
5.167 + {
5.168 + Node n;
5.169 + Edge e(INVALID);
5.170 + n = graph.source(e);
5.171 + n = graph.target(e);
5.172 + n = graph.oppositeNode(n, e);
5.173 + }
5.174 + }
5.175 +
5.176 + const _Graph& graph;
5.177 + };
5.178 + };
5.179 +
5.180 + /// \brief An empty base undirected graph class.
5.181 + ///
5.182 + /// This class provides the minimal set of features needed for an
5.183 + /// undirected graph structure. All undirected graph concepts have
5.184 + /// to be conform to this base graph. It just provides types for
5.185 + /// nodes, edges and undirected edges and functions to get the
5.186 + /// source and the target of the edges and undirected edges,
5.187 + /// conversion from edges to undirected edges and function to get
5.188 + /// both direction of the undirected edges.
5.189 + class BaseUGraphComponent : public BaseGraphComponent {
5.190 + public:
5.191 + typedef BaseGraphComponent::Node Node;
5.192 + typedef BaseGraphComponent::Edge Edge;
5.193 + /// \brief Undirected edge class of the graph.
5.194 + ///
5.195 + /// This class represents the undirected edges of the graph.
5.196 + /// The undirected graphs can be used as a directed graph which
5.197 + /// for each edge contains the opposite edge too so the graph is
5.198 + /// bidirected. The undirected edge represents two opposite
5.199 + /// directed edges.
5.200 + class UEdge : public GraphItem<'u'> {
5.201 + public:
5.202 + typedef GraphItem<'u'> Parent;
5.203 + /// \brief Default constructor.
5.204 + ///
5.205 + /// \warning The default constructor is not required to set
5.206 + /// the item to some well-defined value. So you should consider it
5.207 + /// as uninitialized.
5.208 + UEdge() {}
5.209 + /// \brief Copy constructor.
5.210 + ///
5.211 + /// Copy constructor.
5.212 + ///
5.213 + UEdge(const UEdge &) : Parent() {}
5.214 + /// \brief Invalid constructor \& conversion.
5.215 + ///
5.216 + /// This constructor initializes the item to be invalid.
5.217 + /// \sa Invalid for more details.
5.218 + UEdge(Invalid) {}
5.219 + /// \brief Converter from edge to undirected edge.
5.220 + ///
5.221 + /// Besides the core graph item functionality each edge should
5.222 + /// be convertible to the represented undirected edge.
5.223 + UEdge(const Edge&) {}
5.224 + };
5.225 +
5.226 + /// \brief Returns the direction of the edge.
5.227 + ///
5.228 + /// Returns the direction of the edge. Each edge represents an
5.229 + /// undirected edge with a direction. It gives back the
5.230 + /// direction.
5.231 + bool direction(const Edge&) const { return true; }
5.232 +
5.233 + /// \brief Returns the directed edge.
5.234 + ///
5.235 + /// Returns the directed edge from its direction and the
5.236 + /// represented undirected edge.
5.237 + Edge direct(const UEdge&, bool) const { return INVALID;}
5.238 +
5.239 + /// \brief Returns the directed edge.
5.240 + ///
5.241 + /// Returns the directed edge from its source and the
5.242 + /// represented undirected edge.
5.243 + Edge direct(const UEdge&, const Node&) const { return INVALID;}
5.244 +
5.245 + /// \brief Returns the opposite edge.
5.246 + ///
5.247 + /// Returns the opposite edge. It is the edge representing the
5.248 + /// same undirected edge and has opposite direction.
5.249 + Edge oppositeEdge(const Edge&) const { return INVALID;}
5.250 +
5.251 + /// \brief Gives back the target node of an undirected edge.
5.252 + ///
5.253 + /// Gives back the target node of an undirected edge. The name
5.254 + /// target is a little confusing because the undirected edge
5.255 + /// does not have target but it just means that one of the end
5.256 + /// node.
5.257 + Node target(const UEdge&) const { return INVALID;}
5.258 +
5.259 + /// \brief Gives back the source node of an undirected edge.
5.260 + ///
5.261 + /// Gives back the source node of an undirected edge. The name
5.262 + /// source is a little confusing because the undirected edge
5.263 + /// does not have source but it just means that one of the end
5.264 + /// node.
5.265 + Node source(const UEdge&) const { return INVALID;}
5.266 +
5.267 + template <typename _Graph>
5.268 + struct Constraints {
5.269 + typedef typename _Graph::Node Node;
5.270 + typedef typename _Graph::Edge Edge;
5.271 + typedef typename _Graph::UEdge UEdge;
5.272 +
5.273 + void constraints() {
5.274 + checkConcept<BaseGraphComponent, _Graph>();
5.275 + checkConcept<GraphItem<'u'>, UEdge>();
5.276 + {
5.277 + Node n;
5.278 + UEdge ue(INVALID);
5.279 + Edge e;
5.280 + n = graph.source(ue);
5.281 + n = graph.target(ue);
5.282 + e = graph.direct(ue, true);
5.283 + e = graph.direct(ue, n);
5.284 + e = graph.oppositeEdge(e);
5.285 + ue = e;
5.286 + bool d = graph.direction(e);
5.287 + ignore_unused_variable_warning(d);
5.288 + }
5.289 + }
5.290 +
5.291 + const _Graph& graph;
5.292 + };
5.293 +
5.294 + };
5.295 +
5.296 + /// \brief An empty iterable base graph class.
5.297 + ///
5.298 + /// This class provides beside the core graph features
5.299 + /// core iterable interface for the graph structure.
5.300 + /// Most of the base graphs should be conform to this concept.
5.301 + template <typename _Base = BaseGraphComponent>
5.302 + class BaseIterableGraphComponent : public _Base {
5.303 + public:
5.304 +
5.305 + typedef _Base Base;
5.306 + typedef typename Base::Node Node;
5.307 + typedef typename Base::Edge Edge;
5.308 +
5.309 + /// \brief Gives back the first node in the iterating order.
5.310 + ///
5.311 + /// Gives back the first node in the iterating order.
5.312 + ///
5.313 + void first(Node&) const {}
5.314 +
5.315 + /// \brief Gives back the next node in the iterating order.
5.316 + ///
5.317 + /// Gives back the next node in the iterating order.
5.318 + ///
5.319 + void next(Node&) const {}
5.320 +
5.321 + /// \brief Gives back the first edge in the iterating order.
5.322 + ///
5.323 + /// Gives back the first edge in the iterating order.
5.324 + ///
5.325 + void first(Edge&) const {}
5.326 +
5.327 + /// \brief Gives back the next edge in the iterating order.
5.328 + ///
5.329 + /// Gives back the next edge in the iterating order.
5.330 + ///
5.331 + void next(Edge&) const {}
5.332 +
5.333 +
5.334 + /// \brief Gives back the first of the edges point to the given
5.335 + /// node.
5.336 + ///
5.337 + /// Gives back the first of the edges point to the given node.
5.338 + ///
5.339 + void firstIn(Edge&, const Node&) const {}
5.340 +
5.341 + /// \brief Gives back the next of the edges points to the given
5.342 + /// node.
5.343 + ///
5.344 + /// Gives back the next of the edges points to the given node.
5.345 + ///
5.346 + void nextIn(Edge&) const {}
5.347 +
5.348 + /// \brief Gives back the first of the edges start from the
5.349 + /// given node.
5.350 + ///
5.351 + /// Gives back the first of the edges start from the given node.
5.352 + ///
5.353 + void firstOut(Edge&, const Node&) const {}
5.354 +
5.355 + /// \brief Gives back the next of the edges start from the given
5.356 + /// node.
5.357 + ///
5.358 + /// Gives back the next of the edges start from the given node.
5.359 + ///
5.360 + void nextOut(Edge&) const {}
5.361 +
5.362 +
5.363 + template <typename _Graph>
5.364 + struct Constraints {
5.365 +
5.366 + void constraints() {
5.367 + checkConcept< BaseGraphComponent, _Graph >();
5.368 + typename _Graph::Node node;
5.369 + typename _Graph::Edge edge;
5.370 + {
5.371 + graph.first(node);
5.372 + graph.next(node);
5.373 + }
5.374 + {
5.375 + graph.first(edge);
5.376 + graph.next(edge);
5.377 + }
5.378 + {
5.379 + graph.firstIn(edge, node);
5.380 + graph.nextIn(edge);
5.381 + }
5.382 + {
5.383 + graph.firstOut(edge, node);
5.384 + graph.nextOut(edge);
5.385 + }
5.386 + }
5.387 +
5.388 + const _Graph& graph;
5.389 + };
5.390 + };
5.391 +
5.392 + /// \brief An empty iterable base undirected graph class.
5.393 + ///
5.394 + /// This class provides beside the core undirceted graph features
5.395 + /// core iterable interface for the undirected graph structure.
5.396 + /// Most of the base undirected graphs should be conform to this
5.397 + /// concept.
5.398 + template <typename _Base = BaseUGraphComponent>
5.399 + class BaseIterableUGraphComponent
5.400 + : public BaseIterableGraphComponent<_Base> {
5.401 + public:
5.402 +
5.403 + typedef _Base Base;
5.404 + typedef typename Base::UEdge UEdge;
5.405 + typedef typename Base::Node Node;
5.406 +
5.407 + using BaseIterableGraphComponent<_Base>::first;
5.408 + using BaseIterableGraphComponent<_Base>::next;
5.409 +
5.410 + /// \brief Gives back the first undirected edge in the iterating
5.411 + /// order.
5.412 + ///
5.413 + /// Gives back the first undirected edge in the iterating order.
5.414 + ///
5.415 + void first(UEdge&) const {}
5.416 +
5.417 + /// \brief Gives back the next undirected edge in the iterating
5.418 + /// order.
5.419 + ///
5.420 + /// Gives back the next undirected edge in the iterating order.
5.421 + ///
5.422 + void next(UEdge&) const {}
5.423 +
5.424 +
5.425 + /// \brief Gives back the first of the undirected edges from the
5.426 + /// given node.
5.427 + ///
5.428 + /// Gives back the first of the undirected edges from the given
5.429 + /// node. The bool parameter gives back that direction which
5.430 + /// gives a good direction of the uedge so the source of the
5.431 + /// directed edge is the given node.
5.432 + void firstInc(UEdge&, bool&, const Node&) const {}
5.433 +
5.434 + /// \brief Gives back the next of the undirected edges from the
5.435 + /// given node.
5.436 + ///
5.437 + /// Gives back the next of the undirected edges from the given
5.438 + /// node. The bool parameter should be used as the \c firstInc()
5.439 + /// use it.
5.440 + void nextInc(UEdge&, bool&) const {}
5.441 +
5.442 + template <typename _Graph>
5.443 + struct Constraints {
5.444 +
5.445 + void constraints() {
5.446 + checkConcept<Base, _Graph >();
5.447 + checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
5.448 + typename _Graph::Node node;
5.449 + typename _Graph::UEdge uedge;
5.450 + bool dir;
5.451 + {
5.452 + graph.first(uedge);
5.453 + graph.next(uedge);
5.454 + }
5.455 + {
5.456 + graph.firstInc(uedge, dir, node);
5.457 + graph.nextInc(uedge, dir);
5.458 + }
5.459 + }
5.460 +
5.461 + const _Graph& graph;
5.462 + };
5.463 + };
5.464 +
5.465 + /// \brief An empty idable base graph class.
5.466 + ///
5.467 + /// This class provides beside the core graph features
5.468 + /// core id functions for the graph structure.
5.469 + /// The most of the base graphs should be conform to this concept.
5.470 + /// The id's are unique and immutable.
5.471 + template <typename _Base = BaseGraphComponent>
5.472 + class IDableGraphComponent : public _Base {
5.473 + public:
5.474 +
5.475 + typedef _Base Base;
5.476 + typedef typename Base::Node Node;
5.477 + typedef typename Base::Edge Edge;
5.478 +
5.479 + /// \brief Gives back an unique integer id for the Node.
5.480 + ///
5.481 + /// Gives back an unique integer id for the Node.
5.482 + ///
5.483 + int id(const Node&) const { return -1;}
5.484 +
5.485 + /// \brief Gives back the node by the unique id.
5.486 + ///
5.487 + /// Gives back the node by the unique id.
5.488 + /// If the graph does not contain node with the given id
5.489 + /// then the result of the function is undetermined.
5.490 + Node nodeFromId(int) const { return INVALID;}
5.491 +
5.492 + /// \brief Gives back an unique integer id for the Edge.
5.493 + ///
5.494 + /// Gives back an unique integer id for the Edge.
5.495 + ///
5.496 + int id(const Edge&) const { return -1;}
5.497 +
5.498 + /// \brief Gives back the edge by the unique id.
5.499 + ///
5.500 + /// Gives back the edge by the unique id.
5.501 + /// If the graph does not contain edge with the given id
5.502 + /// then the result of the function is undetermined.
5.503 + Edge edgeFromId(int) const { return INVALID;}
5.504 +
5.505 + /// \brief Gives back an integer greater or equal to the maximum
5.506 + /// Node id.
5.507 + ///
5.508 + /// Gives back an integer greater or equal to the maximum Node
5.509 + /// id.
5.510 + int maxNodeId() const { return -1;}
5.511 +
5.512 + /// \brief Gives back an integer greater or equal to the maximum
5.513 + /// Edge id.
5.514 + ///
5.515 + /// Gives back an integer greater or equal to the maximum Edge
5.516 + /// id.
5.517 + int maxEdgeId() const { return -1;}
5.518 +
5.519 + template <typename _Graph>
5.520 + struct Constraints {
5.521 +
5.522 + void constraints() {
5.523 + checkConcept< BaseGraphComponent, _Graph >();
5.524 + typename _Graph::Node node;
5.525 + int nid = graph.id(node);
5.526 + nid = graph.id(node);
5.527 + node = graph.nodeFromId(nid);
5.528 + typename _Graph::Edge edge;
5.529 + int eid = graph.id(edge);
5.530 + eid = graph.id(edge);
5.531 + edge = graph.edgeFromId(eid);
5.532 +
5.533 + nid = graph.maxNodeId();
5.534 + ignore_unused_variable_warning(nid);
5.535 + eid = graph.maxEdgeId();
5.536 + ignore_unused_variable_warning(eid);
5.537 + }
5.538 +
5.539 + const _Graph& graph;
5.540 + };
5.541 + };
5.542 +
5.543 + /// \brief An empty idable base undirected graph class.
5.544 + ///
5.545 + /// This class provides beside the core undirected graph features
5.546 + /// core id functions for the undirected graph structure. The
5.547 + /// most of the base undirected graphs should be conform to this
5.548 + /// concept. The id's are unique and immutable.
5.549 + template <typename _Base = BaseUGraphComponent>
5.550 + class IDableUGraphComponent : public IDableGraphComponent<_Base> {
5.551 + public:
5.552 +
5.553 + typedef _Base Base;
5.554 + typedef typename Base::UEdge UEdge;
5.555 +
5.556 + using IDableGraphComponent<_Base>::id;
5.557 +
5.558 + /// \brief Gives back an unique integer id for the UEdge.
5.559 + ///
5.560 + /// Gives back an unique integer id for the UEdge.
5.561 + ///
5.562 + int id(const UEdge&) const { return -1;}
5.563 +
5.564 + /// \brief Gives back the undirected edge by the unique id.
5.565 + ///
5.566 + /// Gives back the undirected edge by the unique id. If the
5.567 + /// graph does not contain edge with the given id then the
5.568 + /// result of the function is undetermined.
5.569 + UEdge uEdgeFromId(int) const { return INVALID;}
5.570 +
5.571 + /// \brief Gives back an integer greater or equal to the maximum
5.572 + /// UEdge id.
5.573 + ///
5.574 + /// Gives back an integer greater or equal to the maximum UEdge
5.575 + /// id.
5.576 + int maxUEdgeId() const { return -1;}
5.577 +
5.578 + template <typename _Graph>
5.579 + struct Constraints {
5.580 +
5.581 + void constraints() {
5.582 + checkConcept<Base, _Graph >();
5.583 + checkConcept<IDableGraphComponent<Base>, _Graph >();
5.584 + typename _Graph::UEdge uedge;
5.585 + int ueid = graph.id(uedge);
5.586 + ueid = graph.id(uedge);
5.587 + uedge = graph.uEdgeFromId(ueid);
5.588 + ueid = graph.maxUEdgeId();
5.589 + ignore_unused_variable_warning(ueid);
5.590 + }
5.591 +
5.592 + const _Graph& graph;
5.593 + };
5.594 + };
5.595 +
5.596 + /// \brief An empty extendable base graph class.
5.597 + ///
5.598 + /// This class provides beside the core graph features
5.599 + /// core graph extend interface for the graph structure.
5.600 + /// The most of the base graphs should be conform to this concept.
5.601 + template <typename _Base = BaseGraphComponent>
5.602 + class BaseExtendableGraphComponent : public _Base {
5.603 + public:
5.604 +
5.605 + typedef typename _Base::Node Node;
5.606 + typedef typename _Base::Edge Edge;
5.607 +
5.608 + /// \brief Adds a new node to the graph.
5.609 + ///
5.610 + /// Adds a new node to the graph.
5.611 + ///
5.612 + Node addNode() {
5.613 + return INVALID;
5.614 + }
5.615 +
5.616 + /// \brief Adds a new edge connects the given two nodes.
5.617 + ///
5.618 + /// Adds a new edge connects the the given two nodes.
5.619 + Edge addEdge(const Node&, const Node&) {
5.620 + return INVALID;
5.621 + }
5.622 +
5.623 + template <typename _Graph>
5.624 + struct Constraints {
5.625 + void constraints() {
5.626 + typename _Graph::Node node_a, node_b;
5.627 + node_a = graph.addNode();
5.628 + node_b = graph.addNode();
5.629 + typename _Graph::Edge edge;
5.630 + edge = graph.addEdge(node_a, node_b);
5.631 + }
5.632 +
5.633 + _Graph& graph;
5.634 + };
5.635 + };
5.636 +
5.637 + /// \brief An empty extendable base undirected graph class.
5.638 + ///
5.639 + /// This class provides beside the core undirected graph features
5.640 + /// core undircted graph extend interface for the graph structure.
5.641 + /// The most of the base graphs should be conform to this concept.
5.642 + template <typename _Base = BaseUGraphComponent>
5.643 + class BaseExtendableUGraphComponent : public _Base {
5.644 + public:
5.645 +
5.646 + typedef typename _Base::Node Node;
5.647 + typedef typename _Base::UEdge UEdge;
5.648 +
5.649 + /// \brief Adds a new node to the graph.
5.650 + ///
5.651 + /// Adds a new node to the graph.
5.652 + ///
5.653 + Node addNode() {
5.654 + return INVALID;
5.655 + }
5.656 +
5.657 + /// \brief Adds a new edge connects the given two nodes.
5.658 + ///
5.659 + /// Adds a new edge connects the the given two nodes.
5.660 + UEdge addEdge(const Node&, const Node&) {
5.661 + return INVALID;
5.662 + }
5.663 +
5.664 + template <typename _Graph>
5.665 + struct Constraints {
5.666 + void constraints() {
5.667 + typename _Graph::Node node_a, node_b;
5.668 + node_a = graph.addNode();
5.669 + node_b = graph.addNode();
5.670 + typename _Graph::UEdge uedge;
5.671 + uedge = graph.addUEdge(node_a, node_b);
5.672 + }
5.673 +
5.674 + _Graph& graph;
5.675 + };
5.676 + };
5.677 +
5.678 + /// \brief An empty erasable base graph class.
5.679 + ///
5.680 + /// This class provides beside the core graph features
5.681 + /// core erase functions for the graph structure.
5.682 + /// The most of the base graphs should be conform to this concept.
5.683 + template <typename _Base = BaseGraphComponent>
5.684 + class BaseErasableGraphComponent : public _Base {
5.685 + public:
5.686 +
5.687 + typedef _Base Base;
5.688 + typedef typename Base::Node Node;
5.689 + typedef typename Base::Edge Edge;
5.690 +
5.691 + /// \brief Erase a node from the graph.
5.692 + ///
5.693 + /// Erase a node from the graph. This function should not
5.694 + /// erase edges connecting to the Node.
5.695 + void erase(const Node&) {}
5.696 +
5.697 + /// \brief Erase an edge from the graph.
5.698 + ///
5.699 + /// Erase an edge from the graph.
5.700 + ///
5.701 + void erase(const Edge&) {}
5.702 +
5.703 + template <typename _Graph>
5.704 + struct Constraints {
5.705 + void constraints() {
5.706 + typename _Graph::Node node;
5.707 + graph.erase(node);
5.708 + typename _Graph::Edge edge;
5.709 + graph.erase(edge);
5.710 + }
5.711 +
5.712 + _Graph& graph;
5.713 + };
5.714 + };
5.715 +
5.716 + /// \brief An empty erasable base undirected graph class.
5.717 + ///
5.718 + /// This class provides beside the core undirected graph features
5.719 + /// core erase functions for the undirceted graph structure.
5.720 + template <typename _Base = BaseUGraphComponent>
5.721 + class BaseErasableUGraphComponent : public _Base {
5.722 + public:
5.723 +
5.724 + typedef _Base Base;
5.725 + typedef typename Base::Node Node;
5.726 + typedef typename Base::UEdge UEdge;
5.727 +
5.728 + /// \brief Erase a node from the graph.
5.729 + ///
5.730 + /// Erase a node from the graph. This function should not
5.731 + /// erase edges connecting to the Node.
5.732 + void erase(const Node&) {}
5.733 +
5.734 + /// \brief Erase an edge from the graph.
5.735 + ///
5.736 + /// Erase an edge from the graph.
5.737 + ///
5.738 + void erase(const UEdge&) {}
5.739 +
5.740 + template <typename _Graph>
5.741 + struct Constraints {
5.742 + void constraints() {
5.743 + typename _Graph::Node node;
5.744 + graph.erase(node);
5.745 + typename _Graph::Edge edge;
5.746 + graph.erase(edge);
5.747 + }
5.748 +
5.749 + _Graph& graph;
5.750 + };
5.751 + };
5.752 +
5.753 + /// \brief An empty clearable base graph class.
5.754 + ///
5.755 + /// This class provides beside the core graph features
5.756 + /// core clear functions for the graph structure.
5.757 + /// The most of the base graphs should be conform to this concept.
5.758 + template <typename _Base = BaseGraphComponent>
5.759 + class BaseClearableGraphComponent : public _Base {
5.760 + public:
5.761 +
5.762 + /// \brief Erase all the nodes and edges from the graph.
5.763 + ///
5.764 + /// Erase all the nodes and edges from the graph.
5.765 + ///
5.766 + void clear() {}
5.767 +
5.768 + template <typename _Graph>
5.769 + struct Constraints {
5.770 + void constraints() {
5.771 + graph.clear();
5.772 + }
5.773 +
5.774 + _Graph graph;
5.775 + };
5.776 + };
5.777 +
5.778 + /// \brief An empty clearable base undirected graph class.
5.779 + ///
5.780 + /// This class provides beside the core undirected graph features
5.781 + /// core clear functions for the undirected graph structure.
5.782 + /// The most of the base graphs should be conform to this concept.
5.783 + template <typename _Base = BaseUGraphComponent>
5.784 + class BaseClearableUGraphComponent : public _Base {
5.785 + public:
5.786 +
5.787 + /// \brief Erase all the nodes and undirected edges from the graph.
5.788 + ///
5.789 + /// Erase all the nodes and undirected edges from the graph.
5.790 + ///
5.791 + void clear() {}
5.792 +
5.793 + template <typename _Graph>
5.794 + struct Constraints {
5.795 + void constraints() {
5.796 + graph.clear();
5.797 + }
5.798 +
5.799 + _Graph graph;
5.800 + };
5.801 + };
5.802 +
5.803 +
5.804 + /// \brief Skeleton class for graph NodeIt and EdgeIt
5.805 + ///
5.806 + /// Skeleton class for graph NodeIt and EdgeIt.
5.807 + ///
5.808 + template <typename _Graph, typename _Item>
5.809 + class GraphItemIt : public _Item {
5.810 + public:
5.811 + /// \brief Default constructor.
5.812 + ///
5.813 + /// @warning The default constructor sets the iterator
5.814 + /// to an undefined value.
5.815 + GraphItemIt() {}
5.816 + /// \brief Copy constructor.
5.817 + ///
5.818 + /// Copy constructor.
5.819 + ///
5.820 + GraphItemIt(const GraphItemIt& ) {}
5.821 + /// \brief Sets the iterator to the first item.
5.822 + ///
5.823 + /// Sets the iterator to the first item of \c the graph.
5.824 + ///
5.825 + explicit GraphItemIt(const _Graph&) {}
5.826 + /// \brief Invalid constructor \& conversion.
5.827 + ///
5.828 + /// This constructor initializes the item to be invalid.
5.829 + /// \sa Invalid for more details.
5.830 + GraphItemIt(Invalid) {}
5.831 + /// \brief Assign operator for items.
5.832 + ///
5.833 + /// The items are assignable.
5.834 + ///
5.835 + GraphItemIt& operator=(const GraphItemIt&) { return *this; }
5.836 + /// \brief Next item.
5.837 + ///
5.838 + /// Assign the iterator to the next item.
5.839 + ///
5.840 + GraphItemIt& operator++() { return *this; }
5.841 + /// \brief Equality operator
5.842 + ///
5.843 + /// Two iterators are equal if and only if they point to the
5.844 + /// same object or both are invalid.
5.845 + bool operator==(const GraphItemIt&) const { return true;}
5.846 + /// \brief Inequality operator
5.847 + ///
5.848 + /// \sa operator==(Node n)
5.849 + ///
5.850 + bool operator!=(const GraphItemIt&) const { return true;}
5.851 +
5.852 + template<typename _GraphItemIt>
5.853 + struct Constraints {
5.854 + void constraints() {
5.855 + _GraphItemIt it1(g);
5.856 + _GraphItemIt it2;
5.857 +
5.858 + it2 = ++it1;
5.859 + ++it2 = it1;
5.860 + ++(++it1);
5.861 +
5.862 + _Item bi = it1;
5.863 + bi = it2;
5.864 + }
5.865 + _Graph& g;
5.866 + };
5.867 + };
5.868 +
5.869 + /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt
5.870 + ///
5.871 + /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
5.872 + /// base class, the _selector is a additional template parameter. For
5.873 + /// InEdgeIt you should instantiate it with character 'i' and for
5.874 + /// OutEdgeIt with 'o'.
5.875 + template <typename _Graph,
5.876 + typename _Item = typename _Graph::Edge,
5.877 + typename _Base = typename _Graph::Node,
5.878 + char _selector = '0'>
5.879 + class GraphIncIt : public _Item {
5.880 + public:
5.881 + /// \brief Default constructor.
5.882 + ///
5.883 + /// @warning The default constructor sets the iterator
5.884 + /// to an undefined value.
5.885 + GraphIncIt() {}
5.886 + /// \brief Copy constructor.
5.887 + ///
5.888 + /// Copy constructor.
5.889 + ///
5.890 + GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
5.891 + /// \brief Sets the iterator to the first edge incoming into or outgoing
5.892 + /// from the node.
5.893 + ///
5.894 + /// Sets the iterator to the first edge incoming into or outgoing
5.895 + /// from the node.
5.896 + ///
5.897 + explicit GraphIncIt(const _Graph&, const _Base&) {}
5.898 + /// \brief Invalid constructor \& conversion.
5.899 + ///
5.900 + /// This constructor initializes the item to be invalid.
5.901 + /// \sa Invalid for more details.
5.902 + GraphIncIt(Invalid) {}
5.903 + /// \brief Assign operator for iterators.
5.904 + ///
5.905 + /// The iterators are assignable.
5.906 + ///
5.907 + GraphIncIt& operator=(GraphIncIt const&) { return *this; }
5.908 + /// \brief Next item.
5.909 + ///
5.910 + /// Assign the iterator to the next item.
5.911 + ///
5.912 + GraphIncIt& operator++() { return *this; }
5.913 +
5.914 + /// \brief Equality operator
5.915 + ///
5.916 + /// Two iterators are equal if and only if they point to the
5.917 + /// same object or both are invalid.
5.918 + bool operator==(const GraphIncIt&) const { return true;}
5.919 +
5.920 + /// \brief Inequality operator
5.921 + ///
5.922 + /// \sa operator==(Node n)
5.923 + ///
5.924 + bool operator!=(const GraphIncIt&) const { return true;}
5.925 +
5.926 + template <typename _GraphIncIt>
5.927 + struct Constraints {
5.928 + void constraints() {
5.929 + checkConcept<GraphItem<_selector>, _GraphIncIt>();
5.930 + _GraphIncIt it1(graph, node);
5.931 + _GraphIncIt it2;
5.932 +
5.933 + it2 = ++it1;
5.934 + ++it2 = it1;
5.935 + ++(++it1);
5.936 + _Item e = it1;
5.937 + e = it2;
5.938 +
5.939 + }
5.940 +
5.941 + _Item edge;
5.942 + _Base node;
5.943 + _Graph graph;
5.944 + _GraphIncIt it;
5.945 + };
5.946 + };
5.947 +
5.948 +
5.949 + /// \brief An empty iterable graph class.
5.950 + ///
5.951 + /// This class provides beside the core graph features
5.952 + /// iterator based iterable interface for the graph structure.
5.953 + /// This concept is part of the GraphConcept.
5.954 + template <typename _Base = BaseGraphComponent>
5.955 + class IterableGraphComponent : public _Base {
5.956 +
5.957 + public:
5.958 +
5.959 + typedef _Base Base;
5.960 + typedef typename Base::Node Node;
5.961 + typedef typename Base::Edge Edge;
5.962 +
5.963 + typedef IterableGraphComponent Graph;
5.964 +
5.965 +
5.966 + /// \brief This iterator goes through each node.
5.967 + ///
5.968 + /// This iterator goes through each node.
5.969 + ///
5.970 + typedef GraphItemIt<Graph, Node> NodeIt;
5.971 +
5.972 + /// \brief This iterator goes through each node.
5.973 + ///
5.974 + /// This iterator goes through each node.
5.975 + ///
5.976 + typedef GraphItemIt<Graph, Edge> EdgeIt;
5.977 +
5.978 + /// \brief This iterator goes trough the incoming edges of a node.
5.979 + ///
5.980 + /// This iterator goes trough the \e inccoming edges of a certain node
5.981 + /// of a graph.
5.982 + typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt;
5.983 +
5.984 + /// \brief This iterator goes trough the outgoing edges of a node.
5.985 + ///
5.986 + /// This iterator goes trough the \e outgoing edges of a certain node
5.987 + /// of a graph.
5.988 + typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt;
5.989 +
5.990 + /// \brief The base node of the iterator.
5.991 + ///
5.992 + /// Gives back the base node of the iterator.
5.993 + /// It is always the target of the pointed edge.
5.994 + Node baseNode(const InEdgeIt&) const { return INVALID; }
5.995 +
5.996 + /// \brief The running node of the iterator.
5.997 + ///
5.998 + /// Gives back the running node of the iterator.
5.999 + /// It is always the source of the pointed edge.
5.1000 + Node runningNode(const InEdgeIt&) const { return INVALID; }
5.1001 +
5.1002 + /// \brief The base node of the iterator.
5.1003 + ///
5.1004 + /// Gives back the base node of the iterator.
5.1005 + /// It is always the source of the pointed edge.
5.1006 + Node baseNode(const OutEdgeIt&) const { return INVALID; }
5.1007 +
5.1008 + /// \brief The running node of the iterator.
5.1009 + ///
5.1010 + /// Gives back the running node of the iterator.
5.1011 + /// It is always the target of the pointed edge.
5.1012 + Node runningNode(const OutEdgeIt&) const { return INVALID; }
5.1013 +
5.1014 + /// \brief The opposite node on the given edge.
5.1015 + ///
5.1016 + /// Gives back the opposite on the given edge.
5.1017 + /// \todo It should not be here.
5.1018 + Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
5.1019 +
5.1020 +
5.1021 + template <typename _Graph>
5.1022 + struct Constraints {
5.1023 + void constraints() {
5.1024 + checkConcept<Base, _Graph>();
5.1025 +
5.1026 + checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
5.1027 + typename _Graph::EdgeIt >();
5.1028 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
5.1029 + typename _Graph::NodeIt >();
5.1030 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
5.1031 + typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
5.1032 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
5.1033 + typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
5.1034 +
5.1035 + typename _Graph::Node n;
5.1036 + typename _Graph::InEdgeIt ieit(INVALID);
5.1037 + typename _Graph::OutEdgeIt oeit(INVALID);
5.1038 + n = graph.baseNode(ieit);
5.1039 + n = graph.runningNode(ieit);
5.1040 + n = graph.baseNode(oeit);
5.1041 + n = graph.runningNode(oeit);
5.1042 + ignore_unused_variable_warning(n);
5.1043 + }
5.1044 +
5.1045 + const _Graph& graph;
5.1046 +
5.1047 + };
5.1048 + };
5.1049 +
5.1050 + /// \brief An empty iterable undirected graph class.
5.1051 + ///
5.1052 + /// This class provides beside the core graph features iterator
5.1053 + /// based iterable interface for the undirected graph structure.
5.1054 + /// This concept is part of the GraphConcept.
5.1055 + template <typename _Base = BaseUGraphComponent>
5.1056 + class IterableUGraphComponent : public IterableGraphComponent<_Base> {
5.1057 + public:
5.1058 +
5.1059 + typedef _Base Base;
5.1060 + typedef typename Base::Node Node;
5.1061 + typedef typename Base::Edge Edge;
5.1062 + typedef typename Base::UEdge UEdge;
5.1063 +
5.1064 +
5.1065 + typedef IterableUGraphComponent Graph;
5.1066 + using IterableGraphComponent<_Base>::baseNode;
5.1067 + using IterableGraphComponent<_Base>::runningNode;
5.1068 +
5.1069 +
5.1070 + /// \brief This iterator goes through each node.
5.1071 + ///
5.1072 + /// This iterator goes through each node.
5.1073 + typedef GraphItemIt<Graph, UEdge> UEdgeIt;
5.1074 + /// \brief This iterator goes trough the incident edges of a
5.1075 + /// node.
5.1076 + ///
5.1077 + /// This iterator goes trough the incident edges of a certain
5.1078 + /// node of a graph.
5.1079 + typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt;
5.1080 + /// \brief The base node of the iterator.
5.1081 + ///
5.1082 + /// Gives back the base node of the iterator.
5.1083 + Node baseNode(const IncEdgeIt&) const { return INVALID; }
5.1084 +
5.1085 + /// \brief The running node of the iterator.
5.1086 + ///
5.1087 + /// Gives back the running node of the iterator.
5.1088 + Node runningNode(const IncEdgeIt&) const { return INVALID; }
5.1089 +
5.1090 + template <typename _Graph>
5.1091 + struct Constraints {
5.1092 + void constraints() {
5.1093 + checkConcept<Base, _Graph>();
5.1094 + checkConcept<IterableGraphComponent<Base>, _Graph>();
5.1095 +
5.1096 + checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
5.1097 + typename _Graph::UEdgeIt >();
5.1098 + checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
5.1099 + typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
5.1100 +
5.1101 + typename _Graph::Node n;
5.1102 + typename _Graph::IncEdgeIt ueit(INVALID);
5.1103 + n = graph.baseNode(ueit);
5.1104 + n = graph.runningNode(ueit);
5.1105 + }
5.1106 +
5.1107 + const _Graph& graph;
5.1108 +
5.1109 + };
5.1110 + };
5.1111 +
5.1112 + /// \brief An empty alteration notifier graph class.
5.1113 + ///
5.1114 + /// This class provides beside the core graph features alteration
5.1115 + /// notifier interface for the graph structure. This implements
5.1116 + /// an observer-notifier pattern for each graph item. More
5.1117 + /// obsevers can be registered into the notifier and whenever an
5.1118 + /// alteration occured in the graph all the observers will
5.1119 + /// notified about it.
5.1120 + template <typename _Base = BaseGraphComponent>
5.1121 + class AlterableGraphComponent : public _Base {
5.1122 + public:
5.1123 +
5.1124 + typedef _Base Base;
5.1125 + typedef typename Base::Node Node;
5.1126 + typedef typename Base::Edge Edge;
5.1127 +
5.1128 +
5.1129 + /// The node observer registry.
5.1130 + typedef AlterationNotifier<AlterableGraphComponent, Node>
5.1131 + NodeNotifier;
5.1132 + /// The edge observer registry.
5.1133 + typedef AlterationNotifier<AlterableGraphComponent, Edge>
5.1134 + EdgeNotifier;
5.1135 +
5.1136 + /// \brief Gives back the node alteration notifier.
5.1137 + ///
5.1138 + /// Gives back the node alteration notifier.
5.1139 + NodeNotifier& getNotifier(Node) const {
5.1140 + return NodeNotifier();
5.1141 + }
5.1142 +
5.1143 + /// \brief Gives back the edge alteration notifier.
5.1144 + ///
5.1145 + /// Gives back the edge alteration notifier.
5.1146 + EdgeNotifier& getNotifier(Edge) const {
5.1147 + return EdgeNotifier();
5.1148 + }
5.1149 +
5.1150 + template <typename _Graph>
5.1151 + struct Constraints {
5.1152 + void constraints() {
5.1153 + checkConcept<Base, _Graph>();
5.1154 + typename _Graph::NodeNotifier& nn
5.1155 + = graph.getNotifier(typename _Graph::Node());
5.1156 +
5.1157 + typename _Graph::EdgeNotifier& en
5.1158 + = graph.getNotifier(typename _Graph::Edge());
5.1159 +
5.1160 + ignore_unused_variable_warning(nn);
5.1161 + ignore_unused_variable_warning(en);
5.1162 + }
5.1163 +
5.1164 + const _Graph& graph;
5.1165 +
5.1166 + };
5.1167 +
5.1168 + };
5.1169 +
5.1170 + /// \brief An empty alteration notifier undirected graph class.
5.1171 + ///
5.1172 + /// This class provides beside the core graph features alteration
5.1173 + /// notifier interface for the graph structure. This implements
5.1174 + /// an observer-notifier pattern for each graph item. More
5.1175 + /// obsevers can be registered into the notifier and whenever an
5.1176 + /// alteration occured in the graph all the observers will
5.1177 + /// notified about it.
5.1178 + template <typename _Base = BaseUGraphComponent>
5.1179 + class AlterableUGraphComponent : public AlterableGraphComponent<_Base> {
5.1180 + public:
5.1181 +
5.1182 + typedef _Base Base;
5.1183 + typedef typename Base::UEdge UEdge;
5.1184 +
5.1185 +
5.1186 + /// The edge observer registry.
5.1187 + typedef AlterationNotifier<AlterableUGraphComponent, UEdge>
5.1188 + UEdgeNotifier;
5.1189 +
5.1190 + /// \brief Gives back the edge alteration notifier.
5.1191 + ///
5.1192 + /// Gives back the edge alteration notifier.
5.1193 + UEdgeNotifier& getNotifier(UEdge) const {
5.1194 + return UEdgeNotifier();
5.1195 + }
5.1196 +
5.1197 + template <typename _Graph>
5.1198 + struct Constraints {
5.1199 + void constraints() {
5.1200 + checkConcept<Base, _Graph>();
5.1201 + checkConcept<AlterableGraphComponent, _Graph>();
5.1202 + typename _Graph::UEdgeNotifier& uen
5.1203 + = graph.getNotifier(typename _Graph::UEdge());
5.1204 + ignore_unused_variable_warning(uen);
5.1205 + }
5.1206 +
5.1207 + const _Graph& graph;
5.1208 +
5.1209 + };
5.1210 +
5.1211 + };
5.1212 +
5.1213 +
5.1214 + /// \brief Class describing the concept of graph maps
5.1215 + ///
5.1216 + /// This class describes the common interface of the graph maps
5.1217 + /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to
5.1218 + /// associate data to graph descriptors (nodes or edges).
5.1219 + template <typename _Graph, typename _Item, typename _Value>
5.1220 + class GraphMap : public ReadWriteMap<_Item, _Value> {
5.1221 + public:
5.1222 +
5.1223 + typedef ReadWriteMap<_Item, _Value> Parent;
5.1224 +
5.1225 + /// The graph type of the map.
5.1226 + typedef _Graph Graph;
5.1227 + /// The key type of the map.
5.1228 + typedef _Item Key;
5.1229 + /// The value type of the map.
5.1230 + typedef _Value Value;
5.1231 +
5.1232 + /// \brief Construct a new map.
5.1233 + ///
5.1234 + /// Construct a new map for the graph.
5.1235 + explicit GraphMap(const Graph&) {}
5.1236 + /// \brief Construct a new map with default value.
5.1237 + ///
5.1238 + /// Construct a new map for the graph and initalise the values.
5.1239 + GraphMap(const Graph&, const Value&) {}
5.1240 + /// \brief Copy constructor.
5.1241 + ///
5.1242 + /// Copy Constructor.
5.1243 + GraphMap(const GraphMap&) : Parent() {}
5.1244 +
5.1245 + /// \brief Assign operator.
5.1246 + ///
5.1247 + /// Assign operator. It does not mofify the underlying graph,
5.1248 + /// it just iterates on the current item set and set the map
5.1249 + /// with the value returned by the assigned map.
5.1250 + template <typename CMap>
5.1251 + GraphMap& operator=(const CMap&) {
5.1252 + checkConcept<ReadMap<Key, Value>, CMap>();
5.1253 + return *this;
5.1254 + }
5.1255 +
5.1256 + template<typename _Map>
5.1257 + struct Constraints {
5.1258 + void constraints() {
5.1259 + checkConcept<ReadWriteMap<Key, Value>, _Map >();
5.1260 + // Construction with a graph parameter
5.1261 + _Map a(g);
5.1262 + // Constructor with a graph and a default value parameter
5.1263 + _Map a2(g,t);
5.1264 + // Copy constructor.
5.1265 + _Map b(c);
5.1266 +
5.1267 + ReadMap<Key, Value> cmap;
5.1268 + b = cmap;
5.1269 +
5.1270 + ignore_unused_variable_warning(a2);
5.1271 + ignore_unused_variable_warning(b);
5.1272 + }
5.1273 +
5.1274 + const _Map &c;
5.1275 + const Graph &g;
5.1276 + const typename GraphMap::Value &t;
5.1277 + };
5.1278 +
5.1279 + };
5.1280 +
5.1281 + /// \brief An empty mappable graph class.
5.1282 + ///
5.1283 + /// This class provides beside the core graph features
5.1284 + /// map interface for the graph structure.
5.1285 + /// This concept is part of the Graph concept.
5.1286 + template <typename _Base = BaseGraphComponent>
5.1287 + class MappableGraphComponent : public _Base {
5.1288 + public:
5.1289 +
5.1290 + typedef _Base Base;
5.1291 + typedef typename Base::Node Node;
5.1292 + typedef typename Base::Edge Edge;
5.1293 +
5.1294 + typedef MappableGraphComponent Graph;
5.1295 +
5.1296 + /// \brief ReadWrite map of the nodes.
5.1297 + ///
5.1298 + /// ReadWrite map of the nodes.
5.1299 + ///
5.1300 + template <typename Value>
5.1301 + class NodeMap : public GraphMap<Graph, Node, Value> {
5.1302 + private:
5.1303 + NodeMap();
5.1304 + public:
5.1305 + typedef GraphMap<Graph, Node, Value> Parent;
5.1306 +
5.1307 + /// \brief Construct a new map.
5.1308 + ///
5.1309 + /// Construct a new map for the graph.
5.1310 + /// \todo call the right parent class constructor
5.1311 + explicit NodeMap(const Graph& graph) : Parent(graph) {}
5.1312 +
5.1313 + /// \brief Construct a new map with default value.
5.1314 + ///
5.1315 + /// Construct a new map for the graph and initalise the values.
5.1316 + NodeMap(const Graph& graph, const Value& value)
5.1317 + : Parent(graph, value) {}
5.1318 +
5.1319 + /// \brief Copy constructor.
5.1320 + ///
5.1321 + /// Copy Constructor.
5.1322 + NodeMap(const NodeMap& nm) : Parent(nm) {}
5.1323 +
5.1324 + /// \brief Assign operator.
5.1325 + ///
5.1326 + /// Assign operator.
5.1327 + template <typename CMap>
5.1328 + NodeMap& operator=(const CMap&) {
5.1329 + checkConcept<ReadMap<Node, Value>, CMap>();
5.1330 + return *this;
5.1331 + }
5.1332 +
5.1333 + };
5.1334 +
5.1335 + /// \brief ReadWrite map of the edges.
5.1336 + ///
5.1337 + /// ReadWrite map of the edges.
5.1338 + ///
5.1339 + template <typename Value>
5.1340 + class EdgeMap : public GraphMap<Graph, Edge, Value> {
5.1341 + private:
5.1342 + EdgeMap();
5.1343 + public:
5.1344 + typedef GraphMap<Graph, Edge, Value> Parent;
5.1345 +
5.1346 + /// \brief Construct a new map.
5.1347 + ///
5.1348 + /// Construct a new map for the graph.
5.1349 + /// \todo call the right parent class constructor
5.1350 + explicit EdgeMap(const Graph& graph) : Parent(graph) {}
5.1351 +
5.1352 + /// \brief Construct a new map with default value.
5.1353 + ///
5.1354 + /// Construct a new map for the graph and initalise the values.
5.1355 + EdgeMap(const Graph& graph, const Value& value)
5.1356 + : Parent(graph, value) {}
5.1357 +
5.1358 + /// \brief Copy constructor.
5.1359 + ///
5.1360 + /// Copy Constructor.
5.1361 + EdgeMap(const EdgeMap& nm) : Parent(nm) {}
5.1362 +
5.1363 + /// \brief Assign operator.
5.1364 + ///
5.1365 + /// Assign operator.
5.1366 + template <typename CMap>
5.1367 + EdgeMap& operator=(const CMap&) {
5.1368 + checkConcept<ReadMap<Edge, Value>, CMap>();
5.1369 + return *this;
5.1370 + }
5.1371 +
5.1372 + };
5.1373 +
5.1374 +
5.1375 + template <typename _Graph>
5.1376 + struct Constraints {
5.1377 +
5.1378 + struct Dummy {
5.1379 + int value;
5.1380 + Dummy() : value(0) {}
5.1381 + Dummy(int _v) : value(_v) {}
5.1382 + };
5.1383 +
5.1384 + void constraints() {
5.1385 + checkConcept<Base, _Graph>();
5.1386 + { // int map test
5.1387 + typedef typename _Graph::template NodeMap<int> IntNodeMap;
5.1388 + checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
5.1389 + IntNodeMap >();
5.1390 + } { // bool map test
5.1391 + typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
5.1392 + checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
5.1393 + BoolNodeMap >();
5.1394 + } { // Dummy map test
5.1395 + typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap;
5.1396 + checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>,
5.1397 + DummyNodeMap >();
5.1398 + }
5.1399 +
5.1400 + { // int map test
5.1401 + typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
5.1402 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
5.1403 + IntEdgeMap >();
5.1404 + } { // bool map test
5.1405 + typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
5.1406 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
5.1407 + BoolEdgeMap >();
5.1408 + } { // Dummy map test
5.1409 + typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
5.1410 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
5.1411 + DummyEdgeMap >();
5.1412 + }
5.1413 + }
5.1414 +
5.1415 + _Graph& graph;
5.1416 + };
5.1417 + };
5.1418 +
5.1419 + /// \brief An empty mappable base graph class.
5.1420 + ///
5.1421 + /// This class provides beside the core graph features
5.1422 + /// map interface for the graph structure.
5.1423 + /// This concept is part of the UGraph concept.
5.1424 + template <typename _Base = BaseUGraphComponent>
5.1425 + class MappableUGraphComponent : public MappableGraphComponent<_Base> {
5.1426 + public:
5.1427 +
5.1428 + typedef _Base Base;
5.1429 + typedef typename Base::UEdge UEdge;
5.1430 +
5.1431 + typedef MappableUGraphComponent Graph;
5.1432 +
5.1433 + /// \brief ReadWrite map of the uedges.
5.1434 + ///
5.1435 + /// ReadWrite map of the uedges.
5.1436 + ///
5.1437 + template <typename Value>
5.1438 + class UEdgeMap : public GraphMap<Graph, UEdge, Value> {
5.1439 + public:
5.1440 + typedef GraphMap<Graph, UEdge, Value> Parent;
5.1441 +
5.1442 + /// \brief Construct a new map.
5.1443 + ///
5.1444 + /// Construct a new map for the graph.
5.1445 + /// \todo call the right parent class constructor
5.1446 + explicit UEdgeMap(const Graph& graph) : Parent(graph) {}
5.1447 +
5.1448 + /// \brief Construct a new map with default value.
5.1449 + ///
5.1450 + /// Construct a new map for the graph and initalise the values.
5.1451 + UEdgeMap(const Graph& graph, const Value& value)
5.1452 + : Parent(graph, value) {}
5.1453 +
5.1454 + /// \brief Copy constructor.
5.1455 + ///
5.1456 + /// Copy Constructor.
5.1457 + UEdgeMap(const UEdgeMap& nm) : Parent(nm) {}
5.1458 +
5.1459 + /// \brief Assign operator.
5.1460 + ///
5.1461 + /// Assign operator.
5.1462 + template <typename CMap>
5.1463 + UEdgeMap& operator=(const CMap&) {
5.1464 + checkConcept<ReadMap<UEdge, Value>, CMap>();
5.1465 + return *this;
5.1466 + }
5.1467 +
5.1468 + };
5.1469 +
5.1470 +
5.1471 + template <typename _Graph>
5.1472 + struct Constraints {
5.1473 +
5.1474 + struct Dummy {
5.1475 + int value;
5.1476 + Dummy() : value(0) {}
5.1477 + Dummy(int _v) : value(_v) {}
5.1478 + };
5.1479 +
5.1480 + void constraints() {
5.1481 + checkConcept<Base, _Graph>();
5.1482 + checkConcept<MappableGraphComponent<Base>, _Graph>();
5.1483 +
5.1484 + { // int map test
5.1485 + typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap;
5.1486 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>,
5.1487 + IntUEdgeMap >();
5.1488 + } { // bool map test
5.1489 + typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap;
5.1490 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>,
5.1491 + BoolUEdgeMap >();
5.1492 + } { // Dummy map test
5.1493 + typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap;
5.1494 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>,
5.1495 + DummyUEdgeMap >();
5.1496 + }
5.1497 + }
5.1498 +
5.1499 + _Graph& graph;
5.1500 + };
5.1501 + };
5.1502 +
5.1503 +
5.1504 + /// \brief An empty extendable graph class.
5.1505 + ///
5.1506 + /// This class provides beside the core graph features graph
5.1507 + /// extendable interface for the graph structure. The main
5.1508 + /// difference between the base and this interface is that the
5.1509 + /// graph alterations should handled already on this level.
5.1510 + template <typename _Base = BaseGraphComponent>
5.1511 + class ExtendableGraphComponent : public _Base {
5.1512 + public:
5.1513 +
5.1514 + typedef typename _Base::Node Node;
5.1515 + typedef typename _Base::Edge Edge;
5.1516 +
5.1517 + /// \brief Adds a new node to the graph.
5.1518 + ///
5.1519 + /// Adds a new node to the graph.
5.1520 + ///
5.1521 + Node addNode() {
5.1522 + return INVALID;
5.1523 + }
5.1524 +
5.1525 + /// \brief Adds a new edge connects the given two nodes.
5.1526 + ///
5.1527 + /// Adds a new edge connects the the given two nodes.
5.1528 + Edge addEdge(const Node&, const Node&) {
5.1529 + return INVALID;
5.1530 + }
5.1531 +
5.1532 + template <typename _Graph>
5.1533 + struct Constraints {
5.1534 + void constraints() {
5.1535 + typename _Graph::Node node_a, node_b;
5.1536 + node_a = graph.addNode();
5.1537 + node_b = graph.addNode();
5.1538 + typename _Graph::Edge edge;
5.1539 + edge = graph.addEdge(node_a, node_b);
5.1540 + }
5.1541 +
5.1542 + _Graph& graph;
5.1543 + };
5.1544 + };
5.1545 +
5.1546 + /// \brief An empty extendable base undirected graph class.
5.1547 + ///
5.1548 + /// This class provides beside the core undirected graph features
5.1549 + /// core undircted graph extend interface for the graph structure.
5.1550 + /// The main difference between the base and this interface is
5.1551 + /// that the graph alterations should handled already on this
5.1552 + /// level.
5.1553 + template <typename _Base = BaseUGraphComponent>
5.1554 + class ExtendableUGraphComponent : public _Base {
5.1555 + public:
5.1556 +
5.1557 + typedef typename _Base::Node Node;
5.1558 + typedef typename _Base::UEdge UEdge;
5.1559 +
5.1560 + /// \brief Adds a new node to the graph.
5.1561 + ///
5.1562 + /// Adds a new node to the graph.
5.1563 + ///
5.1564 + Node addNode() {
5.1565 + return INVALID;
5.1566 + }
5.1567 +
5.1568 + /// \brief Adds a new edge connects the given two nodes.
5.1569 + ///
5.1570 + /// Adds a new edge connects the the given two nodes.
5.1571 + UEdge addEdge(const Node&, const Node&) {
5.1572 + return INVALID;
5.1573 + }
5.1574 +
5.1575 + template <typename _Graph>
5.1576 + struct Constraints {
5.1577 + void constraints() {
5.1578 + typename _Graph::Node node_a, node_b;
5.1579 + node_a = graph.addNode();
5.1580 + node_b = graph.addNode();
5.1581 + typename _Graph::UEdge uedge;
5.1582 + uedge = graph.addUEdge(node_a, node_b);
5.1583 + }
5.1584 +
5.1585 + _Graph& graph;
5.1586 + };
5.1587 + };
5.1588 +
5.1589 + /// \brief An empty erasable graph class.
5.1590 + ///
5.1591 + /// This class provides beside the core graph features core erase
5.1592 + /// functions for the graph structure. The main difference between
5.1593 + /// the base and this interface is that the graph alterations
5.1594 + /// should handled already on this level.
5.1595 + template <typename _Base = BaseGraphComponent>
5.1596 + class ErasableGraphComponent : public _Base {
5.1597 + public:
5.1598 +
5.1599 + typedef _Base Base;
5.1600 + typedef typename Base::Node Node;
5.1601 + typedef typename Base::Edge Edge;
5.1602 +
5.1603 + /// \brief Erase a node from the graph.
5.1604 + ///
5.1605 + /// Erase a node from the graph. This function should
5.1606 + /// erase all edges connecting to the node.
5.1607 + void erase(const Node&) {}
5.1608 +
5.1609 + /// \brief Erase an edge from the graph.
5.1610 + ///
5.1611 + /// Erase an edge from the graph.
5.1612 + ///
5.1613 + void erase(const Edge&) {}
5.1614 +
5.1615 + template <typename _Graph>
5.1616 + struct Constraints {
5.1617 + void constraints() {
5.1618 + typename _Graph::Node node;
5.1619 + graph.erase(node);
5.1620 + typename _Graph::Edge edge;
5.1621 + graph.erase(edge);
5.1622 + }
5.1623 +
5.1624 + _Graph& graph;
5.1625 + };
5.1626 + };
5.1627 +
5.1628 + /// \brief An empty erasable base undirected graph class.
5.1629 + ///
5.1630 + /// This class provides beside the core undirected graph features
5.1631 + /// core erase functions for the undirceted graph structure. The
5.1632 + /// main difference between the base and this interface is that
5.1633 + /// the graph alterations should handled already on this level.
5.1634 + template <typename _Base = BaseUGraphComponent>
5.1635 + class ErasableUGraphComponent : public _Base {
5.1636 + public:
5.1637 +
5.1638 + typedef _Base Base;
5.1639 + typedef typename Base::Node Node;
5.1640 + typedef typename Base::UEdge UEdge;
5.1641 +
5.1642 + /// \brief Erase a node from the graph.
5.1643 + ///
5.1644 + /// Erase a node from the graph. This function should erase
5.1645 + /// edges connecting to the node.
5.1646 + void erase(const Node&) {}
5.1647 +
5.1648 + /// \brief Erase an edge from the graph.
5.1649 + ///
5.1650 + /// Erase an edge from the graph.
5.1651 + ///
5.1652 + void erase(const UEdge&) {}
5.1653 +
5.1654 + template <typename _Graph>
5.1655 + struct Constraints {
5.1656 + void constraints() {
5.1657 + typename _Graph::Node node;
5.1658 + graph.erase(node);
5.1659 + typename _Graph::Edge edge;
5.1660 + graph.erase(edge);
5.1661 + }
5.1662 +
5.1663 + _Graph& graph;
5.1664 + };
5.1665 + };
5.1666 +
5.1667 + /// \brief An empty clearable base graph class.
5.1668 + ///
5.1669 + /// This class provides beside the core graph features core clear
5.1670 + /// functions for the graph structure. The main difference between
5.1671 + /// the base and this interface is that the graph alterations
5.1672 + /// should handled already on this level.
5.1673 + template <typename _Base = BaseGraphComponent>
5.1674 + class ClearableGraphComponent : public _Base {
5.1675 + public:
5.1676 +
5.1677 + /// \brief Erase all nodes and edges from the graph.
5.1678 + ///
5.1679 + /// Erase all nodes and edges from the graph.
5.1680 + ///
5.1681 + void clear() {}
5.1682 +
5.1683 + template <typename _Graph>
5.1684 + struct Constraints {
5.1685 + void constraints() {
5.1686 + graph.clear();
5.1687 + }
5.1688 +
5.1689 + _Graph graph;
5.1690 + };
5.1691 + };
5.1692 +
5.1693 + /// \brief An empty clearable base undirected graph class.
5.1694 + ///
5.1695 + /// This class provides beside the core undirected graph features
5.1696 + /// core clear functions for the undirected graph structure. The
5.1697 + /// main difference between the base and this interface is that
5.1698 + /// the graph alterations should handled already on this level.
5.1699 + template <typename _Base = BaseUGraphComponent>
5.1700 + class ClearableUGraphComponent : public _Base {
5.1701 + public:
5.1702 +
5.1703 + /// \brief Erase all nodes and undirected edges from the graph.
5.1704 + ///
5.1705 + /// Erase all nodes and undirected edges from the graph.
5.1706 + ///
5.1707 + void clear() {}
5.1708 +
5.1709 + template <typename _Graph>
5.1710 + struct Constraints {
5.1711 + void constraints() {
5.1712 + graph.clear();
5.1713 + }
5.1714 +
5.1715 + _Graph graph;
5.1716 + };
5.1717 + };
5.1718 +
5.1719 + }
5.1720 +
5.1721 +}
5.1722 +
5.1723 +#endif
6.1 --- a/lemon/concept/ugraph.h Tue Jul 11 14:42:06 2006 +0000
6.2 +++ b/lemon/concept/ugraph.h Tue Jul 11 15:42:15 2006 +0000
6.3 @@ -24,7 +24,7 @@
6.4 #ifndef LEMON_CONCEPT_UGRAPH_H
6.5 #define LEMON_CONCEPT_UGRAPH_H
6.6
6.7 -#include <lemon/concept/graph_component.h>
6.8 +#include <lemon/concept/graph_components.h>
6.9 #include <lemon/concept/graph.h>
6.10 #include <lemon/bits/utility.h>
6.11