[209] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
[57] | 2 | * |
---|
[209] | 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
[57] | 4 | * |
---|
[107] | 5 | * Copyright (C) 2003-2008 |
---|
[57] | 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_BASE_EXTENDER_H |
---|
| 20 | #define LEMON_BITS_BASE_EXTENDER_H |
---|
| 21 | |
---|
[220] | 22 | #include <lemon/core.h> |
---|
[57] | 23 | #include <lemon/error.h> |
---|
| 24 | |
---|
| 25 | #include <lemon/bits/map_extender.h> |
---|
| 26 | #include <lemon/bits/default_map.h> |
---|
| 27 | |
---|
| 28 | #include <lemon/concept_check.h> |
---|
| 29 | #include <lemon/concepts/maps.h> |
---|
| 30 | |
---|
| 31 | ///\ingroup digraphbits |
---|
| 32 | ///\file |
---|
| 33 | ///\brief Extenders for the digraph types |
---|
| 34 | namespace lemon { |
---|
| 35 | |
---|
| 36 | /// \ingroup digraphbits |
---|
| 37 | /// |
---|
| 38 | /// \brief BaseDigraph to BaseGraph extender |
---|
| 39 | template <typename Base> |
---|
| 40 | class UndirDigraphExtender : public Base { |
---|
| 41 | |
---|
| 42 | public: |
---|
| 43 | |
---|
| 44 | typedef Base Parent; |
---|
| 45 | typedef typename Parent::Arc Edge; |
---|
| 46 | typedef typename Parent::Node Node; |
---|
| 47 | |
---|
| 48 | typedef True UndirectedTag; |
---|
| 49 | |
---|
| 50 | class Arc : public Edge { |
---|
| 51 | friend class UndirDigraphExtender; |
---|
| 52 | |
---|
| 53 | protected: |
---|
| 54 | bool forward; |
---|
| 55 | |
---|
| 56 | Arc(const Edge &ue, bool _forward) : |
---|
| 57 | Edge(ue), forward(_forward) {} |
---|
| 58 | |
---|
| 59 | public: |
---|
| 60 | Arc() {} |
---|
| 61 | |
---|
[256] | 62 | // Invalid arc constructor |
---|
[57] | 63 | Arc(Invalid i) : Edge(i), forward(true) {} |
---|
| 64 | |
---|
| 65 | bool operator==(const Arc &that) const { |
---|
[209] | 66 | return forward==that.forward && Edge(*this)==Edge(that); |
---|
[57] | 67 | } |
---|
| 68 | bool operator!=(const Arc &that) const { |
---|
[209] | 69 | return forward!=that.forward || Edge(*this)!=Edge(that); |
---|
[57] | 70 | } |
---|
| 71 | bool operator<(const Arc &that) const { |
---|
[209] | 72 | return forward<that.forward || |
---|
| 73 | (!(that.forward<forward) && Edge(*this)<Edge(that)); |
---|
[57] | 74 | } |
---|
| 75 | }; |
---|
| 76 | |
---|
[256] | 77 | /// First node of the edge |
---|
| 78 | Node u(const Edge &e) const { |
---|
| 79 | return Parent::source(e); |
---|
| 80 | } |
---|
[57] | 81 | |
---|
[256] | 82 | /// Source of the given arc |
---|
[57] | 83 | Node source(const Arc &e) const { |
---|
| 84 | return e.forward ? Parent::source(e) : Parent::target(e); |
---|
| 85 | } |
---|
| 86 | |
---|
[256] | 87 | /// Second node of the edge |
---|
| 88 | Node v(const Edge &e) const { |
---|
| 89 | return Parent::target(e); |
---|
| 90 | } |
---|
[57] | 91 | |
---|
[256] | 92 | /// Target of the given arc |
---|
[57] | 93 | Node target(const Arc &e) const { |
---|
| 94 | return e.forward ? Parent::target(e) : Parent::source(e); |
---|
| 95 | } |
---|
| 96 | |
---|
| 97 | /// \brief Directed arc from an edge. |
---|
| 98 | /// |
---|
[256] | 99 | /// Returns a directed arc corresponding to the specified edge. |
---|
| 100 | /// If the given bool is true, the first node of the given edge and |
---|
| 101 | /// the source node of the returned arc are the same. |
---|
| 102 | static Arc direct(const Edge &e, bool d) { |
---|
| 103 | return Arc(e, d); |
---|
[57] | 104 | } |
---|
| 105 | |
---|
[256] | 106 | /// Returns whether the given directed arc has the same orientation |
---|
| 107 | /// as the corresponding edge. |
---|
| 108 | static bool direction(const Arc &a) { return a.forward; } |
---|
[57] | 109 | |
---|
| 110 | using Parent::first; |
---|
| 111 | using Parent::next; |
---|
| 112 | |
---|
| 113 | void first(Arc &e) const { |
---|
| 114 | Parent::first(e); |
---|
| 115 | e.forward=true; |
---|
| 116 | } |
---|
| 117 | |
---|
| 118 | void next(Arc &e) const { |
---|
| 119 | if( e.forward ) { |
---|
[209] | 120 | e.forward = false; |
---|
[57] | 121 | } |
---|
| 122 | else { |
---|
[209] | 123 | Parent::next(e); |
---|
| 124 | e.forward = true; |
---|
[57] | 125 | } |
---|
| 126 | } |
---|
| 127 | |
---|
| 128 | void firstOut(Arc &e, const Node &n) const { |
---|
| 129 | Parent::firstIn(e,n); |
---|
| 130 | if( Edge(e) != INVALID ) { |
---|
[209] | 131 | e.forward = false; |
---|
[57] | 132 | } |
---|
| 133 | else { |
---|
[209] | 134 | Parent::firstOut(e,n); |
---|
| 135 | e.forward = true; |
---|
[57] | 136 | } |
---|
| 137 | } |
---|
| 138 | void nextOut(Arc &e) const { |
---|
| 139 | if( ! e.forward ) { |
---|
[209] | 140 | Node n = Parent::target(e); |
---|
| 141 | Parent::nextIn(e); |
---|
| 142 | if( Edge(e) == INVALID ) { |
---|
| 143 | Parent::firstOut(e, n); |
---|
| 144 | e.forward = true; |
---|
| 145 | } |
---|
[57] | 146 | } |
---|
| 147 | else { |
---|
[209] | 148 | Parent::nextOut(e); |
---|
[57] | 149 | } |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | void firstIn(Arc &e, const Node &n) const { |
---|
| 153 | Parent::firstOut(e,n); |
---|
| 154 | if( Edge(e) != INVALID ) { |
---|
[209] | 155 | e.forward = false; |
---|
[57] | 156 | } |
---|
| 157 | else { |
---|
[209] | 158 | Parent::firstIn(e,n); |
---|
| 159 | e.forward = true; |
---|
[57] | 160 | } |
---|
| 161 | } |
---|
| 162 | void nextIn(Arc &e) const { |
---|
| 163 | if( ! e.forward ) { |
---|
[209] | 164 | Node n = Parent::source(e); |
---|
| 165 | Parent::nextOut(e); |
---|
| 166 | if( Edge(e) == INVALID ) { |
---|
| 167 | Parent::firstIn(e, n); |
---|
| 168 | e.forward = true; |
---|
| 169 | } |
---|
[57] | 170 | } |
---|
| 171 | else { |
---|
[209] | 172 | Parent::nextIn(e); |
---|
[57] | 173 | } |
---|
| 174 | } |
---|
| 175 | |
---|
| 176 | void firstInc(Edge &e, bool &d, const Node &n) const { |
---|
| 177 | d = true; |
---|
| 178 | Parent::firstOut(e, n); |
---|
| 179 | if (e != INVALID) return; |
---|
| 180 | d = false; |
---|
| 181 | Parent::firstIn(e, n); |
---|
| 182 | } |
---|
| 183 | |
---|
| 184 | void nextInc(Edge &e, bool &d) const { |
---|
| 185 | if (d) { |
---|
[209] | 186 | Node s = Parent::source(e); |
---|
| 187 | Parent::nextOut(e); |
---|
| 188 | if (e != INVALID) return; |
---|
| 189 | d = false; |
---|
| 190 | Parent::firstIn(e, s); |
---|
[57] | 191 | } else { |
---|
[209] | 192 | Parent::nextIn(e); |
---|
[57] | 193 | } |
---|
| 194 | } |
---|
| 195 | |
---|
| 196 | Node nodeFromId(int ix) const { |
---|
| 197 | return Parent::nodeFromId(ix); |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | Arc arcFromId(int ix) const { |
---|
| 201 | return direct(Parent::arcFromId(ix >> 1), bool(ix & 1)); |
---|
| 202 | } |
---|
| 203 | |
---|
| 204 | Edge edgeFromId(int ix) const { |
---|
| 205 | return Parent::arcFromId(ix); |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | int id(const Node &n) const { |
---|
| 209 | return Parent::id(n); |
---|
| 210 | } |
---|
| 211 | |
---|
| 212 | int id(const Edge &e) const { |
---|
| 213 | return Parent::id(e); |
---|
| 214 | } |
---|
| 215 | |
---|
| 216 | int id(const Arc &e) const { |
---|
| 217 | return 2 * Parent::id(e) + int(e.forward); |
---|
| 218 | } |
---|
| 219 | |
---|
| 220 | int maxNodeId() const { |
---|
| 221 | return Parent::maxNodeId(); |
---|
| 222 | } |
---|
| 223 | |
---|
| 224 | int maxArcId() const { |
---|
| 225 | return 2 * Parent::maxArcId() + 1; |
---|
| 226 | } |
---|
| 227 | |
---|
| 228 | int maxEdgeId() const { |
---|
| 229 | return Parent::maxArcId(); |
---|
| 230 | } |
---|
| 231 | |
---|
| 232 | int arcNum() const { |
---|
| 233 | return 2 * Parent::arcNum(); |
---|
| 234 | } |
---|
| 235 | |
---|
| 236 | int edgeNum() const { |
---|
| 237 | return Parent::arcNum(); |
---|
| 238 | } |
---|
| 239 | |
---|
| 240 | Arc findArc(Node s, Node t, Arc p = INVALID) const { |
---|
| 241 | if (p == INVALID) { |
---|
[209] | 242 | Edge arc = Parent::findArc(s, t); |
---|
| 243 | if (arc != INVALID) return direct(arc, true); |
---|
| 244 | arc = Parent::findArc(t, s); |
---|
| 245 | if (arc != INVALID) return direct(arc, false); |
---|
[57] | 246 | } else if (direction(p)) { |
---|
[209] | 247 | Edge arc = Parent::findArc(s, t, p); |
---|
| 248 | if (arc != INVALID) return direct(arc, true); |
---|
| 249 | arc = Parent::findArc(t, s); |
---|
| 250 | if (arc != INVALID) return direct(arc, false); |
---|
[57] | 251 | } else { |
---|
[209] | 252 | Edge arc = Parent::findArc(t, s, p); |
---|
| 253 | if (arc != INVALID) return direct(arc, false); |
---|
[57] | 254 | } |
---|
| 255 | return INVALID; |
---|
| 256 | } |
---|
| 257 | |
---|
| 258 | Edge findEdge(Node s, Node t, Edge p = INVALID) const { |
---|
| 259 | if (s != t) { |
---|
| 260 | if (p == INVALID) { |
---|
| 261 | Edge arc = Parent::findArc(s, t); |
---|
| 262 | if (arc != INVALID) return arc; |
---|
| 263 | arc = Parent::findArc(t, s); |
---|
| 264 | if (arc != INVALID) return arc; |
---|
| 265 | } else if (Parent::s(p) == s) { |
---|
| 266 | Edge arc = Parent::findArc(s, t, p); |
---|
| 267 | if (arc != INVALID) return arc; |
---|
| 268 | arc = Parent::findArc(t, s); |
---|
[209] | 269 | if (arc != INVALID) return arc; |
---|
[57] | 270 | } else { |
---|
| 271 | Edge arc = Parent::findArc(t, s, p); |
---|
[209] | 272 | if (arc != INVALID) return arc; |
---|
[57] | 273 | } |
---|
| 274 | } else { |
---|
| 275 | return Parent::findArc(s, t, p); |
---|
| 276 | } |
---|
| 277 | return INVALID; |
---|
| 278 | } |
---|
| 279 | }; |
---|
| 280 | |
---|
| 281 | template <typename Base> |
---|
| 282 | class BidirBpGraphExtender : public Base { |
---|
| 283 | public: |
---|
| 284 | typedef Base Parent; |
---|
| 285 | typedef BidirBpGraphExtender Digraph; |
---|
| 286 | |
---|
| 287 | typedef typename Parent::Node Node; |
---|
| 288 | typedef typename Parent::Edge Edge; |
---|
| 289 | |
---|
| 290 | |
---|
| 291 | using Parent::first; |
---|
| 292 | using Parent::next; |
---|
| 293 | |
---|
| 294 | using Parent::id; |
---|
| 295 | |
---|
| 296 | class Red : public Node { |
---|
| 297 | friend class BidirBpGraphExtender; |
---|
| 298 | public: |
---|
| 299 | Red() {} |
---|
| 300 | Red(const Node& node) : Node(node) { |
---|
[209] | 301 | LEMON_ASSERT(Parent::red(node) || node == INVALID, |
---|
| 302 | typename Parent::NodeSetError()); |
---|
[57] | 303 | } |
---|
| 304 | Red& operator=(const Node& node) { |
---|
[209] | 305 | LEMON_ASSERT(Parent::red(node) || node == INVALID, |
---|
| 306 | typename Parent::NodeSetError()); |
---|
[57] | 307 | Node::operator=(node); |
---|
| 308 | return *this; |
---|
| 309 | } |
---|
| 310 | Red(Invalid) : Node(INVALID) {} |
---|
| 311 | Red& operator=(Invalid) { |
---|
| 312 | Node::operator=(INVALID); |
---|
| 313 | return *this; |
---|
| 314 | } |
---|
| 315 | }; |
---|
| 316 | |
---|
| 317 | void first(Red& node) const { |
---|
| 318 | Parent::firstRed(static_cast<Node&>(node)); |
---|
| 319 | } |
---|
| 320 | void next(Red& node) const { |
---|
| 321 | Parent::nextRed(static_cast<Node&>(node)); |
---|
| 322 | } |
---|
| 323 | |
---|
| 324 | int id(const Red& node) const { |
---|
| 325 | return Parent::redId(node); |
---|
| 326 | } |
---|
| 327 | |
---|
| 328 | class Blue : public Node { |
---|
| 329 | friend class BidirBpGraphExtender; |
---|
| 330 | public: |
---|
| 331 | Blue() {} |
---|
| 332 | Blue(const Node& node) : Node(node) { |
---|
[209] | 333 | LEMON_ASSERT(Parent::blue(node) || node == INVALID, |
---|
| 334 | typename Parent::NodeSetError()); |
---|
[57] | 335 | } |
---|
| 336 | Blue& operator=(const Node& node) { |
---|
[209] | 337 | LEMON_ASSERT(Parent::blue(node) || node == INVALID, |
---|
| 338 | typename Parent::NodeSetError()); |
---|
[57] | 339 | Node::operator=(node); |
---|
| 340 | return *this; |
---|
| 341 | } |
---|
| 342 | Blue(Invalid) : Node(INVALID) {} |
---|
| 343 | Blue& operator=(Invalid) { |
---|
| 344 | Node::operator=(INVALID); |
---|
| 345 | return *this; |
---|
| 346 | } |
---|
| 347 | }; |
---|
| 348 | |
---|
| 349 | void first(Blue& node) const { |
---|
| 350 | Parent::firstBlue(static_cast<Node&>(node)); |
---|
| 351 | } |
---|
| 352 | void next(Blue& node) const { |
---|
| 353 | Parent::nextBlue(static_cast<Node&>(node)); |
---|
| 354 | } |
---|
[209] | 355 | |
---|
[57] | 356 | int id(const Blue& node) const { |
---|
| 357 | return Parent::redId(node); |
---|
| 358 | } |
---|
| 359 | |
---|
| 360 | Node source(const Edge& arc) const { |
---|
| 361 | return red(arc); |
---|
| 362 | } |
---|
| 363 | Node target(const Edge& arc) const { |
---|
| 364 | return blue(arc); |
---|
| 365 | } |
---|
| 366 | |
---|
| 367 | void firstInc(Edge& arc, bool& dir, const Node& node) const { |
---|
| 368 | if (Parent::red(node)) { |
---|
[209] | 369 | Parent::firstFromRed(arc, node); |
---|
| 370 | dir = true; |
---|
[57] | 371 | } else { |
---|
[209] | 372 | Parent::firstFromBlue(arc, node); |
---|
| 373 | dir = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 374 | } |
---|
| 375 | } |
---|
| 376 | void nextInc(Edge& arc, bool& dir) const { |
---|
| 377 | if (dir) { |
---|
[209] | 378 | Parent::nextFromRed(arc); |
---|
[57] | 379 | } else { |
---|
[209] | 380 | Parent::nextFromBlue(arc); |
---|
| 381 | if (arc == INVALID) dir = true; |
---|
[57] | 382 | } |
---|
| 383 | } |
---|
| 384 | |
---|
| 385 | class Arc : public Edge { |
---|
| 386 | friend class BidirBpGraphExtender; |
---|
| 387 | protected: |
---|
| 388 | bool forward; |
---|
| 389 | |
---|
| 390 | Arc(const Edge& arc, bool _forward) |
---|
[209] | 391 | : Edge(arc), forward(_forward) {} |
---|
[57] | 392 | |
---|
| 393 | public: |
---|
| 394 | Arc() {} |
---|
| 395 | Arc (Invalid) : Edge(INVALID), forward(true) {} |
---|
| 396 | bool operator==(const Arc& i) const { |
---|
[209] | 397 | return Edge::operator==(i) && forward == i.forward; |
---|
[57] | 398 | } |
---|
| 399 | bool operator!=(const Arc& i) const { |
---|
[209] | 400 | return Edge::operator!=(i) || forward != i.forward; |
---|
[57] | 401 | } |
---|
| 402 | bool operator<(const Arc& i) const { |
---|
[209] | 403 | return Edge::operator<(i) || |
---|
| 404 | (!(i.forward<forward) && Edge(*this)<Edge(i)); |
---|
[57] | 405 | } |
---|
| 406 | }; |
---|
| 407 | |
---|
| 408 | void first(Arc& arc) const { |
---|
| 409 | Parent::first(static_cast<Edge&>(arc)); |
---|
| 410 | arc.forward = true; |
---|
| 411 | } |
---|
| 412 | |
---|
| 413 | void next(Arc& arc) const { |
---|
| 414 | if (!arc.forward) { |
---|
[209] | 415 | Parent::next(static_cast<Edge&>(arc)); |
---|
[57] | 416 | } |
---|
| 417 | arc.forward = !arc.forward; |
---|
| 418 | } |
---|
| 419 | |
---|
| 420 | void firstOut(Arc& arc, const Node& node) const { |
---|
| 421 | if (Parent::red(node)) { |
---|
[209] | 422 | Parent::firstFromRed(arc, node); |
---|
| 423 | arc.forward = true; |
---|
[57] | 424 | } else { |
---|
[209] | 425 | Parent::firstFromBlue(arc, node); |
---|
| 426 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 427 | } |
---|
| 428 | } |
---|
| 429 | void nextOut(Arc& arc) const { |
---|
| 430 | if (arc.forward) { |
---|
[209] | 431 | Parent::nextFromRed(arc); |
---|
[57] | 432 | } else { |
---|
[209] | 433 | Parent::nextFromBlue(arc); |
---|
[57] | 434 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
| 435 | } |
---|
| 436 | } |
---|
| 437 | |
---|
| 438 | void firstIn(Arc& arc, const Node& node) const { |
---|
| 439 | if (Parent::blue(node)) { |
---|
[209] | 440 | Parent::firstFromBlue(arc, node); |
---|
| 441 | arc.forward = true; |
---|
[57] | 442 | } else { |
---|
[209] | 443 | Parent::firstFromRed(arc, node); |
---|
| 444 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 445 | } |
---|
| 446 | } |
---|
| 447 | void nextIn(Arc& arc) const { |
---|
| 448 | if (arc.forward) { |
---|
[209] | 449 | Parent::nextFromBlue(arc); |
---|
[57] | 450 | } else { |
---|
[209] | 451 | Parent::nextFromRed(arc); |
---|
| 452 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 453 | } |
---|
| 454 | } |
---|
| 455 | |
---|
| 456 | Node source(const Arc& arc) const { |
---|
| 457 | return arc.forward ? Parent::red(arc) : Parent::blue(arc); |
---|
| 458 | } |
---|
| 459 | Node target(const Arc& arc) const { |
---|
| 460 | return arc.forward ? Parent::blue(arc) : Parent::red(arc); |
---|
| 461 | } |
---|
| 462 | |
---|
| 463 | int id(const Arc& arc) const { |
---|
[209] | 464 | return (Parent::id(static_cast<const Edge&>(arc)) << 1) + |
---|
[57] | 465 | (arc.forward ? 0 : 1); |
---|
| 466 | } |
---|
| 467 | Arc arcFromId(int ix) const { |
---|
| 468 | return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0); |
---|
| 469 | } |
---|
| 470 | int maxArcId() const { |
---|
| 471 | return (Parent::maxEdgeId() << 1) + 1; |
---|
| 472 | } |
---|
| 473 | |
---|
| 474 | bool direction(const Arc& arc) const { |
---|
| 475 | return arc.forward; |
---|
| 476 | } |
---|
| 477 | |
---|
| 478 | Arc direct(const Edge& arc, bool dir) const { |
---|
| 479 | return Arc(arc, dir); |
---|
| 480 | } |
---|
| 481 | |
---|
| 482 | int arcNum() const { |
---|
| 483 | return 2 * Parent::edgeNum(); |
---|
| 484 | } |
---|
| 485 | |
---|
| 486 | int edgeNum() const { |
---|
| 487 | return Parent::edgeNum(); |
---|
| 488 | } |
---|
| 489 | |
---|
| 490 | |
---|
| 491 | }; |
---|
| 492 | } |
---|
| 493 | |
---|
| 494 | #endif |
---|