1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/edge_set_extender.h Mon Jan 12 13:37:37 2009 +0000
1.3 @@ -0,0 +1,628 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-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_BITS_EDGE_SET_EXTENDER_H
1.23 +#define LEMON_BITS_EDGE_SET_EXTENDER_H
1.24 +
1.25 +#include <lemon/error.h>
1.26 +#include <lemon/bits/default_map.h>
1.27 +
1.28 +///\ingroup digraphbits
1.29 +///\file
1.30 +///\brief Extenders for the arc set types
1.31 +namespace lemon {
1.32 +
1.33 + /// \ingroup digraphbits
1.34 + ///
1.35 + /// \brief Extender for the ArcSets
1.36 + template <typename Base>
1.37 + class ArcSetExtender : public Base {
1.38 + public:
1.39 +
1.40 + typedef Base Parent;
1.41 + typedef ArcSetExtender Digraph;
1.42 +
1.43 + // Base extensions
1.44 +
1.45 + typedef typename Parent::Node Node;
1.46 + typedef typename Parent::Arc Arc;
1.47 +
1.48 + int maxId(Node) const {
1.49 + return Parent::maxNodeId();
1.50 + }
1.51 +
1.52 + int maxId(Arc) const {
1.53 + return Parent::maxArcId();
1.54 + }
1.55 +
1.56 + Node fromId(int id, Node) const {
1.57 + return Parent::nodeFromId(id);
1.58 + }
1.59 +
1.60 + Arc fromId(int id, Arc) const {
1.61 + return Parent::arcFromId(id);
1.62 + }
1.63 +
1.64 + Node oppositeNode(const Node &n, const Arc &e) const {
1.65 + if (n == Parent::source(e))
1.66 + return Parent::target(e);
1.67 + else if(n==Parent::target(e))
1.68 + return Parent::source(e);
1.69 + else
1.70 + return INVALID;
1.71 + }
1.72 +
1.73 +
1.74 + // Alteration notifier extensions
1.75 +
1.76 + /// The arc observer registry.
1.77 + typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
1.78 +
1.79 + protected:
1.80 +
1.81 + mutable ArcNotifier arc_notifier;
1.82 +
1.83 + public:
1.84 +
1.85 + using Parent::notifier;
1.86 +
1.87 + /// \brief Gives back the arc alteration notifier.
1.88 + ///
1.89 + /// Gives back the arc alteration notifier.
1.90 + ArcNotifier& notifier(Arc) const {
1.91 + return arc_notifier;
1.92 + }
1.93 +
1.94 + // Iterable extensions
1.95 +
1.96 + class NodeIt : public Node {
1.97 + const Digraph* digraph;
1.98 + public:
1.99 +
1.100 + NodeIt() {}
1.101 +
1.102 + NodeIt(Invalid i) : Node(i) { }
1.103 +
1.104 + explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
1.105 + _graph.first(static_cast<Node&>(*this));
1.106 + }
1.107 +
1.108 + NodeIt(const Digraph& _graph, const Node& node)
1.109 + : Node(node), digraph(&_graph) {}
1.110 +
1.111 + NodeIt& operator++() {
1.112 + digraph->next(*this);
1.113 + return *this;
1.114 + }
1.115 +
1.116 + };
1.117 +
1.118 +
1.119 + class ArcIt : public Arc {
1.120 + const Digraph* digraph;
1.121 + public:
1.122 +
1.123 + ArcIt() { }
1.124 +
1.125 + ArcIt(Invalid i) : Arc(i) { }
1.126 +
1.127 + explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
1.128 + _graph.first(static_cast<Arc&>(*this));
1.129 + }
1.130 +
1.131 + ArcIt(const Digraph& _graph, const Arc& e) :
1.132 + Arc(e), digraph(&_graph) { }
1.133 +
1.134 + ArcIt& operator++() {
1.135 + digraph->next(*this);
1.136 + return *this;
1.137 + }
1.138 +
1.139 + };
1.140 +
1.141 +
1.142 + class OutArcIt : public Arc {
1.143 + const Digraph* digraph;
1.144 + public:
1.145 +
1.146 + OutArcIt() { }
1.147 +
1.148 + OutArcIt(Invalid i) : Arc(i) { }
1.149 +
1.150 + OutArcIt(const Digraph& _graph, const Node& node)
1.151 + : digraph(&_graph) {
1.152 + _graph.firstOut(*this, node);
1.153 + }
1.154 +
1.155 + OutArcIt(const Digraph& _graph, const Arc& arc)
1.156 + : Arc(arc), digraph(&_graph) {}
1.157 +
1.158 + OutArcIt& operator++() {
1.159 + digraph->nextOut(*this);
1.160 + return *this;
1.161 + }
1.162 +
1.163 + };
1.164 +
1.165 +
1.166 + class InArcIt : public Arc {
1.167 + const Digraph* digraph;
1.168 + public:
1.169 +
1.170 + InArcIt() { }
1.171 +
1.172 + InArcIt(Invalid i) : Arc(i) { }
1.173 +
1.174 + InArcIt(const Digraph& _graph, const Node& node)
1.175 + : digraph(&_graph) {
1.176 + _graph.firstIn(*this, node);
1.177 + }
1.178 +
1.179 + InArcIt(const Digraph& _graph, const Arc& arc) :
1.180 + Arc(arc), digraph(&_graph) {}
1.181 +
1.182 + InArcIt& operator++() {
1.183 + digraph->nextIn(*this);
1.184 + return *this;
1.185 + }
1.186 +
1.187 + };
1.188 +
1.189 + /// \brief Base node of the iterator
1.190 + ///
1.191 + /// Returns the base node (ie. the source in this case) of the iterator
1.192 + Node baseNode(const OutArcIt &e) const {
1.193 + return Parent::source(static_cast<const Arc&>(e));
1.194 + }
1.195 + /// \brief Running node of the iterator
1.196 + ///
1.197 + /// Returns the running node (ie. the target in this case) of the
1.198 + /// iterator
1.199 + Node runningNode(const OutArcIt &e) const {
1.200 + return Parent::target(static_cast<const Arc&>(e));
1.201 + }
1.202 +
1.203 + /// \brief Base node of the iterator
1.204 + ///
1.205 + /// Returns the base node (ie. the target in this case) of the iterator
1.206 + Node baseNode(const InArcIt &e) const {
1.207 + return Parent::target(static_cast<const Arc&>(e));
1.208 + }
1.209 + /// \brief Running node of the iterator
1.210 + ///
1.211 + /// Returns the running node (ie. the source in this case) of the
1.212 + /// iterator
1.213 + Node runningNode(const InArcIt &e) const {
1.214 + return Parent::source(static_cast<const Arc&>(e));
1.215 + }
1.216 +
1.217 + using Parent::first;
1.218 +
1.219 + // Mappable extension
1.220 +
1.221 + template <typename _Value>
1.222 + class ArcMap
1.223 + : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
1.224 + public:
1.225 + typedef ArcSetExtender Digraph;
1.226 + typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
1.227 +
1.228 + explicit ArcMap(const Digraph& _g)
1.229 + : Parent(_g) {}
1.230 + ArcMap(const Digraph& _g, const _Value& _v)
1.231 + : Parent(_g, _v) {}
1.232 +
1.233 + ArcMap& operator=(const ArcMap& cmap) {
1.234 + return operator=<ArcMap>(cmap);
1.235 + }
1.236 +
1.237 + template <typename CMap>
1.238 + ArcMap& operator=(const CMap& cmap) {
1.239 + Parent::operator=(cmap);
1.240 + return *this;
1.241 + }
1.242 +
1.243 + };
1.244 +
1.245 +
1.246 + // Alteration extension
1.247 +
1.248 + Arc addArc(const Node& from, const Node& to) {
1.249 + Arc arc = Parent::addArc(from, to);
1.250 + notifier(Arc()).add(arc);
1.251 + return arc;
1.252 + }
1.253 +
1.254 + void clear() {
1.255 + notifier(Arc()).clear();
1.256 + Parent::clear();
1.257 + }
1.258 +
1.259 + void erase(const Arc& arc) {
1.260 + notifier(Arc()).erase(arc);
1.261 + Parent::erase(arc);
1.262 + }
1.263 +
1.264 + ArcSetExtender() {
1.265 + arc_notifier.setContainer(*this);
1.266 + }
1.267 +
1.268 + ~ArcSetExtender() {
1.269 + arc_notifier.clear();
1.270 + }
1.271 +
1.272 + };
1.273 +
1.274 +
1.275 + /// \ingroup digraphbits
1.276 + ///
1.277 + /// \brief Extender for the EdgeSets
1.278 + template <typename Base>
1.279 + class EdgeSetExtender : public Base {
1.280 +
1.281 + public:
1.282 +
1.283 + typedef Base Parent;
1.284 + typedef EdgeSetExtender Digraph;
1.285 +
1.286 + typedef typename Parent::Node Node;
1.287 + typedef typename Parent::Arc Arc;
1.288 + typedef typename Parent::Edge Edge;
1.289 +
1.290 +
1.291 + int maxId(Node) const {
1.292 + return Parent::maxNodeId();
1.293 + }
1.294 +
1.295 + int maxId(Arc) const {
1.296 + return Parent::maxArcId();
1.297 + }
1.298 +
1.299 + int maxId(Edge) const {
1.300 + return Parent::maxEdgeId();
1.301 + }
1.302 +
1.303 + Node fromId(int id, Node) const {
1.304 + return Parent::nodeFromId(id);
1.305 + }
1.306 +
1.307 + Arc fromId(int id, Arc) const {
1.308 + return Parent::arcFromId(id);
1.309 + }
1.310 +
1.311 + Edge fromId(int id, Edge) const {
1.312 + return Parent::edgeFromId(id);
1.313 + }
1.314 +
1.315 + Node oppositeNode(const Node &n, const Edge &e) const {
1.316 + if( n == Parent::u(e))
1.317 + return Parent::v(e);
1.318 + else if( n == Parent::v(e))
1.319 + return Parent::u(e);
1.320 + else
1.321 + return INVALID;
1.322 + }
1.323 +
1.324 + Arc oppositeArc(const Arc &e) const {
1.325 + return Parent::direct(e, !Parent::direction(e));
1.326 + }
1.327 +
1.328 + using Parent::direct;
1.329 + Arc direct(const Edge &e, const Node &s) const {
1.330 + return Parent::direct(e, Parent::u(e) == s);
1.331 + }
1.332 +
1.333 + typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
1.334 + typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
1.335 +
1.336 +
1.337 + protected:
1.338 +
1.339 + mutable ArcNotifier arc_notifier;
1.340 + mutable EdgeNotifier edge_notifier;
1.341 +
1.342 + public:
1.343 +
1.344 + using Parent::notifier;
1.345 +
1.346 + ArcNotifier& notifier(Arc) const {
1.347 + return arc_notifier;
1.348 + }
1.349 +
1.350 + EdgeNotifier& notifier(Edge) const {
1.351 + return edge_notifier;
1.352 + }
1.353 +
1.354 +
1.355 + class NodeIt : public Node {
1.356 + const Digraph* digraph;
1.357 + public:
1.358 +
1.359 + NodeIt() {}
1.360 +
1.361 + NodeIt(Invalid i) : Node(i) { }
1.362 +
1.363 + explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
1.364 + _graph.first(static_cast<Node&>(*this));
1.365 + }
1.366 +
1.367 + NodeIt(const Digraph& _graph, const Node& node)
1.368 + : Node(node), digraph(&_graph) {}
1.369 +
1.370 + NodeIt& operator++() {
1.371 + digraph->next(*this);
1.372 + return *this;
1.373 + }
1.374 +
1.375 + };
1.376 +
1.377 +
1.378 + class ArcIt : public Arc {
1.379 + const Digraph* digraph;
1.380 + public:
1.381 +
1.382 + ArcIt() { }
1.383 +
1.384 + ArcIt(Invalid i) : Arc(i) { }
1.385 +
1.386 + explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
1.387 + _graph.first(static_cast<Arc&>(*this));
1.388 + }
1.389 +
1.390 + ArcIt(const Digraph& _graph, const Arc& e) :
1.391 + Arc(e), digraph(&_graph) { }
1.392 +
1.393 + ArcIt& operator++() {
1.394 + digraph->next(*this);
1.395 + return *this;
1.396 + }
1.397 +
1.398 + };
1.399 +
1.400 +
1.401 + class OutArcIt : public Arc {
1.402 + const Digraph* digraph;
1.403 + public:
1.404 +
1.405 + OutArcIt() { }
1.406 +
1.407 + OutArcIt(Invalid i) : Arc(i) { }
1.408 +
1.409 + OutArcIt(const Digraph& _graph, const Node& node)
1.410 + : digraph(&_graph) {
1.411 + _graph.firstOut(*this, node);
1.412 + }
1.413 +
1.414 + OutArcIt(const Digraph& _graph, const Arc& arc)
1.415 + : Arc(arc), digraph(&_graph) {}
1.416 +
1.417 + OutArcIt& operator++() {
1.418 + digraph->nextOut(*this);
1.419 + return *this;
1.420 + }
1.421 +
1.422 + };
1.423 +
1.424 +
1.425 + class InArcIt : public Arc {
1.426 + const Digraph* digraph;
1.427 + public:
1.428 +
1.429 + InArcIt() { }
1.430 +
1.431 + InArcIt(Invalid i) : Arc(i) { }
1.432 +
1.433 + InArcIt(const Digraph& _graph, const Node& node)
1.434 + : digraph(&_graph) {
1.435 + _graph.firstIn(*this, node);
1.436 + }
1.437 +
1.438 + InArcIt(const Digraph& _graph, const Arc& arc) :
1.439 + Arc(arc), digraph(&_graph) {}
1.440 +
1.441 + InArcIt& operator++() {
1.442 + digraph->nextIn(*this);
1.443 + return *this;
1.444 + }
1.445 +
1.446 + };
1.447 +
1.448 +
1.449 + class EdgeIt : public Parent::Edge {
1.450 + const Digraph* digraph;
1.451 + public:
1.452 +
1.453 + EdgeIt() { }
1.454 +
1.455 + EdgeIt(Invalid i) : Edge(i) { }
1.456 +
1.457 + explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
1.458 + _graph.first(static_cast<Edge&>(*this));
1.459 + }
1.460 +
1.461 + EdgeIt(const Digraph& _graph, const Edge& e) :
1.462 + Edge(e), digraph(&_graph) { }
1.463 +
1.464 + EdgeIt& operator++() {
1.465 + digraph->next(*this);
1.466 + return *this;
1.467 + }
1.468 +
1.469 + };
1.470 +
1.471 + class IncEdgeIt : public Parent::Edge {
1.472 + friend class EdgeSetExtender;
1.473 + const Digraph* digraph;
1.474 + bool direction;
1.475 + public:
1.476 +
1.477 + IncEdgeIt() { }
1.478 +
1.479 + IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
1.480 +
1.481 + IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
1.482 + _graph.firstInc(*this, direction, n);
1.483 + }
1.484 +
1.485 + IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
1.486 + : digraph(&_graph), Edge(ue) {
1.487 + direction = (_graph.source(ue) == n);
1.488 + }
1.489 +
1.490 + IncEdgeIt& operator++() {
1.491 + digraph->nextInc(*this, direction);
1.492 + return *this;
1.493 + }
1.494 + };
1.495 +
1.496 + /// \brief Base node of the iterator
1.497 + ///
1.498 + /// Returns the base node (ie. the source in this case) of the iterator
1.499 + Node baseNode(const OutArcIt &e) const {
1.500 + return Parent::source(static_cast<const Arc&>(e));
1.501 + }
1.502 + /// \brief Running node of the iterator
1.503 + ///
1.504 + /// Returns the running node (ie. the target in this case) of the
1.505 + /// iterator
1.506 + Node runningNode(const OutArcIt &e) const {
1.507 + return Parent::target(static_cast<const Arc&>(e));
1.508 + }
1.509 +
1.510 + /// \brief Base node of the iterator
1.511 + ///
1.512 + /// Returns the base node (ie. the target in this case) of the iterator
1.513 + Node baseNode(const InArcIt &e) const {
1.514 + return Parent::target(static_cast<const Arc&>(e));
1.515 + }
1.516 + /// \brief Running node of the iterator
1.517 + ///
1.518 + /// Returns the running node (ie. the source in this case) of the
1.519 + /// iterator
1.520 + Node runningNode(const InArcIt &e) const {
1.521 + return Parent::source(static_cast<const Arc&>(e));
1.522 + }
1.523 +
1.524 + /// Base node of the iterator
1.525 + ///
1.526 + /// Returns the base node of the iterator
1.527 + Node baseNode(const IncEdgeIt &e) const {
1.528 + return e.direction ? u(e) : v(e);
1.529 + }
1.530 + /// Running node of the iterator
1.531 + ///
1.532 + /// Returns the running node of the iterator
1.533 + Node runningNode(const IncEdgeIt &e) const {
1.534 + return e.direction ? v(e) : u(e);
1.535 + }
1.536 +
1.537 +
1.538 + template <typename _Value>
1.539 + class ArcMap
1.540 + : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
1.541 + public:
1.542 + typedef EdgeSetExtender Digraph;
1.543 + typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
1.544 +
1.545 + ArcMap(const Digraph& _g)
1.546 + : Parent(_g) {}
1.547 + ArcMap(const Digraph& _g, const _Value& _v)
1.548 + : Parent(_g, _v) {}
1.549 +
1.550 + ArcMap& operator=(const ArcMap& cmap) {
1.551 + return operator=<ArcMap>(cmap);
1.552 + }
1.553 +
1.554 + template <typename CMap>
1.555 + ArcMap& operator=(const CMap& cmap) {
1.556 + Parent::operator=(cmap);
1.557 + return *this;
1.558 + }
1.559 +
1.560 + };
1.561 +
1.562 +
1.563 + template <typename _Value>
1.564 + class EdgeMap
1.565 + : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
1.566 + public:
1.567 + typedef EdgeSetExtender Digraph;
1.568 + typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
1.569 +
1.570 + EdgeMap(const Digraph& _g)
1.571 + : Parent(_g) {}
1.572 +
1.573 + EdgeMap(const Digraph& _g, const _Value& _v)
1.574 + : Parent(_g, _v) {}
1.575 +
1.576 + EdgeMap& operator=(const EdgeMap& cmap) {
1.577 + return operator=<EdgeMap>(cmap);
1.578 + }
1.579 +
1.580 + template <typename CMap>
1.581 + EdgeMap& operator=(const CMap& cmap) {
1.582 + Parent::operator=(cmap);
1.583 + return *this;
1.584 + }
1.585 +
1.586 + };
1.587 +
1.588 +
1.589 + // Alteration extension
1.590 +
1.591 + Edge addEdge(const Node& from, const Node& to) {
1.592 + Edge edge = Parent::addEdge(from, to);
1.593 + notifier(Edge()).add(edge);
1.594 + std::vector<Arc> arcs;
1.595 + arcs.push_back(Parent::direct(edge, true));
1.596 + arcs.push_back(Parent::direct(edge, false));
1.597 + notifier(Arc()).add(arcs);
1.598 + return edge;
1.599 + }
1.600 +
1.601 + void clear() {
1.602 + notifier(Arc()).clear();
1.603 + notifier(Edge()).clear();
1.604 + Parent::clear();
1.605 + }
1.606 +
1.607 + void erase(const Edge& edge) {
1.608 + std::vector<Arc> arcs;
1.609 + arcs.push_back(Parent::direct(edge, true));
1.610 + arcs.push_back(Parent::direct(edge, false));
1.611 + notifier(Arc()).erase(arcs);
1.612 + notifier(Edge()).erase(edge);
1.613 + Parent::erase(edge);
1.614 + }
1.615 +
1.616 +
1.617 + EdgeSetExtender() {
1.618 + arc_notifier.setContainer(*this);
1.619 + edge_notifier.setContainer(*this);
1.620 + }
1.621 +
1.622 + ~EdgeSetExtender() {
1.623 + edge_notifier.clear();
1.624 + arc_notifier.clear();
1.625 + }
1.626 +
1.627 + };
1.628 +
1.629 +}
1.630 +
1.631 +#endif