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