1.1 --- a/lemon/Makefile.am Sat May 09 16:39:59 2009 +0200
1.2 +++ b/lemon/Makefile.am Sat May 09 16:47:26 2009 +0200
1.3 @@ -111,7 +111,6 @@
1.4 bits_HEADERS += \
1.5 lemon/bits/alteration_notifier.h \
1.6 lemon/bits/array_map.h \
1.7 - lemon/bits/base_extender.h \
1.8 lemon/bits/bezier.h \
1.9 lemon/bits/default_map.h \
1.10 lemon/bits/edge_set_extender.h \
2.1 --- a/lemon/bits/base_extender.h Sat May 09 16:39:59 2009 +0200
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,495 +0,0 @@
2.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 - *
2.6 - * This file is a part of LEMON, a generic C++ optimization library.
2.7 - *
2.8 - * Copyright (C) 2003-2009
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_BASE_EXTENDER_H
2.23 -#define LEMON_BITS_BASE_EXTENDER_H
2.24 -
2.25 -#include <lemon/core.h>
2.26 -#include <lemon/error.h>
2.27 -
2.28 -#include <lemon/bits/map_extender.h>
2.29 -#include <lemon/bits/default_map.h>
2.30 -
2.31 -#include <lemon/concept_check.h>
2.32 -#include <lemon/concepts/maps.h>
2.33 -
2.34 -//\ingroup digraphbits
2.35 -//\file
2.36 -//\brief Extenders for the graph types
2.37 -namespace lemon {
2.38 -
2.39 - // \ingroup digraphbits
2.40 - //
2.41 - // \brief BaseDigraph to BaseGraph extender
2.42 - template <typename Base>
2.43 - class UndirDigraphExtender : public Base {
2.44 - typedef Base Parent;
2.45 -
2.46 - public:
2.47 -
2.48 - typedef typename Parent::Arc Edge;
2.49 - typedef typename Parent::Node Node;
2.50 -
2.51 - typedef True UndirectedTag;
2.52 -
2.53 - class Arc : public Edge {
2.54 - friend class UndirDigraphExtender;
2.55 -
2.56 - protected:
2.57 - bool forward;
2.58 -
2.59 - Arc(const Edge &ue, bool _forward) :
2.60 - Edge(ue), forward(_forward) {}
2.61 -
2.62 - public:
2.63 - Arc() {}
2.64 -
2.65 - // Invalid arc constructor
2.66 - Arc(Invalid i) : Edge(i), forward(true) {}
2.67 -
2.68 - bool operator==(const Arc &that) const {
2.69 - return forward==that.forward && Edge(*this)==Edge(that);
2.70 - }
2.71 - bool operator!=(const Arc &that) const {
2.72 - return forward!=that.forward || Edge(*this)!=Edge(that);
2.73 - }
2.74 - bool operator<(const Arc &that) const {
2.75 - return forward<that.forward ||
2.76 - (!(that.forward<forward) && Edge(*this)<Edge(that));
2.77 - }
2.78 - };
2.79 -
2.80 - // First node of the edge
2.81 - Node u(const Edge &e) const {
2.82 - return Parent::source(e);
2.83 - }
2.84 -
2.85 - // Source of the given arc
2.86 - Node source(const Arc &e) const {
2.87 - return e.forward ? Parent::source(e) : Parent::target(e);
2.88 - }
2.89 -
2.90 - // Second node of the edge
2.91 - Node v(const Edge &e) const {
2.92 - return Parent::target(e);
2.93 - }
2.94 -
2.95 - // Target of the given arc
2.96 - Node target(const Arc &e) const {
2.97 - return e.forward ? Parent::target(e) : Parent::source(e);
2.98 - }
2.99 -
2.100 - // \brief Directed arc from an edge.
2.101 - //
2.102 - // Returns a directed arc corresponding to the specified edge.
2.103 - // If the given bool is true, the first node of the given edge and
2.104 - // the source node of the returned arc are the same.
2.105 - static Arc direct(const Edge &e, bool d) {
2.106 - return Arc(e, d);
2.107 - }
2.108 -
2.109 - // Returns whether the given directed arc has the same orientation
2.110 - // as the corresponding edge.
2.111 - static bool direction(const Arc &a) { return a.forward; }
2.112 -
2.113 - using Parent::first;
2.114 - using Parent::next;
2.115 -
2.116 - void first(Arc &e) const {
2.117 - Parent::first(e);
2.118 - e.forward=true;
2.119 - }
2.120 -
2.121 - void next(Arc &e) const {
2.122 - if( e.forward ) {
2.123 - e.forward = false;
2.124 - }
2.125 - else {
2.126 - Parent::next(e);
2.127 - e.forward = true;
2.128 - }
2.129 - }
2.130 -
2.131 - void firstOut(Arc &e, const Node &n) const {
2.132 - Parent::firstIn(e,n);
2.133 - if( Edge(e) != INVALID ) {
2.134 - e.forward = false;
2.135 - }
2.136 - else {
2.137 - Parent::firstOut(e,n);
2.138 - e.forward = true;
2.139 - }
2.140 - }
2.141 - void nextOut(Arc &e) const {
2.142 - if( ! e.forward ) {
2.143 - Node n = Parent::target(e);
2.144 - Parent::nextIn(e);
2.145 - if( Edge(e) == INVALID ) {
2.146 - Parent::firstOut(e, n);
2.147 - e.forward = true;
2.148 - }
2.149 - }
2.150 - else {
2.151 - Parent::nextOut(e);
2.152 - }
2.153 - }
2.154 -
2.155 - void firstIn(Arc &e, const Node &n) const {
2.156 - Parent::firstOut(e,n);
2.157 - if( Edge(e) != INVALID ) {
2.158 - e.forward = false;
2.159 - }
2.160 - else {
2.161 - Parent::firstIn(e,n);
2.162 - e.forward = true;
2.163 - }
2.164 - }
2.165 - void nextIn(Arc &e) const {
2.166 - if( ! e.forward ) {
2.167 - Node n = Parent::source(e);
2.168 - Parent::nextOut(e);
2.169 - if( Edge(e) == INVALID ) {
2.170 - Parent::firstIn(e, n);
2.171 - e.forward = true;
2.172 - }
2.173 - }
2.174 - else {
2.175 - Parent::nextIn(e);
2.176 - }
2.177 - }
2.178 -
2.179 - void firstInc(Edge &e, bool &d, const Node &n) const {
2.180 - d = true;
2.181 - Parent::firstOut(e, n);
2.182 - if (e != INVALID) return;
2.183 - d = false;
2.184 - Parent::firstIn(e, n);
2.185 - }
2.186 -
2.187 - void nextInc(Edge &e, bool &d) const {
2.188 - if (d) {
2.189 - Node s = Parent::source(e);
2.190 - Parent::nextOut(e);
2.191 - if (e != INVALID) return;
2.192 - d = false;
2.193 - Parent::firstIn(e, s);
2.194 - } else {
2.195 - Parent::nextIn(e);
2.196 - }
2.197 - }
2.198 -
2.199 - Node nodeFromId(int ix) const {
2.200 - return Parent::nodeFromId(ix);
2.201 - }
2.202 -
2.203 - Arc arcFromId(int ix) const {
2.204 - return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
2.205 - }
2.206 -
2.207 - Edge edgeFromId(int ix) const {
2.208 - return Parent::arcFromId(ix);
2.209 - }
2.210 -
2.211 - int id(const Node &n) const {
2.212 - return Parent::id(n);
2.213 - }
2.214 -
2.215 - int id(const Edge &e) const {
2.216 - return Parent::id(e);
2.217 - }
2.218 -
2.219 - int id(const Arc &e) const {
2.220 - return 2 * Parent::id(e) + int(e.forward);
2.221 - }
2.222 -
2.223 - int maxNodeId() const {
2.224 - return Parent::maxNodeId();
2.225 - }
2.226 -
2.227 - int maxArcId() const {
2.228 - return 2 * Parent::maxArcId() + 1;
2.229 - }
2.230 -
2.231 - int maxEdgeId() const {
2.232 - return Parent::maxArcId();
2.233 - }
2.234 -
2.235 - int arcNum() const {
2.236 - return 2 * Parent::arcNum();
2.237 - }
2.238 -
2.239 - int edgeNum() const {
2.240 - return Parent::arcNum();
2.241 - }
2.242 -
2.243 - Arc findArc(Node s, Node t, Arc p = INVALID) const {
2.244 - if (p == INVALID) {
2.245 - Edge arc = Parent::findArc(s, t);
2.246 - if (arc != INVALID) return direct(arc, true);
2.247 - arc = Parent::findArc(t, s);
2.248 - if (arc != INVALID) return direct(arc, false);
2.249 - } else if (direction(p)) {
2.250 - Edge arc = Parent::findArc(s, t, p);
2.251 - if (arc != INVALID) return direct(arc, true);
2.252 - arc = Parent::findArc(t, s);
2.253 - if (arc != INVALID) return direct(arc, false);
2.254 - } else {
2.255 - Edge arc = Parent::findArc(t, s, p);
2.256 - if (arc != INVALID) return direct(arc, false);
2.257 - }
2.258 - return INVALID;
2.259 - }
2.260 -
2.261 - Edge findEdge(Node s, Node t, Edge p = INVALID) const {
2.262 - if (s != t) {
2.263 - if (p == INVALID) {
2.264 - Edge arc = Parent::findArc(s, t);
2.265 - if (arc != INVALID) return arc;
2.266 - arc = Parent::findArc(t, s);
2.267 - if (arc != INVALID) return arc;
2.268 - } else if (Parent::s(p) == s) {
2.269 - Edge arc = Parent::findArc(s, t, p);
2.270 - if (arc != INVALID) return arc;
2.271 - arc = Parent::findArc(t, s);
2.272 - if (arc != INVALID) return arc;
2.273 - } else {
2.274 - Edge arc = Parent::findArc(t, s, p);
2.275 - if (arc != INVALID) return arc;
2.276 - }
2.277 - } else {
2.278 - return Parent::findArc(s, t, p);
2.279 - }
2.280 - return INVALID;
2.281 - }
2.282 - };
2.283 -
2.284 - template <typename Base>
2.285 - class BidirBpGraphExtender : public Base {
2.286 - typedef Base Parent;
2.287 -
2.288 - public:
2.289 - typedef BidirBpGraphExtender Digraph;
2.290 -
2.291 - typedef typename Parent::Node Node;
2.292 - typedef typename Parent::Edge Edge;
2.293 -
2.294 -
2.295 - using Parent::first;
2.296 - using Parent::next;
2.297 -
2.298 - using Parent::id;
2.299 -
2.300 - class Red : public Node {
2.301 - friend class BidirBpGraphExtender;
2.302 - public:
2.303 - Red() {}
2.304 - Red(const Node& node) : Node(node) {
2.305 - LEMON_DEBUG(Parent::red(node) || node == INVALID,
2.306 - typename Parent::NodeSetError());
2.307 - }
2.308 - Red& operator=(const Node& node) {
2.309 - LEMON_DEBUG(Parent::red(node) || node == INVALID,
2.310 - typename Parent::NodeSetError());
2.311 - Node::operator=(node);
2.312 - return *this;
2.313 - }
2.314 - Red(Invalid) : Node(INVALID) {}
2.315 - Red& operator=(Invalid) {
2.316 - Node::operator=(INVALID);
2.317 - return *this;
2.318 - }
2.319 - };
2.320 -
2.321 - void first(Red& node) const {
2.322 - Parent::firstRed(static_cast<Node&>(node));
2.323 - }
2.324 - void next(Red& node) const {
2.325 - Parent::nextRed(static_cast<Node&>(node));
2.326 - }
2.327 -
2.328 - int id(const Red& node) const {
2.329 - return Parent::redId(node);
2.330 - }
2.331 -
2.332 - class Blue : public Node {
2.333 - friend class BidirBpGraphExtender;
2.334 - public:
2.335 - Blue() {}
2.336 - Blue(const Node& node) : Node(node) {
2.337 - LEMON_DEBUG(Parent::blue(node) || node == INVALID,
2.338 - typename Parent::NodeSetError());
2.339 - }
2.340 - Blue& operator=(const Node& node) {
2.341 - LEMON_DEBUG(Parent::blue(node) || node == INVALID,
2.342 - typename Parent::NodeSetError());
2.343 - Node::operator=(node);
2.344 - return *this;
2.345 - }
2.346 - Blue(Invalid) : Node(INVALID) {}
2.347 - Blue& operator=(Invalid) {
2.348 - Node::operator=(INVALID);
2.349 - return *this;
2.350 - }
2.351 - };
2.352 -
2.353 - void first(Blue& node) const {
2.354 - Parent::firstBlue(static_cast<Node&>(node));
2.355 - }
2.356 - void next(Blue& node) const {
2.357 - Parent::nextBlue(static_cast<Node&>(node));
2.358 - }
2.359 -
2.360 - int id(const Blue& node) const {
2.361 - return Parent::redId(node);
2.362 - }
2.363 -
2.364 - Node source(const Edge& arc) const {
2.365 - return red(arc);
2.366 - }
2.367 - Node target(const Edge& arc) const {
2.368 - return blue(arc);
2.369 - }
2.370 -
2.371 - void firstInc(Edge& arc, bool& dir, const Node& node) const {
2.372 - if (Parent::red(node)) {
2.373 - Parent::firstFromRed(arc, node);
2.374 - dir = true;
2.375 - } else {
2.376 - Parent::firstFromBlue(arc, node);
2.377 - dir = static_cast<Edge&>(arc) == INVALID;
2.378 - }
2.379 - }
2.380 - void nextInc(Edge& arc, bool& dir) const {
2.381 - if (dir) {
2.382 - Parent::nextFromRed(arc);
2.383 - } else {
2.384 - Parent::nextFromBlue(arc);
2.385 - if (arc == INVALID) dir = true;
2.386 - }
2.387 - }
2.388 -
2.389 - class Arc : public Edge {
2.390 - friend class BidirBpGraphExtender;
2.391 - protected:
2.392 - bool forward;
2.393 -
2.394 - Arc(const Edge& arc, bool _forward)
2.395 - : Edge(arc), forward(_forward) {}
2.396 -
2.397 - public:
2.398 - Arc() {}
2.399 - Arc (Invalid) : Edge(INVALID), forward(true) {}
2.400 - bool operator==(const Arc& i) const {
2.401 - return Edge::operator==(i) && forward == i.forward;
2.402 - }
2.403 - bool operator!=(const Arc& i) const {
2.404 - return Edge::operator!=(i) || forward != i.forward;
2.405 - }
2.406 - bool operator<(const Arc& i) const {
2.407 - return Edge::operator<(i) ||
2.408 - (!(i.forward<forward) && Edge(*this)<Edge(i));
2.409 - }
2.410 - };
2.411 -
2.412 - void first(Arc& arc) const {
2.413 - Parent::first(static_cast<Edge&>(arc));
2.414 - arc.forward = true;
2.415 - }
2.416 -
2.417 - void next(Arc& arc) const {
2.418 - if (!arc.forward) {
2.419 - Parent::next(static_cast<Edge&>(arc));
2.420 - }
2.421 - arc.forward = !arc.forward;
2.422 - }
2.423 -
2.424 - void firstOut(Arc& arc, const Node& node) const {
2.425 - if (Parent::red(node)) {
2.426 - Parent::firstFromRed(arc, node);
2.427 - arc.forward = true;
2.428 - } else {
2.429 - Parent::firstFromBlue(arc, node);
2.430 - arc.forward = static_cast<Edge&>(arc) == INVALID;
2.431 - }
2.432 - }
2.433 - void nextOut(Arc& arc) const {
2.434 - if (arc.forward) {
2.435 - Parent::nextFromRed(arc);
2.436 - } else {
2.437 - Parent::nextFromBlue(arc);
2.438 - arc.forward = static_cast<Edge&>(arc) == INVALID;
2.439 - }
2.440 - }
2.441 -
2.442 - void firstIn(Arc& arc, const Node& node) const {
2.443 - if (Parent::blue(node)) {
2.444 - Parent::firstFromBlue(arc, node);
2.445 - arc.forward = true;
2.446 - } else {
2.447 - Parent::firstFromRed(arc, node);
2.448 - arc.forward = static_cast<Edge&>(arc) == INVALID;
2.449 - }
2.450 - }
2.451 - void nextIn(Arc& arc) const {
2.452 - if (arc.forward) {
2.453 - Parent::nextFromBlue(arc);
2.454 - } else {
2.455 - Parent::nextFromRed(arc);
2.456 - arc.forward = static_cast<Edge&>(arc) == INVALID;
2.457 - }
2.458 - }
2.459 -
2.460 - Node source(const Arc& arc) const {
2.461 - return arc.forward ? Parent::red(arc) : Parent::blue(arc);
2.462 - }
2.463 - Node target(const Arc& arc) const {
2.464 - return arc.forward ? Parent::blue(arc) : Parent::red(arc);
2.465 - }
2.466 -
2.467 - int id(const Arc& arc) const {
2.468 - return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
2.469 - (arc.forward ? 0 : 1);
2.470 - }
2.471 - Arc arcFromId(int ix) const {
2.472 - return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
2.473 - }
2.474 - int maxArcId() const {
2.475 - return (Parent::maxEdgeId() << 1) + 1;
2.476 - }
2.477 -
2.478 - bool direction(const Arc& arc) const {
2.479 - return arc.forward;
2.480 - }
2.481 -
2.482 - Arc direct(const Edge& arc, bool dir) const {
2.483 - return Arc(arc, dir);
2.484 - }
2.485 -
2.486 - int arcNum() const {
2.487 - return 2 * Parent::edgeNum();
2.488 - }
2.489 -
2.490 - int edgeNum() const {
2.491 - return Parent::edgeNum();
2.492 - }
2.493 -
2.494 -
2.495 - };
2.496 -}
2.497 -
2.498 -#endif