1 /* -*- C++ -*- |
1 /* -*- C++ -*- |
2 * lemon/graph_extender.h - Part of LEMON, a generic C++ optimization library |
2 * lemon/graph_extender.h - Part of LEMON, a generic C++ optimization library |
3 * |
3 * |
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi |
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi |
5 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization, |
5 * Kutatocsoport (Egervary Research Groin on Combinatorial Optimization, |
6 * EGRES). |
6 * EGRES). |
7 * |
7 * |
8 * Permission to use, modify and distribute this software is granted |
8 * Permission to use, modify and distribute this software is granted |
9 * provided that this copyright notice appears in all copies. For |
9 * provided that this copyright notice appears in all copies. For |
10 * precise terms see the accompanying LICENSE file. |
10 * precise terms see the accompanying LICENSE file. |
377 |
377 |
378 }; |
378 }; |
379 |
379 |
380 |
380 |
381 template <typename _Base> |
381 template <typename _Base> |
382 class UBipartiteGraphExtender : public _Base { |
382 class BpUGraphExtender : public _Base { |
383 public: |
383 public: |
384 typedef _Base Parent; |
384 typedef _Base Parent; |
385 typedef UBipartiteGraphExtender Graph; |
385 typedef BpUGraphExtender Graph; |
386 |
386 |
387 typedef typename Parent::Node Node; |
387 typedef typename Parent::Node Node; |
388 typedef typename Parent::Edge UEdge; |
388 typedef typename Parent::Edge UEdge; |
389 |
389 |
390 using Parent::first; |
390 using Parent::first; |
391 using Parent::next; |
391 using Parent::next; |
392 |
392 |
393 using Parent::id; |
393 using Parent::id; |
394 |
394 |
395 Node source(const UEdge& edge) const { |
395 Node source(const UEdge& edge) const { |
396 return upperNode(edge); |
396 return aNode(edge); |
397 } |
397 } |
398 Node target(const UEdge& edge) const { |
398 Node target(const UEdge& edge) const { |
399 return lowerNode(edge); |
399 return bNode(edge); |
400 } |
400 } |
401 |
401 |
402 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
402 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
403 if (Parent::upper(node)) { |
403 if (Parent::aNode(node)) { |
404 Parent::firstDown(edge, node); |
404 Parent::firstOut(edge, node); |
405 direction = true; |
405 direction = true; |
406 } else { |
406 } else { |
407 Parent::firstUp(edge, node); |
407 Parent::firstIn(edge, node); |
408 direction = static_cast<UEdge&>(edge) == INVALID; |
408 direction = static_cast<UEdge&>(edge) == INVALID; |
409 } |
409 } |
410 } |
410 } |
411 void nextInc(UEdge& edge, bool& direction) const { |
411 void nextInc(UEdge& edge, bool& direction) const { |
412 if (direction) { |
412 if (direction) { |
413 Parent::nextDown(edge); |
413 Parent::nextOut(edge); |
414 } else { |
414 } else { |
415 Parent::nextUp(edge); |
415 Parent::nextIn(edge); |
416 if (edge == INVALID) direction = true; |
416 if (edge == INVALID) direction = true; |
417 } |
417 } |
418 } |
418 } |
419 |
419 |
420 int maxUEdgeId() const { |
420 int maxUEdgeId() const { |
459 } |
459 } |
460 edge.forward = !edge.forward; |
460 edge.forward = !edge.forward; |
461 } |
461 } |
462 |
462 |
463 void firstOut(Edge& edge, const Node& node) const { |
463 void firstOut(Edge& edge, const Node& node) const { |
464 if (Parent::upper(node)) { |
464 if (Parent::aNode(node)) { |
465 Parent::firstDown(edge, node); |
465 Parent::firstOut(edge, node); |
466 edge.forward = true; |
466 edge.forward = true; |
467 } else { |
467 } else { |
468 Parent::firstUp(edge, node); |
468 Parent::firstIn(edge, node); |
469 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
469 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
470 } |
470 } |
471 } |
471 } |
472 void nextOut(Edge& edge) const { |
472 void nextOut(Edge& edge) const { |
473 if (edge.forward) { |
473 if (edge.forward) { |
474 Parent::nextDown(edge); |
474 Parent::nextOut(edge); |
475 } else { |
475 } else { |
476 Parent::nextUp(edge); |
476 Parent::nextIn(edge); |
477 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
477 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
478 } |
478 } |
479 } |
479 } |
480 |
480 |
481 void firstIn(Edge& edge, const Node& node) const { |
481 void firstIn(Edge& edge, const Node& node) const { |
482 if (Parent::lower(node)) { |
482 if (Parent::bNode(node)) { |
483 Parent::firstUp(edge, node); |
483 Parent::firstIn(edge, node); |
484 edge.forward = true; |
484 edge.forward = true; |
485 } else { |
485 } else { |
486 Parent::firstDown(edge, node); |
486 Parent::firstOut(edge, node); |
487 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
487 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
488 } |
488 } |
489 } |
489 } |
490 void nextIn(Edge& edge) const { |
490 void nextIn(Edge& edge) const { |
491 if (edge.forward) { |
491 if (edge.forward) { |
492 Parent::nextUp(edge); |
492 Parent::nextIn(edge); |
493 } else { |
493 } else { |
494 Parent::nextDown(edge); |
494 Parent::nextOut(edge); |
495 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
495 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
496 } |
496 } |
497 } |
497 } |
498 |
498 |
499 Node source(const Edge& edge) const { |
499 Node source(const Edge& edge) const { |
500 return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge); |
500 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); |
501 } |
501 } |
502 Node target(const Edge& edge) const { |
502 Node target(const Edge& edge) const { |
503 return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge); |
503 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); |
504 } |
504 } |
505 |
505 |
506 bool direction(const Edge& edge) const { |
506 bool direction(const Edge& edge) const { |
507 return edge.forward; |
507 return edge.forward; |
508 } |
508 } |
532 } |
532 } |
533 int maxEdgeId() const { |
533 int maxEdgeId() const { |
534 return (Parent::maxId(UEdge()) << 1) + 1; |
534 return (Parent::maxId(UEdge()) << 1) + 1; |
535 } |
535 } |
536 |
536 |
537 class UpperNode : public Node { |
537 class ANode : public Node { |
538 friend class UBipartiteGraphExtender; |
538 friend class BpUGraphExtender; |
539 public: |
539 public: |
540 UpperNode() {} |
540 ANode() {} |
541 UpperNode(const Node& node) : Node(node) { |
541 ANode(const Node& node) : Node(node) { |
542 LEMON_ASSERT(Parent::upper(node) || node == INVALID, |
542 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, |
543 typename Parent::NodeSetError()); |
543 typename Parent::NodeSetError()); |
544 } |
544 } |
545 UpperNode(Invalid) : Node(INVALID) {} |
545 ANode(Invalid) : Node(INVALID) {} |
546 }; |
546 }; |
547 |
547 |
548 void first(UpperNode& node) const { |
548 void first(ANode& node) const { |
549 Parent::firstUpper(static_cast<Node&>(node)); |
549 Parent::firstANode(static_cast<Node&>(node)); |
550 } |
550 } |
551 void next(UpperNode& node) const { |
551 void next(ANode& node) const { |
552 Parent::nextUpper(static_cast<Node&>(node)); |
552 Parent::nextANode(static_cast<Node&>(node)); |
553 } |
553 } |
554 |
554 |
555 int id(const UpperNode& node) const { |
555 int id(const ANode& node) const { |
556 return Parent::upperId(node); |
556 return Parent::aNodeId(node); |
557 } |
557 } |
558 |
558 |
559 class LowerNode : public Node { |
559 class BNode : public Node { |
560 friend class UBipartiteGraphExtender; |
560 friend class BpUGraphExtender; |
561 public: |
561 public: |
562 LowerNode() {} |
562 BNode() {} |
563 LowerNode(const Node& node) : Node(node) { |
563 BNode(const Node& node) : Node(node) { |
564 LEMON_ASSERT(Parent::lower(node) || node == INVALID, |
564 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, |
565 typename Parent::NodeSetError()); |
565 typename Parent::NodeSetError()); |
566 } |
566 } |
567 LowerNode(Invalid) : Node(INVALID) {} |
567 BNode(Invalid) : Node(INVALID) {} |
568 }; |
568 }; |
569 |
569 |
570 void first(LowerNode& node) const { |
570 void first(BNode& node) const { |
571 Parent::firstLower(static_cast<Node&>(node)); |
571 Parent::firstBNode(static_cast<Node&>(node)); |
572 } |
572 } |
573 void next(LowerNode& node) const { |
573 void next(BNode& node) const { |
574 Parent::nextLower(static_cast<Node&>(node)); |
574 Parent::nextBNode(static_cast<Node&>(node)); |
575 } |
575 } |
576 |
576 |
577 int id(const LowerNode& node) const { |
577 int id(const BNode& node) const { |
578 return Parent::upperId(node); |
578 return Parent::aNodeId(node); |
579 } |
579 } |
580 |
580 |
581 |
581 |
582 |
582 |
583 int maxId(Node) const { |
583 int maxId(Node) const { |
584 return Parent::maxNodeId(); |
584 return Parent::maxNodeId(); |
585 } |
585 } |
586 int maxId(LowerNode) const { |
586 int maxId(BNode) const { |
587 return Parent::maxLowerId(); |
587 return Parent::maxBNodeId(); |
588 } |
588 } |
589 int maxId(UpperNode) const { |
589 int maxId(ANode) const { |
590 return Parent::maxUpperId(); |
590 return Parent::maxANodeId(); |
591 } |
591 } |
592 int maxId(Edge) const { |
592 int maxId(Edge) const { |
593 return maxEdgeId(); |
593 return maxEdgeId(); |
594 } |
594 } |
595 int maxId(UEdge) const { |
595 int maxId(UEdge) const { |
598 |
598 |
599 |
599 |
600 Node fromId(int id, Node) const { |
600 Node fromId(int id, Node) const { |
601 return Parent::nodeFromId(id); |
601 return Parent::nodeFromId(id); |
602 } |
602 } |
603 UpperNode fromId(int id, UpperNode) const { |
603 ANode fromId(int id, ANode) const { |
604 return Parent::fromUpperId(id); |
604 return Parent::fromANodeId(id); |
605 } |
605 } |
606 LowerNode fromId(int id, LowerNode) const { |
606 BNode fromId(int id, BNode) const { |
607 return Parent::fromLowerId(id); |
607 return Parent::fromBNodeId(id); |
608 } |
608 } |
609 Edge fromId(int id, Edge) const { |
609 Edge fromId(int id, Edge) const { |
610 return edgeFromId(id); |
610 return edgeFromId(id); |
611 } |
611 } |
612 UEdge fromId(int id, UEdge) const { |
612 UEdge fromId(int id, UEdge) const { |