[432] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
[430] | 2 | * |
---|
[432] | 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
[430] | 4 | * |
---|
[463] | 5 | * Copyright (C) 2003-2009 |
---|
[430] | 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | #ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H |
---|
| 20 | #define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H |
---|
| 21 | |
---|
| 22 | #include <lemon/core.h> |
---|
| 23 | #include <lemon/error.h> |
---|
| 24 | |
---|
| 25 | namespace lemon { |
---|
| 26 | |
---|
| 27 | template <typename _Digraph> |
---|
| 28 | class DigraphAdaptorExtender : public _Digraph { |
---|
| 29 | public: |
---|
| 30 | |
---|
| 31 | typedef _Digraph Parent; |
---|
| 32 | typedef _Digraph Digraph; |
---|
| 33 | typedef DigraphAdaptorExtender Adaptor; |
---|
| 34 | |
---|
| 35 | // Base extensions |
---|
| 36 | |
---|
| 37 | typedef typename Parent::Node Node; |
---|
| 38 | typedef typename Parent::Arc Arc; |
---|
| 39 | |
---|
| 40 | int maxId(Node) const { |
---|
| 41 | return Parent::maxNodeId(); |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | int maxId(Arc) const { |
---|
| 45 | return Parent::maxArcId(); |
---|
| 46 | } |
---|
| 47 | |
---|
| 48 | Node fromId(int id, Node) const { |
---|
| 49 | return Parent::nodeFromId(id); |
---|
| 50 | } |
---|
| 51 | |
---|
| 52 | Arc fromId(int id, Arc) const { |
---|
| 53 | return Parent::arcFromId(id); |
---|
| 54 | } |
---|
| 55 | |
---|
| 56 | Node oppositeNode(const Node &n, const Arc &e) const { |
---|
| 57 | if (n == Parent::source(e)) |
---|
[432] | 58 | return Parent::target(e); |
---|
[430] | 59 | else if(n==Parent::target(e)) |
---|
[432] | 60 | return Parent::source(e); |
---|
[430] | 61 | else |
---|
[432] | 62 | return INVALID; |
---|
[430] | 63 | } |
---|
| 64 | |
---|
[432] | 65 | class NodeIt : public Node { |
---|
[430] | 66 | const Adaptor* _adaptor; |
---|
| 67 | public: |
---|
| 68 | |
---|
| 69 | NodeIt() {} |
---|
| 70 | |
---|
| 71 | NodeIt(Invalid i) : Node(i) { } |
---|
| 72 | |
---|
| 73 | explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
---|
[432] | 74 | _adaptor->first(static_cast<Node&>(*this)); |
---|
[430] | 75 | } |
---|
| 76 | |
---|
[432] | 77 | NodeIt(const Adaptor& adaptor, const Node& node) |
---|
| 78 | : Node(node), _adaptor(&adaptor) {} |
---|
[430] | 79 | |
---|
[432] | 80 | NodeIt& operator++() { |
---|
| 81 | _adaptor->next(*this); |
---|
| 82 | return *this; |
---|
[430] | 83 | } |
---|
| 84 | |
---|
| 85 | }; |
---|
| 86 | |
---|
| 87 | |
---|
[432] | 88 | class ArcIt : public Arc { |
---|
[430] | 89 | const Adaptor* _adaptor; |
---|
| 90 | public: |
---|
| 91 | |
---|
| 92 | ArcIt() { } |
---|
| 93 | |
---|
| 94 | ArcIt(Invalid i) : Arc(i) { } |
---|
| 95 | |
---|
| 96 | explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
---|
[432] | 97 | _adaptor->first(static_cast<Arc&>(*this)); |
---|
[430] | 98 | } |
---|
| 99 | |
---|
[432] | 100 | ArcIt(const Adaptor& adaptor, const Arc& e) : |
---|
| 101 | Arc(e), _adaptor(&adaptor) { } |
---|
[430] | 102 | |
---|
[432] | 103 | ArcIt& operator++() { |
---|
| 104 | _adaptor->next(*this); |
---|
| 105 | return *this; |
---|
[430] | 106 | } |
---|
| 107 | |
---|
| 108 | }; |
---|
| 109 | |
---|
| 110 | |
---|
[432] | 111 | class OutArcIt : public Arc { |
---|
[430] | 112 | const Adaptor* _adaptor; |
---|
| 113 | public: |
---|
| 114 | |
---|
| 115 | OutArcIt() { } |
---|
| 116 | |
---|
| 117 | OutArcIt(Invalid i) : Arc(i) { } |
---|
| 118 | |
---|
[432] | 119 | OutArcIt(const Adaptor& adaptor, const Node& node) |
---|
| 120 | : _adaptor(&adaptor) { |
---|
| 121 | _adaptor->firstOut(*this, node); |
---|
[430] | 122 | } |
---|
| 123 | |
---|
[432] | 124 | OutArcIt(const Adaptor& adaptor, const Arc& arc) |
---|
| 125 | : Arc(arc), _adaptor(&adaptor) {} |
---|
[430] | 126 | |
---|
[432] | 127 | OutArcIt& operator++() { |
---|
| 128 | _adaptor->nextOut(*this); |
---|
| 129 | return *this; |
---|
[430] | 130 | } |
---|
| 131 | |
---|
| 132 | }; |
---|
| 133 | |
---|
| 134 | |
---|
[432] | 135 | class InArcIt : public Arc { |
---|
[430] | 136 | const Adaptor* _adaptor; |
---|
| 137 | public: |
---|
| 138 | |
---|
| 139 | InArcIt() { } |
---|
| 140 | |
---|
| 141 | InArcIt(Invalid i) : Arc(i) { } |
---|
| 142 | |
---|
[432] | 143 | InArcIt(const Adaptor& adaptor, const Node& node) |
---|
| 144 | : _adaptor(&adaptor) { |
---|
| 145 | _adaptor->firstIn(*this, node); |
---|
[430] | 146 | } |
---|
| 147 | |
---|
[432] | 148 | InArcIt(const Adaptor& adaptor, const Arc& arc) : |
---|
| 149 | Arc(arc), _adaptor(&adaptor) {} |
---|
[430] | 150 | |
---|
[432] | 151 | InArcIt& operator++() { |
---|
| 152 | _adaptor->nextIn(*this); |
---|
| 153 | return *this; |
---|
[430] | 154 | } |
---|
| 155 | |
---|
| 156 | }; |
---|
| 157 | |
---|
| 158 | Node baseNode(const OutArcIt &e) const { |
---|
| 159 | return Parent::source(e); |
---|
| 160 | } |
---|
| 161 | Node runningNode(const OutArcIt &e) const { |
---|
| 162 | return Parent::target(e); |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | Node baseNode(const InArcIt &e) const { |
---|
| 166 | return Parent::target(e); |
---|
| 167 | } |
---|
| 168 | Node runningNode(const InArcIt &e) const { |
---|
| 169 | return Parent::source(e); |
---|
| 170 | } |
---|
| 171 | |
---|
| 172 | }; |
---|
| 173 | |
---|
[432] | 174 | template <typename _Graph> |
---|
[430] | 175 | class GraphAdaptorExtender : public _Graph { |
---|
| 176 | public: |
---|
[432] | 177 | |
---|
[430] | 178 | typedef _Graph Parent; |
---|
| 179 | typedef _Graph Graph; |
---|
| 180 | typedef GraphAdaptorExtender Adaptor; |
---|
| 181 | |
---|
| 182 | typedef typename Parent::Node Node; |
---|
| 183 | typedef typename Parent::Arc Arc; |
---|
| 184 | typedef typename Parent::Edge Edge; |
---|
| 185 | |
---|
[432] | 186 | // Graph extension |
---|
[430] | 187 | |
---|
| 188 | int maxId(Node) const { |
---|
| 189 | return Parent::maxNodeId(); |
---|
| 190 | } |
---|
| 191 | |
---|
| 192 | int maxId(Arc) const { |
---|
| 193 | return Parent::maxArcId(); |
---|
| 194 | } |
---|
| 195 | |
---|
| 196 | int maxId(Edge) const { |
---|
| 197 | return Parent::maxEdgeId(); |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | Node fromId(int id, Node) const { |
---|
| 201 | return Parent::nodeFromId(id); |
---|
| 202 | } |
---|
| 203 | |
---|
| 204 | Arc fromId(int id, Arc) const { |
---|
| 205 | return Parent::arcFromId(id); |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | Edge fromId(int id, Edge) const { |
---|
| 209 | return Parent::edgeFromId(id); |
---|
| 210 | } |
---|
| 211 | |
---|
| 212 | Node oppositeNode(const Node &n, const Edge &e) const { |
---|
| 213 | if( n == Parent::u(e)) |
---|
[432] | 214 | return Parent::v(e); |
---|
[430] | 215 | else if( n == Parent::v(e)) |
---|
[432] | 216 | return Parent::u(e); |
---|
[430] | 217 | else |
---|
[432] | 218 | return INVALID; |
---|
[430] | 219 | } |
---|
| 220 | |
---|
| 221 | Arc oppositeArc(const Arc &a) const { |
---|
| 222 | return Parent::direct(a, !Parent::direction(a)); |
---|
| 223 | } |
---|
| 224 | |
---|
| 225 | using Parent::direct; |
---|
| 226 | Arc direct(const Edge &e, const Node &s) const { |
---|
| 227 | return Parent::direct(e, Parent::u(e) == s); |
---|
| 228 | } |
---|
| 229 | |
---|
| 230 | |
---|
[432] | 231 | class NodeIt : public Node { |
---|
[430] | 232 | const Adaptor* _adaptor; |
---|
| 233 | public: |
---|
| 234 | |
---|
| 235 | NodeIt() {} |
---|
| 236 | |
---|
| 237 | NodeIt(Invalid i) : Node(i) { } |
---|
| 238 | |
---|
| 239 | explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
---|
[432] | 240 | _adaptor->first(static_cast<Node&>(*this)); |
---|
[430] | 241 | } |
---|
| 242 | |
---|
[432] | 243 | NodeIt(const Adaptor& adaptor, const Node& node) |
---|
| 244 | : Node(node), _adaptor(&adaptor) {} |
---|
[430] | 245 | |
---|
[432] | 246 | NodeIt& operator++() { |
---|
| 247 | _adaptor->next(*this); |
---|
| 248 | return *this; |
---|
[430] | 249 | } |
---|
| 250 | |
---|
| 251 | }; |
---|
| 252 | |
---|
| 253 | |
---|
[432] | 254 | class ArcIt : public Arc { |
---|
[430] | 255 | const Adaptor* _adaptor; |
---|
| 256 | public: |
---|
| 257 | |
---|
| 258 | ArcIt() { } |
---|
| 259 | |
---|
| 260 | ArcIt(Invalid i) : Arc(i) { } |
---|
| 261 | |
---|
| 262 | explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
---|
[432] | 263 | _adaptor->first(static_cast<Arc&>(*this)); |
---|
[430] | 264 | } |
---|
| 265 | |
---|
[432] | 266 | ArcIt(const Adaptor& adaptor, const Arc& e) : |
---|
| 267 | Arc(e), _adaptor(&adaptor) { } |
---|
[430] | 268 | |
---|
[432] | 269 | ArcIt& operator++() { |
---|
| 270 | _adaptor->next(*this); |
---|
| 271 | return *this; |
---|
[430] | 272 | } |
---|
| 273 | |
---|
| 274 | }; |
---|
| 275 | |
---|
| 276 | |
---|
[432] | 277 | class OutArcIt : public Arc { |
---|
[430] | 278 | const Adaptor* _adaptor; |
---|
| 279 | public: |
---|
| 280 | |
---|
| 281 | OutArcIt() { } |
---|
| 282 | |
---|
| 283 | OutArcIt(Invalid i) : Arc(i) { } |
---|
| 284 | |
---|
[432] | 285 | OutArcIt(const Adaptor& adaptor, const Node& node) |
---|
| 286 | : _adaptor(&adaptor) { |
---|
| 287 | _adaptor->firstOut(*this, node); |
---|
[430] | 288 | } |
---|
| 289 | |
---|
[432] | 290 | OutArcIt(const Adaptor& adaptor, const Arc& arc) |
---|
| 291 | : Arc(arc), _adaptor(&adaptor) {} |
---|
[430] | 292 | |
---|
[432] | 293 | OutArcIt& operator++() { |
---|
| 294 | _adaptor->nextOut(*this); |
---|
| 295 | return *this; |
---|
[430] | 296 | } |
---|
| 297 | |
---|
| 298 | }; |
---|
| 299 | |
---|
| 300 | |
---|
[432] | 301 | class InArcIt : public Arc { |
---|
[430] | 302 | const Adaptor* _adaptor; |
---|
| 303 | public: |
---|
| 304 | |
---|
| 305 | InArcIt() { } |
---|
| 306 | |
---|
| 307 | InArcIt(Invalid i) : Arc(i) { } |
---|
| 308 | |
---|
[432] | 309 | InArcIt(const Adaptor& adaptor, const Node& node) |
---|
| 310 | : _adaptor(&adaptor) { |
---|
| 311 | _adaptor->firstIn(*this, node); |
---|
[430] | 312 | } |
---|
| 313 | |
---|
[432] | 314 | InArcIt(const Adaptor& adaptor, const Arc& arc) : |
---|
| 315 | Arc(arc), _adaptor(&adaptor) {} |
---|
[430] | 316 | |
---|
[432] | 317 | InArcIt& operator++() { |
---|
| 318 | _adaptor->nextIn(*this); |
---|
| 319 | return *this; |
---|
[430] | 320 | } |
---|
| 321 | |
---|
| 322 | }; |
---|
| 323 | |
---|
[432] | 324 | class EdgeIt : public Parent::Edge { |
---|
[430] | 325 | const Adaptor* _adaptor; |
---|
| 326 | public: |
---|
| 327 | |
---|
| 328 | EdgeIt() { } |
---|
| 329 | |
---|
| 330 | EdgeIt(Invalid i) : Edge(i) { } |
---|
| 331 | |
---|
| 332 | explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
---|
[432] | 333 | _adaptor->first(static_cast<Edge&>(*this)); |
---|
[430] | 334 | } |
---|
| 335 | |
---|
[432] | 336 | EdgeIt(const Adaptor& adaptor, const Edge& e) : |
---|
| 337 | Edge(e), _adaptor(&adaptor) { } |
---|
[430] | 338 | |
---|
[432] | 339 | EdgeIt& operator++() { |
---|
| 340 | _adaptor->next(*this); |
---|
| 341 | return *this; |
---|
[430] | 342 | } |
---|
| 343 | |
---|
| 344 | }; |
---|
| 345 | |
---|
[432] | 346 | class IncEdgeIt : public Edge { |
---|
[430] | 347 | friend class GraphAdaptorExtender; |
---|
| 348 | const Adaptor* _adaptor; |
---|
| 349 | bool direction; |
---|
| 350 | public: |
---|
| 351 | |
---|
| 352 | IncEdgeIt() { } |
---|
| 353 | |
---|
| 354 | IncEdgeIt(Invalid i) : Edge(i), direction(false) { } |
---|
| 355 | |
---|
| 356 | IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) { |
---|
[432] | 357 | _adaptor->firstInc(static_cast<Edge&>(*this), direction, n); |
---|
[430] | 358 | } |
---|
| 359 | |
---|
| 360 | IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n) |
---|
[432] | 361 | : _adaptor(&adaptor), Edge(e) { |
---|
| 362 | direction = (_adaptor->u(e) == n); |
---|
[430] | 363 | } |
---|
| 364 | |
---|
| 365 | IncEdgeIt& operator++() { |
---|
[432] | 366 | _adaptor->nextInc(*this, direction); |
---|
| 367 | return *this; |
---|
[430] | 368 | } |
---|
| 369 | }; |
---|
| 370 | |
---|
| 371 | Node baseNode(const OutArcIt &a) const { |
---|
| 372 | return Parent::source(a); |
---|
| 373 | } |
---|
| 374 | Node runningNode(const OutArcIt &a) const { |
---|
| 375 | return Parent::target(a); |
---|
| 376 | } |
---|
| 377 | |
---|
| 378 | Node baseNode(const InArcIt &a) const { |
---|
| 379 | return Parent::target(a); |
---|
| 380 | } |
---|
| 381 | Node runningNode(const InArcIt &a) const { |
---|
| 382 | return Parent::source(a); |
---|
| 383 | } |
---|
| 384 | |
---|
| 385 | Node baseNode(const IncEdgeIt &e) const { |
---|
| 386 | return e.direction ? Parent::u(e) : Parent::v(e); |
---|
| 387 | } |
---|
| 388 | Node runningNode(const IncEdgeIt &e) const { |
---|
| 389 | return e.direction ? Parent::v(e) : Parent::u(e); |
---|
| 390 | } |
---|
| 391 | |
---|
| 392 | }; |
---|
| 393 | |
---|
| 394 | } |
---|
| 395 | |
---|
| 396 | |
---|
| 397 | #endif |
---|