1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/concept/graph_component.h Thu Nov 04 20:24:59 2004 +0000
1.3 @@ -0,0 +1,827 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +///\ingroup concept
1.21 +///\file
1.22 +///\brief The graph components.
1.23 +
1.24 +
1.25 +#ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
1.26 +#define LEMON_CONCEPT_GRAPH_COMPONENT_H
1.27 +
1.28 +#include <lemon/invalid.h>
1.29 +#include <lemon/concept/maps.h>
1.30 +
1.31 +namespace lemon {
1.32 + namespace concept {
1.33 +
1.34 + /// An empty base graph class.
1.35 +
1.36 + /// This class provides the most minimal features of a graph structure.
1.37 + /// All the graph concepts have to be conform to this base graph.
1.38 +
1.39 + class BaseGraphComponent {
1.40 + public:
1.41 +
1.42 + typedef BaseGraphComponent Graph;
1.43 +
1.44 + /// Node class of the graph.
1.45 +
1.46 + /// This class represents the Nodes of the graph.
1.47 + ///
1.48 + class Node {
1.49 + public:
1.50 +
1.51 + /// Default constructor.
1.52 +
1.53 + /// @warning The default constructor sets the iterator
1.54 + /// to an undefined value.
1.55 +
1.56 + Node() {}
1.57 + /// Copy constructor.
1.58 +
1.59 + /// Copy constructor.
1.60 + ///
1.61 + Node(const Node&) {}
1.62 +
1.63 + /// Invalid constructor \& conversion.
1.64 +
1.65 + /// This constructor initializes the iterator to be invalid.
1.66 + /// \sa Invalid for more details.
1.67 + Node(Invalid) {}
1.68 +
1.69 +
1.70 + Node& operator=(const Node&) { return *this;}
1.71 +
1.72 + /// Equality operator.
1.73 +
1.74 + /// Two iterators are equal if and only if they represents the
1.75 + /// same node in the graph or both are invalid.
1.76 + bool operator==(const Node&) { return true;}
1.77 +
1.78 +
1.79 + /// Inequality operator.
1.80 +
1.81 + /// \sa operator==(const Node& n)
1.82 + ///
1.83 + bool operator!=(const Node&) { return true;}
1.84 +
1.85 + /// Comparison operator.
1.86 +
1.87 + /// This is a strict ordering between the nodes.
1.88 + ///
1.89 + /// This ordering can be different from the iterating order of nodes.
1.90 + /// \todo Possibly we don't need it.
1.91 + bool operator<(const Node&) { return true;}
1.92 + };
1.93 +
1.94 + /// Edge class of the graph.
1.95 +
1.96 + /// This class represents the Edges of the graph.
1.97 + ///
1.98 + class Edge {
1.99 + public:
1.100 +
1.101 + /// Default constructor.
1.102 +
1.103 + /// @warning The default constructor sets the iterator
1.104 + /// to an undefined value.
1.105 +
1.106 + Edge() {}
1.107 + /// Copy constructor.
1.108 +
1.109 + /// Copy constructor.
1.110 + ///
1.111 + Edge(const Edge&) {}
1.112 +
1.113 + /// Invalid constructor \& conversion.
1.114 +
1.115 + /// This constructor initializes the iterator to be invalid.
1.116 + /// \sa Invalid for more details.
1.117 + Edge(Invalid) {}
1.118 +
1.119 +
1.120 + Edge& operator=(const Edge&) { return *this;}
1.121 +
1.122 + /// Equality operator.
1.123 +
1.124 + /// Two iterators are equal if and only if they represents the
1.125 + /// same edge in the graph or both are invalid.
1.126 + bool operator==(const Edge&) { return true;}
1.127 +
1.128 +
1.129 + /// Inequality operator.
1.130 +
1.131 + /// \sa operator==(const Edge& n)
1.132 + ///
1.133 + bool operator!=(const Edge&) { return true;}
1.134 +
1.135 + /// Comparison operator.
1.136 +
1.137 + /// This is a strict ordering between the edges.
1.138 + ///
1.139 + /// This ordering can be different from the iterating order of edges.
1.140 + /// \todo Possibly we don't need it.
1.141 + bool operator<(const Edge&) { return true;}
1.142 + };
1.143 +
1.144 + ///Gives back the head node of an edge.
1.145 +
1.146 + ///Gives back the head node of an edge.
1.147 + ///
1.148 + Node head(const Edge&) const { return INVALID;}
1.149 +
1.150 + ///Gives back the tail node of an edge.
1.151 +
1.152 + ///Gives back the tail node of an edge.
1.153 + ///
1.154 + Node tail(const Edge&) const { return INVALID;}
1.155 + };
1.156 +
1.157 + /// Concept check structure for BaseGraph.
1.158 +
1.159 + /// Concept check structure for BaseGraph.
1.160 + ///
1.161 +
1.162 + template <typename Graph>
1.163 + struct BaseGraphComponentConcept {
1.164 + typedef typename Graph::Node Node;
1.165 + typedef typename Graph::Edge Edge;
1.166 +
1.167 + void constraints() {
1.168 + {
1.169 + Node ni;
1.170 + Node nj(ni);
1.171 + Node nk(INVALID);
1.172 + ni = nj;
1.173 + bool b; b = true;
1.174 + b = (ni == INVALID); b = (ni != INVALID);
1.175 + b = (ni==nj); b = (ni != nj); b=( ni < nj);
1.176 + }
1.177 + {
1.178 + Edge ei;
1.179 + Edge ej(ei);
1.180 + Edge ek(INVALID);
1.181 + ei = ej;
1.182 + bool b; b = true;
1.183 + b = (ei == INVALID); b = (ei != INVALID);
1.184 + b = (ei==ej); b = (ei != ej); b=( ei < ej);
1.185 + }
1.186 + {
1.187 + const Graph& const_graph = graph;
1.188 + Node n;
1.189 + Edge e;
1.190 + n = const_graph.tail(e);
1.191 + n = const_graph.head(e);
1.192 + }
1.193 + }
1.194 +
1.195 + Graph& graph;
1.196 + };
1.197 +
1.198 + /// An empty iterable base graph class.
1.199 +
1.200 + /// This class provides beside the core graph features
1.201 + /// core iterable interface for the graph structure.
1.202 + /// Most of the base graphs should be conform to this concept.
1.203 +
1.204 + class BaseIterableGraphComponent : virtual public BaseGraphComponent {
1.205 + public:
1.206 +
1.207 + typedef BaseGraphComponent::Node Node;
1.208 + typedef BaseGraphComponent::Edge Edge;
1.209 +
1.210 + /// Gives back the first Node in the iterating order.
1.211 +
1.212 + /// Gives back the first Node in the iterating order.
1.213 + ///
1.214 + void first(Node&) const {}
1.215 +
1.216 + /// Gives back the next Node in the iterating order.
1.217 +
1.218 + /// Gives back the next Node in the iterating order.
1.219 + ///
1.220 + void next(Node&) const {}
1.221 +
1.222 + /// Gives back the first Edge in the iterating order.
1.223 +
1.224 + /// Gives back the first Edge in the iterating order.
1.225 + ///
1.226 + void first(Edge&) const {}
1.227 + /// Gives back the next Edge in the iterating order.
1.228 +
1.229 + /// Gives back the next Edge in the iterating order.
1.230 + ///
1.231 + void next(Edge&) const {}
1.232 +
1.233 +
1.234 + /// Gives back the first of the Edges point to the given Node.
1.235 +
1.236 + /// Gives back the first of the Edges point to the given Node.
1.237 + ///
1.238 + void firstIn(Edge&, const Node&) const {}
1.239 +
1.240 + /// Gives back the next of the Edges points to the given Node.
1.241 +
1.242 +
1.243 + /// Gives back the next of the Edges points to the given Node.
1.244 + ///
1.245 + void nextIn(Edge&) const {}
1.246 +
1.247 + /// Gives back the first of the Edges start from the given Node.
1.248 +
1.249 + /// Gives back the first of the Edges start from the given Node.
1.250 + ///
1.251 + void firstOut(Edge&, const Node&) const {}
1.252 +
1.253 + /// Gives back the next of the Edges start from the given Node.
1.254 +
1.255 + /// Gives back the next of the Edges start from the given Node.
1.256 + ///
1.257 + void nextOut(Edge&) const {}
1.258 + };
1.259 +
1.260 +
1.261 + /// Concept check structure for IterableBaseGraph.
1.262 +
1.263 + /// Concept check structure for IterableBaseGraph.
1.264 + ///
1.265 + template <typename Graph>
1.266 + struct BaseIterableGraphComponentConcept {
1.267 +
1.268 + void constraints() {
1.269 + const Graph& const_graph = graph;
1.270 + typename Graph::Node node;
1.271 + typename Graph::Edge edge;
1.272 + {
1.273 + const_graph.first(node);
1.274 + const_graph.next(node);
1.275 + }
1.276 + {
1.277 + const_graph.first(edge);
1.278 + const_graph.next(edge);
1.279 + }
1.280 + {
1.281 + const_graph.firstIn(edge, node);
1.282 + const_graph.nextIn(edge);
1.283 + }
1.284 + {
1.285 + const_graph.firstOut(edge, node);
1.286 + const_graph.nextOut(edge);
1.287 + }
1.288 + }
1.289 +
1.290 + Graph& graph;
1.291 + };
1.292 +
1.293 + /// An empty idable base graph class.
1.294 +
1.295 + /// This class provides beside the core graph features
1.296 + /// core id functions for the graph structure.
1.297 + /// The most of the base graphs should be conform to this concept.
1.298 + /// The id's are unique and immutable.
1.299 +
1.300 + class IDableGraphComponent : virtual public BaseGraphComponent {
1.301 + public:
1.302 +
1.303 + typedef BaseGraphComponent::Node Node;
1.304 + typedef BaseGraphComponent::Edge Edge;
1.305 +
1.306 + /// Gives back an unique integer id for the Node.
1.307 +
1.308 + /// Gives back an unique integer id for the Node.
1.309 + ///
1.310 + int id(const Node&) const { return -1;}
1.311 +
1.312 + /// Gives back an unique integer id for the Edge.
1.313 +
1.314 + /// Gives back an unique integer id for the Edge.
1.315 + ///
1.316 + int id(const Edge&) const { return -1;}
1.317 + };
1.318 +
1.319 +
1.320 + /// Concept check structure for IdableBaseGraph.
1.321 +
1.322 + /// Concept check structure for IdableBaseGraph.
1.323 + ///
1.324 + template <typename Graph>
1.325 + struct IDableGraphComponentConcept {
1.326 +
1.327 + void constraints() {
1.328 + const Graph& const_graph = graph;
1.329 + typename Graph::Node node;
1.330 + int nid = const_graph.id(node);
1.331 + nid = const_graph.id(node);
1.332 + typename Graph::Edge edge;
1.333 + int eid = const_graph.id(edge);
1.334 + eid = const_graph.id(edge);
1.335 + }
1.336 +
1.337 + Graph& graph;
1.338 + };
1.339 +
1.340 +
1.341 + /// An empty max-idable base graph class.
1.342 +
1.343 + /// This class provides beside the core graph features
1.344 + /// core max id functions for the graph structure.
1.345 + /// The most of the base graphs should be conform to this concept.
1.346 + /// The id's are unique and immutable.
1.347 + class MaxIDableGraphComponent : virtual public BaseGraphComponent {
1.348 + public:
1.349 +
1.350 + /// Gives back an integer greater or equal to the maximum Node id.
1.351 +
1.352 + /// Gives back an integer greater or equal to the maximum Node id.
1.353 + ///
1.354 + int maxEdgeId() const { return -1;}
1.355 +
1.356 + /// Gives back an integer greater or equal to the maximum Edge id.
1.357 +
1.358 + /// Gives back an integer greater or equal to the maximum Edge id.
1.359 + ///
1.360 + int maxNodeId() const { return -1;}
1.361 + };
1.362 +
1.363 + /// Concept check structure for MaxIdableBaseGraph.
1.364 +
1.365 + /// Concept check structure for MaxIdableBaseGraph.
1.366 + ///
1.367 + template <typename Graph>
1.368 + struct MaxIDableGraphComponentConcept {
1.369 +
1.370 + void constraints() {
1.371 + const Graph& const_graph = graph;
1.372 + int nid = const_graph.maxEdgeId();
1.373 + ignore_unused_variable_warning(nid);
1.374 + int eid = const_graph.maxNodeId();
1.375 + ignore_unused_variable_warning(eid);
1.376 + }
1.377 +
1.378 + Graph& graph;
1.379 + };
1.380 +
1.381 + /// An empty extendable base graph class.
1.382 +
1.383 + /// This class provides beside the core graph features
1.384 + /// core graph extend interface for the graph structure.
1.385 + /// The most of the base graphs should be conform to this concept.
1.386 + class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
1.387 + public:
1.388 +
1.389 + typedef BaseGraphComponent::Node Node;
1.390 + typedef BaseGraphComponent::Edge Edge;
1.391 +
1.392 + /// Adds a new Node to the graph.
1.393 +
1.394 + /// Adds a new Node to the graph.
1.395 + ///
1.396 + Node addNode() {
1.397 + return INVALID;
1.398 + }
1.399 +
1.400 + /// Adds a new Edge connects the two Nodes to the graph.
1.401 +
1.402 + /// Adds a new Edge connects the two Nodes to the graph.
1.403 + ///
1.404 + Edge addEdge(const Node& from, const Node& to) {
1.405 + return INVALID;
1.406 + }
1.407 +
1.408 + };
1.409 +
1.410 + /// Concept check structure for ExtendableBaseGraph.
1.411 +
1.412 + /// Concept check structure for ExtendableBaseGraph.
1.413 + ///
1.414 + template <typename Graph>
1.415 + struct BaseExtendableGraphComponentConcept {
1.416 + void constraints() {
1.417 + typename Graph::Node node_a, node_b;
1.418 + node_a = graph.addNode();
1.419 + typename Graph::Edge edge;
1.420 + edge = graph.addEdge(node_a, node_b);
1.421 + }
1.422 +
1.423 + Graph& graph;
1.424 + };
1.425 +
1.426 + /// An empty erasable base graph class.
1.427 +
1.428 + /// This class provides beside the core graph features
1.429 + /// core erase functions for the graph structure.
1.430 + /// The most of the base graphs should be conform to this concept.
1.431 + class BaseErasableGraphComponent : virtual public BaseGraphComponent {
1.432 + public:
1.433 +
1.434 + typedef BaseGraphComponent::Node Node;
1.435 + typedef BaseGraphComponent::Edge Edge;
1.436 +
1.437 + /// Erase a Node from the graph.
1.438 +
1.439 + /// Erase a Node from the graph. This function should not
1.440 + /// erase edges connecting to the Node.
1.441 + void erase(const Node&) {}
1.442 +
1.443 + /// Erase an Edge from the graph.
1.444 +
1.445 + /// Erase an Edge from the graph.
1.446 + ///
1.447 + void erase(const Edge&) {}
1.448 +
1.449 + };
1.450 +
1.451 + /// Concept check structure for ErasableBaseGraph.
1.452 +
1.453 + /// Concept check structure for ErasableBaseGraph.
1.454 + ///
1.455 + template <typename Graph>
1.456 + struct BaseErasableGraphComponentConcept {
1.457 + void constraints() {
1.458 + typename Graph::Node node;
1.459 + graph.erase(node);
1.460 + typename Graph::Edge edge;
1.461 + graph.erase(edge);
1.462 + }
1.463 +
1.464 + Graph& graph;
1.465 + };
1.466 +
1.467 + /// An empty clearable base graph class.
1.468 +
1.469 + /// This class provides beside the core graph features
1.470 + /// core clear functions for the graph structure.
1.471 + /// The most of the base graphs should be conform to this concept.
1.472 + class BaseClearableGraphComponent : virtual public BaseGraphComponent {
1.473 + public:
1.474 +
1.475 + /// Erase all the Nodes and Edges from the graph.
1.476 +
1.477 + /// Erase all the Nodes and Edges from the graph.
1.478 + ///
1.479 + void clear() {}
1.480 + };
1.481 +
1.482 + /// Concept check function for ErasableBaseGraph.
1.483 +
1.484 + /// Concept check function for ErasableBaseGraph.
1.485 + ///
1.486 + template <typename Graph>
1.487 + struct BaseClearableGraphComponentConcept {
1.488 + void constraints() {
1.489 + graph.clear();
1.490 + }
1.491 +
1.492 + Graph& graph;
1.493 + };
1.494 +
1.495 +
1.496 + class IterableGraphComponent : virtual public BaseGraphComponent {
1.497 +
1.498 + public:
1.499 +
1.500 + typedef IterableGraphComponent Graph;
1.501 +
1.502 + typedef BaseGraphComponent::Node Node;
1.503 + typedef BaseGraphComponent::Edge Edge;
1.504 +
1.505 + class NodeIt : public Node {
1.506 + public:
1.507 + NodeIt() {}
1.508 + NodeIt(Invalid) {}
1.509 + NodeIt(const Graph&) {}
1.510 +
1.511 + NodeIt& operator++() { return *this; }
1.512 + // Node operator*() const { return INVALID; }
1.513 +
1.514 + bool operator==(const NodeIt&) { return true;}
1.515 + bool operator!=(const NodeIt&) { return true;}
1.516 + };
1.517 +
1.518 + class EdgeIt : public Edge {
1.519 + public:
1.520 + EdgeIt() {}
1.521 + EdgeIt(Invalid) {}
1.522 + EdgeIt(const Graph&) {}
1.523 +
1.524 + EdgeIt& operator++() { return *this; }
1.525 + // Edge operator*() const { return INVALID; }
1.526 +
1.527 + bool operator==(const EdgeIt&) { return true;}
1.528 + bool operator!=(const EdgeIt&) { return true;}
1.529 + };
1.530 +
1.531 + class InEdgeIt : public Edge {
1.532 + public:
1.533 + InEdgeIt() {}
1.534 + InEdgeIt(Invalid) {}
1.535 + InEdgeIt(const Graph&, const Node&) {}
1.536 +
1.537 + InEdgeIt& operator++() { return *this; }
1.538 + // Edge operator*() const { return INVALID; }
1.539 +
1.540 + bool operator==(const InEdgeIt&) { return true;}
1.541 + bool operator!=(const InEdgeIt&) { return true;}
1.542 + };
1.543 +
1.544 + class OutEdgeIt : public Edge {
1.545 + public:
1.546 + OutEdgeIt() {}
1.547 + OutEdgeIt(Invalid) {}
1.548 + OutEdgeIt(const Graph&, const Node&) {}
1.549 +
1.550 + OutEdgeIt& operator++() { return *this; }
1.551 + // Edge operator*() const { return INVALID; }
1.552 +
1.553 + bool operator==(const OutEdgeIt&) { return true;}
1.554 + bool operator!=(const OutEdgeIt&) { return true;}
1.555 + };
1.556 +
1.557 + };
1.558 +
1.559 + template <typename Graph>
1.560 + struct IterableGraphComponentConcept {
1.561 +
1.562 + void constraints() {
1.563 +
1.564 + typedef typename Graph::Node Node;
1.565 + typedef typename Graph::NodeIt NodeIt;
1.566 + typedef typename Graph::Edge Edge;
1.567 + typedef typename Graph::EdgeIt EdgeIt;
1.568 + typedef typename Graph::InEdgeIt InEdgeIt;
1.569 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.570 +
1.571 + {
1.572 + NodeIt it;
1.573 + NodeIt jt(it);
1.574 + NodeIt kt(INVALID);
1.575 + NodeIt lt(graph);
1.576 + it = jt;
1.577 + jt = ++it;
1.578 + bool b;
1.579 + b = (it == INVALID);
1.580 + b = (it != INVALID);
1.581 + b = (it == jt);
1.582 + b = (it != jt);
1.583 + Node node = it;
1.584 + node = it;
1.585 + }
1.586 + {
1.587 + EdgeIt it;
1.588 + EdgeIt jt(it);
1.589 + EdgeIt kt(INVALID);
1.590 + EdgeIt lt(graph);
1.591 + it = jt;
1.592 + jt = ++it;
1.593 + bool b;
1.594 + b = (it == INVALID);
1.595 + b = (it != INVALID);
1.596 + b = (it == jt);
1.597 + b = (it != jt);
1.598 + Edge edge = it;
1.599 + edge = it;
1.600 + }
1.601 + {
1.602 + InEdgeIt it;
1.603 + InEdgeIt jt(it);
1.604 + InEdgeIt kt(INVALID);
1.605 + Node node;
1.606 + InEdgeIt lt(graph, node);
1.607 + it = jt;
1.608 + jt = ++it;
1.609 + bool b;
1.610 + b = (it == INVALID);
1.611 + b = (it != INVALID);
1.612 + b = (it == jt);
1.613 + b = (it != jt);
1.614 + Edge edge = it;
1.615 + edge = it;
1.616 + }
1.617 + {
1.618 + OutEdgeIt it;
1.619 + OutEdgeIt jt(it);
1.620 + OutEdgeIt kt(INVALID);
1.621 + Node node;
1.622 + OutEdgeIt lt(graph, node);
1.623 + it = jt;
1.624 + jt = ++it;
1.625 + bool b;
1.626 + b = (it == INVALID);
1.627 + b = (it != INVALID);
1.628 + b = (it == jt);
1.629 + b = (it != jt);
1.630 + Edge edge = it;
1.631 + edge = it;
1.632 + }
1.633 + }
1.634 + Graph& graph;
1.635 + };
1.636 +
1.637 +
1.638 + class IdMappableGraphComponent : virtual public BaseGraphComponent {
1.639 +
1.640 + typedef IdMappableGraphComponent Graph;
1.641 +
1.642 + typedef BaseGraphComponent::Node Node;
1.643 + typedef BaseGraphComponent::Edge Edge;
1.644 +
1.645 + public:
1.646 +
1.647 + class NodeIdMap : public ReadMap<Node, int> {
1.648 + public:
1.649 + NodeIdMap(const Graph&) {}
1.650 + int maxId() const { return -1;}
1.651 + };
1.652 +
1.653 + class EdgeIdMap : public ReadMap<Edge, int> {
1.654 + public:
1.655 + EdgeIdMap(const Graph&) {}
1.656 + int maxId() const { return -1;}
1.657 + };
1.658 +
1.659 + };
1.660 +
1.661 + template <typename Graph>
1.662 + struct IdMappableGraphComponentConcept {
1.663 + void constraints() {
1.664 + {
1.665 + typedef typename Graph::EdgeIdMap EdgeIdMap;
1.666 + function_requires<ReadMapConcept<EdgeIdMap> >();
1.667 + EdgeIdMap edge_map(graph);
1.668 + int n = edge_map.maxId();
1.669 + ignore_unused_variable_warning(n);
1.670 + }
1.671 + {
1.672 + typedef typename Graph::NodeIdMap NodeIdMap;
1.673 + function_requires<ReadMapConcept<NodeIdMap> >();
1.674 + NodeIdMap node_map(graph);
1.675 + int n = node_map.maxId();
1.676 + ignore_unused_variable_warning(n);
1.677 + }
1.678 + }
1.679 + Graph& graph;
1.680 + };
1.681 +
1.682 +
1.683 + class MappableGraphComponent : virtual public BaseGraphComponent {
1.684 + public:
1.685 +
1.686 + typedef MappableGraphComponent Graph;
1.687 +
1.688 + typedef BaseGraphComponent::Node Node;
1.689 + typedef BaseGraphComponent::Edge Edge;
1.690 +
1.691 + template <typename Value>
1.692 + class NodeMap : public ReferenceMap<Node, Value> {
1.693 + public:
1.694 + NodeMap(const Graph&) {}
1.695 + NodeMap(const Graph&, const Value&) {}
1.696 + NodeMap(const NodeMap&) {}
1.697 +
1.698 + NodeMap& operator=(const NodeMap&) { return *this;}
1.699 +
1.700 + };
1.701 +
1.702 + template <typename Value>
1.703 + class EdgeMap : public ReferenceMap<Edge, Value> {
1.704 + public:
1.705 + EdgeMap(const Graph&) {}
1.706 + EdgeMap(const Graph&, const Value&) {}
1.707 + EdgeMap(const EdgeMap&) {}
1.708 +
1.709 + EdgeMap& operator=(const EdgeMap&) { return *this;}
1.710 +
1.711 + };
1.712 +
1.713 + };
1.714 +
1.715 + template <typename Graph>
1.716 + struct MappableGraphComponentConcept {
1.717 +
1.718 + struct Type {
1.719 + int value;
1.720 + Type() : value(0) {}
1.721 + Type(int _v) : value(_v) {}
1.722 + };
1.723 +
1.724 + void constraints() {
1.725 + { // int map test
1.726 + typedef typename Graph::template NodeMap<int> IntNodeMap;
1.727 + function_requires<GraphMapConcept<IntNodeMap,Graph> >();
1.728 + } { // bool map test
1.729 + typedef typename Graph::template NodeMap<bool> BoolNodeMap;
1.730 + function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
1.731 + } { // Type map test
1.732 + typedef typename Graph::template NodeMap<Type> TypeNodeMap;
1.733 + function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
1.734 + }
1.735 +
1.736 + { // int map test
1.737 + typedef typename Graph::template EdgeMap<int> IntEdgeMap;
1.738 + function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
1.739 + } { // bool map test
1.740 + typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
1.741 + function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
1.742 + } { // Type map test
1.743 + typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
1.744 + function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
1.745 + }
1.746 + }
1.747 +
1.748 + Graph& graph;
1.749 + };
1.750 +
1.751 +
1.752 + class ExtendableGraphComponent : virtual public BaseGraphComponent {
1.753 + public:
1.754 +
1.755 + typedef ExtendableGraphComponent Graph;
1.756 +
1.757 + typedef BaseGraphComponent::Node Node;
1.758 + typedef BaseGraphComponent::Edge Edge;
1.759 +
1.760 + Node addNode() {
1.761 + return INVALID;
1.762 + }
1.763 +
1.764 + Edge addEdge(const Node& from, const Node& to) {
1.765 + return INVALID;
1.766 + }
1.767 +
1.768 + };
1.769 +
1.770 + template <typename Graph>
1.771 + struct ExtendableGraphComponentConcept {
1.772 + void constraints() {
1.773 + typename Graph::Node node_a, node_b;
1.774 + node_a = graph.addNode();
1.775 + typename Graph::Edge edge;
1.776 + edge = graph.addEdge(node_a, node_b);
1.777 + }
1.778 + Graph& graph;
1.779 + };
1.780 +
1.781 + class ErasableGraphComponent : virtual public BaseGraphComponent {
1.782 + public:
1.783 +
1.784 + typedef ErasableGraphComponent Graph;
1.785 +
1.786 + typedef BaseGraphComponent::Node Node;
1.787 + typedef BaseGraphComponent::Edge Edge;
1.788 +
1.789 + void erase(const Node&) {}
1.790 + void erase(const Edge&) {}
1.791 +
1.792 + };
1.793 +
1.794 + template <typename Graph>
1.795 + struct ErasableGraphComponentConcept {
1.796 + void constraints() {
1.797 + typename Graph::Node node;
1.798 + graph.erase(node);
1.799 + typename Graph::Edge edge;
1.800 + graph.erase(edge);
1.801 + }
1.802 +
1.803 + Graph& graph;
1.804 + };
1.805 +
1.806 + class ClearableGraphComponent : virtual public BaseGraphComponent {
1.807 + public:
1.808 +
1.809 + typedef ClearableGraphComponent Graph;
1.810 +
1.811 + typedef BaseGraphComponent::Node Node;
1.812 + typedef BaseGraphComponent::Edge Edge;
1.813 +
1.814 + void clear() {}
1.815 +
1.816 + };
1.817 +
1.818 + template <typename Graph>
1.819 + struct ClearableGraphComponentConcept {
1.820 + void constraints() {
1.821 + graph.clear();
1.822 + }
1.823 + Graph& graph;
1.824 + };
1.825 +
1.826 + }
1.827 +
1.828 +}
1.829 +
1.830 +#endif