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