1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/edge_set.h Mon Dec 08 11:38:02 2008 +0100
1.3 @@ -0,0 +1,1410 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
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 +#ifndef LEMON_EDGE_SET_H
1.23 +#define LEMON_EDGE_SET_H
1.24 +
1.25 +#include <lemon/core.h>
1.26 +#include <lemon/bits/edge_set_extender.h>
1.27 +
1.28 +/// \ingroup semi_adaptors
1.29 +/// \file
1.30 +/// \brief ArcSet and EdgeSet classes.
1.31 +///
1.32 +/// Graphs which use another graph's node-set as own.
1.33 +namespace lemon {
1.34 +
1.35 + template <typename _Graph>
1.36 + class ListArcSetBase {
1.37 + public:
1.38 +
1.39 + typedef _Graph Graph;
1.40 + typedef typename Graph::Node Node;
1.41 + typedef typename Graph::NodeIt NodeIt;
1.42 +
1.43 + protected:
1.44 +
1.45 + struct NodeT {
1.46 + int first_out, first_in;
1.47 + NodeT() : first_out(-1), first_in(-1) {}
1.48 + };
1.49 +
1.50 + typedef typename ItemSetTraits<Graph, Node>::
1.51 + template Map<NodeT>::Type NodesImplBase;
1.52 +
1.53 + NodesImplBase* nodes;
1.54 +
1.55 + struct ArcT {
1.56 + Node source, target;
1.57 + int next_out, next_in;
1.58 + int prev_out, prev_in;
1.59 + ArcT() : prev_out(-1), prev_in(-1) {}
1.60 + };
1.61 +
1.62 + std::vector<ArcT> arcs;
1.63 +
1.64 + int first_arc;
1.65 + int first_free_arc;
1.66 +
1.67 + const Graph* graph;
1.68 +
1.69 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.70 + graph = &_graph;
1.71 + nodes = &_nodes;
1.72 + }
1.73 +
1.74 + public:
1.75 +
1.76 + class Arc {
1.77 + friend class ListArcSetBase<Graph>;
1.78 + protected:
1.79 + Arc(int _id) : id(_id) {}
1.80 + int id;
1.81 + public:
1.82 + Arc() {}
1.83 + Arc(Invalid) : id(-1) {}
1.84 + bool operator==(const Arc& arc) const { return id == arc.id; }
1.85 + bool operator!=(const Arc& arc) const { return id != arc.id; }
1.86 + bool operator<(const Arc& arc) const { return id < arc.id; }
1.87 + };
1.88 +
1.89 + ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
1.90 +
1.91 + Arc addArc(const Node& u, const Node& v) {
1.92 + int n;
1.93 + if (first_free_arc == -1) {
1.94 + n = arcs.size();
1.95 + arcs.push_back(ArcT());
1.96 + } else {
1.97 + n = first_free_arc;
1.98 + first_free_arc = arcs[first_free_arc].next_in;
1.99 + }
1.100 + arcs[n].next_in = (*nodes)[v].first_in;
1.101 + if ((*nodes)[v].first_in != -1) {
1.102 + arcs[(*nodes)[v].first_in].prev_in = n;
1.103 + }
1.104 + (*nodes)[v].first_in = n;
1.105 + arcs[n].next_out = (*nodes)[u].first_out;
1.106 + if ((*nodes)[u].first_out != -1) {
1.107 + arcs[(*nodes)[u].first_out].prev_out = n;
1.108 + }
1.109 + (*nodes)[u].first_out = n;
1.110 + arcs[n].source = u;
1.111 + arcs[n].target = v;
1.112 + return Arc(n);
1.113 + }
1.114 +
1.115 + void erase(const Arc& arc) {
1.116 + int n = arc.id;
1.117 + if (arcs[n].prev_in != -1) {
1.118 + arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
1.119 + } else {
1.120 + (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
1.121 + }
1.122 + if (arcs[n].next_in != -1) {
1.123 + arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
1.124 + }
1.125 +
1.126 + if (arcs[n].prev_out != -1) {
1.127 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.128 + } else {
1.129 + (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
1.130 + }
1.131 + if (arcs[n].next_out != -1) {
1.132 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.133 + }
1.134 +
1.135 + }
1.136 +
1.137 + void clear() {
1.138 + Node node;
1.139 + for (first(node); node != INVALID; next(node)) {
1.140 + (*nodes)[node].first_in = -1;
1.141 + (*nodes)[node].first_out = -1;
1.142 + }
1.143 + arcs.clear();
1.144 + first_arc = -1;
1.145 + first_free_arc = -1;
1.146 + }
1.147 +
1.148 + void first(Node& node) const {
1.149 + graph->first(node);
1.150 + }
1.151 +
1.152 + void next(Node& node) const {
1.153 + graph->next(node);
1.154 + }
1.155 +
1.156 + void first(Arc& arc) const {
1.157 + Node node;
1.158 + first(node);
1.159 + while (node != INVALID && (*nodes)[node].first_in == -1) {
1.160 + next(node);
1.161 + }
1.162 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.163 + }
1.164 +
1.165 + void next(Arc& arc) const {
1.166 + if (arcs[arc.id].next_in != -1) {
1.167 + arc.id = arcs[arc.id].next_in;
1.168 + } else {
1.169 + Node node = arcs[arc.id].target;
1.170 + next(node);
1.171 + while (node != INVALID && (*nodes)[node].first_in == -1) {
1.172 + next(node);
1.173 + }
1.174 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.175 + }
1.176 + }
1.177 +
1.178 + void firstOut(Arc& arc, const Node& node) const {
1.179 + arc.id = (*nodes)[node].first_out;
1.180 + }
1.181 +
1.182 + void nextOut(Arc& arc) const {
1.183 + arc.id = arcs[arc.id].next_out;
1.184 + }
1.185 +
1.186 + void firstIn(Arc& arc, const Node& node) const {
1.187 + arc.id = (*nodes)[node].first_in;
1.188 + }
1.189 +
1.190 + void nextIn(Arc& arc) const {
1.191 + arc.id = arcs[arc.id].next_in;
1.192 + }
1.193 +
1.194 + int id(const Node& node) const { return graph->id(node); }
1.195 + int id(const Arc& arc) const { return arc.id; }
1.196 +
1.197 + Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
1.198 + Arc arcFromId(int ix) const { return Arc(ix); }
1.199 +
1.200 + int maxNodeId() const { return graph->maxNodeId(); };
1.201 + int maxArcId() const { return arcs.size() - 1; }
1.202 +
1.203 + Node source(const Arc& arc) const { return arcs[arc.id].source;}
1.204 + Node target(const Arc& arc) const { return arcs[arc.id].target;}
1.205 +
1.206 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.207 +
1.208 + NodeNotifier& notifier(Node) const {
1.209 + return graph->notifier(Node());
1.210 + }
1.211 +
1.212 + template <typename _Value>
1.213 + class NodeMap : public Graph::template NodeMap<_Value> {
1.214 + public:
1.215 +
1.216 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.217 +
1.218 + explicit NodeMap(const ListArcSetBase<Graph>& arcset)
1.219 + : Parent(*arcset.graph) {}
1.220 +
1.221 + NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
1.222 + : Parent(*arcset.graph, value) {}
1.223 +
1.224 + NodeMap& operator=(const NodeMap& cmap) {
1.225 + return operator=<NodeMap>(cmap);
1.226 + }
1.227 +
1.228 + template <typename CMap>
1.229 + NodeMap& operator=(const CMap& cmap) {
1.230 + Parent::operator=(cmap);
1.231 + return *this;
1.232 + }
1.233 + };
1.234 +
1.235 + };
1.236 +
1.237 + /// \ingroup semi_adaptors
1.238 + ///
1.239 + /// \brief Digraph using a node set of another digraph or graph and
1.240 + /// an own arc set.
1.241 + ///
1.242 + /// This structure can be used to establish another directed graph
1.243 + /// over a node set of an existing one. This class uses the same
1.244 + /// Node type as the underlying graph, and each valid node of the
1.245 + /// original graph is valid in this arc set, therefore the node
1.246 + /// objects of the original graph can be used directly with this
1.247 + /// class. The node handling functions (id handling, observing, and
1.248 + /// iterators) works equivalently as in the original graph.
1.249 + ///
1.250 + /// This implementation is based on doubly-linked lists, from each
1.251 + /// node the outgoing and the incoming arcs make up lists, therefore
1.252 + /// one arc can be erased in constant time. It also makes possible,
1.253 + /// that node can be removed from the underlying graph, in this case
1.254 + /// all arcs incident to the given node is erased from the arc set.
1.255 + ///
1.256 + /// \param _Graph The type of the graph which shares its node set with
1.257 + /// this class. Its interface must conform to the
1.258 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.259 + /// concept.
1.260 + ///
1.261 + /// This class is fully conform to the \ref concepts::Digraph
1.262 + /// "Digraph" concept.
1.263 + template <typename _Graph>
1.264 + class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
1.265 +
1.266 + public:
1.267 +
1.268 + typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
1.269 +
1.270 + typedef typename Parent::Node Node;
1.271 + typedef typename Parent::Arc Arc;
1.272 +
1.273 + typedef _Graph Graph;
1.274 +
1.275 +
1.276 + typedef typename Parent::NodesImplBase NodesImplBase;
1.277 +
1.278 + void eraseNode(const Node& node) {
1.279 + Arc arc;
1.280 + Parent::firstOut(arc, node);
1.281 + while (arc != INVALID ) {
1.282 + erase(arc);
1.283 + Parent::firstOut(arc, node);
1.284 + }
1.285 +
1.286 + Parent::firstIn(arc, node);
1.287 + while (arc != INVALID ) {
1.288 + erase(arc);
1.289 + Parent::firstIn(arc, node);
1.290 + }
1.291 + }
1.292 +
1.293 + void clearNodes() {
1.294 + Parent::clear();
1.295 + }
1.296 +
1.297 + class NodesImpl : public NodesImplBase {
1.298 + public:
1.299 + typedef NodesImplBase Parent;
1.300 +
1.301 + NodesImpl(const Graph& graph, ListArcSet& arcset)
1.302 + : Parent(graph), _arcset(arcset) {}
1.303 +
1.304 + virtual ~NodesImpl() {}
1.305 +
1.306 + protected:
1.307 +
1.308 + virtual void erase(const Node& node) {
1.309 + _arcset.eraseNode(node);
1.310 + Parent::erase(node);
1.311 + }
1.312 + virtual void erase(const std::vector<Node>& nodes) {
1.313 + for (int i = 0; i < int(nodes.size()); ++i) {
1.314 + _arcset.eraseNode(nodes[i]);
1.315 + }
1.316 + Parent::erase(nodes);
1.317 + }
1.318 + virtual void clear() {
1.319 + _arcset.clearNodes();
1.320 + Parent::clear();
1.321 + }
1.322 +
1.323 + private:
1.324 + ListArcSet& _arcset;
1.325 + };
1.326 +
1.327 + NodesImpl nodes;
1.328 +
1.329 + public:
1.330 +
1.331 + /// \brief Constructor of the ArcSet.
1.332 + ///
1.333 + /// Constructor of the ArcSet.
1.334 + ListArcSet(const Graph& graph) : nodes(graph, *this) {
1.335 + Parent::initalize(graph, nodes);
1.336 + }
1.337 +
1.338 + /// \brief Add a new arc to the digraph.
1.339 + ///
1.340 + /// Add a new arc to the digraph with source node \c s
1.341 + /// and target node \c t.
1.342 + /// \return the new arc.
1.343 + Arc addArc(const Node& s, const Node& t) {
1.344 + return Parent::addArc(s, t);
1.345 + }
1.346 +
1.347 + /// \brief Erase an arc from the digraph.
1.348 + ///
1.349 + /// Erase an arc \c a from the digraph.
1.350 + void erase(const Arc& a) {
1.351 + return Parent::erase(a);
1.352 + }
1.353 +
1.354 + };
1.355 +
1.356 + template <typename _Graph>
1.357 + class ListEdgeSetBase {
1.358 + public:
1.359 +
1.360 + typedef _Graph Graph;
1.361 + typedef typename Graph::Node Node;
1.362 + typedef typename Graph::NodeIt NodeIt;
1.363 +
1.364 + protected:
1.365 +
1.366 + struct NodeT {
1.367 + int first_out;
1.368 + NodeT() : first_out(-1) {}
1.369 + };
1.370 +
1.371 + typedef typename ItemSetTraits<Graph, Node>::
1.372 + template Map<NodeT>::Type NodesImplBase;
1.373 +
1.374 + NodesImplBase* nodes;
1.375 +
1.376 + struct ArcT {
1.377 + Node target;
1.378 + int prev_out, next_out;
1.379 + ArcT() : prev_out(-1), next_out(-1) {}
1.380 + };
1.381 +
1.382 + std::vector<ArcT> arcs;
1.383 +
1.384 + int first_arc;
1.385 + int first_free_arc;
1.386 +
1.387 + const Graph* graph;
1.388 +
1.389 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.390 + graph = &_graph;
1.391 + nodes = &_nodes;
1.392 + }
1.393 +
1.394 + public:
1.395 +
1.396 + class Edge {
1.397 + friend class ListEdgeSetBase;
1.398 + protected:
1.399 +
1.400 + int id;
1.401 + explicit Edge(int _id) { id = _id;}
1.402 +
1.403 + public:
1.404 + Edge() {}
1.405 + Edge (Invalid) { id = -1; }
1.406 + bool operator==(const Edge& arc) const {return id == arc.id;}
1.407 + bool operator!=(const Edge& arc) const {return id != arc.id;}
1.408 + bool operator<(const Edge& arc) const {return id < arc.id;}
1.409 + };
1.410 +
1.411 + class Arc {
1.412 + friend class ListEdgeSetBase;
1.413 + protected:
1.414 + Arc(int _id) : id(_id) {}
1.415 + int id;
1.416 + public:
1.417 + operator Edge() const { return edgeFromId(id / 2); }
1.418 +
1.419 + Arc() {}
1.420 + Arc(Invalid) : id(-1) {}
1.421 + bool operator==(const Arc& arc) const { return id == arc.id; }
1.422 + bool operator!=(const Arc& arc) const { return id != arc.id; }
1.423 + bool operator<(const Arc& arc) const { return id < arc.id; }
1.424 + };
1.425 +
1.426 + ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
1.427 +
1.428 + Edge addEdge(const Node& u, const Node& v) {
1.429 + int n;
1.430 +
1.431 + if (first_free_arc == -1) {
1.432 + n = arcs.size();
1.433 + arcs.push_back(ArcT());
1.434 + arcs.push_back(ArcT());
1.435 + } else {
1.436 + n = first_free_arc;
1.437 + first_free_arc = arcs[n].next_out;
1.438 + }
1.439 +
1.440 + arcs[n].target = u;
1.441 + arcs[n | 1].target = v;
1.442 +
1.443 + arcs[n].next_out = (*nodes)[v].first_out;
1.444 + if ((*nodes)[v].first_out != -1) {
1.445 + arcs[(*nodes)[v].first_out].prev_out = n;
1.446 + }
1.447 + (*nodes)[v].first_out = n;
1.448 + arcs[n].prev_out = -1;
1.449 +
1.450 + if ((*nodes)[u].first_out != -1) {
1.451 + arcs[(*nodes)[u].first_out].prev_out = (n | 1);
1.452 + }
1.453 + arcs[n | 1].next_out = (*nodes)[u].first_out;
1.454 + (*nodes)[u].first_out = (n | 1);
1.455 + arcs[n | 1].prev_out = -1;
1.456 +
1.457 + return Edge(n / 2);
1.458 + }
1.459 +
1.460 + void erase(const Edge& arc) {
1.461 + int n = arc.id * 2;
1.462 +
1.463 + if (arcs[n].next_out != -1) {
1.464 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.465 + }
1.466 +
1.467 + if (arcs[n].prev_out != -1) {
1.468 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.469 + } else {
1.470 + (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
1.471 + }
1.472 +
1.473 + if (arcs[n | 1].next_out != -1) {
1.474 + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.475 + }
1.476 +
1.477 + if (arcs[n | 1].prev_out != -1) {
1.478 + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.479 + } else {
1.480 + (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
1.481 + }
1.482 +
1.483 + arcs[n].next_out = first_free_arc;
1.484 + first_free_arc = n;
1.485 +
1.486 + }
1.487 +
1.488 + void clear() {
1.489 + Node node;
1.490 + for (first(node); node != INVALID; next(node)) {
1.491 + (*nodes)[node].first_out = -1;
1.492 + }
1.493 + arcs.clear();
1.494 + first_arc = -1;
1.495 + first_free_arc = -1;
1.496 + }
1.497 +
1.498 + void first(Node& node) const {
1.499 + graph->first(node);
1.500 + }
1.501 +
1.502 + void next(Node& node) const {
1.503 + graph->next(node);
1.504 + }
1.505 +
1.506 + void first(Arc& arc) const {
1.507 + Node node;
1.508 + first(node);
1.509 + while (node != INVALID && (*nodes)[node].first_out == -1) {
1.510 + next(node);
1.511 + }
1.512 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
1.513 + }
1.514 +
1.515 + void next(Arc& arc) const {
1.516 + if (arcs[arc.id].next_out != -1) {
1.517 + arc.id = arcs[arc.id].next_out;
1.518 + } else {
1.519 + Node node = arcs[arc.id ^ 1].target;
1.520 + next(node);
1.521 + while(node != INVALID && (*nodes)[node].first_out == -1) {
1.522 + next(node);
1.523 + }
1.524 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
1.525 + }
1.526 + }
1.527 +
1.528 + void first(Edge& edge) const {
1.529 + Node node;
1.530 + first(node);
1.531 + while (node != INVALID) {
1.532 + edge.id = (*nodes)[node].first_out;
1.533 + while ((edge.id & 1) != 1) {
1.534 + edge.id = arcs[edge.id].next_out;
1.535 + }
1.536 + if (edge.id != -1) {
1.537 + edge.id /= 2;
1.538 + return;
1.539 + }
1.540 + next(node);
1.541 + }
1.542 + edge.id = -1;
1.543 + }
1.544 +
1.545 + void next(Edge& edge) const {
1.546 + Node node = arcs[edge.id * 2].target;
1.547 + edge.id = arcs[(edge.id * 2) | 1].next_out;
1.548 + while ((edge.id & 1) != 1) {
1.549 + edge.id = arcs[edge.id].next_out;
1.550 + }
1.551 + if (edge.id != -1) {
1.552 + edge.id /= 2;
1.553 + return;
1.554 + }
1.555 + next(node);
1.556 + while (node != INVALID) {
1.557 + edge.id = (*nodes)[node].first_out;
1.558 + while ((edge.id & 1) != 1) {
1.559 + edge.id = arcs[edge.id].next_out;
1.560 + }
1.561 + if (edge.id != -1) {
1.562 + edge.id /= 2;
1.563 + return;
1.564 + }
1.565 + next(node);
1.566 + }
1.567 + edge.id = -1;
1.568 + }
1.569 +
1.570 + void firstOut(Arc& arc, const Node& node) const {
1.571 + arc.id = (*nodes)[node].first_out;
1.572 + }
1.573 +
1.574 + void nextOut(Arc& arc) const {
1.575 + arc.id = arcs[arc.id].next_out;
1.576 + }
1.577 +
1.578 + void firstIn(Arc& arc, const Node& node) const {
1.579 + arc.id = (((*nodes)[node].first_out) ^ 1);
1.580 + if (arc.id == -2) arc.id = -1;
1.581 + }
1.582 +
1.583 + void nextIn(Arc& arc) const {
1.584 + arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
1.585 + if (arc.id == -2) arc.id = -1;
1.586 + }
1.587 +
1.588 + void firstInc(Edge &arc, bool& dir, const Node& node) const {
1.589 + int de = (*nodes)[node].first_out;
1.590 + if (de != -1 ) {
1.591 + arc.id = de / 2;
1.592 + dir = ((de & 1) == 1);
1.593 + } else {
1.594 + arc.id = -1;
1.595 + dir = true;
1.596 + }
1.597 + }
1.598 + void nextInc(Edge &arc, bool& dir) const {
1.599 + int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
1.600 + if (de != -1 ) {
1.601 + arc.id = de / 2;
1.602 + dir = ((de & 1) == 1);
1.603 + } else {
1.604 + arc.id = -1;
1.605 + dir = true;
1.606 + }
1.607 + }
1.608 +
1.609 + static bool direction(Arc arc) {
1.610 + return (arc.id & 1) == 1;
1.611 + }
1.612 +
1.613 + static Arc direct(Edge edge, bool dir) {
1.614 + return Arc(edge.id * 2 + (dir ? 1 : 0));
1.615 + }
1.616 +
1.617 + int id(const Node& node) const { return graph->id(node); }
1.618 + static int id(Arc e) { return e.id; }
1.619 + static int id(Edge e) { return e.id; }
1.620 +
1.621 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
1.622 + static Arc arcFromId(int id) { return Arc(id);}
1.623 + static Edge edgeFromId(int id) { return Edge(id);}
1.624 +
1.625 + int maxNodeId() const { return graph->maxNodeId(); };
1.626 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.627 + int maxArcId() const { return arcs.size()-1; }
1.628 +
1.629 + Node source(Arc e) const { return arcs[e.id ^ 1].target; }
1.630 + Node target(Arc e) const { return arcs[e.id].target; }
1.631 +
1.632 + Node u(Edge e) const { return arcs[2 * e.id].target; }
1.633 + Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
1.634 +
1.635 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.636 +
1.637 + NodeNotifier& notifier(Node) const {
1.638 + return graph->notifier(Node());
1.639 + }
1.640 +
1.641 + template <typename _Value>
1.642 + class NodeMap : public Graph::template NodeMap<_Value> {
1.643 + public:
1.644 +
1.645 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.646 +
1.647 + explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
1.648 + : Parent(*arcset.graph) {}
1.649 +
1.650 + NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
1.651 + : Parent(*arcset.graph, value) {}
1.652 +
1.653 + NodeMap& operator=(const NodeMap& cmap) {
1.654 + return operator=<NodeMap>(cmap);
1.655 + }
1.656 +
1.657 + template <typename CMap>
1.658 + NodeMap& operator=(const CMap& cmap) {
1.659 + Parent::operator=(cmap);
1.660 + return *this;
1.661 + }
1.662 + };
1.663 +
1.664 + };
1.665 +
1.666 + /// \ingroup semi_adaptors
1.667 + ///
1.668 + /// \brief Graph using a node set of another digraph or graph and an
1.669 + /// own edge set.
1.670 + ///
1.671 + /// This structure can be used to establish another graph over a
1.672 + /// node set of an existing one. This class uses the same Node type
1.673 + /// as the underlying graph, and each valid node of the original
1.674 + /// graph is valid in this arc set, therefore the node objects of
1.675 + /// the original graph can be used directly with this class. The
1.676 + /// node handling functions (id handling, observing, and iterators)
1.677 + /// works equivalently as in the original graph.
1.678 + ///
1.679 + /// This implementation is based on doubly-linked lists, from each
1.680 + /// node the incident edges make up lists, therefore one edge can be
1.681 + /// erased in constant time. It also makes possible, that node can
1.682 + /// be removed from the underlying graph, in this case all edges
1.683 + /// incident to the given node is erased from the arc set.
1.684 + ///
1.685 + /// \param _Graph The type of the graph which shares its node set
1.686 + /// with this class. Its interface must conform to the
1.687 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.688 + /// concept.
1.689 + ///
1.690 + /// This class is fully conform to the \ref concepts::Graph "Graph"
1.691 + /// concept.
1.692 + template <typename _Graph>
1.693 + class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
1.694 +
1.695 + public:
1.696 +
1.697 + typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
1.698 +
1.699 + typedef typename Parent::Node Node;
1.700 + typedef typename Parent::Arc Arc;
1.701 + typedef typename Parent::Edge Edge;
1.702 +
1.703 + typedef _Graph Graph;
1.704 +
1.705 +
1.706 + typedef typename Parent::NodesImplBase NodesImplBase;
1.707 +
1.708 + void eraseNode(const Node& node) {
1.709 + Arc arc;
1.710 + Parent::firstOut(arc, node);
1.711 + while (arc != INVALID ) {
1.712 + erase(arc);
1.713 + Parent::firstOut(arc, node);
1.714 + }
1.715 +
1.716 + }
1.717 +
1.718 + void clearNodes() {
1.719 + Parent::clear();
1.720 + }
1.721 +
1.722 + class NodesImpl : public NodesImplBase {
1.723 + public:
1.724 + typedef NodesImplBase Parent;
1.725 +
1.726 + NodesImpl(const Graph& graph, ListEdgeSet& arcset)
1.727 + : Parent(graph), _arcset(arcset) {}
1.728 +
1.729 + virtual ~NodesImpl() {}
1.730 +
1.731 + protected:
1.732 +
1.733 + virtual void erase(const Node& node) {
1.734 + _arcset.eraseNode(node);
1.735 + Parent::erase(node);
1.736 + }
1.737 + virtual void erase(const std::vector<Node>& nodes) {
1.738 + for (int i = 0; i < int(nodes.size()); ++i) {
1.739 + _arcset.eraseNode(nodes[i]);
1.740 + }
1.741 + Parent::erase(nodes);
1.742 + }
1.743 + virtual void clear() {
1.744 + _arcset.clearNodes();
1.745 + Parent::clear();
1.746 + }
1.747 +
1.748 + private:
1.749 + ListEdgeSet& _arcset;
1.750 + };
1.751 +
1.752 + NodesImpl nodes;
1.753 +
1.754 + public:
1.755 +
1.756 + /// \brief Constructor of the EdgeSet.
1.757 + ///
1.758 + /// Constructor of the EdgeSet.
1.759 + ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.760 + Parent::initalize(graph, nodes);
1.761 + }
1.762 +
1.763 + /// \brief Add a new edge to the graph.
1.764 + ///
1.765 + /// Add a new edge to the graph with node \c u
1.766 + /// and node \c v endpoints.
1.767 + /// \return the new edge.
1.768 + Edge addEdge(const Node& u, const Node& v) {
1.769 + return Parent::addEdge(u, v);
1.770 + }
1.771 +
1.772 + /// \brief Erase an edge from the graph.
1.773 + ///
1.774 + /// Erase the edge \c e from the graph.
1.775 + void erase(const Edge& e) {
1.776 + return Parent::erase(e);
1.777 + }
1.778 +
1.779 + };
1.780 +
1.781 + template <typename _Graph>
1.782 + class SmartArcSetBase {
1.783 + public:
1.784 +
1.785 + typedef _Graph Graph;
1.786 + typedef typename Graph::Node Node;
1.787 + typedef typename Graph::NodeIt NodeIt;
1.788 +
1.789 + protected:
1.790 +
1.791 + struct NodeT {
1.792 + int first_out, first_in;
1.793 + NodeT() : first_out(-1), first_in(-1) {}
1.794 + };
1.795 +
1.796 + typedef typename ItemSetTraits<Graph, Node>::
1.797 + template Map<NodeT>::Type NodesImplBase;
1.798 +
1.799 + NodesImplBase* nodes;
1.800 +
1.801 + struct ArcT {
1.802 + Node source, target;
1.803 + int next_out, next_in;
1.804 + ArcT() {}
1.805 + };
1.806 +
1.807 + std::vector<ArcT> arcs;
1.808 +
1.809 + const Graph* graph;
1.810 +
1.811 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.812 + graph = &_graph;
1.813 + nodes = &_nodes;
1.814 + }
1.815 +
1.816 + public:
1.817 +
1.818 + class Arc {
1.819 + friend class SmartArcSetBase<Graph>;
1.820 + protected:
1.821 + Arc(int _id) : id(_id) {}
1.822 + int id;
1.823 + public:
1.824 + Arc() {}
1.825 + Arc(Invalid) : id(-1) {}
1.826 + bool operator==(const Arc& arc) const { return id == arc.id; }
1.827 + bool operator!=(const Arc& arc) const { return id != arc.id; }
1.828 + bool operator<(const Arc& arc) const { return id < arc.id; }
1.829 + };
1.830 +
1.831 + SmartArcSetBase() {}
1.832 +
1.833 + Arc addArc(const Node& u, const Node& v) {
1.834 + int n = arcs.size();
1.835 + arcs.push_back(ArcT());
1.836 + arcs[n].next_in = (*nodes)[v].first_in;
1.837 + (*nodes)[v].first_in = n;
1.838 + arcs[n].next_out = (*nodes)[u].first_out;
1.839 + (*nodes)[u].first_out = n;
1.840 + arcs[n].source = u;
1.841 + arcs[n].target = v;
1.842 + return Arc(n);
1.843 + }
1.844 +
1.845 + void clear() {
1.846 + Node node;
1.847 + for (first(node); node != INVALID; next(node)) {
1.848 + (*nodes)[node].first_in = -1;
1.849 + (*nodes)[node].first_out = -1;
1.850 + }
1.851 + arcs.clear();
1.852 + }
1.853 +
1.854 + void first(Node& node) const {
1.855 + graph->first(node);
1.856 + }
1.857 +
1.858 + void next(Node& node) const {
1.859 + graph->next(node);
1.860 + }
1.861 +
1.862 + void first(Arc& arc) const {
1.863 + arc.id = arcs.size() - 1;
1.864 + }
1.865 +
1.866 + void next(Arc& arc) const {
1.867 + --arc.id;
1.868 + }
1.869 +
1.870 + void firstOut(Arc& arc, const Node& node) const {
1.871 + arc.id = (*nodes)[node].first_out;
1.872 + }
1.873 +
1.874 + void nextOut(Arc& arc) const {
1.875 + arc.id = arcs[arc.id].next_out;
1.876 + }
1.877 +
1.878 + void firstIn(Arc& arc, const Node& node) const {
1.879 + arc.id = (*nodes)[node].first_in;
1.880 + }
1.881 +
1.882 + void nextIn(Arc& arc) const {
1.883 + arc.id = arcs[arc.id].next_in;
1.884 + }
1.885 +
1.886 + int id(const Node& node) const { return graph->id(node); }
1.887 + int id(const Arc& arc) const { return arc.id; }
1.888 +
1.889 + Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
1.890 + Arc arcFromId(int ix) const { return Arc(ix); }
1.891 +
1.892 + int maxNodeId() const { return graph->maxNodeId(); };
1.893 + int maxArcId() const { return arcs.size() - 1; }
1.894 +
1.895 + Node source(const Arc& arc) const { return arcs[arc.id].source;}
1.896 + Node target(const Arc& arc) const { return arcs[arc.id].target;}
1.897 +
1.898 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.899 +
1.900 + NodeNotifier& notifier(Node) const {
1.901 + return graph->notifier(Node());
1.902 + }
1.903 +
1.904 + template <typename _Value>
1.905 + class NodeMap : public Graph::template NodeMap<_Value> {
1.906 + public:
1.907 +
1.908 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.909 +
1.910 + explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
1.911 + : Parent(*arcset.graph) { }
1.912 +
1.913 + NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
1.914 + : Parent(*arcset.graph, value) { }
1.915 +
1.916 + NodeMap& operator=(const NodeMap& cmap) {
1.917 + return operator=<NodeMap>(cmap);
1.918 + }
1.919 +
1.920 + template <typename CMap>
1.921 + NodeMap& operator=(const CMap& cmap) {
1.922 + Parent::operator=(cmap);
1.923 + return *this;
1.924 + }
1.925 + };
1.926 +
1.927 + };
1.928 +
1.929 +
1.930 + /// \ingroup semi_adaptors
1.931 + ///
1.932 + /// \brief Digraph using a node set of another digraph or graph and
1.933 + /// an own arc set.
1.934 + ///
1.935 + /// This structure can be used to establish another directed graph
1.936 + /// over a node set of an existing one. This class uses the same
1.937 + /// Node type as the underlying graph, and each valid node of the
1.938 + /// original graph is valid in this arc set, therefore the node
1.939 + /// objects of the original graph can be used directly with this
1.940 + /// class. The node handling functions (id handling, observing, and
1.941 + /// iterators) works equivalently as in the original graph.
1.942 + ///
1.943 + /// \param _Graph The type of the graph which shares its node set with
1.944 + /// this class. Its interface must conform to the
1.945 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.946 + /// concept.
1.947 + ///
1.948 + /// This implementation is slightly faster than the \c ListArcSet,
1.949 + /// because it uses continuous storage for arcs and it uses just
1.950 + /// single-linked lists for enumerate outgoing and incoming
1.951 + /// arcs. Therefore the arcs cannot be erased from the arc sets.
1.952 + ///
1.953 + /// \warning If a node is erased from the underlying graph and this
1.954 + /// node is the source or target of one arc in the arc set, then
1.955 + /// the arc set is invalidated, and it cannot be used anymore. The
1.956 + /// validity can be checked with the \c valid() member function.
1.957 + ///
1.958 + /// This class is fully conform to the \ref concepts::Digraph
1.959 + /// "Digraph" concept.
1.960 + template <typename _Graph>
1.961 + class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
1.962 +
1.963 + public:
1.964 +
1.965 + typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
1.966 +
1.967 + typedef typename Parent::Node Node;
1.968 + typedef typename Parent::Arc Arc;
1.969 +
1.970 + typedef _Graph Graph;
1.971 +
1.972 + protected:
1.973 +
1.974 + typedef typename Parent::NodesImplBase NodesImplBase;
1.975 +
1.976 + void eraseNode(const Node& node) {
1.977 + if (typename Parent::InArcIt(*this, node) == INVALID &&
1.978 + typename Parent::OutArcIt(*this, node) == INVALID) {
1.979 + return;
1.980 + }
1.981 + throw typename NodesImplBase::Notifier::ImmediateDetach();
1.982 + }
1.983 +
1.984 + void clearNodes() {
1.985 + Parent::clear();
1.986 + }
1.987 +
1.988 + class NodesImpl : public NodesImplBase {
1.989 + public:
1.990 + typedef NodesImplBase Parent;
1.991 +
1.992 + NodesImpl(const Graph& graph, SmartArcSet& arcset)
1.993 + : Parent(graph), _arcset(arcset) {}
1.994 +
1.995 + virtual ~NodesImpl() {}
1.996 +
1.997 + bool attached() const {
1.998 + return Parent::attached();
1.999 + }
1.1000 +
1.1001 + protected:
1.1002 +
1.1003 + virtual void erase(const Node& node) {
1.1004 + try {
1.1005 + _arcset.eraseNode(node);
1.1006 + Parent::erase(node);
1.1007 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1.1008 + Parent::clear();
1.1009 + throw;
1.1010 + }
1.1011 + }
1.1012 + virtual void erase(const std::vector<Node>& nodes) {
1.1013 + try {
1.1014 + for (int i = 0; i < int(nodes.size()); ++i) {
1.1015 + _arcset.eraseNode(nodes[i]);
1.1016 + }
1.1017 + Parent::erase(nodes);
1.1018 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1.1019 + Parent::clear();
1.1020 + throw;
1.1021 + }
1.1022 + }
1.1023 + virtual void clear() {
1.1024 + _arcset.clearNodes();
1.1025 + Parent::clear();
1.1026 + }
1.1027 +
1.1028 + private:
1.1029 + SmartArcSet& _arcset;
1.1030 + };
1.1031 +
1.1032 + NodesImpl nodes;
1.1033 +
1.1034 + public:
1.1035 +
1.1036 + /// \brief Constructor of the ArcSet.
1.1037 + ///
1.1038 + /// Constructor of the ArcSet.
1.1039 + SmartArcSet(const Graph& graph) : nodes(graph, *this) {
1.1040 + Parent::initalize(graph, nodes);
1.1041 + }
1.1042 +
1.1043 + /// \brief Add a new arc to the digraph.
1.1044 + ///
1.1045 + /// Add a new arc to the digraph with source node \c s
1.1046 + /// and target node \c t.
1.1047 + /// \return the new arc.
1.1048 + Arc addArc(const Node& s, const Node& t) {
1.1049 + return Parent::addArc(s, t);
1.1050 + }
1.1051 +
1.1052 + /// \brief Validity check
1.1053 + ///
1.1054 + /// This functions gives back false if the ArcSet is
1.1055 + /// invalidated. It occurs when a node in the underlying graph is
1.1056 + /// erased and it is not isolated in the ArcSet.
1.1057 + bool valid() const {
1.1058 + return nodes.attached();
1.1059 + }
1.1060 +
1.1061 + };
1.1062 +
1.1063 +
1.1064 + template <typename _Graph>
1.1065 + class SmartEdgeSetBase {
1.1066 + public:
1.1067 +
1.1068 + typedef _Graph Graph;
1.1069 + typedef typename Graph::Node Node;
1.1070 + typedef typename Graph::NodeIt NodeIt;
1.1071 +
1.1072 + protected:
1.1073 +
1.1074 + struct NodeT {
1.1075 + int first_out;
1.1076 + NodeT() : first_out(-1) {}
1.1077 + };
1.1078 +
1.1079 + typedef typename ItemSetTraits<Graph, Node>::
1.1080 + template Map<NodeT>::Type NodesImplBase;
1.1081 +
1.1082 + NodesImplBase* nodes;
1.1083 +
1.1084 + struct ArcT {
1.1085 + Node target;
1.1086 + int next_out;
1.1087 + ArcT() {}
1.1088 + };
1.1089 +
1.1090 + std::vector<ArcT> arcs;
1.1091 +
1.1092 + const Graph* graph;
1.1093 +
1.1094 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.1095 + graph = &_graph;
1.1096 + nodes = &_nodes;
1.1097 + }
1.1098 +
1.1099 + public:
1.1100 +
1.1101 + class Edge {
1.1102 + friend class SmartEdgeSetBase;
1.1103 + protected:
1.1104 +
1.1105 + int id;
1.1106 + explicit Edge(int _id) { id = _id;}
1.1107 +
1.1108 + public:
1.1109 + Edge() {}
1.1110 + Edge (Invalid) { id = -1; }
1.1111 + bool operator==(const Edge& arc) const {return id == arc.id;}
1.1112 + bool operator!=(const Edge& arc) const {return id != arc.id;}
1.1113 + bool operator<(const Edge& arc) const {return id < arc.id;}
1.1114 + };
1.1115 +
1.1116 + class Arc {
1.1117 + friend class SmartEdgeSetBase;
1.1118 + protected:
1.1119 + Arc(int _id) : id(_id) {}
1.1120 + int id;
1.1121 + public:
1.1122 + operator Edge() const { return edgeFromId(id / 2); }
1.1123 +
1.1124 + Arc() {}
1.1125 + Arc(Invalid) : id(-1) {}
1.1126 + bool operator==(const Arc& arc) const { return id == arc.id; }
1.1127 + bool operator!=(const Arc& arc) const { return id != arc.id; }
1.1128 + bool operator<(const Arc& arc) const { return id < arc.id; }
1.1129 + };
1.1130 +
1.1131 + SmartEdgeSetBase() {}
1.1132 +
1.1133 + Edge addEdge(const Node& u, const Node& v) {
1.1134 + int n = arcs.size();
1.1135 + arcs.push_back(ArcT());
1.1136 + arcs.push_back(ArcT());
1.1137 +
1.1138 + arcs[n].target = u;
1.1139 + arcs[n | 1].target = v;
1.1140 +
1.1141 + arcs[n].next_out = (*nodes)[v].first_out;
1.1142 + (*nodes)[v].first_out = n;
1.1143 +
1.1144 + arcs[n | 1].next_out = (*nodes)[u].first_out;
1.1145 + (*nodes)[u].first_out = (n | 1);
1.1146 +
1.1147 + return Edge(n / 2);
1.1148 + }
1.1149 +
1.1150 + void clear() {
1.1151 + Node node;
1.1152 + for (first(node); node != INVALID; next(node)) {
1.1153 + (*nodes)[node].first_out = -1;
1.1154 + }
1.1155 + arcs.clear();
1.1156 + }
1.1157 +
1.1158 + void first(Node& node) const {
1.1159 + graph->first(node);
1.1160 + }
1.1161 +
1.1162 + void next(Node& node) const {
1.1163 + graph->next(node);
1.1164 + }
1.1165 +
1.1166 + void first(Arc& arc) const {
1.1167 + arc.id = arcs.size() - 1;
1.1168 + }
1.1169 +
1.1170 + void next(Arc& arc) const {
1.1171 + --arc.id;
1.1172 + }
1.1173 +
1.1174 + void first(Edge& arc) const {
1.1175 + arc.id = arcs.size() / 2 - 1;
1.1176 + }
1.1177 +
1.1178 + void next(Edge& arc) const {
1.1179 + --arc.id;
1.1180 + }
1.1181 +
1.1182 + void firstOut(Arc& arc, const Node& node) const {
1.1183 + arc.id = (*nodes)[node].first_out;
1.1184 + }
1.1185 +
1.1186 + void nextOut(Arc& arc) const {
1.1187 + arc.id = arcs[arc.id].next_out;
1.1188 + }
1.1189 +
1.1190 + void firstIn(Arc& arc, const Node& node) const {
1.1191 + arc.id = (((*nodes)[node].first_out) ^ 1);
1.1192 + if (arc.id == -2) arc.id = -1;
1.1193 + }
1.1194 +
1.1195 + void nextIn(Arc& arc) const {
1.1196 + arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
1.1197 + if (arc.id == -2) arc.id = -1;
1.1198 + }
1.1199 +
1.1200 + void firstInc(Edge &arc, bool& dir, const Node& node) const {
1.1201 + int de = (*nodes)[node].first_out;
1.1202 + if (de != -1 ) {
1.1203 + arc.id = de / 2;
1.1204 + dir = ((de & 1) == 1);
1.1205 + } else {
1.1206 + arc.id = -1;
1.1207 + dir = true;
1.1208 + }
1.1209 + }
1.1210 + void nextInc(Edge &arc, bool& dir) const {
1.1211 + int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
1.1212 + if (de != -1 ) {
1.1213 + arc.id = de / 2;
1.1214 + dir = ((de & 1) == 1);
1.1215 + } else {
1.1216 + arc.id = -1;
1.1217 + dir = true;
1.1218 + }
1.1219 + }
1.1220 +
1.1221 + static bool direction(Arc arc) {
1.1222 + return (arc.id & 1) == 1;
1.1223 + }
1.1224 +
1.1225 + static Arc direct(Edge edge, bool dir) {
1.1226 + return Arc(edge.id * 2 + (dir ? 1 : 0));
1.1227 + }
1.1228 +
1.1229 + int id(Node node) const { return graph->id(node); }
1.1230 + static int id(Arc arc) { return arc.id; }
1.1231 + static int id(Edge arc) { return arc.id; }
1.1232 +
1.1233 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
1.1234 + static Arc arcFromId(int id) { return Arc(id); }
1.1235 + static Edge edgeFromId(int id) { return Edge(id);}
1.1236 +
1.1237 + int maxNodeId() const { return graph->maxNodeId(); };
1.1238 + int maxArcId() const { return arcs.size() - 1; }
1.1239 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.1240 +
1.1241 + Node source(Arc e) const { return arcs[e.id ^ 1].target; }
1.1242 + Node target(Arc e) const { return arcs[e.id].target; }
1.1243 +
1.1244 + Node u(Edge e) const { return arcs[2 * e.id].target; }
1.1245 + Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
1.1246 +
1.1247 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.1248 +
1.1249 + NodeNotifier& notifier(Node) const {
1.1250 + return graph->notifier(Node());
1.1251 + }
1.1252 +
1.1253 + template <typename _Value>
1.1254 + class NodeMap : public Graph::template NodeMap<_Value> {
1.1255 + public:
1.1256 +
1.1257 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.1258 +
1.1259 + explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
1.1260 + : Parent(*arcset.graph) { }
1.1261 +
1.1262 + NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
1.1263 + : Parent(*arcset.graph, value) { }
1.1264 +
1.1265 + NodeMap& operator=(const NodeMap& cmap) {
1.1266 + return operator=<NodeMap>(cmap);
1.1267 + }
1.1268 +
1.1269 + template <typename CMap>
1.1270 + NodeMap& operator=(const CMap& cmap) {
1.1271 + Parent::operator=(cmap);
1.1272 + return *this;
1.1273 + }
1.1274 + };
1.1275 +
1.1276 + };
1.1277 +
1.1278 + /// \ingroup semi_adaptors
1.1279 + ///
1.1280 + /// \brief Graph using a node set of another digraph or graph and an
1.1281 + /// own edge set.
1.1282 + ///
1.1283 + /// This structure can be used to establish another graph over a
1.1284 + /// node set of an existing one. This class uses the same Node type
1.1285 + /// as the underlying graph, and each valid node of the original
1.1286 + /// graph is valid in this arc set, therefore the node objects of
1.1287 + /// the original graph can be used directly with this class. The
1.1288 + /// node handling functions (id handling, observing, and iterators)
1.1289 + /// works equivalently as in the original graph.
1.1290 + ///
1.1291 + /// \param _Graph The type of the graph which shares its node set
1.1292 + /// with this class. Its interface must conform to the
1.1293 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.1294 + /// concept.
1.1295 + ///
1.1296 + /// This implementation is slightly faster than the \c ListEdgeSet,
1.1297 + /// because it uses continuous storage for edges and it uses just
1.1298 + /// single-linked lists for enumerate incident edges. Therefore the
1.1299 + /// edges cannot be erased from the edge sets.
1.1300 + ///
1.1301 + /// \warning If a node is erased from the underlying graph and this
1.1302 + /// node is incident to one edge in the edge set, then the edge set
1.1303 + /// is invalidated, and it cannot be used anymore. The validity can
1.1304 + /// be checked with the \c valid() member function.
1.1305 + ///
1.1306 + /// This class is fully conform to the \ref concepts::Graph
1.1307 + /// "Graph" concept.
1.1308 + template <typename _Graph>
1.1309 + class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
1.1310 +
1.1311 + public:
1.1312 +
1.1313 + typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
1.1314 +
1.1315 + typedef typename Parent::Node Node;
1.1316 + typedef typename Parent::Arc Arc;
1.1317 + typedef typename Parent::Edge Edge;
1.1318 +
1.1319 + typedef _Graph Graph;
1.1320 +
1.1321 + protected:
1.1322 +
1.1323 + typedef typename Parent::NodesImplBase NodesImplBase;
1.1324 +
1.1325 + void eraseNode(const Node& node) {
1.1326 + if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
1.1327 + return;
1.1328 + }
1.1329 + throw typename NodesImplBase::Notifier::ImmediateDetach();
1.1330 + }
1.1331 +
1.1332 + void clearNodes() {
1.1333 + Parent::clear();
1.1334 + }
1.1335 +
1.1336 + class NodesImpl : public NodesImplBase {
1.1337 + public:
1.1338 + typedef NodesImplBase Parent;
1.1339 +
1.1340 + NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
1.1341 + : Parent(graph), _arcset(arcset) {}
1.1342 +
1.1343 + virtual ~NodesImpl() {}
1.1344 +
1.1345 + bool attached() const {
1.1346 + return Parent::attached();
1.1347 + }
1.1348 +
1.1349 + protected:
1.1350 +
1.1351 + virtual void erase(const Node& node) {
1.1352 + try {
1.1353 + _arcset.eraseNode(node);
1.1354 + Parent::erase(node);
1.1355 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1.1356 + Parent::clear();
1.1357 + throw;
1.1358 + }
1.1359 + }
1.1360 + virtual void erase(const std::vector<Node>& nodes) {
1.1361 + try {
1.1362 + for (int i = 0; i < int(nodes.size()); ++i) {
1.1363 + _arcset.eraseNode(nodes[i]);
1.1364 + }
1.1365 + Parent::erase(nodes);
1.1366 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
1.1367 + Parent::clear();
1.1368 + throw;
1.1369 + }
1.1370 + }
1.1371 + virtual void clear() {
1.1372 + _arcset.clearNodes();
1.1373 + Parent::clear();
1.1374 + }
1.1375 +
1.1376 + private:
1.1377 + SmartEdgeSet& _arcset;
1.1378 + };
1.1379 +
1.1380 + NodesImpl nodes;
1.1381 +
1.1382 + public:
1.1383 +
1.1384 + /// \brief Constructor of the EdgeSet.
1.1385 + ///
1.1386 + /// Constructor of the EdgeSet.
1.1387 + SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.1388 + Parent::initalize(graph, nodes);
1.1389 + }
1.1390 +
1.1391 + /// \brief Add a new edge to the graph.
1.1392 + ///
1.1393 + /// Add a new edge to the graph with node \c u
1.1394 + /// and node \c v endpoints.
1.1395 + /// \return the new edge.
1.1396 + Edge addEdge(const Node& u, const Node& v) {
1.1397 + return Parent::addEdge(u, v);
1.1398 + }
1.1399 +
1.1400 + /// \brief Validity check
1.1401 + ///
1.1402 + /// This functions gives back false if the EdgeSet is
1.1403 + /// invalidated. It occurs when a node in the underlying graph is
1.1404 + /// erased and it is not isolated in the EdgeSet.
1.1405 + bool valid() const {
1.1406 + return nodes.attached();
1.1407 + }
1.1408 +
1.1409 + };
1.1410 +
1.1411 +}
1.1412 +
1.1413 +#endif