1.1 --- a/lemon/bits/undir_graph_extender.h Mon Nov 14 18:36:45 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,311 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * lemon/undir_graph_extender.h - Part of LEMON, a generic C++
1.7 - * optimization library
1.8 - *
1.9 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
1.10 - * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
1.11 - * EGRES).
1.12 - *
1.13 - * Permission to use, modify and distribute this software is granted
1.14 - * provided that this copyright notice appears in all copies. For
1.15 - * precise terms see the accompanying LICENSE file.
1.16 - *
1.17 - * This software is provided "AS IS" with no warranty of any kind,
1.18 - * express or implied, and with no claim as to its suitability for any
1.19 - * purpose.
1.20 - *
1.21 - */
1.22 -
1.23 -#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
1.24 -#define LEMON_UNDIR_GRAPH_EXTENDER_H
1.25 -
1.26 -#include <lemon/invalid.h>
1.27 -
1.28 -namespace lemon {
1.29 -
1.30 - template <typename _Base>
1.31 - class UndirGraphExtender : public _Base {
1.32 - typedef _Base Parent;
1.33 - typedef UndirGraphExtender Graph;
1.34 -
1.35 - public:
1.36 -
1.37 - typedef typename Parent::Edge UndirEdge;
1.38 - typedef typename Parent::Node Node;
1.39 -
1.40 - class Edge : public UndirEdge {
1.41 - friend class UndirGraphExtender;
1.42 -
1.43 - protected:
1.44 - // FIXME: Marci use opposite logic in his graph adaptors. It would
1.45 - // be reasonable to syncronize...
1.46 - bool forward;
1.47 -
1.48 - Edge(const UndirEdge &ue, bool _forward) :
1.49 - UndirEdge(ue), forward(_forward) {}
1.50 -
1.51 - public:
1.52 - Edge() {}
1.53 -
1.54 - /// Invalid edge constructor
1.55 - Edge(Invalid i) : UndirEdge(i), forward(true) {}
1.56 -
1.57 - bool operator==(const Edge &that) const {
1.58 - return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
1.59 - }
1.60 - bool operator!=(const Edge &that) const {
1.61 - return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
1.62 - }
1.63 - bool operator<(const Edge &that) const {
1.64 - return forward<that.forward ||
1.65 - (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
1.66 - }
1.67 - };
1.68 -
1.69 -
1.70 - /// \brief Edge of opposite direction.
1.71 - ///
1.72 - /// Returns the Edge of opposite direction.
1.73 - Edge oppositeEdge(const Edge &e) const {
1.74 - return Edge(e,!e.forward);
1.75 - }
1.76 -
1.77 - public:
1.78 - /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
1.79 - /// or something???
1.80 - using Parent::source;
1.81 -
1.82 - /// Source of the given Edge.
1.83 - Node source(const Edge &e) const {
1.84 - return e.forward ? Parent::source(e) : Parent::target(e);
1.85 - }
1.86 -
1.87 - /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
1.88 - /// or something???
1.89 - using Parent::target;
1.90 -
1.91 - /// Target of the given Edge.
1.92 - Node target(const Edge &e) const {
1.93 - return e.forward ? Parent::target(e) : Parent::source(e);
1.94 - }
1.95 -
1.96 - Node oppositeNode(const Node &n, const UndirEdge &e) const {
1.97 - if( n == Parent::source(e))
1.98 - return Parent::target(e);
1.99 - else if( n == Parent::target(e))
1.100 - return Parent::source(e);
1.101 - else
1.102 - return INVALID;
1.103 - }
1.104 -
1.105 - /// \brief Directed edge from an undirected edge and a source node.
1.106 - ///
1.107 - /// Returns a (directed) Edge corresponding to the specified UndirEdge
1.108 - /// and source Node.
1.109 - ///
1.110 - Edge direct(const UndirEdge &ue, const Node &s) const {
1.111 - return Edge(ue, s == source(ue));
1.112 - }
1.113 -
1.114 - /// \brief Directed edge from an undirected edge.
1.115 - ///
1.116 - /// Returns a directed edge corresponding to the specified UndirEdge.
1.117 - /// If the given bool is true the given undirected edge and the
1.118 - /// returned edge have the same source node.
1.119 - Edge direct(const UndirEdge &ue, bool d) const {
1.120 - return Edge(ue, d);
1.121 - }
1.122 -
1.123 - /// Returns whether the given directed edge is same orientation as the
1.124 - /// corresponding undirected edge.
1.125 - ///
1.126 - /// \todo reference to the corresponding point of the undirected graph
1.127 - /// concept. "What does the direction of an undirected edge mean?"
1.128 - bool direction(const Edge &e) const { return e.forward; }
1.129 -
1.130 -
1.131 - using Parent::first;
1.132 - void first(Edge &e) const {
1.133 - Parent::first(e);
1.134 - e.forward=true;
1.135 - }
1.136 -
1.137 - using Parent::next;
1.138 - void next(Edge &e) const {
1.139 - if( e.forward ) {
1.140 - e.forward = false;
1.141 - }
1.142 - else {
1.143 - Parent::next(e);
1.144 - e.forward = true;
1.145 - }
1.146 - }
1.147 -
1.148 - public:
1.149 -
1.150 - void firstOut(Edge &e, const Node &n) const {
1.151 - Parent::firstIn(e,n);
1.152 - if( UndirEdge(e) != INVALID ) {
1.153 - e.forward = false;
1.154 - }
1.155 - else {
1.156 - Parent::firstOut(e,n);
1.157 - e.forward = true;
1.158 - }
1.159 - }
1.160 - void nextOut(Edge &e) const {
1.161 - if( ! e.forward ) {
1.162 - Node n = Parent::target(e);
1.163 - Parent::nextIn(e);
1.164 - if( UndirEdge(e) == INVALID ) {
1.165 - Parent::firstOut(e, n);
1.166 - e.forward = true;
1.167 - }
1.168 - }
1.169 - else {
1.170 - Parent::nextOut(e);
1.171 - }
1.172 - }
1.173 -
1.174 - void firstIn(Edge &e, const Node &n) const {
1.175 - Parent::firstOut(e,n);
1.176 - if( UndirEdge(e) != INVALID ) {
1.177 - e.forward = false;
1.178 - }
1.179 - else {
1.180 - Parent::firstIn(e,n);
1.181 - e.forward = true;
1.182 - }
1.183 - }
1.184 - void nextIn(Edge &e) const {
1.185 - if( ! e.forward ) {
1.186 - Node n = Parent::source(e);
1.187 - Parent::nextOut(e);
1.188 - if( UndirEdge(e) == INVALID ) {
1.189 - Parent::firstIn(e, n);
1.190 - e.forward = true;
1.191 - }
1.192 - }
1.193 - else {
1.194 - Parent::nextIn(e);
1.195 - }
1.196 - }
1.197 -
1.198 - void firstInc(UndirEdge &e, const Node &n) const {
1.199 - Parent::firstOut(e, n);
1.200 - if (e != INVALID) return;
1.201 - Parent::firstIn(e, n);
1.202 - }
1.203 - void nextInc(UndirEdge &e, const Node &n) const {
1.204 - if (Parent::source(e) == n) {
1.205 - Parent::nextOut(e);
1.206 - if (e != INVALID) return;
1.207 - Parent::firstIn(e, n);
1.208 - } else {
1.209 - Parent::nextIn(e);
1.210 - }
1.211 - }
1.212 -
1.213 - void firstInc(UndirEdge &e, bool &d, const Node &n) const {
1.214 - d = true;
1.215 - Parent::firstOut(e, n);
1.216 - if (e != INVALID) return;
1.217 - d = false;
1.218 - Parent::firstIn(e, n);
1.219 - }
1.220 - void nextInc(UndirEdge &e, bool &d) const {
1.221 - if (d) {
1.222 - Node s = Parent::source(e);
1.223 - Parent::nextOut(e);
1.224 - if (e != INVALID) return;
1.225 - d = false;
1.226 - Parent::firstIn(e, s);
1.227 - } else {
1.228 - Parent::nextIn(e);
1.229 - }
1.230 - }
1.231 -
1.232 - // Miscellaneous stuff:
1.233 -
1.234 - /// \todo these methods (id, maxEdgeId) should be moved into separate
1.235 - /// Extender
1.236 -
1.237 - // using Parent::id;
1.238 - // Using "using" is not a good idea, cause it could be that there is
1.239 - // no "id" in Parent...
1.240 -
1.241 - int id(const Node &n) const {
1.242 - return Parent::id(n);
1.243 - }
1.244 -
1.245 - int id(const UndirEdge &e) const {
1.246 - return Parent::id(e);
1.247 - }
1.248 -
1.249 - int id(const Edge &e) const {
1.250 - return 2 * Parent::id(e) + int(e.forward);
1.251 - }
1.252 -
1.253 -
1.254 - int maxId(Node) const {
1.255 - return Parent::maxId(Node());
1.256 - }
1.257 -
1.258 - int maxId(Edge) const {
1.259 - return 2 * Parent::maxId(typename Parent::Edge()) + 1;
1.260 - }
1.261 - int maxId(UndirEdge) const {
1.262 - return Parent::maxId(typename Parent::Edge());
1.263 - }
1.264 -
1.265 -
1.266 - int edgeNum() const {
1.267 - return 2 * Parent::edgeNum();
1.268 - }
1.269 -
1.270 - int undirEdgeNum() const {
1.271 - return Parent::edgeNum();
1.272 - }
1.273 -
1.274 - Edge findEdge(Node source, Node target, Edge prev) const {
1.275 - if (prev == INVALID) {
1.276 - UndirEdge edge = Parent::findEdge(source, target);
1.277 - if (edge != INVALID) return direct(edge, true);
1.278 - edge = Parent::findEdge(target, source);
1.279 - if (edge != INVALID) return direct(edge, false);
1.280 - } else if (direction(prev)) {
1.281 - UndirEdge edge = Parent::findEdge(source, target, prev);
1.282 - if (edge != INVALID) return direct(edge, true);
1.283 - edge = Parent::findEdge(target, source);
1.284 - if (edge != INVALID) return direct(edge, false);
1.285 - } else {
1.286 - UndirEdge edge = Parent::findEdge(target, source, prev);
1.287 - if (edge != INVALID) return direct(edge, false);
1.288 - }
1.289 - return INVALID;
1.290 - }
1.291 -
1.292 - UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
1.293 - if (prev == INVALID) {
1.294 - UndirEdge edge = Parent::findEdge(source, target);
1.295 - if (edge != INVALID) return edge;
1.296 - edge = Parent::findEdge(target, source);
1.297 - if (edge != INVALID) return edge;
1.298 - } else if (Parent::source(prev) == source) {
1.299 - UndirEdge edge = Parent::findEdge(source, target, prev);
1.300 - if (edge != INVALID) return edge;
1.301 - edge = Parent::findEdge(target, source);
1.302 - if (edge != INVALID) return edge;
1.303 - } else {
1.304 - UndirEdge edge = Parent::findEdge(target, source, prev);
1.305 - if (edge != INVALID) return edge;
1.306 - }
1.307 - return INVALID;
1.308 - }
1.309 -
1.310 - };
1.311 -
1.312 -}
1.313 -
1.314 -#endif // LEMON_UNDIR_GRAPH_EXTENDER_H