[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. |
---|
[57] | 108 | /// |
---|
| 109 | /// \todo reference to the corresponding point of the undirected digraph |
---|
| 110 | /// concept. "What does the direction of an edge mean?" |
---|
[256] | 111 | static bool direction(const Arc &a) { return a.forward; } |
---|
[57] | 112 | |
---|
| 113 | using Parent::first; |
---|
| 114 | using Parent::next; |
---|
| 115 | |
---|
| 116 | void first(Arc &e) const { |
---|
| 117 | Parent::first(e); |
---|
| 118 | e.forward=true; |
---|
| 119 | } |
---|
| 120 | |
---|
| 121 | void next(Arc &e) const { |
---|
| 122 | if( e.forward ) { |
---|
[209] | 123 | e.forward = false; |
---|
[57] | 124 | } |
---|
| 125 | else { |
---|
[209] | 126 | Parent::next(e); |
---|
| 127 | e.forward = true; |
---|
[57] | 128 | } |
---|
| 129 | } |
---|
| 130 | |
---|
| 131 | void firstOut(Arc &e, const Node &n) const { |
---|
| 132 | Parent::firstIn(e,n); |
---|
| 133 | if( Edge(e) != INVALID ) { |
---|
[209] | 134 | e.forward = false; |
---|
[57] | 135 | } |
---|
| 136 | else { |
---|
[209] | 137 | Parent::firstOut(e,n); |
---|
| 138 | e.forward = true; |
---|
[57] | 139 | } |
---|
| 140 | } |
---|
| 141 | void nextOut(Arc &e) const { |
---|
| 142 | if( ! e.forward ) { |
---|
[209] | 143 | Node n = Parent::target(e); |
---|
| 144 | Parent::nextIn(e); |
---|
| 145 | if( Edge(e) == INVALID ) { |
---|
| 146 | Parent::firstOut(e, n); |
---|
| 147 | e.forward = true; |
---|
| 148 | } |
---|
[57] | 149 | } |
---|
| 150 | else { |
---|
[209] | 151 | Parent::nextOut(e); |
---|
[57] | 152 | } |
---|
| 153 | } |
---|
| 154 | |
---|
| 155 | void firstIn(Arc &e, const Node &n) const { |
---|
| 156 | Parent::firstOut(e,n); |
---|
| 157 | if( Edge(e) != INVALID ) { |
---|
[209] | 158 | e.forward = false; |
---|
[57] | 159 | } |
---|
| 160 | else { |
---|
[209] | 161 | Parent::firstIn(e,n); |
---|
| 162 | e.forward = true; |
---|
[57] | 163 | } |
---|
| 164 | } |
---|
| 165 | void nextIn(Arc &e) const { |
---|
| 166 | if( ! e.forward ) { |
---|
[209] | 167 | Node n = Parent::source(e); |
---|
| 168 | Parent::nextOut(e); |
---|
| 169 | if( Edge(e) == INVALID ) { |
---|
| 170 | Parent::firstIn(e, n); |
---|
| 171 | e.forward = true; |
---|
| 172 | } |
---|
[57] | 173 | } |
---|
| 174 | else { |
---|
[209] | 175 | Parent::nextIn(e); |
---|
[57] | 176 | } |
---|
| 177 | } |
---|
| 178 | |
---|
| 179 | void firstInc(Edge &e, bool &d, const Node &n) const { |
---|
| 180 | d = true; |
---|
| 181 | Parent::firstOut(e, n); |
---|
| 182 | if (e != INVALID) return; |
---|
| 183 | d = false; |
---|
| 184 | Parent::firstIn(e, n); |
---|
| 185 | } |
---|
| 186 | |
---|
| 187 | void nextInc(Edge &e, bool &d) const { |
---|
| 188 | if (d) { |
---|
[209] | 189 | Node s = Parent::source(e); |
---|
| 190 | Parent::nextOut(e); |
---|
| 191 | if (e != INVALID) return; |
---|
| 192 | d = false; |
---|
| 193 | Parent::firstIn(e, s); |
---|
[57] | 194 | } else { |
---|
[209] | 195 | Parent::nextIn(e); |
---|
[57] | 196 | } |
---|
| 197 | } |
---|
| 198 | |
---|
| 199 | Node nodeFromId(int ix) const { |
---|
| 200 | return Parent::nodeFromId(ix); |
---|
| 201 | } |
---|
| 202 | |
---|
| 203 | Arc arcFromId(int ix) const { |
---|
| 204 | return direct(Parent::arcFromId(ix >> 1), bool(ix & 1)); |
---|
| 205 | } |
---|
| 206 | |
---|
| 207 | Edge edgeFromId(int ix) const { |
---|
| 208 | return Parent::arcFromId(ix); |
---|
| 209 | } |
---|
| 210 | |
---|
| 211 | int id(const Node &n) const { |
---|
| 212 | return Parent::id(n); |
---|
| 213 | } |
---|
| 214 | |
---|
| 215 | int id(const Edge &e) const { |
---|
| 216 | return Parent::id(e); |
---|
| 217 | } |
---|
| 218 | |
---|
| 219 | int id(const Arc &e) const { |
---|
| 220 | return 2 * Parent::id(e) + int(e.forward); |
---|
| 221 | } |
---|
| 222 | |
---|
| 223 | int maxNodeId() const { |
---|
| 224 | return Parent::maxNodeId(); |
---|
| 225 | } |
---|
| 226 | |
---|
| 227 | int maxArcId() const { |
---|
| 228 | return 2 * Parent::maxArcId() + 1; |
---|
| 229 | } |
---|
| 230 | |
---|
| 231 | int maxEdgeId() const { |
---|
| 232 | return Parent::maxArcId(); |
---|
| 233 | } |
---|
| 234 | |
---|
| 235 | int arcNum() const { |
---|
| 236 | return 2 * Parent::arcNum(); |
---|
| 237 | } |
---|
| 238 | |
---|
| 239 | int edgeNum() const { |
---|
| 240 | return Parent::arcNum(); |
---|
| 241 | } |
---|
| 242 | |
---|
| 243 | Arc findArc(Node s, Node t, Arc p = INVALID) const { |
---|
| 244 | if (p == INVALID) { |
---|
[209] | 245 | Edge arc = Parent::findArc(s, t); |
---|
| 246 | if (arc != INVALID) return direct(arc, true); |
---|
| 247 | arc = Parent::findArc(t, s); |
---|
| 248 | if (arc != INVALID) return direct(arc, false); |
---|
[57] | 249 | } else if (direction(p)) { |
---|
[209] | 250 | Edge arc = Parent::findArc(s, t, p); |
---|
| 251 | if (arc != INVALID) return direct(arc, true); |
---|
| 252 | arc = Parent::findArc(t, s); |
---|
| 253 | if (arc != INVALID) return direct(arc, false); |
---|
[57] | 254 | } else { |
---|
[209] | 255 | Edge arc = Parent::findArc(t, s, p); |
---|
| 256 | if (arc != INVALID) return direct(arc, false); |
---|
[57] | 257 | } |
---|
| 258 | return INVALID; |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | Edge findEdge(Node s, Node t, Edge p = INVALID) const { |
---|
| 262 | if (s != t) { |
---|
| 263 | if (p == INVALID) { |
---|
| 264 | Edge arc = Parent::findArc(s, t); |
---|
| 265 | if (arc != INVALID) return arc; |
---|
| 266 | arc = Parent::findArc(t, s); |
---|
| 267 | if (arc != INVALID) return arc; |
---|
| 268 | } else if (Parent::s(p) == s) { |
---|
| 269 | Edge arc = Parent::findArc(s, t, p); |
---|
| 270 | if (arc != INVALID) return arc; |
---|
| 271 | arc = Parent::findArc(t, s); |
---|
[209] | 272 | if (arc != INVALID) return arc; |
---|
[57] | 273 | } else { |
---|
| 274 | Edge arc = Parent::findArc(t, s, p); |
---|
[209] | 275 | if (arc != INVALID) return arc; |
---|
[57] | 276 | } |
---|
| 277 | } else { |
---|
| 278 | return Parent::findArc(s, t, p); |
---|
| 279 | } |
---|
| 280 | return INVALID; |
---|
| 281 | } |
---|
| 282 | }; |
---|
| 283 | |
---|
| 284 | template <typename Base> |
---|
| 285 | class BidirBpGraphExtender : public Base { |
---|
| 286 | public: |
---|
| 287 | typedef Base Parent; |
---|
| 288 | typedef BidirBpGraphExtender Digraph; |
---|
| 289 | |
---|
| 290 | typedef typename Parent::Node Node; |
---|
| 291 | typedef typename Parent::Edge Edge; |
---|
| 292 | |
---|
| 293 | |
---|
| 294 | using Parent::first; |
---|
| 295 | using Parent::next; |
---|
| 296 | |
---|
| 297 | using Parent::id; |
---|
| 298 | |
---|
| 299 | class Red : public Node { |
---|
| 300 | friend class BidirBpGraphExtender; |
---|
| 301 | public: |
---|
| 302 | Red() {} |
---|
| 303 | Red(const Node& node) : Node(node) { |
---|
[209] | 304 | LEMON_ASSERT(Parent::red(node) || node == INVALID, |
---|
| 305 | typename Parent::NodeSetError()); |
---|
[57] | 306 | } |
---|
| 307 | Red& operator=(const Node& node) { |
---|
[209] | 308 | LEMON_ASSERT(Parent::red(node) || node == INVALID, |
---|
| 309 | typename Parent::NodeSetError()); |
---|
[57] | 310 | Node::operator=(node); |
---|
| 311 | return *this; |
---|
| 312 | } |
---|
| 313 | Red(Invalid) : Node(INVALID) {} |
---|
| 314 | Red& operator=(Invalid) { |
---|
| 315 | Node::operator=(INVALID); |
---|
| 316 | return *this; |
---|
| 317 | } |
---|
| 318 | }; |
---|
| 319 | |
---|
| 320 | void first(Red& node) const { |
---|
| 321 | Parent::firstRed(static_cast<Node&>(node)); |
---|
| 322 | } |
---|
| 323 | void next(Red& node) const { |
---|
| 324 | Parent::nextRed(static_cast<Node&>(node)); |
---|
| 325 | } |
---|
| 326 | |
---|
| 327 | int id(const Red& node) const { |
---|
| 328 | return Parent::redId(node); |
---|
| 329 | } |
---|
| 330 | |
---|
| 331 | class Blue : public Node { |
---|
| 332 | friend class BidirBpGraphExtender; |
---|
| 333 | public: |
---|
| 334 | Blue() {} |
---|
| 335 | Blue(const Node& node) : Node(node) { |
---|
[209] | 336 | LEMON_ASSERT(Parent::blue(node) || node == INVALID, |
---|
| 337 | typename Parent::NodeSetError()); |
---|
[57] | 338 | } |
---|
| 339 | Blue& operator=(const Node& node) { |
---|
[209] | 340 | LEMON_ASSERT(Parent::blue(node) || node == INVALID, |
---|
| 341 | typename Parent::NodeSetError()); |
---|
[57] | 342 | Node::operator=(node); |
---|
| 343 | return *this; |
---|
| 344 | } |
---|
| 345 | Blue(Invalid) : Node(INVALID) {} |
---|
| 346 | Blue& operator=(Invalid) { |
---|
| 347 | Node::operator=(INVALID); |
---|
| 348 | return *this; |
---|
| 349 | } |
---|
| 350 | }; |
---|
| 351 | |
---|
| 352 | void first(Blue& node) const { |
---|
| 353 | Parent::firstBlue(static_cast<Node&>(node)); |
---|
| 354 | } |
---|
| 355 | void next(Blue& node) const { |
---|
| 356 | Parent::nextBlue(static_cast<Node&>(node)); |
---|
| 357 | } |
---|
[209] | 358 | |
---|
[57] | 359 | int id(const Blue& node) const { |
---|
| 360 | return Parent::redId(node); |
---|
| 361 | } |
---|
| 362 | |
---|
| 363 | Node source(const Edge& arc) const { |
---|
| 364 | return red(arc); |
---|
| 365 | } |
---|
| 366 | Node target(const Edge& arc) const { |
---|
| 367 | return blue(arc); |
---|
| 368 | } |
---|
| 369 | |
---|
| 370 | void firstInc(Edge& arc, bool& dir, const Node& node) const { |
---|
| 371 | if (Parent::red(node)) { |
---|
[209] | 372 | Parent::firstFromRed(arc, node); |
---|
| 373 | dir = true; |
---|
[57] | 374 | } else { |
---|
[209] | 375 | Parent::firstFromBlue(arc, node); |
---|
| 376 | dir = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 377 | } |
---|
| 378 | } |
---|
| 379 | void nextInc(Edge& arc, bool& dir) const { |
---|
| 380 | if (dir) { |
---|
[209] | 381 | Parent::nextFromRed(arc); |
---|
[57] | 382 | } else { |
---|
[209] | 383 | Parent::nextFromBlue(arc); |
---|
| 384 | if (arc == INVALID) dir = true; |
---|
[57] | 385 | } |
---|
| 386 | } |
---|
| 387 | |
---|
| 388 | class Arc : public Edge { |
---|
| 389 | friend class BidirBpGraphExtender; |
---|
| 390 | protected: |
---|
| 391 | bool forward; |
---|
| 392 | |
---|
| 393 | Arc(const Edge& arc, bool _forward) |
---|
[209] | 394 | : Edge(arc), forward(_forward) {} |
---|
[57] | 395 | |
---|
| 396 | public: |
---|
| 397 | Arc() {} |
---|
| 398 | Arc (Invalid) : Edge(INVALID), forward(true) {} |
---|
| 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) || forward != i.forward; |
---|
[57] | 404 | } |
---|
| 405 | bool operator<(const Arc& i) const { |
---|
[209] | 406 | return Edge::operator<(i) || |
---|
| 407 | (!(i.forward<forward) && Edge(*this)<Edge(i)); |
---|
[57] | 408 | } |
---|
| 409 | }; |
---|
| 410 | |
---|
| 411 | void first(Arc& arc) const { |
---|
| 412 | Parent::first(static_cast<Edge&>(arc)); |
---|
| 413 | arc.forward = true; |
---|
| 414 | } |
---|
| 415 | |
---|
| 416 | void next(Arc& arc) const { |
---|
| 417 | if (!arc.forward) { |
---|
[209] | 418 | Parent::next(static_cast<Edge&>(arc)); |
---|
[57] | 419 | } |
---|
| 420 | arc.forward = !arc.forward; |
---|
| 421 | } |
---|
| 422 | |
---|
| 423 | void firstOut(Arc& arc, const Node& node) const { |
---|
| 424 | if (Parent::red(node)) { |
---|
[209] | 425 | Parent::firstFromRed(arc, node); |
---|
| 426 | arc.forward = true; |
---|
[57] | 427 | } else { |
---|
[209] | 428 | Parent::firstFromBlue(arc, node); |
---|
| 429 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 430 | } |
---|
| 431 | } |
---|
| 432 | void nextOut(Arc& arc) const { |
---|
| 433 | if (arc.forward) { |
---|
[209] | 434 | Parent::nextFromRed(arc); |
---|
[57] | 435 | } else { |
---|
[209] | 436 | Parent::nextFromBlue(arc); |
---|
[57] | 437 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
| 438 | } |
---|
| 439 | } |
---|
| 440 | |
---|
| 441 | void firstIn(Arc& arc, const Node& node) const { |
---|
| 442 | if (Parent::blue(node)) { |
---|
[209] | 443 | Parent::firstFromBlue(arc, node); |
---|
| 444 | arc.forward = true; |
---|
[57] | 445 | } else { |
---|
[209] | 446 | Parent::firstFromRed(arc, node); |
---|
| 447 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 448 | } |
---|
| 449 | } |
---|
| 450 | void nextIn(Arc& arc) const { |
---|
| 451 | if (arc.forward) { |
---|
[209] | 452 | Parent::nextFromBlue(arc); |
---|
[57] | 453 | } else { |
---|
[209] | 454 | Parent::nextFromRed(arc); |
---|
| 455 | arc.forward = static_cast<Edge&>(arc) == INVALID; |
---|
[57] | 456 | } |
---|
| 457 | } |
---|
| 458 | |
---|
| 459 | Node source(const Arc& arc) const { |
---|
| 460 | return arc.forward ? Parent::red(arc) : Parent::blue(arc); |
---|
| 461 | } |
---|
| 462 | Node target(const Arc& arc) const { |
---|
| 463 | return arc.forward ? Parent::blue(arc) : Parent::red(arc); |
---|
| 464 | } |
---|
| 465 | |
---|
| 466 | int id(const Arc& arc) const { |
---|
[209] | 467 | return (Parent::id(static_cast<const Edge&>(arc)) << 1) + |
---|
[57] | 468 | (arc.forward ? 0 : 1); |
---|
| 469 | } |
---|
| 470 | Arc arcFromId(int ix) const { |
---|
| 471 | return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0); |
---|
| 472 | } |
---|
| 473 | int maxArcId() const { |
---|
| 474 | return (Parent::maxEdgeId() << 1) + 1; |
---|
| 475 | } |
---|
| 476 | |
---|
| 477 | bool direction(const Arc& arc) const { |
---|
| 478 | return arc.forward; |
---|
| 479 | } |
---|
| 480 | |
---|
| 481 | Arc direct(const Edge& arc, bool dir) const { |
---|
| 482 | return Arc(arc, dir); |
---|
| 483 | } |
---|
| 484 | |
---|
| 485 | int arcNum() const { |
---|
| 486 | return 2 * Parent::edgeNum(); |
---|
| 487 | } |
---|
| 488 | |
---|
| 489 | int edgeNum() const { |
---|
| 490 | return Parent::edgeNum(); |
---|
| 491 | } |
---|
| 492 | |
---|
| 493 | |
---|
| 494 | }; |
---|
| 495 | } |
---|
| 496 | |
---|
| 497 | #endif |
---|