00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
00021 #define LEMON_UNDIR_GRAPH_EXTENDER_H
00022
00023 #include <lemon/invalid.h>
00024
00025 namespace lemon {
00026
00027 template <typename _Base>
00028 class UndirGraphExtender : public _Base {
00029 typedef _Base Parent;
00030 typedef UndirGraphExtender Graph;
00031
00032 public:
00033
00034 typedef typename Parent::Edge UndirEdge;
00035 typedef typename Parent::Node Node;
00036
00037 class Edge : public UndirEdge {
00038 friend class UndirGraphExtender;
00039
00040 protected:
00041
00042
00043 bool forward;
00044
00045 public:
00046 Edge() {}
00047
00052 Edge(const UndirEdge &ue, bool _forward) :
00053 UndirEdge(ue), forward(_forward) {}
00054
00060 Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
00061 UndirEdge(ue) { forward = (g.source(ue) == n); }
00062
00064 Edge(Invalid i) : UndirEdge(i), forward(true) {}
00065
00066 bool operator==(const Edge &that) const {
00067 return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
00068 }
00069 bool operator!=(const Edge &that) const {
00070 return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
00071 }
00072 bool operator<(const Edge &that) const {
00073 return forward<that.forward ||
00074 (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
00075 }
00076 };
00077
00078
00082 Edge opposite(const Edge &e) const {
00083 return Edge(e,!e.forward);
00084 }
00085
00086 protected:
00087
00088 template <typename E>
00089 Node _dirSource(const E &e) const {
00090 return e.forward ? Parent::source(e) : Parent::target(e);
00091 }
00092
00093 template <typename E>
00094 Node _dirTarget(const E &e) const {
00095 return e.forward ? Parent::target(e) : Parent::source(e);
00096 }
00097
00098 public:
00101 using Parent::source;
00102
00104 Node source(const Edge &e) const {
00105 return _dirSource(e);
00106 }
00107
00110 using Parent::target;
00111
00113 Node target(const Edge &e) const {
00114 return _dirTarget(e);
00115 }
00116
00122 bool forward(const Edge &e) const { return e.forward; }
00123
00124 Node oppositeNode(const Node &n, const UndirEdge &e) const {
00125 if( n == Parent::source(e))
00126 return Parent::target(e);
00127 else if( n == Parent::target(e))
00128 return Parent::source(e);
00129 else
00130 return INVALID;
00131 }
00132
00141 Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
00142 return Edge(*this, eu, s);
00143 }
00144
00145 using Parent::first;
00146 void first(Edge &e) const {
00147 Parent::first(e);
00148 e.forward=true;
00149 }
00150
00151 using Parent::next;
00152 void next(Edge &e) const {
00153 if( e.forward ) {
00154 e.forward = false;
00155 }
00156 else {
00157 Parent::next(e);
00158 e.forward = true;
00159 }
00160 }
00161
00162
00163 protected:
00164
00165 template <typename E>
00166 void _dirFirstOut(E &e, const Node &n) const {
00167 Parent::firstIn(e,n);
00168 if( UndirEdge(e) != INVALID ) {
00169 e.forward = false;
00170 }
00171 else {
00172 Parent::firstOut(e,n);
00173 e.forward = true;
00174 }
00175 }
00176 template <typename E>
00177 void _dirFirstIn(E &e, const Node &n) const {
00178 Parent::firstOut(e,n);
00179 if( UndirEdge(e) != INVALID ) {
00180 e.forward = false;
00181 }
00182 else {
00183 Parent::firstIn(e,n);
00184 e.forward = true;
00185 }
00186 }
00187
00188 template <typename E>
00189 void _dirNextOut(E &e) const {
00190 if( ! e.forward ) {
00191 Node n = Parent::target(e);
00192 Parent::nextIn(e);
00193 if( UndirEdge(e) == INVALID ) {
00194 Parent::firstOut(e, n);
00195 e.forward = true;
00196 }
00197 }
00198 else {
00199 Parent::nextOut(e);
00200 }
00201 }
00202 template <typename E>
00203 void _dirNextIn(E &e) const {
00204 if( ! e.forward ) {
00205 Node n = Parent::source(e);
00206 Parent::nextOut(e);
00207 if( UndirEdge(e) == INVALID ) {
00208 Parent::firstIn(e, n);
00209 e.forward = true;
00210 }
00211 }
00212 else {
00213 Parent::nextIn(e);
00214 }
00215 }
00216
00217 public:
00218
00219 void firstOut(Edge &e, const Node &n) const {
00220 _dirFirstOut(e, n);
00221 }
00222 void firstIn(Edge &e, const Node &n) const {
00223 _dirFirstIn(e, n);
00224 }
00225
00226 void nextOut(Edge &e) const {
00227 _dirNextOut(e);
00228 }
00229 void nextIn(Edge &e) const {
00230 _dirNextIn(e);
00231 }
00232
00233
00234
00237
00238
00239
00240
00241
00242 int id(const Node &n) const {
00243 return Parent::id(n);
00244 }
00245
00246 int id(const UndirEdge &e) const {
00247 return Parent::id(e);
00248 }
00249
00250 int id(const Edge &e) const {
00251 return 2 * Parent::id(e) + int(e.forward);
00252 }
00253
00254
00255 int maxId(Node) const {
00256 return Parent::maxId(Node());
00257 }
00258
00259 int maxId(Edge) const {
00260 return 2 * Parent::maxId(typename Parent::Edge()) + 1;
00261 }
00262 int maxId(UndirEdge) const {
00263 return Parent::maxId(typename Parent::Edge());
00264 }
00265
00266
00267 int edgeNum() const {
00268 return 2 * Parent::edgeNum();
00269 }
00270 int undirEdgeNum() const {
00271 return Parent::edgeNum();
00272 }
00273
00274 };
00275
00276 }
00277
00278 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H