1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/undir_graph_extender.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,278 @@
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 + public:
1.49 + Edge() {}
1.50 +
1.51 + /// \brief Directed edge from undirected edge and a direction.
1.52 + ///
1.53 + /// This constructor is not a part of the concept interface of
1.54 + /// undirected graph, so please avoid using it if possible!
1.55 + Edge(const UndirEdge &ue, bool _forward) :
1.56 + UndirEdge(ue), forward(_forward) {}
1.57 +
1.58 + /// \brief Directed edge from undirected edge and a source node.
1.59 + ///
1.60 + /// Constructs a directed edge from undirected edge and a source node.
1.61 + ///
1.62 + /// \note You have to specify the graph for this constructor.
1.63 + Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
1.64 + UndirEdge(ue) { forward = (g.source(ue) == n); }
1.65 +
1.66 + /// Invalid edge constructor
1.67 + Edge(Invalid i) : UndirEdge(i), forward(true) {}
1.68 +
1.69 + bool operator==(const Edge &that) const {
1.70 + return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
1.71 + }
1.72 + bool operator!=(const Edge &that) const {
1.73 + return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
1.74 + }
1.75 + bool operator<(const Edge &that) const {
1.76 + return forward<that.forward ||
1.77 + (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
1.78 + }
1.79 + };
1.80 +
1.81 +
1.82 + /// \brief Edge of opposite direction.
1.83 + ///
1.84 + /// Returns the Edge of opposite direction.
1.85 + Edge opposite(const Edge &e) const {
1.86 + return Edge(e,!e.forward);
1.87 + }
1.88 +
1.89 + protected:
1.90 +
1.91 + template <typename E>
1.92 + Node _dirSource(const E &e) const {
1.93 + return e.forward ? Parent::source(e) : Parent::target(e);
1.94 + }
1.95 +
1.96 + template <typename E>
1.97 + Node _dirTarget(const E &e) const {
1.98 + return e.forward ? Parent::target(e) : Parent::source(e);
1.99 + }
1.100 +
1.101 + public:
1.102 + /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
1.103 + /// or something???
1.104 + using Parent::source;
1.105 +
1.106 + /// Source of the given Edge.
1.107 + Node source(const Edge &e) const {
1.108 + return _dirSource(e);
1.109 + }
1.110 +
1.111 + /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
1.112 + /// or something???
1.113 + using Parent::target;
1.114 +
1.115 + /// Target of the given Edge.
1.116 + Node target(const Edge &e) const {
1.117 + return _dirTarget(e);
1.118 + }
1.119 +
1.120 + /// Returns whether the given directed edge is same orientation as the
1.121 + /// corresponding undirected edge.
1.122 + ///
1.123 + /// \todo reference to the corresponding point of the undirected graph
1.124 + /// concept. "What does the direction of an undirected edge mean?"
1.125 + bool forward(const Edge &e) const { return e.forward; }
1.126 +
1.127 + Node oppositeNode(const Node &n, const UndirEdge &e) const {
1.128 + if( n == Parent::source(e))
1.129 + return Parent::target(e);
1.130 + else if( n == Parent::target(e))
1.131 + return Parent::source(e);
1.132 + else
1.133 + return INVALID;
1.134 + }
1.135 +
1.136 + /// Directed edge from an undirected edge and a source node.
1.137 + ///
1.138 + /// Returns a (directed) Edge corresponding to the specified UndirEdge
1.139 + /// and source Node.
1.140 + ///
1.141 + ///\todo Do we need this?
1.142 + ///
1.143 + ///\todo Better name...
1.144 + Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
1.145 + return Edge(*this, ue, s);
1.146 + }
1.147 +
1.148 + using Parent::first;
1.149 + void first(Edge &e) const {
1.150 + Parent::first(e);
1.151 + e.forward=true;
1.152 + }
1.153 +
1.154 + using Parent::next;
1.155 + void next(Edge &e) const {
1.156 + if( e.forward ) {
1.157 + e.forward = false;
1.158 + }
1.159 + else {
1.160 + Parent::next(e);
1.161 + e.forward = true;
1.162 + }
1.163 + }
1.164 +
1.165 +
1.166 + protected:
1.167 +
1.168 + template <typename E>
1.169 + void _dirFirstOut(E &e, const Node &n) const {
1.170 + Parent::firstIn(e,n);
1.171 + if( UndirEdge(e) != INVALID ) {
1.172 + e.forward = false;
1.173 + }
1.174 + else {
1.175 + Parent::firstOut(e,n);
1.176 + e.forward = true;
1.177 + }
1.178 + }
1.179 + template <typename E>
1.180 + void _dirFirstIn(E &e, const Node &n) const {
1.181 + Parent::firstOut(e,n);
1.182 + if( UndirEdge(e) != INVALID ) {
1.183 + e.forward = false;
1.184 + }
1.185 + else {
1.186 + Parent::firstIn(e,n);
1.187 + e.forward = true;
1.188 + }
1.189 + }
1.190 +
1.191 + template <typename E>
1.192 + void _dirNextOut(E &e) const {
1.193 + if( ! e.forward ) {
1.194 + Node n = Parent::target(e);
1.195 + Parent::nextIn(e);
1.196 + if( UndirEdge(e) == INVALID ) {
1.197 + Parent::firstOut(e, n);
1.198 + e.forward = true;
1.199 + }
1.200 + }
1.201 + else {
1.202 + Parent::nextOut(e);
1.203 + }
1.204 + }
1.205 + template <typename E>
1.206 + void _dirNextIn(E &e) const {
1.207 + if( ! e.forward ) {
1.208 + Node n = Parent::source(e);
1.209 + Parent::nextOut(e);
1.210 + if( UndirEdge(e) == INVALID ) {
1.211 + Parent::firstIn(e, n);
1.212 + e.forward = true;
1.213 + }
1.214 + }
1.215 + else {
1.216 + Parent::nextIn(e);
1.217 + }
1.218 + }
1.219 +
1.220 + public:
1.221 +
1.222 + void firstOut(Edge &e, const Node &n) const {
1.223 + _dirFirstOut(e, n);
1.224 + }
1.225 + void firstIn(Edge &e, const Node &n) const {
1.226 + _dirFirstIn(e, n);
1.227 + }
1.228 +
1.229 + void nextOut(Edge &e) const {
1.230 + _dirNextOut(e);
1.231 + }
1.232 + void nextIn(Edge &e) const {
1.233 + _dirNextIn(e);
1.234 + }
1.235 +
1.236 + // Miscellaneous stuff:
1.237 +
1.238 + /// \todo these methods (id, maxEdgeId) should be moved into separate
1.239 + /// Extender
1.240 +
1.241 + // using Parent::id;
1.242 + // Using "using" is not a good idea, cause it could be that there is
1.243 + // no "id" in Parent...
1.244 +
1.245 + int id(const Node &n) const {
1.246 + return Parent::id(n);
1.247 + }
1.248 +
1.249 + int id(const UndirEdge &e) const {
1.250 + return Parent::id(e);
1.251 + }
1.252 +
1.253 + int id(const Edge &e) const {
1.254 + return 2 * Parent::id(e) + int(e.forward);
1.255 + }
1.256 +
1.257 +
1.258 + int maxId(Node) const {
1.259 + return Parent::maxId(Node());
1.260 + }
1.261 +
1.262 + int maxId(Edge) const {
1.263 + return 2 * Parent::maxId(typename Parent::Edge()) + 1;
1.264 + }
1.265 + int maxId(UndirEdge) const {
1.266 + return Parent::maxId(typename Parent::Edge());
1.267 + }
1.268 +
1.269 +
1.270 + int edgeNum() const {
1.271 + return 2 * Parent::edgeNum();
1.272 + }
1.273 + int undirEdgeNum() const {
1.274 + return Parent::edgeNum();
1.275 + }
1.276 +
1.277 + };
1.278 +
1.279 +}
1.280 +
1.281 +#endif // LEMON_UNDIR_GRAPH_EXTENDER_H