1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/graph_extender.h Mon Nov 14 18:38:41 2005 +0000
1.3 @@ -0,0 +1,381 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/graph_extender.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
1.8 + * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
1.9 + * EGRES).
1.10 + *
1.11 + * Permission to use, modify and distribute this software is granted
1.12 + * provided that this copyright notice appears in all copies. For
1.13 + * precise terms see the accompanying LICENSE file.
1.14 + *
1.15 + * This software is provided "AS IS" with no warranty of any kind,
1.16 + * express or implied, and with no claim as to its suitability for any
1.17 + * purpose.
1.18 + *
1.19 + */
1.20 +
1.21 +#ifndef LEMON_GRAPH_EXTENDER_H
1.22 +#define LEMON_GRAPH_EXTENDER_H
1.23 +
1.24 +#include <lemon/invalid.h>
1.25 +
1.26 +namespace lemon {
1.27 +
1.28 + template <typename _Base>
1.29 + class GraphExtender : public _Base {
1.30 + public:
1.31 +
1.32 + typedef _Base Parent;
1.33 + typedef GraphExtender Graph;
1.34 +
1.35 + typedef typename Parent::Node Node;
1.36 + typedef typename Parent::Edge Edge;
1.37 +
1.38 + int maxId(Node) const {
1.39 + return Parent::maxNodeId();
1.40 + }
1.41 +
1.42 + int maxId(Edge) const {
1.43 + return Parent::maxEdgeId();
1.44 + }
1.45 +
1.46 + Node fromId(int id, Node) const {
1.47 + return Parent::nodeFromId(id);
1.48 + }
1.49 +
1.50 + Edge fromId(int id, Edge) const {
1.51 + return Parent::edgeFromId(id);
1.52 + }
1.53 +
1.54 + Node oppositeNode(const Node &n, const Edge &e) const {
1.55 + if (n == Parent::source(e))
1.56 + return Parent::target(e);
1.57 + else if(n==Parent::target(e))
1.58 + return Parent::source(e);
1.59 + else
1.60 + return INVALID;
1.61 + }
1.62 +
1.63 + };
1.64 +
1.65 + template <typename _Base>
1.66 + class UndirGraphExtender : public _Base {
1.67 + typedef _Base Parent;
1.68 + typedef UndirGraphExtender Graph;
1.69 +
1.70 + public:
1.71 +
1.72 + typedef typename Parent::Edge UndirEdge;
1.73 + typedef typename Parent::Node Node;
1.74 +
1.75 + class Edge : public UndirEdge {
1.76 + friend class UndirGraphExtender;
1.77 +
1.78 + protected:
1.79 + // FIXME: Marci use opposite logic in his graph adaptors. It would
1.80 + // be reasonable to syncronize...
1.81 + bool forward;
1.82 +
1.83 + Edge(const UndirEdge &ue, bool _forward) :
1.84 + UndirEdge(ue), forward(_forward) {}
1.85 +
1.86 + public:
1.87 + Edge() {}
1.88 +
1.89 + /// Invalid edge constructor
1.90 + Edge(Invalid i) : UndirEdge(i), forward(true) {}
1.91 +
1.92 + bool operator==(const Edge &that) const {
1.93 + return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
1.94 + }
1.95 + bool operator!=(const Edge &that) const {
1.96 + return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
1.97 + }
1.98 + bool operator<(const Edge &that) const {
1.99 + return forward<that.forward ||
1.100 + (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
1.101 + }
1.102 + };
1.103 +
1.104 +
1.105 + /// \brief Edge of opposite direction.
1.106 + ///
1.107 + /// Returns the Edge of opposite direction.
1.108 + Edge oppositeEdge(const Edge &e) const {
1.109 + return Edge(e,!e.forward);
1.110 + }
1.111 +
1.112 + public:
1.113 + /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
1.114 + /// or something???
1.115 + using Parent::source;
1.116 +
1.117 + /// Source of the given Edge.
1.118 + Node source(const Edge &e) const {
1.119 + return e.forward ? Parent::source(e) : Parent::target(e);
1.120 + }
1.121 +
1.122 + /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
1.123 + /// or something???
1.124 + using Parent::target;
1.125 +
1.126 + /// Target of the given Edge.
1.127 + Node target(const Edge &e) const {
1.128 + return e.forward ? Parent::target(e) : Parent::source(e);
1.129 + }
1.130 +
1.131 + Node oppositeNode(const Node &n, const UndirEdge &e) const {
1.132 + if( n == Parent::source(e))
1.133 + return Parent::target(e);
1.134 + else if( n == Parent::target(e))
1.135 + return Parent::source(e);
1.136 + else
1.137 + return INVALID;
1.138 + }
1.139 +
1.140 + /// \brief Directed edge from an undirected edge and a source node.
1.141 + ///
1.142 + /// Returns a (directed) Edge corresponding to the specified UndirEdge
1.143 + /// and source Node.
1.144 + ///
1.145 + Edge direct(const UndirEdge &ue, const Node &s) const {
1.146 + return Edge(ue, s == source(ue));
1.147 + }
1.148 +
1.149 + /// \brief Directed edge from an undirected edge.
1.150 + ///
1.151 + /// Returns a directed edge corresponding to the specified UndirEdge.
1.152 + /// If the given bool is true the given undirected edge and the
1.153 + /// returned edge have the same source node.
1.154 + Edge direct(const UndirEdge &ue, bool d) const {
1.155 + return Edge(ue, d);
1.156 + }
1.157 +
1.158 + /// Returns whether the given directed edge is same orientation as the
1.159 + /// corresponding undirected edge.
1.160 + ///
1.161 + /// \todo reference to the corresponding point of the undirected graph
1.162 + /// concept. "What does the direction of an undirected edge mean?"
1.163 + bool direction(const Edge &e) const { return e.forward; }
1.164 +
1.165 +
1.166 + using Parent::first;
1.167 + void first(Edge &e) const {
1.168 + Parent::first(e);
1.169 + e.forward=true;
1.170 + }
1.171 +
1.172 + using Parent::next;
1.173 + void next(Edge &e) const {
1.174 + if( e.forward ) {
1.175 + e.forward = false;
1.176 + }
1.177 + else {
1.178 + Parent::next(e);
1.179 + e.forward = true;
1.180 + }
1.181 + }
1.182 +
1.183 + public:
1.184 +
1.185 + void firstOut(Edge &e, const Node &n) const {
1.186 + Parent::firstIn(e,n);
1.187 + if( UndirEdge(e) != INVALID ) {
1.188 + e.forward = false;
1.189 + }
1.190 + else {
1.191 + Parent::firstOut(e,n);
1.192 + e.forward = true;
1.193 + }
1.194 + }
1.195 + void nextOut(Edge &e) const {
1.196 + if( ! e.forward ) {
1.197 + Node n = Parent::target(e);
1.198 + Parent::nextIn(e);
1.199 + if( UndirEdge(e) == INVALID ) {
1.200 + Parent::firstOut(e, n);
1.201 + e.forward = true;
1.202 + }
1.203 + }
1.204 + else {
1.205 + Parent::nextOut(e);
1.206 + }
1.207 + }
1.208 +
1.209 + void firstIn(Edge &e, const Node &n) const {
1.210 + Parent::firstOut(e,n);
1.211 + if( UndirEdge(e) != INVALID ) {
1.212 + e.forward = false;
1.213 + }
1.214 + else {
1.215 + Parent::firstIn(e,n);
1.216 + e.forward = true;
1.217 + }
1.218 + }
1.219 + void nextIn(Edge &e) const {
1.220 + if( ! e.forward ) {
1.221 + Node n = Parent::source(e);
1.222 + Parent::nextOut(e);
1.223 + if( UndirEdge(e) == INVALID ) {
1.224 + Parent::firstIn(e, n);
1.225 + e.forward = true;
1.226 + }
1.227 + }
1.228 + else {
1.229 + Parent::nextIn(e);
1.230 + }
1.231 + }
1.232 +
1.233 + void firstInc(UndirEdge &e, const Node &n) const {
1.234 + Parent::firstOut(e, n);
1.235 + if (e != INVALID) return;
1.236 + Parent::firstIn(e, n);
1.237 + }
1.238 + void nextInc(UndirEdge &e, const Node &n) const {
1.239 + if (Parent::source(e) == n) {
1.240 + Parent::nextOut(e);
1.241 + if (e != INVALID) return;
1.242 + Parent::firstIn(e, n);
1.243 + } else {
1.244 + Parent::nextIn(e);
1.245 + }
1.246 + }
1.247 +
1.248 + void firstInc(UndirEdge &e, bool &d, const Node &n) const {
1.249 + d = true;
1.250 + Parent::firstOut(e, n);
1.251 + if (e != INVALID) return;
1.252 + d = false;
1.253 + Parent::firstIn(e, n);
1.254 + }
1.255 + void nextInc(UndirEdge &e, bool &d) const {
1.256 + if (d) {
1.257 + Node s = Parent::source(e);
1.258 + Parent::nextOut(e);
1.259 + if (e != INVALID) return;
1.260 + d = false;
1.261 + Parent::firstIn(e, s);
1.262 + } else {
1.263 + Parent::nextIn(e);
1.264 + }
1.265 + }
1.266 +
1.267 + // Miscellaneous stuff:
1.268 +
1.269 + /// \todo these methods (id, maxEdgeId) should be moved into separate
1.270 + /// Extender
1.271 +
1.272 + // using Parent::id;
1.273 + // Using "using" is not a good idea, cause it could be that there is
1.274 + // no "id" in Parent...
1.275 +
1.276 + int id(const Node &n) const {
1.277 + return Parent::id(n);
1.278 + }
1.279 +
1.280 + int id(const UndirEdge &e) const {
1.281 + return Parent::id(e);
1.282 + }
1.283 +
1.284 + int id(const Edge &e) const {
1.285 + return 2 * Parent::id(e) + int(e.forward);
1.286 + }
1.287 +
1.288 + int maxNodeId() const {
1.289 + return Parent::maxNodeId();
1.290 + }
1.291 +
1.292 + int maxEdgeId() const {
1.293 + return 2 * Parent::maxEdgeId() + 1;
1.294 + }
1.295 +
1.296 + int maxUndirEdgeId() const {
1.297 + return Parent::maxEdgeId();
1.298 + }
1.299 +
1.300 + int maxId(Node) const {
1.301 + return maxNodeId();
1.302 + }
1.303 +
1.304 + int maxId(Edge) const {
1.305 + return maxEdgeId();
1.306 + }
1.307 + int maxId(UndirEdge) const {
1.308 + return maxUndirEdgeId();
1.309 + }
1.310 +
1.311 + int edgeNum() const {
1.312 + return 2 * Parent::edgeNum();
1.313 + }
1.314 +
1.315 + int undirEdgeNum() const {
1.316 + return Parent::edgeNum();
1.317 + }
1.318 +
1.319 + Node nodeFromId(int id) const {
1.320 + return Parent::nodeFromId(id);
1.321 + }
1.322 +
1.323 + Edge edgeFromId(int id) const {
1.324 + return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
1.325 + }
1.326 +
1.327 + UndirEdge undirEdgeFromId(int id) const {
1.328 + return Parent::edgeFromId(id >> 1);
1.329 + }
1.330 +
1.331 + Node fromId(int id, Node) const {
1.332 + return nodeFromId(id);
1.333 + }
1.334 +
1.335 + Edge fromId(int id, Edge) const {
1.336 + return edgeFromId(id);
1.337 + }
1.338 +
1.339 + UndirEdge fromId(int id, UndirEdge) const {
1.340 + return undirEdgeFromId(id);
1.341 + }
1.342 +
1.343 +
1.344 + Edge findEdge(Node source, Node target, Edge prev) const {
1.345 + if (prev == INVALID) {
1.346 + UndirEdge edge = Parent::findEdge(source, target);
1.347 + if (edge != INVALID) return direct(edge, true);
1.348 + edge = Parent::findEdge(target, source);
1.349 + if (edge != INVALID) return direct(edge, false);
1.350 + } else if (direction(prev)) {
1.351 + UndirEdge edge = Parent::findEdge(source, target, prev);
1.352 + if (edge != INVALID) return direct(edge, true);
1.353 + edge = Parent::findEdge(target, source);
1.354 + if (edge != INVALID) return direct(edge, false);
1.355 + } else {
1.356 + UndirEdge edge = Parent::findEdge(target, source, prev);
1.357 + if (edge != INVALID) return direct(edge, false);
1.358 + }
1.359 + return INVALID;
1.360 + }
1.361 +
1.362 + UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
1.363 + if (prev == INVALID) {
1.364 + UndirEdge edge = Parent::findEdge(source, target);
1.365 + if (edge != INVALID) return edge;
1.366 + edge = Parent::findEdge(target, source);
1.367 + if (edge != INVALID) return edge;
1.368 + } else if (Parent::source(prev) == source) {
1.369 + UndirEdge edge = Parent::findEdge(source, target, prev);
1.370 + if (edge != INVALID) return edge;
1.371 + edge = Parent::findEdge(target, source);
1.372 + if (edge != INVALID) return edge;
1.373 + } else {
1.374 + UndirEdge edge = Parent::findEdge(target, source, prev);
1.375 + if (edge != INVALID) return edge;
1.376 + }
1.377 + return INVALID;
1.378 + }
1.379 +
1.380 + };
1.381 +
1.382 +}
1.383 +
1.384 +#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
2.1 --- a/lemon/bits/undir_graph_extender.h Mon Nov 14 18:36:45 2005 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,311 +0,0 @@
2.4 -/* -*- C++ -*-
2.5 - *
2.6 - * lemon/undir_graph_extender.h - Part of LEMON, a generic C++
2.7 - * optimization library
2.8 - *
2.9 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
2.10 - * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
2.11 - * EGRES).
2.12 - *
2.13 - * Permission to use, modify and distribute this software is granted
2.14 - * provided that this copyright notice appears in all copies. For
2.15 - * precise terms see the accompanying LICENSE file.
2.16 - *
2.17 - * This software is provided "AS IS" with no warranty of any kind,
2.18 - * express or implied, and with no claim as to its suitability for any
2.19 - * purpose.
2.20 - *
2.21 - */
2.22 -
2.23 -#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
2.24 -#define LEMON_UNDIR_GRAPH_EXTENDER_H
2.25 -
2.26 -#include <lemon/invalid.h>
2.27 -
2.28 -namespace lemon {
2.29 -
2.30 - template <typename _Base>
2.31 - class UndirGraphExtender : public _Base {
2.32 - typedef _Base Parent;
2.33 - typedef UndirGraphExtender Graph;
2.34 -
2.35 - public:
2.36 -
2.37 - typedef typename Parent::Edge UndirEdge;
2.38 - typedef typename Parent::Node Node;
2.39 -
2.40 - class Edge : public UndirEdge {
2.41 - friend class UndirGraphExtender;
2.42 -
2.43 - protected:
2.44 - // FIXME: Marci use opposite logic in his graph adaptors. It would
2.45 - // be reasonable to syncronize...
2.46 - bool forward;
2.47 -
2.48 - Edge(const UndirEdge &ue, bool _forward) :
2.49 - UndirEdge(ue), forward(_forward) {}
2.50 -
2.51 - public:
2.52 - Edge() {}
2.53 -
2.54 - /// Invalid edge constructor
2.55 - Edge(Invalid i) : UndirEdge(i), forward(true) {}
2.56 -
2.57 - bool operator==(const Edge &that) const {
2.58 - return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
2.59 - }
2.60 - bool operator!=(const Edge &that) const {
2.61 - return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
2.62 - }
2.63 - bool operator<(const Edge &that) const {
2.64 - return forward<that.forward ||
2.65 - (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
2.66 - }
2.67 - };
2.68 -
2.69 -
2.70 - /// \brief Edge of opposite direction.
2.71 - ///
2.72 - /// Returns the Edge of opposite direction.
2.73 - Edge oppositeEdge(const Edge &e) const {
2.74 - return Edge(e,!e.forward);
2.75 - }
2.76 -
2.77 - public:
2.78 - /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
2.79 - /// or something???
2.80 - using Parent::source;
2.81 -
2.82 - /// Source of the given Edge.
2.83 - Node source(const Edge &e) const {
2.84 - return e.forward ? Parent::source(e) : Parent::target(e);
2.85 - }
2.86 -
2.87 - /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
2.88 - /// or something???
2.89 - using Parent::target;
2.90 -
2.91 - /// Target of the given Edge.
2.92 - Node target(const Edge &e) const {
2.93 - return e.forward ? Parent::target(e) : Parent::source(e);
2.94 - }
2.95 -
2.96 - Node oppositeNode(const Node &n, const UndirEdge &e) const {
2.97 - if( n == Parent::source(e))
2.98 - return Parent::target(e);
2.99 - else if( n == Parent::target(e))
2.100 - return Parent::source(e);
2.101 - else
2.102 - return INVALID;
2.103 - }
2.104 -
2.105 - /// \brief Directed edge from an undirected edge and a source node.
2.106 - ///
2.107 - /// Returns a (directed) Edge corresponding to the specified UndirEdge
2.108 - /// and source Node.
2.109 - ///
2.110 - Edge direct(const UndirEdge &ue, const Node &s) const {
2.111 - return Edge(ue, s == source(ue));
2.112 - }
2.113 -
2.114 - /// \brief Directed edge from an undirected edge.
2.115 - ///
2.116 - /// Returns a directed edge corresponding to the specified UndirEdge.
2.117 - /// If the given bool is true the given undirected edge and the
2.118 - /// returned edge have the same source node.
2.119 - Edge direct(const UndirEdge &ue, bool d) const {
2.120 - return Edge(ue, d);
2.121 - }
2.122 -
2.123 - /// Returns whether the given directed edge is same orientation as the
2.124 - /// corresponding undirected edge.
2.125 - ///
2.126 - /// \todo reference to the corresponding point of the undirected graph
2.127 - /// concept. "What does the direction of an undirected edge mean?"
2.128 - bool direction(const Edge &e) const { return e.forward; }
2.129 -
2.130 -
2.131 - using Parent::first;
2.132 - void first(Edge &e) const {
2.133 - Parent::first(e);
2.134 - e.forward=true;
2.135 - }
2.136 -
2.137 - using Parent::next;
2.138 - void next(Edge &e) const {
2.139 - if( e.forward ) {
2.140 - e.forward = false;
2.141 - }
2.142 - else {
2.143 - Parent::next(e);
2.144 - e.forward = true;
2.145 - }
2.146 - }
2.147 -
2.148 - public:
2.149 -
2.150 - void firstOut(Edge &e, const Node &n) const {
2.151 - Parent::firstIn(e,n);
2.152 - if( UndirEdge(e) != INVALID ) {
2.153 - e.forward = false;
2.154 - }
2.155 - else {
2.156 - Parent::firstOut(e,n);
2.157 - e.forward = true;
2.158 - }
2.159 - }
2.160 - void nextOut(Edge &e) const {
2.161 - if( ! e.forward ) {
2.162 - Node n = Parent::target(e);
2.163 - Parent::nextIn(e);
2.164 - if( UndirEdge(e) == INVALID ) {
2.165 - Parent::firstOut(e, n);
2.166 - e.forward = true;
2.167 - }
2.168 - }
2.169 - else {
2.170 - Parent::nextOut(e);
2.171 - }
2.172 - }
2.173 -
2.174 - void firstIn(Edge &e, const Node &n) const {
2.175 - Parent::firstOut(e,n);
2.176 - if( UndirEdge(e) != INVALID ) {
2.177 - e.forward = false;
2.178 - }
2.179 - else {
2.180 - Parent::firstIn(e,n);
2.181 - e.forward = true;
2.182 - }
2.183 - }
2.184 - void nextIn(Edge &e) const {
2.185 - if( ! e.forward ) {
2.186 - Node n = Parent::source(e);
2.187 - Parent::nextOut(e);
2.188 - if( UndirEdge(e) == INVALID ) {
2.189 - Parent::firstIn(e, n);
2.190 - e.forward = true;
2.191 - }
2.192 - }
2.193 - else {
2.194 - Parent::nextIn(e);
2.195 - }
2.196 - }
2.197 -
2.198 - void firstInc(UndirEdge &e, const Node &n) const {
2.199 - Parent::firstOut(e, n);
2.200 - if (e != INVALID) return;
2.201 - Parent::firstIn(e, n);
2.202 - }
2.203 - void nextInc(UndirEdge &e, const Node &n) const {
2.204 - if (Parent::source(e) == n) {
2.205 - Parent::nextOut(e);
2.206 - if (e != INVALID) return;
2.207 - Parent::firstIn(e, n);
2.208 - } else {
2.209 - Parent::nextIn(e);
2.210 - }
2.211 - }
2.212 -
2.213 - void firstInc(UndirEdge &e, bool &d, const Node &n) const {
2.214 - d = true;
2.215 - Parent::firstOut(e, n);
2.216 - if (e != INVALID) return;
2.217 - d = false;
2.218 - Parent::firstIn(e, n);
2.219 - }
2.220 - void nextInc(UndirEdge &e, bool &d) const {
2.221 - if (d) {
2.222 - Node s = Parent::source(e);
2.223 - Parent::nextOut(e);
2.224 - if (e != INVALID) return;
2.225 - d = false;
2.226 - Parent::firstIn(e, s);
2.227 - } else {
2.228 - Parent::nextIn(e);
2.229 - }
2.230 - }
2.231 -
2.232 - // Miscellaneous stuff:
2.233 -
2.234 - /// \todo these methods (id, maxEdgeId) should be moved into separate
2.235 - /// Extender
2.236 -
2.237 - // using Parent::id;
2.238 - // Using "using" is not a good idea, cause it could be that there is
2.239 - // no "id" in Parent...
2.240 -
2.241 - int id(const Node &n) const {
2.242 - return Parent::id(n);
2.243 - }
2.244 -
2.245 - int id(const UndirEdge &e) const {
2.246 - return Parent::id(e);
2.247 - }
2.248 -
2.249 - int id(const Edge &e) const {
2.250 - return 2 * Parent::id(e) + int(e.forward);
2.251 - }
2.252 -
2.253 -
2.254 - int maxId(Node) const {
2.255 - return Parent::maxId(Node());
2.256 - }
2.257 -
2.258 - int maxId(Edge) const {
2.259 - return 2 * Parent::maxId(typename Parent::Edge()) + 1;
2.260 - }
2.261 - int maxId(UndirEdge) const {
2.262 - return Parent::maxId(typename Parent::Edge());
2.263 - }
2.264 -
2.265 -
2.266 - int edgeNum() const {
2.267 - return 2 * Parent::edgeNum();
2.268 - }
2.269 -
2.270 - int undirEdgeNum() const {
2.271 - return Parent::edgeNum();
2.272 - }
2.273 -
2.274 - Edge findEdge(Node source, Node target, Edge prev) const {
2.275 - if (prev == INVALID) {
2.276 - UndirEdge edge = Parent::findEdge(source, target);
2.277 - if (edge != INVALID) return direct(edge, true);
2.278 - edge = Parent::findEdge(target, source);
2.279 - if (edge != INVALID) return direct(edge, false);
2.280 - } else if (direction(prev)) {
2.281 - UndirEdge edge = Parent::findEdge(source, target, prev);
2.282 - if (edge != INVALID) return direct(edge, true);
2.283 - edge = Parent::findEdge(target, source);
2.284 - if (edge != INVALID) return direct(edge, false);
2.285 - } else {
2.286 - UndirEdge edge = Parent::findEdge(target, source, prev);
2.287 - if (edge != INVALID) return direct(edge, false);
2.288 - }
2.289 - return INVALID;
2.290 - }
2.291 -
2.292 - UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
2.293 - if (prev == INVALID) {
2.294 - UndirEdge edge = Parent::findEdge(source, target);
2.295 - if (edge != INVALID) return edge;
2.296 - edge = Parent::findEdge(target, source);
2.297 - if (edge != INVALID) return edge;
2.298 - } else if (Parent::source(prev) == source) {
2.299 - UndirEdge edge = Parent::findEdge(source, target, prev);
2.300 - if (edge != INVALID) return edge;
2.301 - edge = Parent::findEdge(target, source);
2.302 - if (edge != INVALID) return edge;
2.303 - } else {
2.304 - UndirEdge edge = Parent::findEdge(target, source, prev);
2.305 - if (edge != INVALID) return edge;
2.306 - }
2.307 - return INVALID;
2.308 - }
2.309 -
2.310 - };
2.311 -
2.312 -}
2.313 -
2.314 -#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
3.1 --- a/lemon/full_graph.h Mon Nov 14 18:36:45 2005 +0000
3.2 +++ b/lemon/full_graph.h Mon Nov 14 18:38:41 2005 +0000
3.3 @@ -23,8 +23,7 @@
3.4 #include <lemon/bits/iterable_graph_extender.h>
3.5 #include <lemon/bits/alteration_notifier.h>
3.6 #include <lemon/bits/static_map.h>
3.7 -
3.8 -#include <lemon/bits/undir_graph_extender.h>
3.9 +#include <lemon/bits/graph_extender.h>
3.10
3.11 #include <lemon/invalid.h>
3.12 #include <lemon/utility.h>
3.13 @@ -70,12 +69,12 @@
3.14
3.15 /// Maximum node ID.
3.16 ///\sa id(Node)
3.17 - int maxId(Node = INVALID) const { return _nodeNum-1; }
3.18 + int maxNodeId() const { return _nodeNum-1; }
3.19 /// Maximum edge ID.
3.20
3.21 /// Maximum edge ID.
3.22 ///\sa id(Edge)
3.23 - int maxId(Edge = INVALID) const { return _edgeNum-1; }
3.24 + int maxEdgeId() const { return _edgeNum-1; }
3.25
3.26 Node source(Edge e) const { return e.id % _nodeNum; }
3.27 Node target(Edge e) const { return e.id / _nodeNum; }
3.28 @@ -101,9 +100,9 @@
3.29 ///\return The ID of the edge \c e.
3.30 static int id(Edge e) { return e.id; }
3.31
3.32 - static Node fromId(int id, Node) { return Node(id);}
3.33 + static Node nodeFromId(int id) { return Node(id);}
3.34
3.35 - static Edge fromId(int id, Edge) { return Edge(id);}
3.36 + static Edge edgeFromId(int id) { return Edge(id);}
3.37
3.38 typedef True FindEdgeTag;
3.39
3.40 @@ -190,14 +189,10 @@
3.41
3.42 };
3.43
3.44 -
3.45 - typedef AlterableGraphExtender<FullGraphBase>
3.46 - AlterableFullGraphBase;
3.47 - typedef IterableGraphExtender<AlterableFullGraphBase>
3.48 - IterableFullGraphBase;
3.49 typedef StaticMappableGraphExtender<
3.50 IterableGraphExtender<
3.51 - AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase;
3.52 + AlterableGraphExtender<
3.53 + GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase;
3.54
3.55 /// \ingroup graphs
3.56 ///
3.57 @@ -217,7 +212,6 @@
3.58 FullGraph(int n) { construct(n); }
3.59 };
3.60
3.61 - ///@}
3.62
3.63 class UndirFullGraphBase {
3.64 int _nodeNum;
3.65 @@ -252,12 +246,12 @@
3.66
3.67 /// Maximum node ID.
3.68 ///\sa id(Node)
3.69 - int maxId(Node = INVALID) const { return _nodeNum-1; }
3.70 + int maxNodeId() const { return _nodeNum-1; }
3.71 /// Maximum edge ID.
3.72
3.73 /// Maximum edge ID.
3.74 ///\sa id(Edge)
3.75 - int maxId(Edge = INVALID) const { return _edgeNum-1; }
3.76 + int maxEdgeId() const { return _edgeNum-1; }
3.77
3.78 Node source(Edge e) const {
3.79 /// \todo we may do it faster
4.1 --- a/lemon/graph_adaptor.h Mon Nov 14 18:36:45 2005 +0000
4.2 +++ b/lemon/graph_adaptor.h Mon Nov 14 18:38:41 2005 +0000
4.3 @@ -33,7 +33,7 @@
4.4 #include <lemon/bits/iterable_graph_extender.h>
4.5 #include <lemon/bits/alteration_notifier.h>
4.6 #include <lemon/bits/default_map.h>
4.7 -#include <lemon/bits/undir_graph_extender.h>
4.8 +#include <lemon/bits/graph_extender.h>
4.9 #include <iostream>
4.10
4.11 namespace lemon {
4.12 @@ -1859,11 +1859,11 @@
4.13 int id(const Node& node) const { return graph->id(node); }
4.14 int id(const Edge& edge) const { return edge.id; }
4.15
4.16 - Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
4.17 - Edge fromId(int id, Edge) const { return Edge(id); }
4.18 + Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
4.19 + Edge edgeFromId(int id) const { return Edge(id); }
4.20
4.21 - int maxId(Node) const { return graph->maxId(Node()); };
4.22 - int maxId(Edge) const { return edges.size() - 1; }
4.23 + int maxNodeId() const { return graph->maxId(Node()); };
4.24 + int maxEdgeId() const { return edges.size() - 1; }
4.25
4.26 Node source(const Edge& edge) const { return edges[edge.id].source;}
4.27 Node target(const Edge& edge) const { return edges[edge.id].target;}
5.1 --- a/lemon/grid_graph.h Mon Nov 14 18:36:45 2005 +0000
5.2 +++ b/lemon/grid_graph.h Mon Nov 14 18:38:41 2005 +0000
5.3 @@ -24,8 +24,7 @@
5.4 #include <lemon/bits/iterable_graph_extender.h>
5.5 #include <lemon/bits/alteration_notifier.h>
5.6 #include <lemon/bits/static_map.h>
5.7 -
5.8 -#include <lemon/bits/undir_graph_extender.h>
5.9 +#include <lemon/bits/graph_extender.h>
5.10
5.11 #include <lemon/xy.h>
5.12
5.13 @@ -164,12 +163,12 @@
5.14
5.15 /// Maximum node ID.
5.16 ///\sa id(Node)
5.17 - int maxId(Node = INVALID) const { return nodeNum() - 1; }
5.18 + int maxNodeId() const { return nodeNum() - 1; }
5.19 /// Maximum edge ID.
5.20
5.21 /// Maximum edge ID.
5.22 ///\sa id(Edge)
5.23 - int maxId(Edge = INVALID) const { return edgeNum() - 1; }
5.24 + int maxEdgeId() const { return edgeNum() - 1; }
5.25
5.26 /// \brief Gives back the source node of an edge.
5.27 ///
5.28 @@ -215,9 +214,9 @@
5.29 ///\return The ID of the edge \c e.
5.30 static int id(Edge e) { return e.id; }
5.31
5.32 - static Node fromId(int id, Node) { return Node(id);}
5.33 + static Node nodeFromId(int id) { return Node(id);}
5.34
5.35 - static Edge fromId(int id, Edge) { return Edge(id);}
5.36 + static Edge edgeFromId(int id) { return Edge(id);}
5.37
5.38 typedef True FindEdgeTag;
5.39
5.40 @@ -358,8 +357,8 @@
5.41 /// \code
5.42 /// GridGraph graph(h, w);
5.43 /// GridGraph::NodeMap<int> val(graph);
5.44 - /// for (int i = 0; i < graph.height(); ++i) {
5.45 - /// for (int j = 0; j < graph.width(); ++j) {
5.46 + /// for (int i = 0; i < graph.width(); ++i) {
5.47 + /// for (int j = 0; j < graph.height(); ++j) {
5.48 /// val[graph(i, j)] = i + j;
5.49 /// }
5.50 /// }
5.51 @@ -503,14 +502,14 @@
5.52
5.53 /// \brief Row map of the grid graph
5.54 ///
5.55 - /// Just returns an RowMap for the grid graph.
5.56 + /// Just returns a RowMap for the grid graph.
5.57 GridGraph::RowMap rowMap(const GridGraph& graph) {
5.58 return GridGraph::RowMap(graph);
5.59 }
5.60
5.61 - /// \brief Coloumn map of the grid graph
5.62 + /// \brief Column map of the grid graph
5.63 ///
5.64 - /// Just returns an ColMap for the grid graph.
5.65 + /// Just returns a ColMap for the grid graph.
5.66 GridGraph::ColMap colMap(const GridGraph& graph) {
5.67 return GridGraph::ColMap(graph);
5.68 }
6.1 --- a/lemon/hypercube_graph.h Mon Nov 14 18:36:45 2005 +0000
6.2 +++ b/lemon/hypercube_graph.h Mon Nov 14 18:38:41 2005 +0000
6.3 @@ -21,10 +21,12 @@
6.4 #include <vector>
6.5 #include <lemon/invalid.h>
6.6 #include <lemon/utility.h>
6.7 +#include <lemon/error.h>
6.8
6.9 #include <lemon/bits/iterable_graph_extender.h>
6.10 #include <lemon/bits/alteration_notifier.h>
6.11 #include <lemon/bits/default_map.h>
6.12 +#include <lemon/bits/graph_extender.h>
6.13
6.14 ///\ingroup graphs
6.15 ///\file
6.16 @@ -32,7 +34,7 @@
6.17
6.18 namespace lemon {
6.19
6.20 - /// \brief Base graph for HyperGraph.
6.21 + /// \brief Base graph for HyperCubeGraph.
6.22 ///
6.23 /// Base graph for hyper-cube graph. It describes some member functions
6.24 /// which can be used in the HyperCubeGraph.
6.25 @@ -77,12 +79,12 @@
6.26
6.27 /// Maximum node ID.
6.28 ///\sa id(Node)
6.29 - int maxId(Node = INVALID) const { return nodeNum() - 1; }
6.30 + int maxNodeId() const { return nodeNum() - 1; }
6.31 /// Maximum edge ID.
6.32
6.33 /// Maximum edge ID.
6.34 ///\sa id(Edge)
6.35 - int maxId(Edge = INVALID) const { return edgeNum() - 1; }
6.36 + int maxEdgeId() const { return edgeNum() - 1; }
6.37
6.38 /// \brief Gives back the source node of an edge.
6.39 ///
6.40 @@ -118,9 +120,9 @@
6.41 ///\return The ID of the edge \c e.
6.42 static int id(Edge e) { return e.id; }
6.43
6.44 - static Node fromId(int id, Node) { return Node(id);}
6.45 + static Node nodeFromId(int id) { return Node(id);}
6.46
6.47 - static Edge fromId(int id, Edge) { return Edge(id);}
6.48 + static Edge edgeFromId(int id) { return Edge(id);}
6.49
6.50 class Node {
6.51 friend class HyperCubeGraphBase;
6.52 @@ -235,7 +237,8 @@
6.53 typedef StaticMappableGraphExtender<
6.54 IterableGraphExtender<
6.55 AlterableGraphExtender<
6.56 - HyperCubeGraphBase > > > ExtendedHyperCubeGraphBase;
6.57 + GraphExtender<
6.58 + HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase;
6.59
6.60 /// \ingroup graphs
6.61 ///
6.62 @@ -307,7 +310,8 @@
6.63 HyperMap(const Graph& graph, It begin, It end,
6.64 T fv = 0.0, const BF& bf = BF())
6.65 : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {
6.66 - if (_values.size() != graph.dimension()) {}
6.67 + LEMON_ASSERT(_values.size() != graph.dimension(),
6.68 + "Wrong size of dimension");
6.69 }
6.70
6.71 /// \brief Gives back the partial accumulated value.
7.1 --- a/lemon/list_graph.h Mon Nov 14 18:36:45 2005 +0000
7.2 +++ b/lemon/list_graph.h Mon Nov 14 18:38:41 2005 +0000
7.3 @@ -27,8 +27,7 @@
7.4 #include <lemon/bits/iterable_graph_extender.h>
7.5 #include <lemon/bits/alteration_notifier.h>
7.6 #include <lemon/bits/default_map.h>
7.7 -
7.8 -#include <lemon/bits/undir_graph_extender.h>
7.9 +#include <lemon/bits/graph_extender.h>
7.10
7.11 #include <lemon/error.h>
7.12
7.13 @@ -105,13 +104,13 @@
7.14
7.15 /// Maximum node ID.
7.16 ///\sa id(Node)
7.17 - int maxId(Node = INVALID) const { return nodes.size()-1; }
7.18 + int maxNodeId() const { return nodes.size()-1; }
7.19
7.20 /// Maximum edge ID.
7.21
7.22 /// Maximum edge ID.
7.23 ///\sa id(Edge)
7.24 - int maxId(Edge = INVALID) const { return edges.size()-1; }
7.25 + int maxEdgeId() const { return edges.size()-1; }
7.26
7.27 Node source(Edge e) const { return edges[e.id].source; }
7.28 Node target(Edge e) const { return edges[e.id].target; }
7.29 @@ -164,8 +163,8 @@
7.30 static int id(Node v) { return v.id; }
7.31 static int id(Edge e) { return e.id; }
7.32
7.33 - static Node fromId(int id, Node) { return Node(id);}
7.34 - static Edge fromId(int id, Edge) { return Edge(id);}
7.35 + static Node nodeFromId(int id) { return Node(id);}
7.36 + static Edge edgeFromId(int id) { return Edge(id);}
7.37
7.38 /// Adds a new node to the graph.
7.39
7.40 @@ -315,7 +314,8 @@
7.41 ExtendableGraphExtender<
7.42 MappableGraphExtender<
7.43 IterableGraphExtender<
7.44 - AlterableGraphExtender<ListGraphBase> > > > > > ExtendedListGraphBase;
7.45 + AlterableGraphExtender<
7.46 + GraphExtender<ListGraphBase> > > > > > > ExtendedListGraphBase;
7.47
7.48 /// \addtogroup graphs
7.49 /// @{
8.1 --- a/lemon/smart_graph.h Mon Nov 14 18:36:45 2005 +0000
8.2 +++ b/lemon/smart_graph.h Mon Nov 14 18:38:41 2005 +0000
8.3 @@ -30,8 +30,7 @@
8.4 #include <lemon/bits/iterable_graph_extender.h>
8.5 #include <lemon/bits/alteration_notifier.h>
8.6 #include <lemon/bits/default_map.h>
8.7 -
8.8 -#include <lemon/bits/undir_graph_extender.h>
8.9 +#include <lemon/bits/graph_extender.h>
8.10
8.11 #include <lemon/utility.h>
8.12
8.13 @@ -90,12 +89,12 @@
8.14
8.15 /// Maximum node ID.
8.16 ///\sa id(Node)
8.17 - int maxId(Node) const { return nodes.size()-1; }
8.18 + int maxNodeId() const { return nodes.size()-1; }
8.19 /// Maximum edge ID.
8.20
8.21 /// Maximum edge ID.
8.22 ///\sa id(Edge)
8.23 - int maxId(Edge) const { return edges.size()-1; }
8.24 + int maxEdgeId() const { return edges.size()-1; }
8.25
8.26 Node source(Edge e) const { return edges[e.n].source; }
8.27 Node target(Edge e) const { return edges[e.n].target; }
8.28 @@ -103,8 +102,8 @@
8.29 /// Node ID.
8.30
8.31 /// The ID of a valid Node is a nonnegative integer not greater than
8.32 - /// \ref maxId(Node). The range of the ID's is not surely continuous
8.33 - /// and the greatest node ID can be actually less then \ref maxId(Node).
8.34 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
8.35 + /// and the greatest node ID can be actually less then \ref maxNodeId().
8.36 ///
8.37 /// The ID of the \ref INVALID node is -1.
8.38 ///\return The ID of the node \c v.
8.39 @@ -112,16 +111,16 @@
8.40 /// Edge ID.
8.41
8.42 /// The ID of a valid Edge is a nonnegative integer not greater than
8.43 - /// \ref maxId(Edge). The range of the ID's is not surely continuous
8.44 - /// and the greatest edge ID can be actually less then \ref maxId(Edge).
8.45 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
8.46 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
8.47 ///
8.48 /// The ID of the \ref INVALID edge is -1.
8.49 ///\return The ID of the edge \c e.
8.50 static int id(Edge e) { return e.n; }
8.51
8.52 - static Node fromId(int id, Node) { return Node(id);}
8.53 + static Node nodeFromId(int id) { return Node(id);}
8.54
8.55 - static Edge fromId(int id, Edge) { return Edge(id);}
8.56 + static Edge edgeFromId(int id) { return Edge(id);}
8.57
8.58 Node addNode() {
8.59 Node n; n.n=nodes.size();
8.60 @@ -151,10 +150,6 @@
8.61
8.62 protected:
8.63 int n;
8.64 - ///\e
8.65 -
8.66 - ///\todo It should be removed (or at least define a setToId() instead).
8.67 - ///
8.68 Node(int nn) {n=nn;}
8.69 public:
8.70 Node() {}
8.71 @@ -171,8 +166,6 @@
8.72
8.73 protected:
8.74 int n;
8.75 - ///\todo It should be removed (or at least define a setToId() instead).
8.76 - ///
8.77 Edge(int nn) {n=nn;}
8.78 public:
8.79 Edge() { }
8.80 @@ -230,10 +223,10 @@
8.81 ExtendableGraphExtender<
8.82 MappableGraphExtender<
8.83 IterableGraphExtender<
8.84 - AlterableGraphExtender<SmartGraphBase> > > > > ExtendedSmartGraphBase;
8.85 + AlterableGraphExtender<
8.86 + GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
8.87
8.88 - /// \addtogroup graphs
8.89 - /// @{
8.90 + /// \ingroup graphs
8.91
8.92 ///A smart graph class.
8.93