1.1 --- a/lemon/Makefile.am Mon Jan 12 13:18:03 2009 +0000
1.2 +++ b/lemon/Makefile.am Mon Jan 12 13:37:37 2009 +0000
1.3 @@ -60,6 +60,7 @@
1.4 lemon/dijkstra.h \
1.5 lemon/dim2.h \
1.6 lemon/dimacs.h \
1.7 + lemon/edge_set.h \
1.8 lemon/elevator.h \
1.9 lemon/error.h \
1.10 lemon/full_graph.h \
1.11 @@ -97,6 +98,7 @@
1.12 lemon/bits/base_extender.h \
1.13 lemon/bits/bezier.h \
1.14 lemon/bits/default_map.h \
1.15 + lemon/bits/edge_set_extender.h \
1.16 lemon/bits/enable_if.h \
1.17 lemon/bits/graph_adaptor_extender.h \
1.18 lemon/bits/graph_extender.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/bits/edge_set_extender.h Mon Jan 12 13:37:37 2009 +0000
2.3 @@ -0,0 +1,628 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_BITS_EDGE_SET_EXTENDER_H
2.23 +#define LEMON_BITS_EDGE_SET_EXTENDER_H
2.24 +
2.25 +#include <lemon/error.h>
2.26 +#include <lemon/bits/default_map.h>
2.27 +
2.28 +///\ingroup digraphbits
2.29 +///\file
2.30 +///\brief Extenders for the arc set types
2.31 +namespace lemon {
2.32 +
2.33 + /// \ingroup digraphbits
2.34 + ///
2.35 + /// \brief Extender for the ArcSets
2.36 + template <typename Base>
2.37 + class ArcSetExtender : public Base {
2.38 + public:
2.39 +
2.40 + typedef Base Parent;
2.41 + typedef ArcSetExtender Digraph;
2.42 +
2.43 + // Base extensions
2.44 +
2.45 + typedef typename Parent::Node Node;
2.46 + typedef typename Parent::Arc Arc;
2.47 +
2.48 + int maxId(Node) const {
2.49 + return Parent::maxNodeId();
2.50 + }
2.51 +
2.52 + int maxId(Arc) const {
2.53 + return Parent::maxArcId();
2.54 + }
2.55 +
2.56 + Node fromId(int id, Node) const {
2.57 + return Parent::nodeFromId(id);
2.58 + }
2.59 +
2.60 + Arc fromId(int id, Arc) const {
2.61 + return Parent::arcFromId(id);
2.62 + }
2.63 +
2.64 + Node oppositeNode(const Node &n, const Arc &e) const {
2.65 + if (n == Parent::source(e))
2.66 + return Parent::target(e);
2.67 + else if(n==Parent::target(e))
2.68 + return Parent::source(e);
2.69 + else
2.70 + return INVALID;
2.71 + }
2.72 +
2.73 +
2.74 + // Alteration notifier extensions
2.75 +
2.76 + /// The arc observer registry.
2.77 + typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
2.78 +
2.79 + protected:
2.80 +
2.81 + mutable ArcNotifier arc_notifier;
2.82 +
2.83 + public:
2.84 +
2.85 + using Parent::notifier;
2.86 +
2.87 + /// \brief Gives back the arc alteration notifier.
2.88 + ///
2.89 + /// Gives back the arc alteration notifier.
2.90 + ArcNotifier& notifier(Arc) const {
2.91 + return arc_notifier;
2.92 + }
2.93 +
2.94 + // Iterable extensions
2.95 +
2.96 + class NodeIt : public Node {
2.97 + const Digraph* digraph;
2.98 + public:
2.99 +
2.100 + NodeIt() {}
2.101 +
2.102 + NodeIt(Invalid i) : Node(i) { }
2.103 +
2.104 + explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
2.105 + _graph.first(static_cast<Node&>(*this));
2.106 + }
2.107 +
2.108 + NodeIt(const Digraph& _graph, const Node& node)
2.109 + : Node(node), digraph(&_graph) {}
2.110 +
2.111 + NodeIt& operator++() {
2.112 + digraph->next(*this);
2.113 + return *this;
2.114 + }
2.115 +
2.116 + };
2.117 +
2.118 +
2.119 + class ArcIt : public Arc {
2.120 + const Digraph* digraph;
2.121 + public:
2.122 +
2.123 + ArcIt() { }
2.124 +
2.125 + ArcIt(Invalid i) : Arc(i) { }
2.126 +
2.127 + explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
2.128 + _graph.first(static_cast<Arc&>(*this));
2.129 + }
2.130 +
2.131 + ArcIt(const Digraph& _graph, const Arc& e) :
2.132 + Arc(e), digraph(&_graph) { }
2.133 +
2.134 + ArcIt& operator++() {
2.135 + digraph->next(*this);
2.136 + return *this;
2.137 + }
2.138 +
2.139 + };
2.140 +
2.141 +
2.142 + class OutArcIt : public Arc {
2.143 + const Digraph* digraph;
2.144 + public:
2.145 +
2.146 + OutArcIt() { }
2.147 +
2.148 + OutArcIt(Invalid i) : Arc(i) { }
2.149 +
2.150 + OutArcIt(const Digraph& _graph, const Node& node)
2.151 + : digraph(&_graph) {
2.152 + _graph.firstOut(*this, node);
2.153 + }
2.154 +
2.155 + OutArcIt(const Digraph& _graph, const Arc& arc)
2.156 + : Arc(arc), digraph(&_graph) {}
2.157 +
2.158 + OutArcIt& operator++() {
2.159 + digraph->nextOut(*this);
2.160 + return *this;
2.161 + }
2.162 +
2.163 + };
2.164 +
2.165 +
2.166 + class InArcIt : public Arc {
2.167 + const Digraph* digraph;
2.168 + public:
2.169 +
2.170 + InArcIt() { }
2.171 +
2.172 + InArcIt(Invalid i) : Arc(i) { }
2.173 +
2.174 + InArcIt(const Digraph& _graph, const Node& node)
2.175 + : digraph(&_graph) {
2.176 + _graph.firstIn(*this, node);
2.177 + }
2.178 +
2.179 + InArcIt(const Digraph& _graph, const Arc& arc) :
2.180 + Arc(arc), digraph(&_graph) {}
2.181 +
2.182 + InArcIt& operator++() {
2.183 + digraph->nextIn(*this);
2.184 + return *this;
2.185 + }
2.186 +
2.187 + };
2.188 +
2.189 + /// \brief Base node of the iterator
2.190 + ///
2.191 + /// Returns the base node (ie. the source in this case) of the iterator
2.192 + Node baseNode(const OutArcIt &e) const {
2.193 + return Parent::source(static_cast<const Arc&>(e));
2.194 + }
2.195 + /// \brief Running node of the iterator
2.196 + ///
2.197 + /// Returns the running node (ie. the target in this case) of the
2.198 + /// iterator
2.199 + Node runningNode(const OutArcIt &e) const {
2.200 + return Parent::target(static_cast<const Arc&>(e));
2.201 + }
2.202 +
2.203 + /// \brief Base node of the iterator
2.204 + ///
2.205 + /// Returns the base node (ie. the target in this case) of the iterator
2.206 + Node baseNode(const InArcIt &e) const {
2.207 + return Parent::target(static_cast<const Arc&>(e));
2.208 + }
2.209 + /// \brief Running node of the iterator
2.210 + ///
2.211 + /// Returns the running node (ie. the source in this case) of the
2.212 + /// iterator
2.213 + Node runningNode(const InArcIt &e) const {
2.214 + return Parent::source(static_cast<const Arc&>(e));
2.215 + }
2.216 +
2.217 + using Parent::first;
2.218 +
2.219 + // Mappable extension
2.220 +
2.221 + template <typename _Value>
2.222 + class ArcMap
2.223 + : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
2.224 + public:
2.225 + typedef ArcSetExtender Digraph;
2.226 + typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
2.227 +
2.228 + explicit ArcMap(const Digraph& _g)
2.229 + : Parent(_g) {}
2.230 + ArcMap(const Digraph& _g, const _Value& _v)
2.231 + : Parent(_g, _v) {}
2.232 +
2.233 + ArcMap& operator=(const ArcMap& cmap) {
2.234 + return operator=<ArcMap>(cmap);
2.235 + }
2.236 +
2.237 + template <typename CMap>
2.238 + ArcMap& operator=(const CMap& cmap) {
2.239 + Parent::operator=(cmap);
2.240 + return *this;
2.241 + }
2.242 +
2.243 + };
2.244 +
2.245 +
2.246 + // Alteration extension
2.247 +
2.248 + Arc addArc(const Node& from, const Node& to) {
2.249 + Arc arc = Parent::addArc(from, to);
2.250 + notifier(Arc()).add(arc);
2.251 + return arc;
2.252 + }
2.253 +
2.254 + void clear() {
2.255 + notifier(Arc()).clear();
2.256 + Parent::clear();
2.257 + }
2.258 +
2.259 + void erase(const Arc& arc) {
2.260 + notifier(Arc()).erase(arc);
2.261 + Parent::erase(arc);
2.262 + }
2.263 +
2.264 + ArcSetExtender() {
2.265 + arc_notifier.setContainer(*this);
2.266 + }
2.267 +
2.268 + ~ArcSetExtender() {
2.269 + arc_notifier.clear();
2.270 + }
2.271 +
2.272 + };
2.273 +
2.274 +
2.275 + /// \ingroup digraphbits
2.276 + ///
2.277 + /// \brief Extender for the EdgeSets
2.278 + template <typename Base>
2.279 + class EdgeSetExtender : public Base {
2.280 +
2.281 + public:
2.282 +
2.283 + typedef Base Parent;
2.284 + typedef EdgeSetExtender Digraph;
2.285 +
2.286 + typedef typename Parent::Node Node;
2.287 + typedef typename Parent::Arc Arc;
2.288 + typedef typename Parent::Edge Edge;
2.289 +
2.290 +
2.291 + int maxId(Node) const {
2.292 + return Parent::maxNodeId();
2.293 + }
2.294 +
2.295 + int maxId(Arc) const {
2.296 + return Parent::maxArcId();
2.297 + }
2.298 +
2.299 + int maxId(Edge) const {
2.300 + return Parent::maxEdgeId();
2.301 + }
2.302 +
2.303 + Node fromId(int id, Node) const {
2.304 + return Parent::nodeFromId(id);
2.305 + }
2.306 +
2.307 + Arc fromId(int id, Arc) const {
2.308 + return Parent::arcFromId(id);
2.309 + }
2.310 +
2.311 + Edge fromId(int id, Edge) const {
2.312 + return Parent::edgeFromId(id);
2.313 + }
2.314 +
2.315 + Node oppositeNode(const Node &n, const Edge &e) const {
2.316 + if( n == Parent::u(e))
2.317 + return Parent::v(e);
2.318 + else if( n == Parent::v(e))
2.319 + return Parent::u(e);
2.320 + else
2.321 + return INVALID;
2.322 + }
2.323 +
2.324 + Arc oppositeArc(const Arc &e) const {
2.325 + return Parent::direct(e, !Parent::direction(e));
2.326 + }
2.327 +
2.328 + using Parent::direct;
2.329 + Arc direct(const Edge &e, const Node &s) const {
2.330 + return Parent::direct(e, Parent::u(e) == s);
2.331 + }
2.332 +
2.333 + typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
2.334 + typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
2.335 +
2.336 +
2.337 + protected:
2.338 +
2.339 + mutable ArcNotifier arc_notifier;
2.340 + mutable EdgeNotifier edge_notifier;
2.341 +
2.342 + public:
2.343 +
2.344 + using Parent::notifier;
2.345 +
2.346 + ArcNotifier& notifier(Arc) const {
2.347 + return arc_notifier;
2.348 + }
2.349 +
2.350 + EdgeNotifier& notifier(Edge) const {
2.351 + return edge_notifier;
2.352 + }
2.353 +
2.354 +
2.355 + class NodeIt : public Node {
2.356 + const Digraph* digraph;
2.357 + public:
2.358 +
2.359 + NodeIt() {}
2.360 +
2.361 + NodeIt(Invalid i) : Node(i) { }
2.362 +
2.363 + explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
2.364 + _graph.first(static_cast<Node&>(*this));
2.365 + }
2.366 +
2.367 + NodeIt(const Digraph& _graph, const Node& node)
2.368 + : Node(node), digraph(&_graph) {}
2.369 +
2.370 + NodeIt& operator++() {
2.371 + digraph->next(*this);
2.372 + return *this;
2.373 + }
2.374 +
2.375 + };
2.376 +
2.377 +
2.378 + class ArcIt : public Arc {
2.379 + const Digraph* digraph;
2.380 + public:
2.381 +
2.382 + ArcIt() { }
2.383 +
2.384 + ArcIt(Invalid i) : Arc(i) { }
2.385 +
2.386 + explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
2.387 + _graph.first(static_cast<Arc&>(*this));
2.388 + }
2.389 +
2.390 + ArcIt(const Digraph& _graph, const Arc& e) :
2.391 + Arc(e), digraph(&_graph) { }
2.392 +
2.393 + ArcIt& operator++() {
2.394 + digraph->next(*this);
2.395 + return *this;
2.396 + }
2.397 +
2.398 + };
2.399 +
2.400 +
2.401 + class OutArcIt : public Arc {
2.402 + const Digraph* digraph;
2.403 + public:
2.404 +
2.405 + OutArcIt() { }
2.406 +
2.407 + OutArcIt(Invalid i) : Arc(i) { }
2.408 +
2.409 + OutArcIt(const Digraph& _graph, const Node& node)
2.410 + : digraph(&_graph) {
2.411 + _graph.firstOut(*this, node);
2.412 + }
2.413 +
2.414 + OutArcIt(const Digraph& _graph, const Arc& arc)
2.415 + : Arc(arc), digraph(&_graph) {}
2.416 +
2.417 + OutArcIt& operator++() {
2.418 + digraph->nextOut(*this);
2.419 + return *this;
2.420 + }
2.421 +
2.422 + };
2.423 +
2.424 +
2.425 + class InArcIt : public Arc {
2.426 + const Digraph* digraph;
2.427 + public:
2.428 +
2.429 + InArcIt() { }
2.430 +
2.431 + InArcIt(Invalid i) : Arc(i) { }
2.432 +
2.433 + InArcIt(const Digraph& _graph, const Node& node)
2.434 + : digraph(&_graph) {
2.435 + _graph.firstIn(*this, node);
2.436 + }
2.437 +
2.438 + InArcIt(const Digraph& _graph, const Arc& arc) :
2.439 + Arc(arc), digraph(&_graph) {}
2.440 +
2.441 + InArcIt& operator++() {
2.442 + digraph->nextIn(*this);
2.443 + return *this;
2.444 + }
2.445 +
2.446 + };
2.447 +
2.448 +
2.449 + class EdgeIt : public Parent::Edge {
2.450 + const Digraph* digraph;
2.451 + public:
2.452 +
2.453 + EdgeIt() { }
2.454 +
2.455 + EdgeIt(Invalid i) : Edge(i) { }
2.456 +
2.457 + explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
2.458 + _graph.first(static_cast<Edge&>(*this));
2.459 + }
2.460 +
2.461 + EdgeIt(const Digraph& _graph, const Edge& e) :
2.462 + Edge(e), digraph(&_graph) { }
2.463 +
2.464 + EdgeIt& operator++() {
2.465 + digraph->next(*this);
2.466 + return *this;
2.467 + }
2.468 +
2.469 + };
2.470 +
2.471 + class IncEdgeIt : public Parent::Edge {
2.472 + friend class EdgeSetExtender;
2.473 + const Digraph* digraph;
2.474 + bool direction;
2.475 + public:
2.476 +
2.477 + IncEdgeIt() { }
2.478 +
2.479 + IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
2.480 +
2.481 + IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
2.482 + _graph.firstInc(*this, direction, n);
2.483 + }
2.484 +
2.485 + IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
2.486 + : digraph(&_graph), Edge(ue) {
2.487 + direction = (_graph.source(ue) == n);
2.488 + }
2.489 +
2.490 + IncEdgeIt& operator++() {
2.491 + digraph->nextInc(*this, direction);
2.492 + return *this;
2.493 + }
2.494 + };
2.495 +
2.496 + /// \brief Base node of the iterator
2.497 + ///
2.498 + /// Returns the base node (ie. the source in this case) of the iterator
2.499 + Node baseNode(const OutArcIt &e) const {
2.500 + return Parent::source(static_cast<const Arc&>(e));
2.501 + }
2.502 + /// \brief Running node of the iterator
2.503 + ///
2.504 + /// Returns the running node (ie. the target in this case) of the
2.505 + /// iterator
2.506 + Node runningNode(const OutArcIt &e) const {
2.507 + return Parent::target(static_cast<const Arc&>(e));
2.508 + }
2.509 +
2.510 + /// \brief Base node of the iterator
2.511 + ///
2.512 + /// Returns the base node (ie. the target in this case) of the iterator
2.513 + Node baseNode(const InArcIt &e) const {
2.514 + return Parent::target(static_cast<const Arc&>(e));
2.515 + }
2.516 + /// \brief Running node of the iterator
2.517 + ///
2.518 + /// Returns the running node (ie. the source in this case) of the
2.519 + /// iterator
2.520 + Node runningNode(const InArcIt &e) const {
2.521 + return Parent::source(static_cast<const Arc&>(e));
2.522 + }
2.523 +
2.524 + /// Base node of the iterator
2.525 + ///
2.526 + /// Returns the base node of the iterator
2.527 + Node baseNode(const IncEdgeIt &e) const {
2.528 + return e.direction ? u(e) : v(e);
2.529 + }
2.530 + /// Running node of the iterator
2.531 + ///
2.532 + /// Returns the running node of the iterator
2.533 + Node runningNode(const IncEdgeIt &e) const {
2.534 + return e.direction ? v(e) : u(e);
2.535 + }
2.536 +
2.537 +
2.538 + template <typename _Value>
2.539 + class ArcMap
2.540 + : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
2.541 + public:
2.542 + typedef EdgeSetExtender Digraph;
2.543 + typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
2.544 +
2.545 + ArcMap(const Digraph& _g)
2.546 + : Parent(_g) {}
2.547 + ArcMap(const Digraph& _g, const _Value& _v)
2.548 + : Parent(_g, _v) {}
2.549 +
2.550 + ArcMap& operator=(const ArcMap& cmap) {
2.551 + return operator=<ArcMap>(cmap);
2.552 + }
2.553 +
2.554 + template <typename CMap>
2.555 + ArcMap& operator=(const CMap& cmap) {
2.556 + Parent::operator=(cmap);
2.557 + return *this;
2.558 + }
2.559 +
2.560 + };
2.561 +
2.562 +
2.563 + template <typename _Value>
2.564 + class EdgeMap
2.565 + : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
2.566 + public:
2.567 + typedef EdgeSetExtender Digraph;
2.568 + typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
2.569 +
2.570 + EdgeMap(const Digraph& _g)
2.571 + : Parent(_g) {}
2.572 +
2.573 + EdgeMap(const Digraph& _g, const _Value& _v)
2.574 + : Parent(_g, _v) {}
2.575 +
2.576 + EdgeMap& operator=(const EdgeMap& cmap) {
2.577 + return operator=<EdgeMap>(cmap);
2.578 + }
2.579 +
2.580 + template <typename CMap>
2.581 + EdgeMap& operator=(const CMap& cmap) {
2.582 + Parent::operator=(cmap);
2.583 + return *this;
2.584 + }
2.585 +
2.586 + };
2.587 +
2.588 +
2.589 + // Alteration extension
2.590 +
2.591 + Edge addEdge(const Node& from, const Node& to) {
2.592 + Edge edge = Parent::addEdge(from, to);
2.593 + notifier(Edge()).add(edge);
2.594 + std::vector<Arc> arcs;
2.595 + arcs.push_back(Parent::direct(edge, true));
2.596 + arcs.push_back(Parent::direct(edge, false));
2.597 + notifier(Arc()).add(arcs);
2.598 + return edge;
2.599 + }
2.600 +
2.601 + void clear() {
2.602 + notifier(Arc()).clear();
2.603 + notifier(Edge()).clear();
2.604 + Parent::clear();
2.605 + }
2.606 +
2.607 + void erase(const Edge& edge) {
2.608 + std::vector<Arc> arcs;
2.609 + arcs.push_back(Parent::direct(edge, true));
2.610 + arcs.push_back(Parent::direct(edge, false));
2.611 + notifier(Arc()).erase(arcs);
2.612 + notifier(Edge()).erase(edge);
2.613 + Parent::erase(edge);
2.614 + }
2.615 +
2.616 +
2.617 + EdgeSetExtender() {
2.618 + arc_notifier.setContainer(*this);
2.619 + edge_notifier.setContainer(*this);
2.620 + }
2.621 +
2.622 + ~EdgeSetExtender() {
2.623 + edge_notifier.clear();
2.624 + arc_notifier.clear();
2.625 + }
2.626 +
2.627 + };
2.628 +
2.629 +}
2.630 +
2.631 +#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/edge_set.h Mon Jan 12 13:37:37 2009 +0000
3.3 @@ -0,0 +1,1410 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2008
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#ifndef LEMON_EDGE_SET_H
3.23 +#define LEMON_EDGE_SET_H
3.24 +
3.25 +#include <lemon/core.h>
3.26 +#include <lemon/bits/edge_set_extender.h>
3.27 +
3.28 +/// \ingroup semi_adaptors
3.29 +/// \file
3.30 +/// \brief ArcSet and EdgeSet classes.
3.31 +///
3.32 +/// Graphs which use another graph's node-set as own.
3.33 +namespace lemon {
3.34 +
3.35 + template <typename _Graph>
3.36 + class ListArcSetBase {
3.37 + public:
3.38 +
3.39 + typedef _Graph Graph;
3.40 + typedef typename Graph::Node Node;
3.41 + typedef typename Graph::NodeIt NodeIt;
3.42 +
3.43 + protected:
3.44 +
3.45 + struct NodeT {
3.46 + int first_out, first_in;
3.47 + NodeT() : first_out(-1), first_in(-1) {}
3.48 + };
3.49 +
3.50 + typedef typename ItemSetTraits<Graph, Node>::
3.51 + template Map<NodeT>::Type NodesImplBase;
3.52 +
3.53 + NodesImplBase* nodes;
3.54 +
3.55 + struct ArcT {
3.56 + Node source, target;
3.57 + int next_out, next_in;
3.58 + int prev_out, prev_in;
3.59 + ArcT() : prev_out(-1), prev_in(-1) {}
3.60 + };
3.61 +
3.62 + std::vector<ArcT> arcs;
3.63 +
3.64 + int first_arc;
3.65 + int first_free_arc;
3.66 +
3.67 + const Graph* graph;
3.68 +
3.69 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
3.70 + graph = &_graph;
3.71 + nodes = &_nodes;
3.72 + }
3.73 +
3.74 + public:
3.75 +
3.76 + class Arc {
3.77 + friend class ListArcSetBase<Graph>;
3.78 + protected:
3.79 + Arc(int _id) : id(_id) {}
3.80 + int id;
3.81 + public:
3.82 + Arc() {}
3.83 + Arc(Invalid) : id(-1) {}
3.84 + bool operator==(const Arc& arc) const { return id == arc.id; }
3.85 + bool operator!=(const Arc& arc) const { return id != arc.id; }
3.86 + bool operator<(const Arc& arc) const { return id < arc.id; }
3.87 + };
3.88 +
3.89 + ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
3.90 +
3.91 + Arc addArc(const Node& u, const Node& v) {
3.92 + int n;
3.93 + if (first_free_arc == -1) {
3.94 + n = arcs.size();
3.95 + arcs.push_back(ArcT());
3.96 + } else {
3.97 + n = first_free_arc;
3.98 + first_free_arc = arcs[first_free_arc].next_in;
3.99 + }
3.100 + arcs[n].next_in = (*nodes)[v].first_in;
3.101 + if ((*nodes)[v].first_in != -1) {
3.102 + arcs[(*nodes)[v].first_in].prev_in = n;
3.103 + }
3.104 + (*nodes)[v].first_in = n;
3.105 + arcs[n].next_out = (*nodes)[u].first_out;
3.106 + if ((*nodes)[u].first_out != -1) {
3.107 + arcs[(*nodes)[u].first_out].prev_out = n;
3.108 + }
3.109 + (*nodes)[u].first_out = n;
3.110 + arcs[n].source = u;
3.111 + arcs[n].target = v;
3.112 + return Arc(n);
3.113 + }
3.114 +
3.115 + void erase(const Arc& arc) {
3.116 + int n = arc.id;
3.117 + if (arcs[n].prev_in != -1) {
3.118 + arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
3.119 + } else {
3.120 + (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
3.121 + }
3.122 + if (arcs[n].next_in != -1) {
3.123 + arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
3.124 + }
3.125 +
3.126 + if (arcs[n].prev_out != -1) {
3.127 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
3.128 + } else {
3.129 + (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
3.130 + }
3.131 + if (arcs[n].next_out != -1) {
3.132 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
3.133 + }
3.134 +
3.135 + }
3.136 +
3.137 + void clear() {
3.138 + Node node;
3.139 + for (first(node); node != INVALID; next(node)) {
3.140 + (*nodes)[node].first_in = -1;
3.141 + (*nodes)[node].first_out = -1;
3.142 + }
3.143 + arcs.clear();
3.144 + first_arc = -1;
3.145 + first_free_arc = -1;
3.146 + }
3.147 +
3.148 + void first(Node& node) const {
3.149 + graph->first(node);
3.150 + }
3.151 +
3.152 + void next(Node& node) const {
3.153 + graph->next(node);
3.154 + }
3.155 +
3.156 + void first(Arc& arc) const {
3.157 + Node node;
3.158 + first(node);
3.159 + while (node != INVALID && (*nodes)[node].first_in == -1) {
3.160 + next(node);
3.161 + }
3.162 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
3.163 + }
3.164 +
3.165 + void next(Arc& arc) const {
3.166 + if (arcs[arc.id].next_in != -1) {
3.167 + arc.id = arcs[arc.id].next_in;
3.168 + } else {
3.169 + Node node = arcs[arc.id].target;
3.170 + next(node);
3.171 + while (node != INVALID && (*nodes)[node].first_in == -1) {
3.172 + next(node);
3.173 + }
3.174 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
3.175 + }
3.176 + }
3.177 +
3.178 + void firstOut(Arc& arc, const Node& node) const {
3.179 + arc.id = (*nodes)[node].first_out;
3.180 + }
3.181 +
3.182 + void nextOut(Arc& arc) const {
3.183 + arc.id = arcs[arc.id].next_out;
3.184 + }
3.185 +
3.186 + void firstIn(Arc& arc, const Node& node) const {
3.187 + arc.id = (*nodes)[node].first_in;
3.188 + }
3.189 +
3.190 + void nextIn(Arc& arc) const {
3.191 + arc.id = arcs[arc.id].next_in;
3.192 + }
3.193 +
3.194 + int id(const Node& node) const { return graph->id(node); }
3.195 + int id(const Arc& arc) const { return arc.id; }
3.196 +
3.197 + Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
3.198 + Arc arcFromId(int ix) const { return Arc(ix); }
3.199 +
3.200 + int maxNodeId() const { return graph->maxNodeId(); };
3.201 + int maxArcId() const { return arcs.size() - 1; }
3.202 +
3.203 + Node source(const Arc& arc) const { return arcs[arc.id].source;}
3.204 + Node target(const Arc& arc) const { return arcs[arc.id].target;}
3.205 +
3.206 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
3.207 +
3.208 + NodeNotifier& notifier(Node) const {
3.209 + return graph->notifier(Node());
3.210 + }
3.211 +
3.212 + template <typename _Value>
3.213 + class NodeMap : public Graph::template NodeMap<_Value> {
3.214 + public:
3.215 +
3.216 + typedef typename _Graph::template NodeMap<_Value> Parent;
3.217 +
3.218 + explicit NodeMap(const ListArcSetBase<Graph>& arcset)
3.219 + : Parent(*arcset.graph) {}
3.220 +
3.221 + NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
3.222 + : Parent(*arcset.graph, value) {}
3.223 +
3.224 + NodeMap& operator=(const NodeMap& cmap) {
3.225 + return operator=<NodeMap>(cmap);
3.226 + }
3.227 +
3.228 + template <typename CMap>
3.229 + NodeMap& operator=(const CMap& cmap) {
3.230 + Parent::operator=(cmap);
3.231 + return *this;
3.232 + }
3.233 + };
3.234 +
3.235 + };
3.236 +
3.237 + /// \ingroup semi_adaptors
3.238 + ///
3.239 + /// \brief Digraph using a node set of another digraph or graph and
3.240 + /// an own arc set.
3.241 + ///
3.242 + /// This structure can be used to establish another directed graph
3.243 + /// over a node set of an existing one. This class uses the same
3.244 + /// Node type as the underlying graph, and each valid node of the
3.245 + /// original graph is valid in this arc set, therefore the node
3.246 + /// objects of the original graph can be used directly with this
3.247 + /// class. The node handling functions (id handling, observing, and
3.248 + /// iterators) works equivalently as in the original graph.
3.249 + ///
3.250 + /// This implementation is based on doubly-linked lists, from each
3.251 + /// node the outgoing and the incoming arcs make up lists, therefore
3.252 + /// one arc can be erased in constant time. It also makes possible,
3.253 + /// that node can be removed from the underlying graph, in this case
3.254 + /// all arcs incident to the given node is erased from the arc set.
3.255 + ///
3.256 + /// \param _Graph The type of the graph which shares its node set with
3.257 + /// this class. Its interface must conform to the
3.258 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
3.259 + /// concept.
3.260 + ///
3.261 + /// This class is fully conform to the \ref concepts::Digraph
3.262 + /// "Digraph" concept.
3.263 + template <typename _Graph>
3.264 + class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
3.265 +
3.266 + public:
3.267 +
3.268 + typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
3.269 +
3.270 + typedef typename Parent::Node Node;
3.271 + typedef typename Parent::Arc Arc;
3.272 +
3.273 + typedef _Graph Graph;
3.274 +
3.275 +
3.276 + typedef typename Parent::NodesImplBase NodesImplBase;
3.277 +
3.278 + void eraseNode(const Node& node) {
3.279 + Arc arc;
3.280 + Parent::firstOut(arc, node);
3.281 + while (arc != INVALID ) {
3.282 + erase(arc);
3.283 + Parent::firstOut(arc, node);
3.284 + }
3.285 +
3.286 + Parent::firstIn(arc, node);
3.287 + while (arc != INVALID ) {
3.288 + erase(arc);
3.289 + Parent::firstIn(arc, node);
3.290 + }
3.291 + }
3.292 +
3.293 + void clearNodes() {
3.294 + Parent::clear();
3.295 + }
3.296 +
3.297 + class NodesImpl : public NodesImplBase {
3.298 + public:
3.299 + typedef NodesImplBase Parent;
3.300 +
3.301 + NodesImpl(const Graph& graph, ListArcSet& arcset)
3.302 + : Parent(graph), _arcset(arcset) {}
3.303 +
3.304 + virtual ~NodesImpl() {}
3.305 +
3.306 + protected:
3.307 +
3.308 + virtual void erase(const Node& node) {
3.309 + _arcset.eraseNode(node);
3.310 + Parent::erase(node);
3.311 + }
3.312 + virtual void erase(const std::vector<Node>& nodes) {
3.313 + for (int i = 0; i < int(nodes.size()); ++i) {
3.314 + _arcset.eraseNode(nodes[i]);
3.315 + }
3.316 + Parent::erase(nodes);
3.317 + }
3.318 + virtual void clear() {
3.319 + _arcset.clearNodes();
3.320 + Parent::clear();
3.321 + }
3.322 +
3.323 + private:
3.324 + ListArcSet& _arcset;
3.325 + };
3.326 +
3.327 + NodesImpl nodes;
3.328 +
3.329 + public:
3.330 +
3.331 + /// \brief Constructor of the ArcSet.
3.332 + ///
3.333 + /// Constructor of the ArcSet.
3.334 + ListArcSet(const Graph& graph) : nodes(graph, *this) {
3.335 + Parent::initalize(graph, nodes);
3.336 + }
3.337 +
3.338 + /// \brief Add a new arc to the digraph.
3.339 + ///
3.340 + /// Add a new arc to the digraph with source node \c s
3.341 + /// and target node \c t.
3.342 + /// \return the new arc.
3.343 + Arc addArc(const Node& s, const Node& t) {
3.344 + return Parent::addArc(s, t);
3.345 + }
3.346 +
3.347 + /// \brief Erase an arc from the digraph.
3.348 + ///
3.349 + /// Erase an arc \c a from the digraph.
3.350 + void erase(const Arc& a) {
3.351 + return Parent::erase(a);
3.352 + }
3.353 +
3.354 + };
3.355 +
3.356 + template <typename _Graph>
3.357 + class ListEdgeSetBase {
3.358 + public:
3.359 +
3.360 + typedef _Graph Graph;
3.361 + typedef typename Graph::Node Node;
3.362 + typedef typename Graph::NodeIt NodeIt;
3.363 +
3.364 + protected:
3.365 +
3.366 + struct NodeT {
3.367 + int first_out;
3.368 + NodeT() : first_out(-1) {}
3.369 + };
3.370 +
3.371 + typedef typename ItemSetTraits<Graph, Node>::
3.372 + template Map<NodeT>::Type NodesImplBase;
3.373 +
3.374 + NodesImplBase* nodes;
3.375 +
3.376 + struct ArcT {
3.377 + Node target;
3.378 + int prev_out, next_out;
3.379 + ArcT() : prev_out(-1), next_out(-1) {}
3.380 + };
3.381 +
3.382 + std::vector<ArcT> arcs;
3.383 +
3.384 + int first_arc;
3.385 + int first_free_arc;
3.386 +
3.387 + const Graph* graph;
3.388 +
3.389 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
3.390 + graph = &_graph;
3.391 + nodes = &_nodes;
3.392 + }
3.393 +
3.394 + public:
3.395 +
3.396 + class Edge {
3.397 + friend class ListEdgeSetBase;
3.398 + protected:
3.399 +
3.400 + int id;
3.401 + explicit Edge(int _id) { id = _id;}
3.402 +
3.403 + public:
3.404 + Edge() {}
3.405 + Edge (Invalid) { id = -1; }
3.406 + bool operator==(const Edge& arc) const {return id == arc.id;}
3.407 + bool operator!=(const Edge& arc) const {return id != arc.id;}
3.408 + bool operator<(const Edge& arc) const {return id < arc.id;}
3.409 + };
3.410 +
3.411 + class Arc {
3.412 + friend class ListEdgeSetBase;
3.413 + protected:
3.414 + Arc(int _id) : id(_id) {}
3.415 + int id;
3.416 + public:
3.417 + operator Edge() const { return edgeFromId(id / 2); }
3.418 +
3.419 + Arc() {}
3.420 + Arc(Invalid) : id(-1) {}
3.421 + bool operator==(const Arc& arc) const { return id == arc.id; }
3.422 + bool operator!=(const Arc& arc) const { return id != arc.id; }
3.423 + bool operator<(const Arc& arc) const { return id < arc.id; }
3.424 + };
3.425 +
3.426 + ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
3.427 +
3.428 + Edge addEdge(const Node& u, const Node& v) {
3.429 + int n;
3.430 +
3.431 + if (first_free_arc == -1) {
3.432 + n = arcs.size();
3.433 + arcs.push_back(ArcT());
3.434 + arcs.push_back(ArcT());
3.435 + } else {
3.436 + n = first_free_arc;
3.437 + first_free_arc = arcs[n].next_out;
3.438 + }
3.439 +
3.440 + arcs[n].target = u;
3.441 + arcs[n | 1].target = v;
3.442 +
3.443 + arcs[n].next_out = (*nodes)[v].first_out;
3.444 + if ((*nodes)[v].first_out != -1) {
3.445 + arcs[(*nodes)[v].first_out].prev_out = n;
3.446 + }
3.447 + (*nodes)[v].first_out = n;
3.448 + arcs[n].prev_out = -1;
3.449 +
3.450 + if ((*nodes)[u].first_out != -1) {
3.451 + arcs[(*nodes)[u].first_out].prev_out = (n | 1);
3.452 + }
3.453 + arcs[n | 1].next_out = (*nodes)[u].first_out;
3.454 + (*nodes)[u].first_out = (n | 1);
3.455 + arcs[n | 1].prev_out = -1;
3.456 +
3.457 + return Edge(n / 2);
3.458 + }
3.459 +
3.460 + void erase(const Edge& arc) {
3.461 + int n = arc.id * 2;
3.462 +
3.463 + if (arcs[n].next_out != -1) {
3.464 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
3.465 + }
3.466 +
3.467 + if (arcs[n].prev_out != -1) {
3.468 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
3.469 + } else {
3.470 + (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
3.471 + }
3.472 +
3.473 + if (arcs[n | 1].next_out != -1) {
3.474 + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
3.475 + }
3.476 +
3.477 + if (arcs[n | 1].prev_out != -1) {
3.478 + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
3.479 + } else {
3.480 + (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
3.481 + }
3.482 +
3.483 + arcs[n].next_out = first_free_arc;
3.484 + first_free_arc = n;
3.485 +
3.486 + }
3.487 +
3.488 + void clear() {
3.489 + Node node;
3.490 + for (first(node); node != INVALID; next(node)) {
3.491 + (*nodes)[node].first_out = -1;
3.492 + }
3.493 + arcs.clear();
3.494 + first_arc = -1;
3.495 + first_free_arc = -1;
3.496 + }
3.497 +
3.498 + void first(Node& node) const {
3.499 + graph->first(node);
3.500 + }
3.501 +
3.502 + void next(Node& node) const {
3.503 + graph->next(node);
3.504 + }
3.505 +
3.506 + void first(Arc& arc) const {
3.507 + Node node;
3.508 + first(node);
3.509 + while (node != INVALID && (*nodes)[node].first_out == -1) {
3.510 + next(node);
3.511 + }
3.512 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
3.513 + }
3.514 +
3.515 + void next(Arc& arc) const {
3.516 + if (arcs[arc.id].next_out != -1) {
3.517 + arc.id = arcs[arc.id].next_out;
3.518 + } else {
3.519 + Node node = arcs[arc.id ^ 1].target;
3.520 + next(node);
3.521 + while(node != INVALID && (*nodes)[node].first_out == -1) {
3.522 + next(node);
3.523 + }
3.524 + arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
3.525 + }
3.526 + }
3.527 +
3.528 + void first(Edge& edge) const {
3.529 + Node node;
3.530 + first(node);
3.531 + while (node != INVALID) {
3.532 + edge.id = (*nodes)[node].first_out;
3.533 + while ((edge.id & 1) != 1) {
3.534 + edge.id = arcs[edge.id].next_out;
3.535 + }
3.536 + if (edge.id != -1) {
3.537 + edge.id /= 2;
3.538 + return;
3.539 + }
3.540 + next(node);
3.541 + }
3.542 + edge.id = -1;
3.543 + }
3.544 +
3.545 + void next(Edge& edge) const {
3.546 + Node node = arcs[edge.id * 2].target;
3.547 + edge.id = arcs[(edge.id * 2) | 1].next_out;
3.548 + while ((edge.id & 1) != 1) {
3.549 + edge.id = arcs[edge.id].next_out;
3.550 + }
3.551 + if (edge.id != -1) {
3.552 + edge.id /= 2;
3.553 + return;
3.554 + }
3.555 + next(node);
3.556 + while (node != INVALID) {
3.557 + edge.id = (*nodes)[node].first_out;
3.558 + while ((edge.id & 1) != 1) {
3.559 + edge.id = arcs[edge.id].next_out;
3.560 + }
3.561 + if (edge.id != -1) {
3.562 + edge.id /= 2;
3.563 + return;
3.564 + }
3.565 + next(node);
3.566 + }
3.567 + edge.id = -1;
3.568 + }
3.569 +
3.570 + void firstOut(Arc& arc, const Node& node) const {
3.571 + arc.id = (*nodes)[node].first_out;
3.572 + }
3.573 +
3.574 + void nextOut(Arc& arc) const {
3.575 + arc.id = arcs[arc.id].next_out;
3.576 + }
3.577 +
3.578 + void firstIn(Arc& arc, const Node& node) const {
3.579 + arc.id = (((*nodes)[node].first_out) ^ 1);
3.580 + if (arc.id == -2) arc.id = -1;
3.581 + }
3.582 +
3.583 + void nextIn(Arc& arc) const {
3.584 + arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
3.585 + if (arc.id == -2) arc.id = -1;
3.586 + }
3.587 +
3.588 + void firstInc(Edge &arc, bool& dir, const Node& node) const {
3.589 + int de = (*nodes)[node].first_out;
3.590 + if (de != -1 ) {
3.591 + arc.id = de / 2;
3.592 + dir = ((de & 1) == 1);
3.593 + } else {
3.594 + arc.id = -1;
3.595 + dir = true;
3.596 + }
3.597 + }
3.598 + void nextInc(Edge &arc, bool& dir) const {
3.599 + int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
3.600 + if (de != -1 ) {
3.601 + arc.id = de / 2;
3.602 + dir = ((de & 1) == 1);
3.603 + } else {
3.604 + arc.id = -1;
3.605 + dir = true;
3.606 + }
3.607 + }
3.608 +
3.609 + static bool direction(Arc arc) {
3.610 + return (arc.id & 1) == 1;
3.611 + }
3.612 +
3.613 + static Arc direct(Edge edge, bool dir) {
3.614 + return Arc(edge.id * 2 + (dir ? 1 : 0));
3.615 + }
3.616 +
3.617 + int id(const Node& node) const { return graph->id(node); }
3.618 + static int id(Arc e) { return e.id; }
3.619 + static int id(Edge e) { return e.id; }
3.620 +
3.621 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
3.622 + static Arc arcFromId(int id) { return Arc(id);}
3.623 + static Edge edgeFromId(int id) { return Edge(id);}
3.624 +
3.625 + int maxNodeId() const { return graph->maxNodeId(); };
3.626 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
3.627 + int maxArcId() const { return arcs.size()-1; }
3.628 +
3.629 + Node source(Arc e) const { return arcs[e.id ^ 1].target; }
3.630 + Node target(Arc e) const { return arcs[e.id].target; }
3.631 +
3.632 + Node u(Edge e) const { return arcs[2 * e.id].target; }
3.633 + Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
3.634 +
3.635 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
3.636 +
3.637 + NodeNotifier& notifier(Node) const {
3.638 + return graph->notifier(Node());
3.639 + }
3.640 +
3.641 + template <typename _Value>
3.642 + class NodeMap : public Graph::template NodeMap<_Value> {
3.643 + public:
3.644 +
3.645 + typedef typename _Graph::template NodeMap<_Value> Parent;
3.646 +
3.647 + explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
3.648 + : Parent(*arcset.graph) {}
3.649 +
3.650 + NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
3.651 + : Parent(*arcset.graph, value) {}
3.652 +
3.653 + NodeMap& operator=(const NodeMap& cmap) {
3.654 + return operator=<NodeMap>(cmap);
3.655 + }
3.656 +
3.657 + template <typename CMap>
3.658 + NodeMap& operator=(const CMap& cmap) {
3.659 + Parent::operator=(cmap);
3.660 + return *this;
3.661 + }
3.662 + };
3.663 +
3.664 + };
3.665 +
3.666 + /// \ingroup semi_adaptors
3.667 + ///
3.668 + /// \brief Graph using a node set of another digraph or graph and an
3.669 + /// own edge set.
3.670 + ///
3.671 + /// This structure can be used to establish another graph over a
3.672 + /// node set of an existing one. This class uses the same Node type
3.673 + /// as the underlying graph, and each valid node of the original
3.674 + /// graph is valid in this arc set, therefore the node objects of
3.675 + /// the original graph can be used directly with this class. The
3.676 + /// node handling functions (id handling, observing, and iterators)
3.677 + /// works equivalently as in the original graph.
3.678 + ///
3.679 + /// This implementation is based on doubly-linked lists, from each
3.680 + /// node the incident edges make up lists, therefore one edge can be
3.681 + /// erased in constant time. It also makes possible, that node can
3.682 + /// be removed from the underlying graph, in this case all edges
3.683 + /// incident to the given node is erased from the arc set.
3.684 + ///
3.685 + /// \param _Graph The type of the graph which shares its node set
3.686 + /// with this class. Its interface must conform to the
3.687 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
3.688 + /// concept.
3.689 + ///
3.690 + /// This class is fully conform to the \ref concepts::Graph "Graph"
3.691 + /// concept.
3.692 + template <typename _Graph>
3.693 + class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
3.694 +
3.695 + public:
3.696 +
3.697 + typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
3.698 +
3.699 + typedef typename Parent::Node Node;
3.700 + typedef typename Parent::Arc Arc;
3.701 + typedef typename Parent::Edge Edge;
3.702 +
3.703 + typedef _Graph Graph;
3.704 +
3.705 +
3.706 + typedef typename Parent::NodesImplBase NodesImplBase;
3.707 +
3.708 + void eraseNode(const Node& node) {
3.709 + Arc arc;
3.710 + Parent::firstOut(arc, node);
3.711 + while (arc != INVALID ) {
3.712 + erase(arc);
3.713 + Parent::firstOut(arc, node);
3.714 + }
3.715 +
3.716 + }
3.717 +
3.718 + void clearNodes() {
3.719 + Parent::clear();
3.720 + }
3.721 +
3.722 + class NodesImpl : public NodesImplBase {
3.723 + public:
3.724 + typedef NodesImplBase Parent;
3.725 +
3.726 + NodesImpl(const Graph& graph, ListEdgeSet& arcset)
3.727 + : Parent(graph), _arcset(arcset) {}
3.728 +
3.729 + virtual ~NodesImpl() {}
3.730 +
3.731 + protected:
3.732 +
3.733 + virtual void erase(const Node& node) {
3.734 + _arcset.eraseNode(node);
3.735 + Parent::erase(node);
3.736 + }
3.737 + virtual void erase(const std::vector<Node>& nodes) {
3.738 + for (int i = 0; i < int(nodes.size()); ++i) {
3.739 + _arcset.eraseNode(nodes[i]);
3.740 + }
3.741 + Parent::erase(nodes);
3.742 + }
3.743 + virtual void clear() {
3.744 + _arcset.clearNodes();
3.745 + Parent::clear();
3.746 + }
3.747 +
3.748 + private:
3.749 + ListEdgeSet& _arcset;
3.750 + };
3.751 +
3.752 + NodesImpl nodes;
3.753 +
3.754 + public:
3.755 +
3.756 + /// \brief Constructor of the EdgeSet.
3.757 + ///
3.758 + /// Constructor of the EdgeSet.
3.759 + ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
3.760 + Parent::initalize(graph, nodes);
3.761 + }
3.762 +
3.763 + /// \brief Add a new edge to the graph.
3.764 + ///
3.765 + /// Add a new edge to the graph with node \c u
3.766 + /// and node \c v endpoints.
3.767 + /// \return the new edge.
3.768 + Edge addEdge(const Node& u, const Node& v) {
3.769 + return Parent::addEdge(u, v);
3.770 + }
3.771 +
3.772 + /// \brief Erase an edge from the graph.
3.773 + ///
3.774 + /// Erase the edge \c e from the graph.
3.775 + void erase(const Edge& e) {
3.776 + return Parent::erase(e);
3.777 + }
3.778 +
3.779 + };
3.780 +
3.781 + template <typename _Graph>
3.782 + class SmartArcSetBase {
3.783 + public:
3.784 +
3.785 + typedef _Graph Graph;
3.786 + typedef typename Graph::Node Node;
3.787 + typedef typename Graph::NodeIt NodeIt;
3.788 +
3.789 + protected:
3.790 +
3.791 + struct NodeT {
3.792 + int first_out, first_in;
3.793 + NodeT() : first_out(-1), first_in(-1) {}
3.794 + };
3.795 +
3.796 + typedef typename ItemSetTraits<Graph, Node>::
3.797 + template Map<NodeT>::Type NodesImplBase;
3.798 +
3.799 + NodesImplBase* nodes;
3.800 +
3.801 + struct ArcT {
3.802 + Node source, target;
3.803 + int next_out, next_in;
3.804 + ArcT() {}
3.805 + };
3.806 +
3.807 + std::vector<ArcT> arcs;
3.808 +
3.809 + const Graph* graph;
3.810 +
3.811 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
3.812 + graph = &_graph;
3.813 + nodes = &_nodes;
3.814 + }
3.815 +
3.816 + public:
3.817 +
3.818 + class Arc {
3.819 + friend class SmartArcSetBase<Graph>;
3.820 + protected:
3.821 + Arc(int _id) : id(_id) {}
3.822 + int id;
3.823 + public:
3.824 + Arc() {}
3.825 + Arc(Invalid) : id(-1) {}
3.826 + bool operator==(const Arc& arc) const { return id == arc.id; }
3.827 + bool operator!=(const Arc& arc) const { return id != arc.id; }
3.828 + bool operator<(const Arc& arc) const { return id < arc.id; }
3.829 + };
3.830 +
3.831 + SmartArcSetBase() {}
3.832 +
3.833 + Arc addArc(const Node& u, const Node& v) {
3.834 + int n = arcs.size();
3.835 + arcs.push_back(ArcT());
3.836 + arcs[n].next_in = (*nodes)[v].first_in;
3.837 + (*nodes)[v].first_in = n;
3.838 + arcs[n].next_out = (*nodes)[u].first_out;
3.839 + (*nodes)[u].first_out = n;
3.840 + arcs[n].source = u;
3.841 + arcs[n].target = v;
3.842 + return Arc(n);
3.843 + }
3.844 +
3.845 + void clear() {
3.846 + Node node;
3.847 + for (first(node); node != INVALID; next(node)) {
3.848 + (*nodes)[node].first_in = -1;
3.849 + (*nodes)[node].first_out = -1;
3.850 + }
3.851 + arcs.clear();
3.852 + }
3.853 +
3.854 + void first(Node& node) const {
3.855 + graph->first(node);
3.856 + }
3.857 +
3.858 + void next(Node& node) const {
3.859 + graph->next(node);
3.860 + }
3.861 +
3.862 + void first(Arc& arc) const {
3.863 + arc.id = arcs.size() - 1;
3.864 + }
3.865 +
3.866 + void next(Arc& arc) const {
3.867 + --arc.id;
3.868 + }
3.869 +
3.870 + void firstOut(Arc& arc, const Node& node) const {
3.871 + arc.id = (*nodes)[node].first_out;
3.872 + }
3.873 +
3.874 + void nextOut(Arc& arc) const {
3.875 + arc.id = arcs[arc.id].next_out;
3.876 + }
3.877 +
3.878 + void firstIn(Arc& arc, const Node& node) const {
3.879 + arc.id = (*nodes)[node].first_in;
3.880 + }
3.881 +
3.882 + void nextIn(Arc& arc) const {
3.883 + arc.id = arcs[arc.id].next_in;
3.884 + }
3.885 +
3.886 + int id(const Node& node) const { return graph->id(node); }
3.887 + int id(const Arc& arc) const { return arc.id; }
3.888 +
3.889 + Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
3.890 + Arc arcFromId(int ix) const { return Arc(ix); }
3.891 +
3.892 + int maxNodeId() const { return graph->maxNodeId(); };
3.893 + int maxArcId() const { return arcs.size() - 1; }
3.894 +
3.895 + Node source(const Arc& arc) const { return arcs[arc.id].source;}
3.896 + Node target(const Arc& arc) const { return arcs[arc.id].target;}
3.897 +
3.898 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
3.899 +
3.900 + NodeNotifier& notifier(Node) const {
3.901 + return graph->notifier(Node());
3.902 + }
3.903 +
3.904 + template <typename _Value>
3.905 + class NodeMap : public Graph::template NodeMap<_Value> {
3.906 + public:
3.907 +
3.908 + typedef typename _Graph::template NodeMap<_Value> Parent;
3.909 +
3.910 + explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
3.911 + : Parent(*arcset.graph) { }
3.912 +
3.913 + NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
3.914 + : Parent(*arcset.graph, value) { }
3.915 +
3.916 + NodeMap& operator=(const NodeMap& cmap) {
3.917 + return operator=<NodeMap>(cmap);
3.918 + }
3.919 +
3.920 + template <typename CMap>
3.921 + NodeMap& operator=(const CMap& cmap) {
3.922 + Parent::operator=(cmap);
3.923 + return *this;
3.924 + }
3.925 + };
3.926 +
3.927 + };
3.928 +
3.929 +
3.930 + /// \ingroup semi_adaptors
3.931 + ///
3.932 + /// \brief Digraph using a node set of another digraph or graph and
3.933 + /// an own arc set.
3.934 + ///
3.935 + /// This structure can be used to establish another directed graph
3.936 + /// over a node set of an existing one. This class uses the same
3.937 + /// Node type as the underlying graph, and each valid node of the
3.938 + /// original graph is valid in this arc set, therefore the node
3.939 + /// objects of the original graph can be used directly with this
3.940 + /// class. The node handling functions (id handling, observing, and
3.941 + /// iterators) works equivalently as in the original graph.
3.942 + ///
3.943 + /// \param _Graph The type of the graph which shares its node set with
3.944 + /// this class. Its interface must conform to the
3.945 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
3.946 + /// concept.
3.947 + ///
3.948 + /// This implementation is slightly faster than the \c ListArcSet,
3.949 + /// because it uses continuous storage for arcs and it uses just
3.950 + /// single-linked lists for enumerate outgoing and incoming
3.951 + /// arcs. Therefore the arcs cannot be erased from the arc sets.
3.952 + ///
3.953 + /// \warning If a node is erased from the underlying graph and this
3.954 + /// node is the source or target of one arc in the arc set, then
3.955 + /// the arc set is invalidated, and it cannot be used anymore. The
3.956 + /// validity can be checked with the \c valid() member function.
3.957 + ///
3.958 + /// This class is fully conform to the \ref concepts::Digraph
3.959 + /// "Digraph" concept.
3.960 + template <typename _Graph>
3.961 + class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
3.962 +
3.963 + public:
3.964 +
3.965 + typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
3.966 +
3.967 + typedef typename Parent::Node Node;
3.968 + typedef typename Parent::Arc Arc;
3.969 +
3.970 + typedef _Graph Graph;
3.971 +
3.972 + protected:
3.973 +
3.974 + typedef typename Parent::NodesImplBase NodesImplBase;
3.975 +
3.976 + void eraseNode(const Node& node) {
3.977 + if (typename Parent::InArcIt(*this, node) == INVALID &&
3.978 + typename Parent::OutArcIt(*this, node) == INVALID) {
3.979 + return;
3.980 + }
3.981 + throw typename NodesImplBase::Notifier::ImmediateDetach();
3.982 + }
3.983 +
3.984 + void clearNodes() {
3.985 + Parent::clear();
3.986 + }
3.987 +
3.988 + class NodesImpl : public NodesImplBase {
3.989 + public:
3.990 + typedef NodesImplBase Parent;
3.991 +
3.992 + NodesImpl(const Graph& graph, SmartArcSet& arcset)
3.993 + : Parent(graph), _arcset(arcset) {}
3.994 +
3.995 + virtual ~NodesImpl() {}
3.996 +
3.997 + bool attached() const {
3.998 + return Parent::attached();
3.999 + }
3.1000 +
3.1001 + protected:
3.1002 +
3.1003 + virtual void erase(const Node& node) {
3.1004 + try {
3.1005 + _arcset.eraseNode(node);
3.1006 + Parent::erase(node);
3.1007 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
3.1008 + Parent::clear();
3.1009 + throw;
3.1010 + }
3.1011 + }
3.1012 + virtual void erase(const std::vector<Node>& nodes) {
3.1013 + try {
3.1014 + for (int i = 0; i < int(nodes.size()); ++i) {
3.1015 + _arcset.eraseNode(nodes[i]);
3.1016 + }
3.1017 + Parent::erase(nodes);
3.1018 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
3.1019 + Parent::clear();
3.1020 + throw;
3.1021 + }
3.1022 + }
3.1023 + virtual void clear() {
3.1024 + _arcset.clearNodes();
3.1025 + Parent::clear();
3.1026 + }
3.1027 +
3.1028 + private:
3.1029 + SmartArcSet& _arcset;
3.1030 + };
3.1031 +
3.1032 + NodesImpl nodes;
3.1033 +
3.1034 + public:
3.1035 +
3.1036 + /// \brief Constructor of the ArcSet.
3.1037 + ///
3.1038 + /// Constructor of the ArcSet.
3.1039 + SmartArcSet(const Graph& graph) : nodes(graph, *this) {
3.1040 + Parent::initalize(graph, nodes);
3.1041 + }
3.1042 +
3.1043 + /// \brief Add a new arc to the digraph.
3.1044 + ///
3.1045 + /// Add a new arc to the digraph with source node \c s
3.1046 + /// and target node \c t.
3.1047 + /// \return the new arc.
3.1048 + Arc addArc(const Node& s, const Node& t) {
3.1049 + return Parent::addArc(s, t);
3.1050 + }
3.1051 +
3.1052 + /// \brief Validity check
3.1053 + ///
3.1054 + /// This functions gives back false if the ArcSet is
3.1055 + /// invalidated. It occurs when a node in the underlying graph is
3.1056 + /// erased and it is not isolated in the ArcSet.
3.1057 + bool valid() const {
3.1058 + return nodes.attached();
3.1059 + }
3.1060 +
3.1061 + };
3.1062 +
3.1063 +
3.1064 + template <typename _Graph>
3.1065 + class SmartEdgeSetBase {
3.1066 + public:
3.1067 +
3.1068 + typedef _Graph Graph;
3.1069 + typedef typename Graph::Node Node;
3.1070 + typedef typename Graph::NodeIt NodeIt;
3.1071 +
3.1072 + protected:
3.1073 +
3.1074 + struct NodeT {
3.1075 + int first_out;
3.1076 + NodeT() : first_out(-1) {}
3.1077 + };
3.1078 +
3.1079 + typedef typename ItemSetTraits<Graph, Node>::
3.1080 + template Map<NodeT>::Type NodesImplBase;
3.1081 +
3.1082 + NodesImplBase* nodes;
3.1083 +
3.1084 + struct ArcT {
3.1085 + Node target;
3.1086 + int next_out;
3.1087 + ArcT() {}
3.1088 + };
3.1089 +
3.1090 + std::vector<ArcT> arcs;
3.1091 +
3.1092 + const Graph* graph;
3.1093 +
3.1094 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
3.1095 + graph = &_graph;
3.1096 + nodes = &_nodes;
3.1097 + }
3.1098 +
3.1099 + public:
3.1100 +
3.1101 + class Edge {
3.1102 + friend class SmartEdgeSetBase;
3.1103 + protected:
3.1104 +
3.1105 + int id;
3.1106 + explicit Edge(int _id) { id = _id;}
3.1107 +
3.1108 + public:
3.1109 + Edge() {}
3.1110 + Edge (Invalid) { id = -1; }
3.1111 + bool operator==(const Edge& arc) const {return id == arc.id;}
3.1112 + bool operator!=(const Edge& arc) const {return id != arc.id;}
3.1113 + bool operator<(const Edge& arc) const {return id < arc.id;}
3.1114 + };
3.1115 +
3.1116 + class Arc {
3.1117 + friend class SmartEdgeSetBase;
3.1118 + protected:
3.1119 + Arc(int _id) : id(_id) {}
3.1120 + int id;
3.1121 + public:
3.1122 + operator Edge() const { return edgeFromId(id / 2); }
3.1123 +
3.1124 + Arc() {}
3.1125 + Arc(Invalid) : id(-1) {}
3.1126 + bool operator==(const Arc& arc) const { return id == arc.id; }
3.1127 + bool operator!=(const Arc& arc) const { return id != arc.id; }
3.1128 + bool operator<(const Arc& arc) const { return id < arc.id; }
3.1129 + };
3.1130 +
3.1131 + SmartEdgeSetBase() {}
3.1132 +
3.1133 + Edge addEdge(const Node& u, const Node& v) {
3.1134 + int n = arcs.size();
3.1135 + arcs.push_back(ArcT());
3.1136 + arcs.push_back(ArcT());
3.1137 +
3.1138 + arcs[n].target = u;
3.1139 + arcs[n | 1].target = v;
3.1140 +
3.1141 + arcs[n].next_out = (*nodes)[v].first_out;
3.1142 + (*nodes)[v].first_out = n;
3.1143 +
3.1144 + arcs[n | 1].next_out = (*nodes)[u].first_out;
3.1145 + (*nodes)[u].first_out = (n | 1);
3.1146 +
3.1147 + return Edge(n / 2);
3.1148 + }
3.1149 +
3.1150 + void clear() {
3.1151 + Node node;
3.1152 + for (first(node); node != INVALID; next(node)) {
3.1153 + (*nodes)[node].first_out = -1;
3.1154 + }
3.1155 + arcs.clear();
3.1156 + }
3.1157 +
3.1158 + void first(Node& node) const {
3.1159 + graph->first(node);
3.1160 + }
3.1161 +
3.1162 + void next(Node& node) const {
3.1163 + graph->next(node);
3.1164 + }
3.1165 +
3.1166 + void first(Arc& arc) const {
3.1167 + arc.id = arcs.size() - 1;
3.1168 + }
3.1169 +
3.1170 + void next(Arc& arc) const {
3.1171 + --arc.id;
3.1172 + }
3.1173 +
3.1174 + void first(Edge& arc) const {
3.1175 + arc.id = arcs.size() / 2 - 1;
3.1176 + }
3.1177 +
3.1178 + void next(Edge& arc) const {
3.1179 + --arc.id;
3.1180 + }
3.1181 +
3.1182 + void firstOut(Arc& arc, const Node& node) const {
3.1183 + arc.id = (*nodes)[node].first_out;
3.1184 + }
3.1185 +
3.1186 + void nextOut(Arc& arc) const {
3.1187 + arc.id = arcs[arc.id].next_out;
3.1188 + }
3.1189 +
3.1190 + void firstIn(Arc& arc, const Node& node) const {
3.1191 + arc.id = (((*nodes)[node].first_out) ^ 1);
3.1192 + if (arc.id == -2) arc.id = -1;
3.1193 + }
3.1194 +
3.1195 + void nextIn(Arc& arc) const {
3.1196 + arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
3.1197 + if (arc.id == -2) arc.id = -1;
3.1198 + }
3.1199 +
3.1200 + void firstInc(Edge &arc, bool& dir, const Node& node) const {
3.1201 + int de = (*nodes)[node].first_out;
3.1202 + if (de != -1 ) {
3.1203 + arc.id = de / 2;
3.1204 + dir = ((de & 1) == 1);
3.1205 + } else {
3.1206 + arc.id = -1;
3.1207 + dir = true;
3.1208 + }
3.1209 + }
3.1210 + void nextInc(Edge &arc, bool& dir) const {
3.1211 + int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
3.1212 + if (de != -1 ) {
3.1213 + arc.id = de / 2;
3.1214 + dir = ((de & 1) == 1);
3.1215 + } else {
3.1216 + arc.id = -1;
3.1217 + dir = true;
3.1218 + }
3.1219 + }
3.1220 +
3.1221 + static bool direction(Arc arc) {
3.1222 + return (arc.id & 1) == 1;
3.1223 + }
3.1224 +
3.1225 + static Arc direct(Edge edge, bool dir) {
3.1226 + return Arc(edge.id * 2 + (dir ? 1 : 0));
3.1227 + }
3.1228 +
3.1229 + int id(Node node) const { return graph->id(node); }
3.1230 + static int id(Arc arc) { return arc.id; }
3.1231 + static int id(Edge arc) { return arc.id; }
3.1232 +
3.1233 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
3.1234 + static Arc arcFromId(int id) { return Arc(id); }
3.1235 + static Edge edgeFromId(int id) { return Edge(id);}
3.1236 +
3.1237 + int maxNodeId() const { return graph->maxNodeId(); };
3.1238 + int maxArcId() const { return arcs.size() - 1; }
3.1239 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
3.1240 +
3.1241 + Node source(Arc e) const { return arcs[e.id ^ 1].target; }
3.1242 + Node target(Arc e) const { return arcs[e.id].target; }
3.1243 +
3.1244 + Node u(Edge e) const { return arcs[2 * e.id].target; }
3.1245 + Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
3.1246 +
3.1247 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
3.1248 +
3.1249 + NodeNotifier& notifier(Node) const {
3.1250 + return graph->notifier(Node());
3.1251 + }
3.1252 +
3.1253 + template <typename _Value>
3.1254 + class NodeMap : public Graph::template NodeMap<_Value> {
3.1255 + public:
3.1256 +
3.1257 + typedef typename _Graph::template NodeMap<_Value> Parent;
3.1258 +
3.1259 + explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
3.1260 + : Parent(*arcset.graph) { }
3.1261 +
3.1262 + NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
3.1263 + : Parent(*arcset.graph, value) { }
3.1264 +
3.1265 + NodeMap& operator=(const NodeMap& cmap) {
3.1266 + return operator=<NodeMap>(cmap);
3.1267 + }
3.1268 +
3.1269 + template <typename CMap>
3.1270 + NodeMap& operator=(const CMap& cmap) {
3.1271 + Parent::operator=(cmap);
3.1272 + return *this;
3.1273 + }
3.1274 + };
3.1275 +
3.1276 + };
3.1277 +
3.1278 + /// \ingroup semi_adaptors
3.1279 + ///
3.1280 + /// \brief Graph using a node set of another digraph or graph and an
3.1281 + /// own edge set.
3.1282 + ///
3.1283 + /// This structure can be used to establish another graph over a
3.1284 + /// node set of an existing one. This class uses the same Node type
3.1285 + /// as the underlying graph, and each valid node of the original
3.1286 + /// graph is valid in this arc set, therefore the node objects of
3.1287 + /// the original graph can be used directly with this class. The
3.1288 + /// node handling functions (id handling, observing, and iterators)
3.1289 + /// works equivalently as in the original graph.
3.1290 + ///
3.1291 + /// \param _Graph The type of the graph which shares its node set
3.1292 + /// with this class. Its interface must conform to the
3.1293 + /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
3.1294 + /// concept.
3.1295 + ///
3.1296 + /// This implementation is slightly faster than the \c ListEdgeSet,
3.1297 + /// because it uses continuous storage for edges and it uses just
3.1298 + /// single-linked lists for enumerate incident edges. Therefore the
3.1299 + /// edges cannot be erased from the edge sets.
3.1300 + ///
3.1301 + /// \warning If a node is erased from the underlying graph and this
3.1302 + /// node is incident to one edge in the edge set, then the edge set
3.1303 + /// is invalidated, and it cannot be used anymore. The validity can
3.1304 + /// be checked with the \c valid() member function.
3.1305 + ///
3.1306 + /// This class is fully conform to the \ref concepts::Graph
3.1307 + /// "Graph" concept.
3.1308 + template <typename _Graph>
3.1309 + class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
3.1310 +
3.1311 + public:
3.1312 +
3.1313 + typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
3.1314 +
3.1315 + typedef typename Parent::Node Node;
3.1316 + typedef typename Parent::Arc Arc;
3.1317 + typedef typename Parent::Edge Edge;
3.1318 +
3.1319 + typedef _Graph Graph;
3.1320 +
3.1321 + protected:
3.1322 +
3.1323 + typedef typename Parent::NodesImplBase NodesImplBase;
3.1324 +
3.1325 + void eraseNode(const Node& node) {
3.1326 + if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
3.1327 + return;
3.1328 + }
3.1329 + throw typename NodesImplBase::Notifier::ImmediateDetach();
3.1330 + }
3.1331 +
3.1332 + void clearNodes() {
3.1333 + Parent::clear();
3.1334 + }
3.1335 +
3.1336 + class NodesImpl : public NodesImplBase {
3.1337 + public:
3.1338 + typedef NodesImplBase Parent;
3.1339 +
3.1340 + NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
3.1341 + : Parent(graph), _arcset(arcset) {}
3.1342 +
3.1343 + virtual ~NodesImpl() {}
3.1344 +
3.1345 + bool attached() const {
3.1346 + return Parent::attached();
3.1347 + }
3.1348 +
3.1349 + protected:
3.1350 +
3.1351 + virtual void erase(const Node& node) {
3.1352 + try {
3.1353 + _arcset.eraseNode(node);
3.1354 + Parent::erase(node);
3.1355 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
3.1356 + Parent::clear();
3.1357 + throw;
3.1358 + }
3.1359 + }
3.1360 + virtual void erase(const std::vector<Node>& nodes) {
3.1361 + try {
3.1362 + for (int i = 0; i < int(nodes.size()); ++i) {
3.1363 + _arcset.eraseNode(nodes[i]);
3.1364 + }
3.1365 + Parent::erase(nodes);
3.1366 + } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
3.1367 + Parent::clear();
3.1368 + throw;
3.1369 + }
3.1370 + }
3.1371 + virtual void clear() {
3.1372 + _arcset.clearNodes();
3.1373 + Parent::clear();
3.1374 + }
3.1375 +
3.1376 + private:
3.1377 + SmartEdgeSet& _arcset;
3.1378 + };
3.1379 +
3.1380 + NodesImpl nodes;
3.1381 +
3.1382 + public:
3.1383 +
3.1384 + /// \brief Constructor of the EdgeSet.
3.1385 + ///
3.1386 + /// Constructor of the EdgeSet.
3.1387 + SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
3.1388 + Parent::initalize(graph, nodes);
3.1389 + }
3.1390 +
3.1391 + /// \brief Add a new edge to the graph.
3.1392 + ///
3.1393 + /// Add a new edge to the graph with node \c u
3.1394 + /// and node \c v endpoints.
3.1395 + /// \return the new edge.
3.1396 + Edge addEdge(const Node& u, const Node& v) {
3.1397 + return Parent::addEdge(u, v);
3.1398 + }
3.1399 +
3.1400 + /// \brief Validity check
3.1401 + ///
3.1402 + /// This functions gives back false if the EdgeSet is
3.1403 + /// invalidated. It occurs when a node in the underlying graph is
3.1404 + /// erased and it is not isolated in the EdgeSet.
3.1405 + bool valid() const {
3.1406 + return nodes.attached();
3.1407 + }
3.1408 +
3.1409 + };
3.1410 +
3.1411 +}
3.1412 +
3.1413 +#endif
4.1 --- a/test/CMakeLists.txt Mon Jan 12 13:18:03 2009 +0000
4.2 +++ b/test/CMakeLists.txt Mon Jan 12 13:37:37 2009 +0000
4.3 @@ -12,6 +12,7 @@
4.4 dijkstra_test
4.5 dim_test
4.6 error_test
4.7 + edge_set_test
4.8 graph_copy_test
4.9 graph_test
4.10 graph_utils_test
5.1 --- a/test/Makefile.am Mon Jan 12 13:18:03 2009 +0000
5.2 +++ b/test/Makefile.am Mon Jan 12 13:37:37 2009 +0000
5.3 @@ -14,6 +14,7 @@
5.4 test/digraph_test \
5.5 test/dijkstra_test \
5.6 test/dim_test \
5.7 + test/edge_set_test \
5.8 test/error_test \
5.9 test/graph_copy_test \
5.10 test/graph_test \
5.11 @@ -51,6 +52,7 @@
5.12 test_digraph_test_SOURCES = test/digraph_test.cc
5.13 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
5.14 test_dim_test_SOURCES = test/dim_test.cc
5.15 +test_edge_set_test_SOURCES = test/edge_set_test.cc
5.16 test_error_test_SOURCES = test/error_test.cc
5.17 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
5.18 test_graph_test_SOURCES = test/graph_test.cc
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/test/edge_set_test.cc Mon Jan 12 13:37:37 2009 +0000
6.3 @@ -0,0 +1,380 @@
6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library.
6.7 + *
6.8 + * Copyright (C) 2003-2008
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#include <iostream>
6.23 +#include <vector>
6.24 +
6.25 +#include <lemon/concepts/digraph.h>
6.26 +#include <lemon/concepts/graph.h>
6.27 +#include <lemon/concept_check.h>
6.28 +
6.29 +#include <lemon/list_graph.h>
6.30 +
6.31 +#include <lemon/edge_set.h>
6.32 +
6.33 +#include "graph_test.h"
6.34 +#include "test_tools.h"
6.35 +
6.36 +using namespace lemon;
6.37 +
6.38 +void checkSmartArcSet() {
6.39 + checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
6.40 +
6.41 + typedef ListDigraph Digraph;
6.42 + typedef SmartArcSet<Digraph> ArcSet;
6.43 +
6.44 + Digraph digraph;
6.45 + Digraph::Node
6.46 + n1 = digraph.addNode(),
6.47 + n2 = digraph.addNode();
6.48 +
6.49 + Digraph::Arc ga1 = digraph.addArc(n1, n2);
6.50 +
6.51 + ArcSet arc_set(digraph);
6.52 +
6.53 + Digraph::Arc ga2 = digraph.addArc(n2, n1);
6.54 +
6.55 + checkGraphNodeList(arc_set, 2);
6.56 + checkGraphArcList(arc_set, 0);
6.57 +
6.58 + Digraph::Node
6.59 + n3 = digraph.addNode();
6.60 + checkGraphNodeList(arc_set, 3);
6.61 + checkGraphArcList(arc_set, 0);
6.62 +
6.63 + ArcSet::Arc a1 = arc_set.addArc(n1, n2);
6.64 + check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
6.65 + checkGraphNodeList(arc_set, 3);
6.66 + checkGraphArcList(arc_set, 1);
6.67 +
6.68 + checkGraphOutArcList(arc_set, n1, 1);
6.69 + checkGraphOutArcList(arc_set, n2, 0);
6.70 + checkGraphOutArcList(arc_set, n3, 0);
6.71 +
6.72 + checkGraphInArcList(arc_set, n1, 0);
6.73 + checkGraphInArcList(arc_set, n2, 1);
6.74 + checkGraphInArcList(arc_set, n3, 0);
6.75 +
6.76 + checkGraphConArcList(arc_set, 1);
6.77 +
6.78 + ArcSet::Arc a2 = arc_set.addArc(n2, n1),
6.79 + a3 = arc_set.addArc(n2, n3),
6.80 + a4 = arc_set.addArc(n2, n3);
6.81 + checkGraphNodeList(arc_set, 3);
6.82 + checkGraphArcList(arc_set, 4);
6.83 +
6.84 + checkGraphOutArcList(arc_set, n1, 1);
6.85 + checkGraphOutArcList(arc_set, n2, 3);
6.86 + checkGraphOutArcList(arc_set, n3, 0);
6.87 +
6.88 + checkGraphInArcList(arc_set, n1, 1);
6.89 + checkGraphInArcList(arc_set, n2, 1);
6.90 + checkGraphInArcList(arc_set, n3, 2);
6.91 +
6.92 + checkGraphConArcList(arc_set, 4);
6.93 +
6.94 + checkNodeIds(arc_set);
6.95 + checkArcIds(arc_set);
6.96 + checkGraphNodeMap(arc_set);
6.97 + checkGraphArcMap(arc_set);
6.98 +
6.99 + check(arc_set.valid(), "Wrong validity");
6.100 + digraph.erase(n1);
6.101 + check(!arc_set.valid(), "Wrong validity");
6.102 +}
6.103 +
6.104 +void checkListArcSet() {
6.105 + checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
6.106 +
6.107 + typedef ListDigraph Digraph;
6.108 + typedef ListArcSet<Digraph> ArcSet;
6.109 +
6.110 + Digraph digraph;
6.111 + Digraph::Node
6.112 + n1 = digraph.addNode(),
6.113 + n2 = digraph.addNode();
6.114 +
6.115 + Digraph::Arc ga1 = digraph.addArc(n1, n2);
6.116 +
6.117 + ArcSet arc_set(digraph);
6.118 +
6.119 + Digraph::Arc ga2 = digraph.addArc(n2, n1);
6.120 +
6.121 + checkGraphNodeList(arc_set, 2);
6.122 + checkGraphArcList(arc_set, 0);
6.123 +
6.124 + Digraph::Node
6.125 + n3 = digraph.addNode();
6.126 + checkGraphNodeList(arc_set, 3);
6.127 + checkGraphArcList(arc_set, 0);
6.128 +
6.129 + ArcSet::Arc a1 = arc_set.addArc(n1, n2);
6.130 + check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
6.131 + checkGraphNodeList(arc_set, 3);
6.132 + checkGraphArcList(arc_set, 1);
6.133 +
6.134 + checkGraphOutArcList(arc_set, n1, 1);
6.135 + checkGraphOutArcList(arc_set, n2, 0);
6.136 + checkGraphOutArcList(arc_set, n3, 0);
6.137 +
6.138 + checkGraphInArcList(arc_set, n1, 0);
6.139 + checkGraphInArcList(arc_set, n2, 1);
6.140 + checkGraphInArcList(arc_set, n3, 0);
6.141 +
6.142 + checkGraphConArcList(arc_set, 1);
6.143 +
6.144 + ArcSet::Arc a2 = arc_set.addArc(n2, n1),
6.145 + a3 = arc_set.addArc(n2, n3),
6.146 + a4 = arc_set.addArc(n2, n3);
6.147 + checkGraphNodeList(arc_set, 3);
6.148 + checkGraphArcList(arc_set, 4);
6.149 +
6.150 + checkGraphOutArcList(arc_set, n1, 1);
6.151 + checkGraphOutArcList(arc_set, n2, 3);
6.152 + checkGraphOutArcList(arc_set, n3, 0);
6.153 +
6.154 + checkGraphInArcList(arc_set, n1, 1);
6.155 + checkGraphInArcList(arc_set, n2, 1);
6.156 + checkGraphInArcList(arc_set, n3, 2);
6.157 +
6.158 + checkGraphConArcList(arc_set, 4);
6.159 +
6.160 + checkNodeIds(arc_set);
6.161 + checkArcIds(arc_set);
6.162 + checkGraphNodeMap(arc_set);
6.163 + checkGraphArcMap(arc_set);
6.164 +
6.165 + digraph.erase(n1);
6.166 +
6.167 + checkGraphNodeList(arc_set, 2);
6.168 + checkGraphArcList(arc_set, 2);
6.169 +
6.170 + checkGraphOutArcList(arc_set, n2, 2);
6.171 + checkGraphOutArcList(arc_set, n3, 0);
6.172 +
6.173 + checkGraphInArcList(arc_set, n2, 0);
6.174 + checkGraphInArcList(arc_set, n3, 2);
6.175 +
6.176 + checkNodeIds(arc_set);
6.177 + checkArcIds(arc_set);
6.178 + checkGraphNodeMap(arc_set);
6.179 + checkGraphArcMap(arc_set);
6.180 +
6.181 + checkGraphConArcList(arc_set, 2);
6.182 +}
6.183 +
6.184 +void checkSmartEdgeSet() {
6.185 + checkConcept<concepts::Digraph, SmartEdgeSet<concepts::Digraph> >();
6.186 +
6.187 + typedef ListDigraph Digraph;
6.188 + typedef SmartEdgeSet<Digraph> EdgeSet;
6.189 +
6.190 + Digraph digraph;
6.191 + Digraph::Node
6.192 + n1 = digraph.addNode(),
6.193 + n2 = digraph.addNode();
6.194 +
6.195 + Digraph::Arc ga1 = digraph.addArc(n1, n2);
6.196 +
6.197 + EdgeSet edge_set(digraph);
6.198 +
6.199 + Digraph::Arc ga2 = digraph.addArc(n2, n1);
6.200 +
6.201 + checkGraphNodeList(edge_set, 2);
6.202 + checkGraphArcList(edge_set, 0);
6.203 + checkGraphEdgeList(edge_set, 0);
6.204 +
6.205 + Digraph::Node
6.206 + n3 = digraph.addNode();
6.207 + checkGraphNodeList(edge_set, 3);
6.208 + checkGraphArcList(edge_set, 0);
6.209 + checkGraphEdgeList(edge_set, 0);
6.210 +
6.211 + EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
6.212 + check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
6.213 + (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
6.214 + checkGraphNodeList(edge_set, 3);
6.215 + checkGraphArcList(edge_set, 2);
6.216 + checkGraphEdgeList(edge_set, 1);
6.217 +
6.218 + checkGraphOutArcList(edge_set, n1, 1);
6.219 + checkGraphOutArcList(edge_set, n2, 1);
6.220 + checkGraphOutArcList(edge_set, n3, 0);
6.221 +
6.222 + checkGraphInArcList(edge_set, n1, 1);
6.223 + checkGraphInArcList(edge_set, n2, 1);
6.224 + checkGraphInArcList(edge_set, n3, 0);
6.225 +
6.226 + checkGraphIncEdgeList(edge_set, n1, 1);
6.227 + checkGraphIncEdgeList(edge_set, n2, 1);
6.228 + checkGraphIncEdgeList(edge_set, n3, 0);
6.229 +
6.230 + checkGraphConEdgeList(edge_set, 1);
6.231 + checkGraphConArcList(edge_set, 2);
6.232 +
6.233 + EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
6.234 + e3 = edge_set.addEdge(n2, n3),
6.235 + e4 = edge_set.addEdge(n2, n3);
6.236 + checkGraphNodeList(edge_set, 3);
6.237 + checkGraphEdgeList(edge_set, 4);
6.238 +
6.239 + checkGraphOutArcList(edge_set, n1, 2);
6.240 + checkGraphOutArcList(edge_set, n2, 4);
6.241 + checkGraphOutArcList(edge_set, n3, 2);
6.242 +
6.243 + checkGraphInArcList(edge_set, n1, 2);
6.244 + checkGraphInArcList(edge_set, n2, 4);
6.245 + checkGraphInArcList(edge_set, n3, 2);
6.246 +
6.247 + checkGraphIncEdgeList(edge_set, n1, 2);
6.248 + checkGraphIncEdgeList(edge_set, n2, 4);
6.249 + checkGraphIncEdgeList(edge_set, n3, 2);
6.250 +
6.251 + checkGraphConEdgeList(edge_set, 4);
6.252 + checkGraphConArcList(edge_set, 8);
6.253 +
6.254 + checkArcDirections(edge_set);
6.255 +
6.256 + checkNodeIds(edge_set);
6.257 + checkArcIds(edge_set);
6.258 + checkEdgeIds(edge_set);
6.259 + checkGraphNodeMap(edge_set);
6.260 + checkGraphArcMap(edge_set);
6.261 + checkGraphEdgeMap(edge_set);
6.262 +
6.263 + check(edge_set.valid(), "Wrong validity");
6.264 + digraph.erase(n1);
6.265 + check(!edge_set.valid(), "Wrong validity");
6.266 +}
6.267 +
6.268 +void checkListEdgeSet() {
6.269 + checkConcept<concepts::Digraph, ListEdgeSet<concepts::Digraph> >();
6.270 +
6.271 + typedef ListDigraph Digraph;
6.272 + typedef ListEdgeSet<Digraph> EdgeSet;
6.273 +
6.274 + Digraph digraph;
6.275 + Digraph::Node
6.276 + n1 = digraph.addNode(),
6.277 + n2 = digraph.addNode();
6.278 +
6.279 + Digraph::Arc ga1 = digraph.addArc(n1, n2);
6.280 +
6.281 + EdgeSet edge_set(digraph);
6.282 +
6.283 + Digraph::Arc ga2 = digraph.addArc(n2, n1);
6.284 +
6.285 + checkGraphNodeList(edge_set, 2);
6.286 + checkGraphArcList(edge_set, 0);
6.287 + checkGraphEdgeList(edge_set, 0);
6.288 +
6.289 + Digraph::Node
6.290 + n3 = digraph.addNode();
6.291 + checkGraphNodeList(edge_set, 3);
6.292 + checkGraphArcList(edge_set, 0);
6.293 + checkGraphEdgeList(edge_set, 0);
6.294 +
6.295 + EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
6.296 + check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
6.297 + (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
6.298 + checkGraphNodeList(edge_set, 3);
6.299 + checkGraphArcList(edge_set, 2);
6.300 + checkGraphEdgeList(edge_set, 1);
6.301 +
6.302 + checkGraphOutArcList(edge_set, n1, 1);
6.303 + checkGraphOutArcList(edge_set, n2, 1);
6.304 + checkGraphOutArcList(edge_set, n3, 0);
6.305 +
6.306 + checkGraphInArcList(edge_set, n1, 1);
6.307 + checkGraphInArcList(edge_set, n2, 1);
6.308 + checkGraphInArcList(edge_set, n3, 0);
6.309 +
6.310 + checkGraphIncEdgeList(edge_set, n1, 1);
6.311 + checkGraphIncEdgeList(edge_set, n2, 1);
6.312 + checkGraphIncEdgeList(edge_set, n3, 0);
6.313 +
6.314 + checkGraphConEdgeList(edge_set, 1);
6.315 + checkGraphConArcList(edge_set, 2);
6.316 +
6.317 + EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
6.318 + e3 = edge_set.addEdge(n2, n3),
6.319 + e4 = edge_set.addEdge(n2, n3);
6.320 + checkGraphNodeList(edge_set, 3);
6.321 + checkGraphEdgeList(edge_set, 4);
6.322 +
6.323 + checkGraphOutArcList(edge_set, n1, 2);
6.324 + checkGraphOutArcList(edge_set, n2, 4);
6.325 + checkGraphOutArcList(edge_set, n3, 2);
6.326 +
6.327 + checkGraphInArcList(edge_set, n1, 2);
6.328 + checkGraphInArcList(edge_set, n2, 4);
6.329 + checkGraphInArcList(edge_set, n3, 2);
6.330 +
6.331 + checkGraphIncEdgeList(edge_set, n1, 2);
6.332 + checkGraphIncEdgeList(edge_set, n2, 4);
6.333 + checkGraphIncEdgeList(edge_set, n3, 2);
6.334 +
6.335 + checkGraphConEdgeList(edge_set, 4);
6.336 + checkGraphConArcList(edge_set, 8);
6.337 +
6.338 + checkArcDirections(edge_set);
6.339 +
6.340 + checkNodeIds(edge_set);
6.341 + checkArcIds(edge_set);
6.342 + checkEdgeIds(edge_set);
6.343 + checkGraphNodeMap(edge_set);
6.344 + checkGraphArcMap(edge_set);
6.345 + checkGraphEdgeMap(edge_set);
6.346 +
6.347 + digraph.erase(n1);
6.348 +
6.349 + checkGraphNodeList(edge_set, 2);
6.350 + checkGraphArcList(edge_set, 4);
6.351 + checkGraphEdgeList(edge_set, 2);
6.352 +
6.353 + checkGraphOutArcList(edge_set, n2, 2);
6.354 + checkGraphOutArcList(edge_set, n3, 2);
6.355 +
6.356 + checkGraphInArcList(edge_set, n2, 2);
6.357 + checkGraphInArcList(edge_set, n3, 2);
6.358 +
6.359 + checkGraphIncEdgeList(edge_set, n2, 2);
6.360 + checkGraphIncEdgeList(edge_set, n3, 2);
6.361 +
6.362 + checkNodeIds(edge_set);
6.363 + checkArcIds(edge_set);
6.364 + checkEdgeIds(edge_set);
6.365 + checkGraphNodeMap(edge_set);
6.366 + checkGraphArcMap(edge_set);
6.367 + checkGraphEdgeMap(edge_set);
6.368 +
6.369 + checkGraphConEdgeList(edge_set, 2);
6.370 + checkGraphConArcList(edge_set, 4);
6.371 +
6.372 +}
6.373 +
6.374 +
6.375 +int main() {
6.376 +
6.377 + checkSmartArcSet();
6.378 + checkListArcSet();
6.379 + checkSmartEdgeSet();
6.380 + checkListEdgeSet();
6.381 +
6.382 + return 0;
6.383 +}