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