1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/undir_graph_extender.h Fri Nov 05 00:31:49 2004 +0000
1.3 @@ -0,0 +1,193 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
1.7 + * optimization library
1.8 + *
1.9 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
1.10 + * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
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 Graph;
1.42 +
1.43 + protected:
1.44 + // FIXME: Marci use opposite logic in his graph wrappers. It would
1.45 + // be reasonable to syncronize...
1.46 + bool forward;
1.47 +
1.48 + public:
1.49 + Edge() {}
1.50 + /// Construct a direct edge from undirect edge and a direction.
1.51 + Edge(const UndirEdge &ue, bool _forward) :
1.52 + UndirEdge(ue), forward(_forward) {}
1.53 + /// Invalid edge constructor
1.54 + Edge(Invalid i) : UndirEdge(i), forward(false) {}
1.55 +
1.56 + bool operator==(const Edge &that) const {
1.57 + return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
1.58 + }
1.59 + bool operator!=(const Edge &that) const {
1.60 + return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
1.61 + }
1.62 + bool operator<(const Edge &that) const {
1.63 + return forward<that.forward ||
1.64 + (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
1.65 + }
1.66 + };
1.67 +
1.68 +
1.69 + /// \brief Returns the Edge of opposite direction.
1.70 + ///
1.71 + /// \bug Is this a good name for this? Or "reverse" is better?
1.72 + Edge opposite(const Edge &e) const {
1.73 + return Edge(e,!e.forward);
1.74 + }
1.75 +
1.76 + /// Tail of the given Edge.
1.77 + Node tail(const Edge &e) const {
1.78 + return e.forward ? Parent::tail(e) : Parent::head(e);
1.79 + }
1.80 +
1.81 + /// \todo Shouldn't the "tail" of an undirected edge be called "aNode"
1.82 + /// or something???
1.83 + using Parent::tail;
1.84 +
1.85 + /// Head of the given Edge.
1.86 + Node head(const Edge &e) const {
1.87 + return e.forward ? Parent::head(e) : Parent::tail(e);
1.88 + }
1.89 +
1.90 + /// \todo Shouldn't the "head" of an undirected edge be called "bNode"
1.91 + /// or something???
1.92 + using Parent::head;
1.93 +
1.94 + /// Returns whether the given directed edge is same orientation as the
1.95 + /// corresponding undirected edge.
1.96 + ///
1.97 + /// \todo reference to the corresponding point of the undirected graph
1.98 + /// concept. "What does the direction of an undirected edge mean?"
1.99 + bool forward(const Edge &e) const { return e.forward; }
1.100 +
1.101 + Node oppsiteNode(const Node &n, const Edge &e) const {
1.102 + if( n == Parent::tail(e))
1.103 + return Parent::head(e);
1.104 + else if( n == Parent::head(e))
1.105 + return Parent::tail(e);
1.106 + else
1.107 + return INVALID;
1.108 + }
1.109 +
1.110 +
1.111 + using Parent::first;
1.112 + void first(Edge &e) const {
1.113 + Parent::first(e);
1.114 + e.forward=true;
1.115 + }
1.116 +
1.117 + using Parent::next;
1.118 + void next(Edge &e) const {
1.119 + if( e.forward ) {
1.120 + e.forward = false;
1.121 + }
1.122 + else {
1.123 + Parent::next(e);
1.124 + e.forward = true;
1.125 + }
1.126 + }
1.127 +
1.128 + void firstOut(Edge &e, const Node &n) const {
1.129 + Parent::firstOut(e,n);
1.130 + if( UndirEdge(e) != INVALID ) {
1.131 + e.forward = true;
1.132 + }
1.133 + else {
1.134 + Parent::firstIn(e,n);
1.135 + e.forward = false;
1.136 + }
1.137 + }
1.138 + void firstIn(Edge &e, const Node &n) const {
1.139 + Parent::firstIn(e,n);
1.140 + if( UndirEdge(e) != INVALID ) {
1.141 + e.forward = true;
1.142 + }
1.143 + else {
1.144 + Parent::firstOut(e,n);
1.145 + e.forward = false;
1.146 + }
1.147 + }
1.148 +
1.149 + void nextOut(Edge &e) const {
1.150 + if( e.forward ) {
1.151 + Parent::nextOut(e);
1.152 + if( UndirEdge(e) == INVALID ) {
1.153 + Parent::firstIn(e, Parent::tail(e));
1.154 + e.forward = false;
1.155 + }
1.156 + }
1.157 + else {
1.158 + Parent::nextIn(e);
1.159 + }
1.160 + }
1.161 + void nextIn(Edge &e) const {
1.162 + if( e.forward ) {
1.163 + Parent::nextIn(e);
1.164 + if( UndirEdge(e) == INVALID ) {
1.165 + Parent::firstOut(e, Parent::head(e));
1.166 + e.forward = false;
1.167 + }
1.168 + }
1.169 + else {
1.170 + Parent::nextOut(e);
1.171 + }
1.172 + }
1.173 +
1.174 + // Miscellaneous stuff:
1.175 +
1.176 + /// \todo these methods (id, maxEdgeId) should be moved into separate
1.177 + /// Extender
1.178 +
1.179 + using Parent::id;
1.180 +
1.181 + int id(const Edge &e) const {
1.182 + return 2*Parent::id(e) + int(e.forward);
1.183 + }
1.184 +
1.185 + int maxEdgeId() const {
1.186 + return 2*Parent::maxEdgeId() + 1;
1.187 + }
1.188 + int maxUndirEdgeId() const {
1.189 + return Parent::maxEdgeId();
1.190 + }
1.191 +
1.192 + };
1.193 +
1.194 +}
1.195 +
1.196 +#endif // LEMON_UNDIR_GRAPH_EXTENDER_H