r475:aea2dc0518ce
Fri, 09 Jan 2009 14:03:25
[Not Reviewed]
0 comments (0 inline)
0
1
0
176
144
| ... | ... |
@@ -429,104 +429,101 @@ |
| 429 | 429 |
Parent::first(i); |
| 430 | 430 |
while (i != INVALID && (!(*_arc_filter)[i] |
| 431 | 431 |
|| !(*_node_filter)[Parent::source(i)] |
| 432 | 432 |
|| !(*_node_filter)[Parent::target(i)])) |
| 433 | 433 |
Parent::next(i); |
| 434 | 434 |
} |
| 435 | 435 |
|
| 436 | 436 |
void firstIn(Arc& i, const Node& n) const {
|
| 437 | 437 |
Parent::firstIn(i, n); |
| 438 | 438 |
while (i != INVALID && (!(*_arc_filter)[i] |
| 439 | 439 |
|| !(*_node_filter)[Parent::source(i)])) |
| 440 | 440 |
Parent::nextIn(i); |
| 441 | 441 |
} |
| 442 | 442 |
|
| 443 | 443 |
void firstOut(Arc& i, const Node& n) const {
|
| 444 | 444 |
Parent::firstOut(i, n); |
| 445 | 445 |
while (i != INVALID && (!(*_arc_filter)[i] |
| 446 | 446 |
|| !(*_node_filter)[Parent::target(i)])) |
| 447 | 447 |
Parent::nextOut(i); |
| 448 | 448 |
} |
| 449 | 449 |
|
| 450 | 450 |
void next(Node& i) const {
|
| 451 | 451 |
Parent::next(i); |
| 452 | 452 |
while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); |
| 453 | 453 |
} |
| 454 | 454 |
|
| 455 | 455 |
void next(Arc& i) const {
|
| 456 | 456 |
Parent::next(i); |
| 457 | 457 |
while (i != INVALID && (!(*_arc_filter)[i] |
| 458 | 458 |
|| !(*_node_filter)[Parent::source(i)] |
| 459 | 459 |
|| !(*_node_filter)[Parent::target(i)])) |
| 460 | 460 |
Parent::next(i); |
| 461 | 461 |
} |
| 462 | 462 |
|
| 463 | 463 |
void nextIn(Arc& i) const {
|
| 464 | 464 |
Parent::nextIn(i); |
| 465 | 465 |
while (i != INVALID && (!(*_arc_filter)[i] |
| 466 | 466 |
|| !(*_node_filter)[Parent::source(i)])) |
| 467 | 467 |
Parent::nextIn(i); |
| 468 | 468 |
} |
| 469 | 469 |
|
| 470 | 470 |
void nextOut(Arc& i) const {
|
| 471 | 471 |
Parent::nextOut(i); |
| 472 | 472 |
while (i != INVALID && (!(*_arc_filter)[i] |
| 473 | 473 |
|| !(*_node_filter)[Parent::target(i)])) |
| 474 | 474 |
Parent::nextOut(i); |
| 475 | 475 |
} |
| 476 | 476 |
|
| 477 |
void hide(const Node& n) const { _node_filter->set(n, false); }
|
|
| 478 |
void hide(const Arc& a) const { _arc_filter->set(a, false); }
|
|
| 479 |
|
|
| 480 |
void unHide(const Node& n) const { _node_filter->set(n, true); }
|
|
| 481 |
void unHide(const Arc& a) const { _arc_filter->set(a, true); }
|
|
| 482 |
|
|
| 483 |
bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
|
|
| 484 |
bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
|
|
| 477 |
void status(const Node& n, bool v) const { _node_filter->set(n, v); }
|
|
| 478 |
void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
|
|
| 479 |
|
|
| 480 |
bool status(const Node& n) const { return (*_node_filter)[n]; }
|
|
| 481 |
bool status(const Arc& a) const { return (*_arc_filter)[a]; }
|
|
| 485 | 482 |
|
| 486 | 483 |
typedef False NodeNumTag; |
| 487 | 484 |
typedef False ArcNumTag; |
| 488 | 485 |
|
| 489 | 486 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
| 490 | 487 |
Arc findArc(const Node& source, const Node& target, |
| 491 | 488 |
const Arc& prev = INVALID) const {
|
| 492 | 489 |
if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
|
| 493 | 490 |
return INVALID; |
| 494 | 491 |
} |
| 495 | 492 |
Arc arc = Parent::findArc(source, target, prev); |
| 496 | 493 |
while (arc != INVALID && !(*_arc_filter)[arc]) {
|
| 497 | 494 |
arc = Parent::findArc(source, target, arc); |
| 498 | 495 |
} |
| 499 | 496 |
return arc; |
| 500 | 497 |
} |
| 501 | 498 |
|
| 502 | 499 |
template <typename _Value> |
| 503 | 500 |
class NodeMap : public SubMapExtender<Adaptor, |
| 504 | 501 |
typename Parent::template NodeMap<_Value> > {
|
| 505 | 502 |
public: |
| 506 | 503 |
typedef _Value Value; |
| 507 | 504 |
typedef SubMapExtender<Adaptor, typename Parent:: |
| 508 | 505 |
template NodeMap<Value> > MapParent; |
| 509 | 506 |
|
| 510 | 507 |
NodeMap(const Adaptor& adaptor) |
| 511 | 508 |
: MapParent(adaptor) {}
|
| 512 | 509 |
NodeMap(const Adaptor& adaptor, const Value& value) |
| 513 | 510 |
: MapParent(adaptor, value) {}
|
| 514 | 511 |
|
| 515 | 512 |
private: |
| 516 | 513 |
NodeMap& operator=(const NodeMap& cmap) {
|
| 517 | 514 |
return operator=<NodeMap>(cmap); |
| 518 | 515 |
} |
| 519 | 516 |
|
| 520 | 517 |
template <typename CMap> |
| 521 | 518 |
NodeMap& operator=(const CMap& cmap) {
|
| 522 | 519 |
MapParent::operator=(cmap); |
| 523 | 520 |
return *this; |
| 524 | 521 |
} |
| 525 | 522 |
}; |
| 526 | 523 |
|
| 527 | 524 |
template <typename _Value> |
| 528 | 525 |
class ArcMap : public SubMapExtender<Adaptor, |
| 529 | 526 |
typename Parent::template ArcMap<_Value> > {
|
| 530 | 527 |
public: |
| 531 | 528 |
typedef _Value Value; |
| 532 | 529 |
typedef SubMapExtender<Adaptor, typename Parent:: |
| ... | ... |
@@ -572,104 +569,101 @@ |
| 572 | 569 |
} |
| 573 | 570 |
void setArcFilterMap(ArcFilterMap& arc_filter) {
|
| 574 | 571 |
_arc_filter = &arc_filter; |
| 575 | 572 |
} |
| 576 | 573 |
|
| 577 | 574 |
public: |
| 578 | 575 |
|
| 579 | 576 |
typedef typename Parent::Node Node; |
| 580 | 577 |
typedef typename Parent::Arc Arc; |
| 581 | 578 |
|
| 582 | 579 |
void first(Node& i) const {
|
| 583 | 580 |
Parent::first(i); |
| 584 | 581 |
while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); |
| 585 | 582 |
} |
| 586 | 583 |
|
| 587 | 584 |
void first(Arc& i) const {
|
| 588 | 585 |
Parent::first(i); |
| 589 | 586 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); |
| 590 | 587 |
} |
| 591 | 588 |
|
| 592 | 589 |
void firstIn(Arc& i, const Node& n) const {
|
| 593 | 590 |
Parent::firstIn(i, n); |
| 594 | 591 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); |
| 595 | 592 |
} |
| 596 | 593 |
|
| 597 | 594 |
void firstOut(Arc& i, const Node& n) const {
|
| 598 | 595 |
Parent::firstOut(i, n); |
| 599 | 596 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); |
| 600 | 597 |
} |
| 601 | 598 |
|
| 602 | 599 |
void next(Node& i) const {
|
| 603 | 600 |
Parent::next(i); |
| 604 | 601 |
while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); |
| 605 | 602 |
} |
| 606 | 603 |
void next(Arc& i) const {
|
| 607 | 604 |
Parent::next(i); |
| 608 | 605 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); |
| 609 | 606 |
} |
| 610 | 607 |
void nextIn(Arc& i) const {
|
| 611 | 608 |
Parent::nextIn(i); |
| 612 | 609 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); |
| 613 | 610 |
} |
| 614 | 611 |
|
| 615 | 612 |
void nextOut(Arc& i) const {
|
| 616 | 613 |
Parent::nextOut(i); |
| 617 | 614 |
while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); |
| 618 | 615 |
} |
| 619 | 616 |
|
| 620 |
void hide(const Node& n) const { _node_filter->set(n, false); }
|
|
| 621 |
void hide(const Arc& e) const { _arc_filter->set(e, false); }
|
|
| 622 |
|
|
| 623 |
void unHide(const Node& n) const { _node_filter->set(n, true); }
|
|
| 624 |
void unHide(const Arc& e) const { _arc_filter->set(e, true); }
|
|
| 625 |
|
|
| 626 |
bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
|
|
| 627 |
bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
|
|
| 617 |
void status(const Node& n, bool v) const { _node_filter->set(n, v); }
|
|
| 618 |
void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
|
|
| 619 |
|
|
| 620 |
bool status(const Node& n) const { return (*_node_filter)[n]; }
|
|
| 621 |
bool status(const Arc& a) const { return (*_arc_filter)[a]; }
|
|
| 628 | 622 |
|
| 629 | 623 |
typedef False NodeNumTag; |
| 630 | 624 |
typedef False ArcNumTag; |
| 631 | 625 |
|
| 632 | 626 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
| 633 | 627 |
Arc findArc(const Node& source, const Node& target, |
| 634 | 628 |
const Arc& prev = INVALID) const {
|
| 635 | 629 |
if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
|
| 636 | 630 |
return INVALID; |
| 637 | 631 |
} |
| 638 | 632 |
Arc arc = Parent::findArc(source, target, prev); |
| 639 | 633 |
while (arc != INVALID && !(*_arc_filter)[arc]) {
|
| 640 | 634 |
arc = Parent::findArc(source, target, arc); |
| 641 | 635 |
} |
| 642 | 636 |
return arc; |
| 643 | 637 |
} |
| 644 | 638 |
|
| 645 | 639 |
template <typename _Value> |
| 646 | 640 |
class NodeMap : public SubMapExtender<Adaptor, |
| 647 | 641 |
typename Parent::template NodeMap<_Value> > {
|
| 648 | 642 |
public: |
| 649 | 643 |
typedef _Value Value; |
| 650 | 644 |
typedef SubMapExtender<Adaptor, typename Parent:: |
| 651 | 645 |
template NodeMap<Value> > MapParent; |
| 652 | 646 |
|
| 653 | 647 |
NodeMap(const Adaptor& adaptor) |
| 654 | 648 |
: MapParent(adaptor) {}
|
| 655 | 649 |
NodeMap(const Adaptor& adaptor, const Value& value) |
| 656 | 650 |
: MapParent(adaptor, value) {}
|
| 657 | 651 |
|
| 658 | 652 |
private: |
| 659 | 653 |
NodeMap& operator=(const NodeMap& cmap) {
|
| 660 | 654 |
return operator=<NodeMap>(cmap); |
| 661 | 655 |
} |
| 662 | 656 |
|
| 663 | 657 |
template <typename CMap> |
| 664 | 658 |
NodeMap& operator=(const CMap& cmap) {
|
| 665 | 659 |
MapParent::operator=(cmap); |
| 666 | 660 |
return *this; |
| 667 | 661 |
} |
| 668 | 662 |
}; |
| 669 | 663 |
|
| 670 | 664 |
template <typename _Value> |
| 671 | 665 |
class ArcMap : public SubMapExtender<Adaptor, |
| 672 | 666 |
typename Parent::template ArcMap<_Value> > {
|
| 673 | 667 |
public: |
| 674 | 668 |
typedef _Value Value; |
| 675 | 669 |
typedef SubMapExtender<Adaptor, typename Parent:: |
| ... | ... |
@@ -729,135 +723,147 @@ |
| 729 | 723 |
/// digraph are convertible to each other. |
| 730 | 724 |
/// |
| 731 | 725 |
/// \see FilterNodes |
| 732 | 726 |
/// \see FilterArcs |
| 733 | 727 |
#ifdef DOXYGEN |
| 734 | 728 |
template<typename _Digraph, |
| 735 | 729 |
typename _NodeFilterMap, |
| 736 | 730 |
typename _ArcFilterMap, |
| 737 | 731 |
bool _checked> |
| 738 | 732 |
#else |
| 739 | 733 |
template<typename _Digraph, |
| 740 | 734 |
typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, |
| 741 | 735 |
typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, |
| 742 | 736 |
bool _checked = true> |
| 743 | 737 |
#endif |
| 744 | 738 |
class SubDigraph |
| 745 | 739 |
: public DigraphAdaptorExtender< |
| 746 | 740 |
SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
|
| 747 | 741 |
public: |
| 748 | 742 |
/// The type of the adapted digraph. |
| 749 | 743 |
typedef _Digraph Digraph; |
| 750 | 744 |
/// The type of the node filter map. |
| 751 | 745 |
typedef _NodeFilterMap NodeFilterMap; |
| 752 | 746 |
/// The type of the arc filter map. |
| 753 | 747 |
typedef _ArcFilterMap ArcFilterMap; |
| 754 | 748 |
|
| 755 | 749 |
typedef DigraphAdaptorExtender< |
| 756 | 750 |
SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > |
| 757 | 751 |
Parent; |
| 758 | 752 |
|
| 759 | 753 |
typedef typename Parent::Node Node; |
| 760 | 754 |
typedef typename Parent::Arc Arc; |
| 761 | 755 |
|
| 762 | 756 |
protected: |
| 763 | 757 |
SubDigraph() { }
|
| 764 | 758 |
public: |
| 765 | 759 |
|
| 766 | 760 |
/// \brief Constructor |
| 767 | 761 |
/// |
| 768 | 762 |
/// Creates a subdigraph for the given digraph with the |
| 769 | 763 |
/// given node and arc filter maps. |
| 770 | 764 |
SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, |
| 771 | 765 |
ArcFilterMap& arc_filter) {
|
| 772 | 766 |
setDigraph(digraph); |
| 773 | 767 |
setNodeFilterMap(node_filter); |
| 774 | 768 |
setArcFilterMap(arc_filter); |
| 775 | 769 |
} |
| 776 | 770 |
|
| 777 |
/// \brief |
|
| 771 |
/// \brief Sets the status of the given node |
|
| 778 | 772 |
/// |
| 779 |
/// This function hides the given node in the subdigraph, |
|
| 780 |
/// i.e. the iteration jumps over it. |
|
| 773 |
/// This function sets the status of the given node. |
|
| 781 | 774 |
/// It is done by simply setting the assigned value of \c n |
| 782 |
/// to be \c false in the node filter map. |
|
| 783 |
void hide(const Node& n) const { Parent::hide(n); }
|
|
| 784 |
|
|
| 785 |
/// \brief Hides the given arc |
|
| 775 |
/// to \c v in the node filter map. |
|
| 776 |
void status(const Node& n, bool v) const { Parent::status(n, v); }
|
|
| 777 |
|
|
| 778 |
/// \brief Sets the status of the given arc |
|
| 786 | 779 |
/// |
| 787 |
/// This function hides the given arc in the subdigraph, |
|
| 788 |
/// i.e. the iteration jumps over it. |
|
| 780 |
/// This function sets the status of the given arc. |
|
| 789 | 781 |
/// It is done by simply setting the assigned value of \c a |
| 790 |
/// to be \c false in the arc filter map. |
|
| 791 |
void hide(const Arc& a) const { Parent::hide(a); }
|
|
| 792 |
|
|
| 793 |
/// \brief Shows the given node |
|
| 782 |
/// to \c v in the arc filter map. |
|
| 783 |
void status(const Arc& a, bool v) const { Parent::status(a, v); }
|
|
| 784 |
|
|
| 785 |
/// \brief Returns the status of the given node |
|
| 794 | 786 |
/// |
| 795 |
/// This function shows the given node in the subdigraph. |
|
| 796 |
/// It is done by simply setting the assigned value of \c n |
|
| 797 |
/// to be \c true in the node filter map. |
|
| 798 |
void unHide(const Node& n) const { Parent::unHide(n); }
|
|
| 799 |
|
|
| 800 |
/// \brief Shows the given arc |
|
| 787 |
/// This function returns the status of the given node. |
|
| 788 |
/// It is \c true if the given node is enabled (i.e. not hidden). |
|
| 789 |
bool status(const Node& n) const { return Parent::status(n); }
|
|
| 790 |
|
|
| 791 |
/// \brief Returns the status of the given arc |
|
| 801 | 792 |
/// |
| 802 |
/// This function shows the given arc in the subdigraph. |
|
| 803 |
/// It is done by simply setting the assigned value of \c a |
|
| 804 |
/// to be \c true in the arc filter map. |
|
| 805 |
void unHide(const Arc& a) const { Parent::unHide(a); }
|
|
| 806 |
|
|
| 807 |
/// \brief Returns \c true if the given node is hidden. |
|
| 793 |
/// This function returns the status of the given arc. |
|
| 794 |
/// It is \c true if the given arc is enabled (i.e. not hidden). |
|
| 795 |
bool status(const Arc& a) const { return Parent::status(a); }
|
|
| 796 |
|
|
| 797 |
/// \brief Disables the given node |
|
| 808 | 798 |
/// |
| 809 |
/// This function returns \c true if the given node is hidden. |
|
| 810 |
bool hidden(const Node& n) const { return Parent::hidden(n); }
|
|
| 811 |
|
|
| 812 |
/// \brief Returns \c true if the given arc is hidden. |
|
| 799 |
/// This function disables the given node in the subdigraph, |
|
| 800 |
/// so the iteration jumps over it. |
|
| 801 |
/// It is the same as \ref status() "status(n, false)". |
|
| 802 |
void disable(const Node& n) const { Parent::status(n, false); }
|
|
| 803 |
|
|
| 804 |
/// \brief Disables the given arc |
|
| 813 | 805 |
/// |
| 814 |
/// This function returns \c true if the given arc is hidden. |
|
| 815 |
bool hidden(const Arc& a) const { return Parent::hidden(a); }
|
|
| 806 |
/// This function disables the given arc in the subdigraph, |
|
| 807 |
/// so the iteration jumps over it. |
|
| 808 |
/// It is the same as \ref status() "status(a, false)". |
|
| 809 |
void disable(const Arc& a) const { Parent::status(a, false); }
|
|
| 810 |
|
|
| 811 |
/// \brief Enables the given node |
|
| 812 |
/// |
|
| 813 |
/// This function enables the given node in the subdigraph. |
|
| 814 |
/// It is the same as \ref status() "status(n, true)". |
|
| 815 |
void enable(const Node& n) const { Parent::status(n, true); }
|
|
| 816 |
|
|
| 817 |
/// \brief Enables the given arc |
|
| 818 |
/// |
|
| 819 |
/// This function enables the given arc in the subdigraph. |
|
| 820 |
/// It is the same as \ref status() "status(a, true)". |
|
| 821 |
void enable(const Arc& a) const { Parent::status(a, true); }
|
|
| 816 | 822 |
|
| 817 | 823 |
}; |
| 818 | 824 |
|
| 819 | 825 |
/// \brief Returns a read-only SubDigraph adaptor |
| 820 | 826 |
/// |
| 821 | 827 |
/// This function just returns a read-only \ref SubDigraph adaptor. |
| 822 | 828 |
/// \ingroup graph_adaptors |
| 823 | 829 |
/// \relates SubDigraph |
| 824 | 830 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
| 825 | 831 |
SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> |
| 826 | 832 |
subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
|
| 827 | 833 |
return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> |
| 828 | 834 |
(digraph, nfm, afm); |
| 829 | 835 |
} |
| 830 | 836 |
|
| 831 | 837 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
| 832 | 838 |
SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> |
| 833 | 839 |
subDigraph(const Digraph& digraph, |
| 834 | 840 |
const NodeFilterMap& nfm, ArcFilterMap& afm) {
|
| 835 | 841 |
return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> |
| 836 | 842 |
(digraph, nfm, afm); |
| 837 | 843 |
} |
| 838 | 844 |
|
| 839 | 845 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
| 840 | 846 |
SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> |
| 841 | 847 |
subDigraph(const Digraph& digraph, |
| 842 | 848 |
NodeFilterMap& nfm, const ArcFilterMap& afm) {
|
| 843 | 849 |
return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> |
| 844 | 850 |
(digraph, nfm, afm); |
| 845 | 851 |
} |
| 846 | 852 |
|
| 847 | 853 |
template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
| 848 | 854 |
SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap> |
| 849 | 855 |
subDigraph(const Digraph& digraph, |
| 850 | 856 |
const NodeFilterMap& nfm, const ArcFilterMap& afm) {
|
| 851 | 857 |
return SubDigraph<const Digraph, const NodeFilterMap, |
| 852 | 858 |
const ArcFilterMap>(digraph, nfm, afm); |
| 853 | 859 |
} |
| 854 | 860 |
|
| 855 | 861 |
|
| 856 | 862 |
template <typename _Graph, typename _NodeFilterMap, |
| 857 | 863 |
typename _EdgeFilterMap, bool _checked = true> |
| 858 | 864 |
class SubGraphBase : public GraphAdaptorBase<_Graph> {
|
| 859 | 865 |
public: |
| 860 | 866 |
typedef _Graph Graph; |
| 861 | 867 |
typedef _NodeFilterMap NodeFilterMap; |
| 862 | 868 |
typedef _EdgeFilterMap EdgeFilterMap; |
| 863 | 869 |
|
| ... | ... |
@@ -925,104 +931,101 @@ |
| 925 | 931 |
|| !(*_node_filter_map)[Parent::u(i)] |
| 926 | 932 |
|| !(*_node_filter_map)[Parent::v(i)])) |
| 927 | 933 |
Parent::nextInc(i, d); |
| 928 | 934 |
} |
| 929 | 935 |
|
| 930 | 936 |
void next(Node& i) const {
|
| 931 | 937 |
Parent::next(i); |
| 932 | 938 |
while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); |
| 933 | 939 |
} |
| 934 | 940 |
|
| 935 | 941 |
void next(Arc& i) const {
|
| 936 | 942 |
Parent::next(i); |
| 937 | 943 |
while (i!=INVALID && (!(*_edge_filter_map)[i] |
| 938 | 944 |
|| !(*_node_filter_map)[Parent::source(i)] |
| 939 | 945 |
|| !(*_node_filter_map)[Parent::target(i)])) |
| 940 | 946 |
Parent::next(i); |
| 941 | 947 |
} |
| 942 | 948 |
|
| 943 | 949 |
void next(Edge& i) const {
|
| 944 | 950 |
Parent::next(i); |
| 945 | 951 |
while (i!=INVALID && (!(*_edge_filter_map)[i] |
| 946 | 952 |
|| !(*_node_filter_map)[Parent::u(i)] |
| 947 | 953 |
|| !(*_node_filter_map)[Parent::v(i)])) |
| 948 | 954 |
Parent::next(i); |
| 949 | 955 |
} |
| 950 | 956 |
|
| 951 | 957 |
void nextIn(Arc& i) const {
|
| 952 | 958 |
Parent::nextIn(i); |
| 953 | 959 |
while (i!=INVALID && (!(*_edge_filter_map)[i] |
| 954 | 960 |
|| !(*_node_filter_map)[Parent::source(i)])) |
| 955 | 961 |
Parent::nextIn(i); |
| 956 | 962 |
} |
| 957 | 963 |
|
| 958 | 964 |
void nextOut(Arc& i) const {
|
| 959 | 965 |
Parent::nextOut(i); |
| 960 | 966 |
while (i!=INVALID && (!(*_edge_filter_map)[i] |
| 961 | 967 |
|| !(*_node_filter_map)[Parent::target(i)])) |
| 962 | 968 |
Parent::nextOut(i); |
| 963 | 969 |
} |
| 964 | 970 |
|
| 965 | 971 |
void nextInc(Edge& i, bool& d) const {
|
| 966 | 972 |
Parent::nextInc(i, d); |
| 967 | 973 |
while (i!=INVALID && (!(*_edge_filter_map)[i] |
| 968 | 974 |
|| !(*_node_filter_map)[Parent::u(i)] |
| 969 | 975 |
|| !(*_node_filter_map)[Parent::v(i)])) |
| 970 | 976 |
Parent::nextInc(i, d); |
| 971 | 977 |
} |
| 972 | 978 |
|
| 973 |
void hide(const Node& n) const { _node_filter_map->set(n, false); }
|
|
| 974 |
void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
|
|
| 975 |
|
|
| 976 |
void unHide(const Node& n) const { _node_filter_map->set(n, true); }
|
|
| 977 |
void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
|
|
| 978 |
|
|
| 979 |
bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
|
|
| 980 |
bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
|
|
| 979 |
void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
|
|
| 980 |
void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
|
|
| 981 |
|
|
| 982 |
bool status(const Node& n) const { return (*_node_filter_map)[n]; }
|
|
| 983 |
bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
|
|
| 981 | 984 |
|
| 982 | 985 |
typedef False NodeNumTag; |
| 983 | 986 |
typedef False ArcNumTag; |
| 984 | 987 |
typedef False EdgeNumTag; |
| 985 | 988 |
|
| 986 | 989 |
typedef FindArcTagIndicator<Graph> FindArcTag; |
| 987 | 990 |
Arc findArc(const Node& u, const Node& v, |
| 988 | 991 |
const Arc& prev = INVALID) const {
|
| 989 | 992 |
if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
|
| 990 | 993 |
return INVALID; |
| 991 | 994 |
} |
| 992 | 995 |
Arc arc = Parent::findArc(u, v, prev); |
| 993 | 996 |
while (arc != INVALID && !(*_edge_filter_map)[arc]) {
|
| 994 | 997 |
arc = Parent::findArc(u, v, arc); |
| 995 | 998 |
} |
| 996 | 999 |
return arc; |
| 997 | 1000 |
} |
| 998 | 1001 |
|
| 999 | 1002 |
typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
| 1000 | 1003 |
Edge findEdge(const Node& u, const Node& v, |
| 1001 | 1004 |
const Edge& prev = INVALID) const {
|
| 1002 | 1005 |
if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
|
| 1003 | 1006 |
return INVALID; |
| 1004 | 1007 |
} |
| 1005 | 1008 |
Edge edge = Parent::findEdge(u, v, prev); |
| 1006 | 1009 |
while (edge != INVALID && !(*_edge_filter_map)[edge]) {
|
| 1007 | 1010 |
edge = Parent::findEdge(u, v, edge); |
| 1008 | 1011 |
} |
| 1009 | 1012 |
return edge; |
| 1010 | 1013 |
} |
| 1011 | 1014 |
|
| 1012 | 1015 |
template <typename _Value> |
| 1013 | 1016 |
class NodeMap : public SubMapExtender<Adaptor, |
| 1014 | 1017 |
typename Parent::template NodeMap<_Value> > {
|
| 1015 | 1018 |
public: |
| 1016 | 1019 |
typedef _Value Value; |
| 1017 | 1020 |
typedef SubMapExtender<Adaptor, typename Parent:: |
| 1018 | 1021 |
template NodeMap<Value> > MapParent; |
| 1019 | 1022 |
|
| 1020 | 1023 |
NodeMap(const Adaptor& adaptor) |
| 1021 | 1024 |
: MapParent(adaptor) {}
|
| 1022 | 1025 |
NodeMap(const Adaptor& adaptor, const Value& value) |
| 1023 | 1026 |
: MapParent(adaptor, value) {}
|
| 1024 | 1027 |
|
| 1025 | 1028 |
private: |
| 1026 | 1029 |
NodeMap& operator=(const NodeMap& cmap) {
|
| 1027 | 1030 |
return operator=<NodeMap>(cmap); |
| 1028 | 1031 |
} |
| ... | ... |
@@ -1127,104 +1130,101 @@ |
| 1127 | 1130 |
} |
| 1128 | 1131 |
|
| 1129 | 1132 |
void first(Edge& i) const {
|
| 1130 | 1133 |
Parent::first(i); |
| 1131 | 1134 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); |
| 1132 | 1135 |
} |
| 1133 | 1136 |
|
| 1134 | 1137 |
void firstIn(Arc& i, const Node& n) const {
|
| 1135 | 1138 |
Parent::firstIn(i, n); |
| 1136 | 1139 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); |
| 1137 | 1140 |
} |
| 1138 | 1141 |
|
| 1139 | 1142 |
void firstOut(Arc& i, const Node& n) const {
|
| 1140 | 1143 |
Parent::firstOut(i, n); |
| 1141 | 1144 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); |
| 1142 | 1145 |
} |
| 1143 | 1146 |
|
| 1144 | 1147 |
void firstInc(Edge& i, bool& d, const Node& n) const {
|
| 1145 | 1148 |
Parent::firstInc(i, d, n); |
| 1146 | 1149 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); |
| 1147 | 1150 |
} |
| 1148 | 1151 |
|
| 1149 | 1152 |
void next(Node& i) const {
|
| 1150 | 1153 |
Parent::next(i); |
| 1151 | 1154 |
while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); |
| 1152 | 1155 |
} |
| 1153 | 1156 |
void next(Arc& i) const {
|
| 1154 | 1157 |
Parent::next(i); |
| 1155 | 1158 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); |
| 1156 | 1159 |
} |
| 1157 | 1160 |
void next(Edge& i) const {
|
| 1158 | 1161 |
Parent::next(i); |
| 1159 | 1162 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); |
| 1160 | 1163 |
} |
| 1161 | 1164 |
void nextIn(Arc& i) const {
|
| 1162 | 1165 |
Parent::nextIn(i); |
| 1163 | 1166 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); |
| 1164 | 1167 |
} |
| 1165 | 1168 |
|
| 1166 | 1169 |
void nextOut(Arc& i) const {
|
| 1167 | 1170 |
Parent::nextOut(i); |
| 1168 | 1171 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); |
| 1169 | 1172 |
} |
| 1170 | 1173 |
void nextInc(Edge& i, bool& d) const {
|
| 1171 | 1174 |
Parent::nextInc(i, d); |
| 1172 | 1175 |
while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); |
| 1173 | 1176 |
} |
| 1174 | 1177 |
|
| 1175 |
void hide(const Node& n) const { _node_filter_map->set(n, false); }
|
|
| 1176 |
void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
|
|
| 1177 |
|
|
| 1178 |
void unHide(const Node& n) const { _node_filter_map->set(n, true); }
|
|
| 1179 |
void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
|
|
| 1180 |
|
|
| 1181 |
bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
|
|
| 1182 |
bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
|
|
| 1178 |
void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
|
|
| 1179 |
void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
|
|
| 1180 |
|
|
| 1181 |
bool status(const Node& n) const { return (*_node_filter_map)[n]; }
|
|
| 1182 |
bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
|
|
| 1183 | 1183 |
|
| 1184 | 1184 |
typedef False NodeNumTag; |
| 1185 | 1185 |
typedef False ArcNumTag; |
| 1186 | 1186 |
typedef False EdgeNumTag; |
| 1187 | 1187 |
|
| 1188 | 1188 |
typedef FindArcTagIndicator<Graph> FindArcTag; |
| 1189 | 1189 |
Arc findArc(const Node& u, const Node& v, |
| 1190 | 1190 |
const Arc& prev = INVALID) const {
|
| 1191 | 1191 |
Arc arc = Parent::findArc(u, v, prev); |
| 1192 | 1192 |
while (arc != INVALID && !(*_edge_filter_map)[arc]) {
|
| 1193 | 1193 |
arc = Parent::findArc(u, v, arc); |
| 1194 | 1194 |
} |
| 1195 | 1195 |
return arc; |
| 1196 | 1196 |
} |
| 1197 | 1197 |
|
| 1198 | 1198 |
typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
| 1199 | 1199 |
Edge findEdge(const Node& u, const Node& v, |
| 1200 | 1200 |
const Edge& prev = INVALID) const {
|
| 1201 | 1201 |
Edge edge = Parent::findEdge(u, v, prev); |
| 1202 | 1202 |
while (edge != INVALID && !(*_edge_filter_map)[edge]) {
|
| 1203 | 1203 |
edge = Parent::findEdge(u, v, edge); |
| 1204 | 1204 |
} |
| 1205 | 1205 |
return edge; |
| 1206 | 1206 |
} |
| 1207 | 1207 |
|
| 1208 | 1208 |
template <typename _Value> |
| 1209 | 1209 |
class NodeMap : public SubMapExtender<Adaptor, |
| 1210 | 1210 |
typename Parent::template NodeMap<_Value> > {
|
| 1211 | 1211 |
public: |
| 1212 | 1212 |
typedef _Value Value; |
| 1213 | 1213 |
typedef SubMapExtender<Adaptor, typename Parent:: |
| 1214 | 1214 |
template NodeMap<Value> > MapParent; |
| 1215 | 1215 |
|
| 1216 | 1216 |
NodeMap(const Adaptor& adaptor) |
| 1217 | 1217 |
: MapParent(adaptor) {}
|
| 1218 | 1218 |
NodeMap(const Adaptor& adaptor, const Value& value) |
| 1219 | 1219 |
: MapParent(adaptor, value) {}
|
| 1220 | 1220 |
|
| 1221 | 1221 |
private: |
| 1222 | 1222 |
NodeMap& operator=(const NodeMap& cmap) {
|
| 1223 | 1223 |
return operator=<NodeMap>(cmap); |
| 1224 | 1224 |
} |
| 1225 | 1225 |
|
| 1226 | 1226 |
template <typename CMap> |
| 1227 | 1227 |
NodeMap& operator=(const CMap& cmap) {
|
| 1228 | 1228 |
MapParent::operator=(cmap); |
| 1229 | 1229 |
return *this; |
| 1230 | 1230 |
} |
| ... | ... |
@@ -1318,135 +1318,148 @@ |
| 1318 | 1318 |
/// \note The \c Node, \c Edge and \c Arc types of this adaptor and the |
| 1319 | 1319 |
/// adapted graph are convertible to each other. |
| 1320 | 1320 |
/// |
| 1321 | 1321 |
/// \see FilterNodes |
| 1322 | 1322 |
/// \see FilterEdges |
| 1323 | 1323 |
#ifdef DOXYGEN |
| 1324 | 1324 |
template<typename _Graph, |
| 1325 | 1325 |
typename _NodeFilterMap, |
| 1326 | 1326 |
typename _EdgeFilterMap, |
| 1327 | 1327 |
bool _checked> |
| 1328 | 1328 |
#else |
| 1329 | 1329 |
template<typename _Graph, |
| 1330 | 1330 |
typename _NodeFilterMap = typename _Graph::template NodeMap<bool>, |
| 1331 | 1331 |
typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool>, |
| 1332 | 1332 |
bool _checked = true> |
| 1333 | 1333 |
#endif |
| 1334 | 1334 |
class SubGraph |
| 1335 | 1335 |
: public GraphAdaptorExtender< |
| 1336 | 1336 |
SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > {
|
| 1337 | 1337 |
public: |
| 1338 | 1338 |
/// The type of the adapted graph. |
| 1339 | 1339 |
typedef _Graph Graph; |
| 1340 | 1340 |
/// The type of the node filter map. |
| 1341 | 1341 |
typedef _NodeFilterMap NodeFilterMap; |
| 1342 | 1342 |
/// The type of the edge filter map. |
| 1343 | 1343 |
typedef _EdgeFilterMap EdgeFilterMap; |
| 1344 | 1344 |
|
| 1345 | 1345 |
typedef GraphAdaptorExtender< |
| 1346 | 1346 |
SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent; |
| 1347 | 1347 |
|
| 1348 | 1348 |
typedef typename Parent::Node Node; |
| 1349 | 1349 |
typedef typename Parent::Edge Edge; |
| 1350 | 1350 |
|
| 1351 | 1351 |
protected: |
| 1352 | 1352 |
SubGraph() { }
|
| 1353 | 1353 |
public: |
| 1354 | 1354 |
|
| 1355 | 1355 |
/// \brief Constructor |
| 1356 | 1356 |
/// |
| 1357 | 1357 |
/// Creates a subgraph for the given graph with the given node |
| 1358 | 1358 |
/// and edge filter maps. |
| 1359 | 1359 |
SubGraph(Graph& graph, NodeFilterMap& node_filter_map, |
| 1360 | 1360 |
EdgeFilterMap& edge_filter_map) {
|
| 1361 | 1361 |
setGraph(graph); |
| 1362 | 1362 |
setNodeFilterMap(node_filter_map); |
| 1363 | 1363 |
setEdgeFilterMap(edge_filter_map); |
| 1364 | 1364 |
} |
| 1365 | 1365 |
|
| 1366 |
/// \brief |
|
| 1366 |
/// \brief Sets the status of the given node |
|
| 1367 | 1367 |
/// |
| 1368 |
/// This function hides the given node in the subgraph, |
|
| 1369 |
/// i.e. the iteration jumps over it. |
|
| 1368 |
/// This function sets the status of the given node. |
|
| 1370 | 1369 |
/// It is done by simply setting the assigned value of \c n |
| 1371 |
/// to be \c false in the node filter map. |
|
| 1372 |
void hide(const Node& n) const { Parent::hide(n); }
|
|
| 1373 |
|
|
| 1374 |
/// \brief Hides the given edge |
|
| 1370 |
/// to \c v in the node filter map. |
|
| 1371 |
void status(const Node& n, bool v) const { Parent::status(n, v); }
|
|
| 1372 |
|
|
| 1373 |
/// \brief Sets the status of the given edge |
|
| 1375 | 1374 |
/// |
| 1376 |
/// This function hides the given edge in the subgraph, |
|
| 1377 |
/// i.e. the iteration jumps over it. |
|
| 1375 |
/// This function sets the status of the given edge. |
|
| 1378 | 1376 |
/// It is done by simply setting the assigned value of \c e |
| 1379 |
/// to be \c false in the edge filter map. |
|
| 1380 |
void hide(const Edge& e) const { Parent::hide(e); }
|
|
| 1381 |
|
|
| 1382 |
/// \brief Shows the given node |
|
| 1377 |
/// to \c v in the edge filter map. |
|
| 1378 |
void status(const Edge& e, bool v) const { Parent::status(e, v); }
|
|
| 1379 |
|
|
| 1380 |
/// \brief Returns the status of the given node |
|
| 1383 | 1381 |
/// |
| 1384 |
/// This function shows the given node in the subgraph. |
|
| 1385 |
/// It is done by simply setting the assigned value of \c n |
|
| 1386 |
/// to be \c true in the node filter map. |
|
| 1387 |
void unHide(const Node& n) const { Parent::unHide(n); }
|
|
| 1388 |
|
|
| 1389 |
/// \brief Shows the given edge |
|
| 1382 |
/// This function returns the status of the given node. |
|
| 1383 |
/// It is \c true if the given node is enabled (i.e. not hidden). |
|
| 1384 |
bool status(const Node& n) const { return Parent::status(n); }
|
|
| 1385 |
|
|
| 1386 |
/// \brief Returns the status of the given edge |
|
| 1390 | 1387 |
/// |
| 1391 |
/// This function shows the given edge in the subgraph. |
|
| 1392 |
/// It is done by simply setting the assigned value of \c e |
|
| 1393 |
/// to be \c true in the edge filter map. |
|
| 1394 |
void unHide(const Edge& e) const { Parent::unHide(e); }
|
|
| 1395 |
|
|
| 1396 |
/// \brief Returns \c true if the given node is hidden. |
|
| 1388 |
/// This function returns the status of the given edge. |
|
| 1389 |
/// It is \c true if the given edge is enabled (i.e. not hidden). |
|
| 1390 |
bool status(const Edge& e) const { return Parent::status(e); }
|
|
| 1391 |
|
|
| 1392 |
/// \brief Disables the given node |
|
| 1397 | 1393 |
/// |
| 1398 |
/// This function returns \c true if the given node is hidden. |
|
| 1399 |
bool hidden(const Node& n) const { return Parent::hidden(n); }
|
|
| 1400 |
|
|
| 1401 |
/// \brief Returns \c true if the given edge is hidden. |
|
| 1394 |
/// This function disables the given node in the subdigraph, |
|
| 1395 |
/// so the iteration jumps over it. |
|
| 1396 |
/// It is the same as \ref status() "status(n, false)". |
|
| 1397 |
void disable(const Node& n) const { Parent::status(n, false); }
|
|
| 1398 |
|
|
| 1399 |
/// \brief Disables the given edge |
|
| 1402 | 1400 |
/// |
| 1403 |
/// This function returns \c true if the given edge is hidden. |
|
| 1404 |
bool hidden(const Edge& e) const { return Parent::hidden(e); }
|
|
| 1401 |
/// This function disables the given edge in the subgraph, |
|
| 1402 |
/// so the iteration jumps over it. |
|
| 1403 |
/// It is the same as \ref status() "status(e, false)". |
|
| 1404 |
void disable(const Edge& e) const { Parent::status(e, false); }
|
|
| 1405 |
|
|
| 1406 |
/// \brief Enables the given node |
|
| 1407 |
/// |
|
| 1408 |
/// This function enables the given node in the subdigraph. |
|
| 1409 |
/// It is the same as \ref status() "status(n, true)". |
|
| 1410 |
void enable(const Node& n) const { Parent::status(n, true); }
|
|
| 1411 |
|
|
| 1412 |
/// \brief Enables the given edge |
|
| 1413 |
/// |
|
| 1414 |
/// This function enables the given edge in the subgraph. |
|
| 1415 |
/// It is the same as \ref status() "status(e, true)". |
|
| 1416 |
void enable(const Edge& e) const { Parent::status(e, true); }
|
|
| 1417 |
|
|
| 1405 | 1418 |
}; |
| 1406 | 1419 |
|
| 1407 | 1420 |
/// \brief Returns a read-only SubGraph adaptor |
| 1408 | 1421 |
/// |
| 1409 | 1422 |
/// This function just returns a read-only \ref SubGraph adaptor. |
| 1410 | 1423 |
/// \ingroup graph_adaptors |
| 1411 | 1424 |
/// \relates SubGraph |
| 1412 | 1425 |
template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
| 1413 | 1426 |
SubGraph<const Graph, NodeFilterMap, ArcFilterMap> |
| 1414 | 1427 |
subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
|
| 1415 | 1428 |
return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm); |
| 1416 | 1429 |
} |
| 1417 | 1430 |
|
| 1418 | 1431 |
template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
| 1419 | 1432 |
SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> |
| 1420 | 1433 |
subGraph(const Graph& graph, |
| 1421 | 1434 |
const NodeFilterMap& nfm, ArcFilterMap& efm) {
|
| 1422 | 1435 |
return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> |
| 1423 | 1436 |
(graph, nfm, efm); |
| 1424 | 1437 |
} |
| 1425 | 1438 |
|
| 1426 | 1439 |
template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
| 1427 | 1440 |
SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> |
| 1428 | 1441 |
subGraph(const Graph& graph, |
| 1429 | 1442 |
NodeFilterMap& nfm, const ArcFilterMap& efm) {
|
| 1430 | 1443 |
return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> |
| 1431 | 1444 |
(graph, nfm, efm); |
| 1432 | 1445 |
} |
| 1433 | 1446 |
|
| 1434 | 1447 |
template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
| 1435 | 1448 |
SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> |
| 1436 | 1449 |
subGraph(const Graph& graph, |
| 1437 | 1450 |
const NodeFilterMap& nfm, const ArcFilterMap& efm) {
|
| 1438 | 1451 |
return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> |
| 1439 | 1452 |
(graph, nfm, efm); |
| 1440 | 1453 |
} |
| 1441 | 1454 |
|
| 1442 | 1455 |
|
| 1443 | 1456 |
/// \ingroup graph_adaptors |
| 1444 | 1457 |
/// |
| 1445 | 1458 |
/// \brief Adaptor class for hiding nodes in a digraph or a graph. |
| 1446 | 1459 |
/// |
| 1447 | 1460 |
/// FilterNodes adaptor can be used for hiding nodes in a digraph or a |
| 1448 | 1461 |
/// graph. A \c bool node map must be specified, which defines the filter |
| 1449 | 1462 |
/// for the nodes. Only the nodes with \c true filter value and the |
| 1450 | 1463 |
/// arcs/edges incident to nodes both with \c true filter value are shown |
| 1451 | 1464 |
/// in the subgraph. This adaptor conforms to the \ref concepts::Digraph |
| 1452 | 1465 |
/// "Digraph" concept or the \ref concepts::Graph "Graph" concept |
| ... | ... |
@@ -1474,350 +1487,369 @@ |
| 1474 | 1487 |
#ifdef DOXYGEN |
| 1475 | 1488 |
template<typename _Graph, |
| 1476 | 1489 |
typename _NodeFilterMap, |
| 1477 | 1490 |
bool _checked> |
| 1478 | 1491 |
#else |
| 1479 | 1492 |
template<typename _Digraph, |
| 1480 | 1493 |
typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, |
| 1481 | 1494 |
bool _checked = true, |
| 1482 | 1495 |
typename Enable = void> |
| 1483 | 1496 |
#endif |
| 1484 | 1497 |
class FilterNodes |
| 1485 | 1498 |
: public SubDigraph<_Digraph, _NodeFilterMap, |
| 1486 | 1499 |
ConstMap<typename _Digraph::Arc, bool>, _checked> {
|
| 1487 | 1500 |
public: |
| 1488 | 1501 |
|
| 1489 | 1502 |
typedef _Digraph Digraph; |
| 1490 | 1503 |
typedef _NodeFilterMap NodeFilterMap; |
| 1491 | 1504 |
|
| 1492 | 1505 |
typedef SubDigraph<Digraph, NodeFilterMap, |
| 1493 | 1506 |
ConstMap<typename Digraph::Arc, bool>, _checked> |
| 1494 | 1507 |
Parent; |
| 1495 | 1508 |
|
| 1496 | 1509 |
typedef typename Parent::Node Node; |
| 1497 | 1510 |
|
| 1498 | 1511 |
protected: |
| 1499 | 1512 |
ConstMap<typename Digraph::Arc, bool> const_true_map; |
| 1500 | 1513 |
|
| 1501 | 1514 |
FilterNodes() : const_true_map(true) {
|
| 1502 | 1515 |
Parent::setArcFilterMap(const_true_map); |
| 1503 | 1516 |
} |
| 1504 | 1517 |
|
| 1505 | 1518 |
public: |
| 1506 | 1519 |
|
| 1507 | 1520 |
/// \brief Constructor |
| 1508 | 1521 |
/// |
| 1509 | 1522 |
/// Creates a subgraph for the given digraph or graph with the |
| 1510 | 1523 |
/// given node filter map. |
| 1511 | 1524 |
#ifdef DOXYGEN |
| 1512 | 1525 |
FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) : |
| 1513 | 1526 |
#else |
| 1514 | 1527 |
FilterNodes(Digraph& graph, NodeFilterMap& node_filter) : |
| 1515 | 1528 |
#endif |
| 1516 | 1529 |
Parent(), const_true_map(true) {
|
| 1517 | 1530 |
Parent::setDigraph(graph); |
| 1518 | 1531 |
Parent::setNodeFilterMap(node_filter); |
| 1519 | 1532 |
Parent::setArcFilterMap(const_true_map); |
| 1520 | 1533 |
} |
| 1521 | 1534 |
|
| 1522 |
/// \brief |
|
| 1535 |
/// \brief Sets the status of the given node |
|
| 1523 | 1536 |
/// |
| 1524 |
/// This function hides the given node in the subgraph, |
|
| 1525 |
/// i.e. the iteration jumps over it. |
|
| 1537 |
/// This function sets the status of the given node. |
|
| 1526 | 1538 |
/// It is done by simply setting the assigned value of \c n |
| 1527 |
/// to be \c false in the node filter map. |
|
| 1528 |
void hide(const Node& n) const { Parent::hide(n); }
|
|
| 1529 |
|
|
| 1530 |
/// \brief Shows the given node |
|
| 1539 |
/// to \c v in the node filter map. |
|
| 1540 |
void status(const Node& n, bool v) const { Parent::status(n, v); }
|
|
| 1541 |
|
|
| 1542 |
/// \brief Returns the status of the given node |
|
| 1531 | 1543 |
/// |
| 1532 |
/// This function shows the given node in the subgraph. |
|
| 1533 |
/// It is done by simply setting the assigned value of \c n |
|
| 1534 |
/// to be \c true in the node filter map. |
|
| 1535 |
void unHide(const Node& n) const { Parent::unHide(n); }
|
|
| 1536 |
|
|
| 1537 |
/// \brief Returns \c true if the given node is hidden. |
|
| 1544 |
/// This function returns the status of the given node. |
|
| 1545 |
/// It is \c true if the given node is enabled (i.e. not hidden). |
|
| 1546 |
bool status(const Node& n) const { return Parent::status(n); }
|
|
| 1547 |
|
|
| 1548 |
/// \brief Disables the given node |
|
| 1538 | 1549 |
/// |
| 1539 |
/// This function returns \c true if the given node is hidden. |
|
| 1540 |
bool hidden(const Node& n) const { return Parent::hidden(n); }
|
|
| 1550 |
/// This function disables the given node, so the iteration |
|
| 1551 |
/// jumps over it. |
|
| 1552 |
/// It is the same as \ref status() "status(n, false)". |
|
| 1553 |
void disable(const Node& n) const { Parent::status(n, false); }
|
|
| 1554 |
|
|
| 1555 |
/// \brief Enables the given node |
|
| 1556 |
/// |
|
| 1557 |
/// This function enables the given node. |
|
| 1558 |
/// It is the same as \ref status() "status(n, true)". |
|
| 1559 |
void enable(const Node& n) const { Parent::status(n, true); }
|
|
| 1541 | 1560 |
|
| 1542 | 1561 |
}; |
| 1543 | 1562 |
|
| 1544 | 1563 |
template<typename _Graph, typename _NodeFilterMap, bool _checked> |
| 1545 | 1564 |
class FilterNodes<_Graph, _NodeFilterMap, _checked, |
| 1546 | 1565 |
typename enable_if<UndirectedTagIndicator<_Graph> >::type> |
| 1547 | 1566 |
: public SubGraph<_Graph, _NodeFilterMap, |
| 1548 | 1567 |
ConstMap<typename _Graph::Edge, bool>, _checked> {
|
| 1549 | 1568 |
public: |
| 1550 | 1569 |
typedef _Graph Graph; |
| 1551 | 1570 |
typedef _NodeFilterMap NodeFilterMap; |
| 1552 | 1571 |
typedef SubGraph<Graph, NodeFilterMap, |
| 1553 | 1572 |
ConstMap<typename Graph::Edge, bool> > Parent; |
| 1554 | 1573 |
|
| 1555 | 1574 |
typedef typename Parent::Node Node; |
| 1556 | 1575 |
protected: |
| 1557 | 1576 |
ConstMap<typename Graph::Edge, bool> const_true_map; |
| 1558 | 1577 |
|
| 1559 | 1578 |
FilterNodes() : const_true_map(true) {
|
| 1560 | 1579 |
Parent::setEdgeFilterMap(const_true_map); |
| 1561 | 1580 |
} |
| 1562 | 1581 |
|
| 1563 | 1582 |
public: |
| 1564 | 1583 |
|
| 1565 | 1584 |
FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) : |
| 1566 | 1585 |
Parent(), const_true_map(true) {
|
| 1567 | 1586 |
Parent::setGraph(_graph); |
| 1568 | 1587 |
Parent::setNodeFilterMap(node_filter_map); |
| 1569 | 1588 |
Parent::setEdgeFilterMap(const_true_map); |
| 1570 | 1589 |
} |
| 1571 | 1590 |
|
| 1572 |
void hide(const Node& n) const { Parent::hide(n); }
|
|
| 1573 |
void unHide(const Node& n) const { Parent::unHide(n); }
|
|
| 1574 |
|
|
| 1591 |
void status(const Node& n, bool v) const { Parent::status(n, v); }
|
|
| 1592 |
bool status(const Node& n) const { return Parent::status(n); }
|
|
| 1593 |
void disable(const Node& n) const { Parent::status(n, false); }
|
|
| 1594 |
void enable(const Node& n) const { Parent::status(n, true); }
|
|
| 1575 | 1595 |
|
| 1576 | 1596 |
}; |
| 1577 | 1597 |
|
| 1578 | 1598 |
|
| 1579 | 1599 |
/// \brief Returns a read-only FilterNodes adaptor |
| 1580 | 1600 |
/// |
| 1581 | 1601 |
/// This function just returns a read-only \ref FilterNodes adaptor. |
| 1582 | 1602 |
/// \ingroup graph_adaptors |
| 1583 | 1603 |
/// \relates FilterNodes |
| 1584 | 1604 |
template<typename Digraph, typename NodeFilterMap> |
| 1585 | 1605 |
FilterNodes<const Digraph, NodeFilterMap> |
| 1586 | 1606 |
filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
|
| 1587 | 1607 |
return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm); |
| 1588 | 1608 |
} |
| 1589 | 1609 |
|
| 1590 | 1610 |
template<typename Digraph, typename NodeFilterMap> |
| 1591 | 1611 |
FilterNodes<const Digraph, const NodeFilterMap> |
| 1592 | 1612 |
filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
|
| 1593 | 1613 |
return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm); |
| 1594 | 1614 |
} |
| 1595 | 1615 |
|
| 1596 | 1616 |
/// \ingroup graph_adaptors |
| 1597 | 1617 |
/// |
| 1598 | 1618 |
/// \brief Adaptor class for hiding arcs in a digraph. |
| 1599 | 1619 |
/// |
| 1600 | 1620 |
/// FilterArcs adaptor can be used for hiding arcs in a digraph. |
| 1601 | 1621 |
/// A \c bool arc map must be specified, which defines the filter for |
| 1602 | 1622 |
/// the arcs. Only the arcs with \c true filter value are shown in the |
| 1603 | 1623 |
/// subdigraph. This adaptor conforms to the \ref concepts::Digraph |
| 1604 | 1624 |
/// "Digraph" concept. |
| 1605 | 1625 |
/// |
| 1606 | 1626 |
/// The adapted digraph can also be modified through this adaptor |
| 1607 | 1627 |
/// by adding or removing nodes or arcs, unless the \c _Digraph template |
| 1608 | 1628 |
/// parameter is set to be \c const. |
| 1609 | 1629 |
/// |
| 1610 | 1630 |
/// \tparam _Digraph The type of the adapted digraph. |
| 1611 | 1631 |
/// It must conform to the \ref concepts::Digraph "Digraph" concept. |
| 1612 | 1632 |
/// It can also be specified to be \c const. |
| 1613 | 1633 |
/// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the |
| 1614 | 1634 |
/// adapted digraph. The default map type is |
| 1615 | 1635 |
/// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>". |
| 1616 | 1636 |
/// |
| 1617 | 1637 |
/// \note The \c Node and \c Arc types of this adaptor and the adapted |
| 1618 | 1638 |
/// digraph are convertible to each other. |
| 1619 | 1639 |
#ifdef DOXYGEN |
| 1620 | 1640 |
template<typename _Digraph, |
| 1621 | 1641 |
typename _ArcFilterMap> |
| 1622 | 1642 |
#else |
| 1623 | 1643 |
template<typename _Digraph, |
| 1624 | 1644 |
typename _ArcFilterMap = typename _Digraph::template ArcMap<bool> > |
| 1625 | 1645 |
#endif |
| 1626 | 1646 |
class FilterArcs : |
| 1627 | 1647 |
public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, |
| 1628 | 1648 |
_ArcFilterMap, false> {
|
| 1629 | 1649 |
public: |
| 1630 | 1650 |
|
| 1631 | 1651 |
typedef _Digraph Digraph; |
| 1632 | 1652 |
typedef _ArcFilterMap ArcFilterMap; |
| 1633 | 1653 |
|
| 1634 | 1654 |
typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>, |
| 1635 | 1655 |
ArcFilterMap, false> Parent; |
| 1636 | 1656 |
|
| 1637 | 1657 |
typedef typename Parent::Arc Arc; |
| 1638 | 1658 |
|
| 1639 | 1659 |
protected: |
| 1640 | 1660 |
ConstMap<typename Digraph::Node, bool> const_true_map; |
| 1641 | 1661 |
|
| 1642 | 1662 |
FilterArcs() : const_true_map(true) {
|
| 1643 | 1663 |
Parent::setNodeFilterMap(const_true_map); |
| 1644 | 1664 |
} |
| 1645 | 1665 |
|
| 1646 | 1666 |
public: |
| 1647 | 1667 |
|
| 1648 | 1668 |
/// \brief Constructor |
| 1649 | 1669 |
/// |
| 1650 | 1670 |
/// Creates a subdigraph for the given digraph with the given arc |
| 1651 | 1671 |
/// filter map. |
| 1652 | 1672 |
FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) |
| 1653 | 1673 |
: Parent(), const_true_map(true) {
|
| 1654 | 1674 |
Parent::setDigraph(digraph); |
| 1655 | 1675 |
Parent::setNodeFilterMap(const_true_map); |
| 1656 | 1676 |
Parent::setArcFilterMap(arc_filter); |
| 1657 | 1677 |
} |
| 1658 | 1678 |
|
| 1659 |
/// \brief |
|
| 1679 |
/// \brief Sets the status of the given arc |
|
| 1660 | 1680 |
/// |
| 1661 |
/// This function hides the given arc in the subdigraph, |
|
| 1662 |
/// i.e. the iteration jumps over it. |
|
| 1681 |
/// This function sets the status of the given arc. |
|
| 1663 | 1682 |
/// It is done by simply setting the assigned value of \c a |
| 1664 |
/// to be \c false in the arc filter map. |
|
| 1665 |
void hide(const Arc& a) const { Parent::hide(a); }
|
|
| 1666 |
|
|
| 1667 |
/// \brief Shows the given arc |
|
| 1683 |
/// to \c v in the arc filter map. |
|
| 1684 |
void status(const Arc& a, bool v) const { Parent::status(a, v); }
|
|
| 1685 |
|
|
| 1686 |
/// \brief Returns the status of the given arc |
|
| 1668 | 1687 |
/// |
| 1669 |
/// This function shows the given arc in the subdigraph. |
|
| 1670 |
/// It is done by simply setting the assigned value of \c a |
|
| 1671 |
/// to be \c true in the arc filter map. |
|
| 1672 |
void unHide(const Arc& a) const { Parent::unHide(a); }
|
|
| 1673 |
|
|
| 1674 |
/// \brief Returns \c true if the given arc is hidden. |
|
| 1688 |
/// This function returns the status of the given arc. |
|
| 1689 |
/// It is \c true if the given arc is enabled (i.e. not hidden). |
|
| 1690 |
bool status(const Arc& a) const { return Parent::status(a); }
|
|
| 1691 |
|
|
| 1692 |
/// \brief Disables the given arc |
|
| 1675 | 1693 |
/// |
| 1676 |
/// This function returns \c true if the given arc is hidden. |
|
| 1677 |
bool hidden(const Arc& a) const { return Parent::hidden(a); }
|
|
| 1694 |
/// This function disables the given arc in the subdigraph, |
|
| 1695 |
/// so the iteration jumps over it. |
|
| 1696 |
/// It is the same as \ref status() "status(a, false)". |
|
| 1697 |
void disable(const Arc& a) const { Parent::status(a, false); }
|
|
| 1698 |
|
|
| 1699 |
/// \brief Enables the given arc |
|
| 1700 |
/// |
|
| 1701 |
/// This function enables the given arc in the subdigraph. |
|
| 1702 |
/// It is the same as \ref status() "status(a, true)". |
|
| 1703 |
void enable(const Arc& a) const { Parent::status(a, true); }
|
|
| 1678 | 1704 |
|
| 1679 | 1705 |
}; |
| 1680 | 1706 |
|
| 1681 | 1707 |
/// \brief Returns a read-only FilterArcs adaptor |
| 1682 | 1708 |
/// |
| 1683 | 1709 |
/// This function just returns a read-only \ref FilterArcs adaptor. |
| 1684 | 1710 |
/// \ingroup graph_adaptors |
| 1685 | 1711 |
/// \relates FilterArcs |
| 1686 | 1712 |
template<typename Digraph, typename ArcFilterMap> |
| 1687 | 1713 |
FilterArcs<const Digraph, ArcFilterMap> |
| 1688 | 1714 |
filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
|
| 1689 | 1715 |
return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm); |
| 1690 | 1716 |
} |
| 1691 | 1717 |
|
| 1692 | 1718 |
template<typename Digraph, typename ArcFilterMap> |
| 1693 | 1719 |
FilterArcs<const Digraph, const ArcFilterMap> |
| 1694 | 1720 |
filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
|
| 1695 | 1721 |
return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm); |
| 1696 | 1722 |
} |
| 1697 | 1723 |
|
| 1698 | 1724 |
/// \ingroup graph_adaptors |
| 1699 | 1725 |
/// |
| 1700 | 1726 |
/// \brief Adaptor class for hiding edges in a graph. |
| 1701 | 1727 |
/// |
| 1702 | 1728 |
/// FilterEdges adaptor can be used for hiding edges in a graph. |
| 1703 | 1729 |
/// A \c bool edge map must be specified, which defines the filter for |
| 1704 | 1730 |
/// the edges. Only the edges with \c true filter value are shown in the |
| 1705 | 1731 |
/// subgraph. This adaptor conforms to the \ref concepts::Graph |
| 1706 | 1732 |
/// "Graph" concept. |
| 1707 | 1733 |
/// |
| 1708 | 1734 |
/// The adapted graph can also be modified through this adaptor |
| 1709 | 1735 |
/// by adding or removing nodes or edges, unless the \c _Graph template |
| 1710 | 1736 |
/// parameter is set to be \c const. |
| 1711 | 1737 |
/// |
| 1712 | 1738 |
/// \tparam _Graph The type of the adapted graph. |
| 1713 | 1739 |
/// It must conform to the \ref concepts::Graph "Graph" concept. |
| 1714 | 1740 |
/// It can also be specified to be \c const. |
| 1715 | 1741 |
/// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the |
| 1716 | 1742 |
/// adapted graph. The default map type is |
| 1717 | 1743 |
/// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>". |
| 1718 | 1744 |
/// |
| 1719 | 1745 |
/// \note The \c Node, \c Edge and \c Arc types of this adaptor and the |
| 1720 | 1746 |
/// adapted graph are convertible to each other. |
| 1721 | 1747 |
#ifdef DOXYGEN |
| 1722 | 1748 |
template<typename _Graph, |
| 1723 | 1749 |
typename _EdgeFilterMap> |
| 1724 | 1750 |
#else |
| 1725 | 1751 |
template<typename _Graph, |
| 1726 | 1752 |
typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool> > |
| 1727 | 1753 |
#endif |
| 1728 | 1754 |
class FilterEdges : |
| 1729 | 1755 |
public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, |
| 1730 | 1756 |
_EdgeFilterMap, false> {
|
| 1731 | 1757 |
public: |
| 1732 | 1758 |
typedef _Graph Graph; |
| 1733 | 1759 |
typedef _EdgeFilterMap EdgeFilterMap; |
| 1734 | 1760 |
typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>, |
| 1735 | 1761 |
EdgeFilterMap, false> Parent; |
| 1736 | 1762 |
typedef typename Parent::Edge Edge; |
| 1737 | 1763 |
protected: |
| 1738 | 1764 |
ConstMap<typename Graph::Node, bool> const_true_map; |
| 1739 | 1765 |
|
| 1740 | 1766 |
FilterEdges() : const_true_map(true) {
|
| 1741 | 1767 |
Parent::setNodeFilterMap(const_true_map); |
| 1742 | 1768 |
} |
| 1743 | 1769 |
|
| 1744 | 1770 |
public: |
| 1745 | 1771 |
|
| 1746 | 1772 |
/// \brief Constructor |
| 1747 | 1773 |
/// |
| 1748 | 1774 |
/// Creates a subgraph for the given graph with the given edge |
| 1749 | 1775 |
/// filter map. |
| 1750 | 1776 |
FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) : |
| 1751 | 1777 |
Parent(), const_true_map(true) {
|
| 1752 | 1778 |
Parent::setGraph(graph); |
| 1753 | 1779 |
Parent::setNodeFilterMap(const_true_map); |
| 1754 | 1780 |
Parent::setEdgeFilterMap(edge_filter_map); |
| 1755 | 1781 |
} |
| 1756 | 1782 |
|
| 1757 |
/// \brief |
|
| 1783 |
/// \brief Sets the status of the given edge |
|
| 1758 | 1784 |
/// |
| 1759 |
/// This function hides the given edge in the subgraph, |
|
| 1760 |
/// i.e. the iteration jumps over it. |
|
| 1785 |
/// This function sets the status of the given edge. |
|
| 1761 | 1786 |
/// It is done by simply setting the assigned value of \c e |
| 1762 |
/// to be \c false in the edge filter map. |
|
| 1763 |
void hide(const Edge& e) const { Parent::hide(e); }
|
|
| 1764 |
|
|
| 1765 |
/// \brief Shows the given edge |
|
| 1787 |
/// to \c v in the edge filter map. |
|
| 1788 |
void status(const Edge& e, bool v) const { Parent::status(e, v); }
|
|
| 1789 |
|
|
| 1790 |
/// \brief Returns the status of the given edge |
|
| 1766 | 1791 |
/// |
| 1767 |
/// This function shows the given edge in the subgraph. |
|
| 1768 |
/// It is done by simply setting the assigned value of \c e |
|
| 1769 |
/// to be \c true in the edge filter map. |
|
| 1770 |
void unHide(const Edge& e) const { Parent::unHide(e); }
|
|
| 1771 |
|
|
| 1772 |
/// \brief Returns \c true if the given edge is hidden. |
|
| 1792 |
/// This function returns the status of the given edge. |
|
| 1793 |
/// It is \c true if the given edge is enabled (i.e. not hidden). |
|
| 1794 |
bool status(const Edge& e) const { return Parent::status(e); }
|
|
| 1795 |
|
|
| 1796 |
/// \brief Disables the given edge |
|
| 1773 | 1797 |
/// |
| 1774 |
/// This function returns \c true if the given edge is hidden. |
|
| 1775 |
bool hidden(const Edge& e) const { return Parent::hidden(e); }
|
|
| 1798 |
/// This function disables the given edge in the subgraph, |
|
| 1799 |
/// so the iteration jumps over it. |
|
| 1800 |
/// It is the same as \ref status() "status(e, false)". |
|
| 1801 |
void disable(const Edge& e) const { Parent::status(e, false); }
|
|
| 1802 |
|
|
| 1803 |
/// \brief Enables the given edge |
|
| 1804 |
/// |
|
| 1805 |
/// This function enables the given edge in the subgraph. |
|
| 1806 |
/// It is the same as \ref status() "status(e, true)". |
|
| 1807 |
void enable(const Edge& e) const { Parent::status(e, true); }
|
|
| 1776 | 1808 |
|
| 1777 | 1809 |
}; |
| 1778 | 1810 |
|
| 1779 | 1811 |
/// \brief Returns a read-only FilterEdges adaptor |
| 1780 | 1812 |
/// |
| 1781 | 1813 |
/// This function just returns a read-only \ref FilterEdges adaptor. |
| 1782 | 1814 |
/// \ingroup graph_adaptors |
| 1783 | 1815 |
/// \relates FilterEdges |
| 1784 | 1816 |
template<typename Graph, typename EdgeFilterMap> |
| 1785 | 1817 |
FilterEdges<const Graph, EdgeFilterMap> |
| 1786 | 1818 |
filterEdges(const Graph& graph, EdgeFilterMap& efm) {
|
| 1787 | 1819 |
return FilterEdges<const Graph, EdgeFilterMap>(graph, efm); |
| 1788 | 1820 |
} |
| 1789 | 1821 |
|
| 1790 | 1822 |
template<typename Graph, typename EdgeFilterMap> |
| 1791 | 1823 |
FilterEdges<const Graph, const EdgeFilterMap> |
| 1792 | 1824 |
filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
|
| 1793 | 1825 |
return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm); |
| 1794 | 1826 |
} |
| 1795 | 1827 |
|
| 1796 | 1828 |
|
| 1797 | 1829 |
template <typename _Digraph> |
| 1798 | 1830 |
class UndirectorBase {
|
| 1799 | 1831 |
public: |
| 1800 | 1832 |
typedef _Digraph Digraph; |
| 1801 | 1833 |
typedef UndirectorBase Adaptor; |
| 1802 | 1834 |
|
| 1803 | 1835 |
typedef True UndirectedTag; |
| 1804 | 1836 |
|
| 1805 | 1837 |
typedef typename Digraph::Arc Edge; |
| 1806 | 1838 |
typedef typename Digraph::Node Node; |
| 1807 | 1839 |
|
| 1808 | 1840 |
class Arc : public Edge {
|
| 1809 | 1841 |
friend class UndirectorBase; |
| 1810 | 1842 |
protected: |
| 1811 | 1843 |
bool _forward; |
| 1812 | 1844 |
|
| 1813 | 1845 |
Arc(const Edge& edge, bool forward) : |
| 1814 | 1846 |
Edge(edge), _forward(forward) {}
|
| 1815 | 1847 |
|
| 1816 | 1848 |
public: |
| 1817 | 1849 |
Arc() {}
|
| 1818 | 1850 |
|
| 1819 | 1851 |
Arc(Invalid) : Edge(INVALID), _forward(true) {}
|
| 1820 | 1852 |
|
| 1821 | 1853 |
bool operator==(const Arc &other) const {
|
| 1822 | 1854 |
return _forward == other._forward && |
| 1823 | 1855 |
static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); |
| ... | ... |
@@ -2722,99 +2754,99 @@ |
| 2722 | 2754 |
FlowMap, Tolerance> ForwardFilter; |
| 2723 | 2755 |
|
| 2724 | 2756 |
typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap, |
| 2725 | 2757 |
FlowMap, Tolerance> BackwardFilter; |
| 2726 | 2758 |
|
| 2727 | 2759 |
typedef typename Undirected:: |
| 2728 | 2760 |
template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; |
| 2729 | 2761 |
|
| 2730 | 2762 |
typedef FilterArcs<Undirected, ArcFilter> Parent; |
| 2731 | 2763 |
|
| 2732 | 2764 |
const CapacityMap* _capacity; |
| 2733 | 2765 |
FlowMap* _flow; |
| 2734 | 2766 |
|
| 2735 | 2767 |
Undirected _graph; |
| 2736 | 2768 |
ForwardFilter _forward_filter; |
| 2737 | 2769 |
BackwardFilter _backward_filter; |
| 2738 | 2770 |
ArcFilter _arc_filter; |
| 2739 | 2771 |
|
| 2740 | 2772 |
public: |
| 2741 | 2773 |
|
| 2742 | 2774 |
/// \brief Constructor |
| 2743 | 2775 |
/// |
| 2744 | 2776 |
/// Constructor of the residual digraph adaptor. The parameters are the |
| 2745 | 2777 |
/// digraph, the capacity map, the flow map, and a tolerance object. |
| 2746 | 2778 |
Residual(const Digraph& digraph, const CapacityMap& capacity, |
| 2747 | 2779 |
FlowMap& flow, const Tolerance& tolerance = Tolerance()) |
| 2748 | 2780 |
: Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), |
| 2749 | 2781 |
_forward_filter(capacity, flow, tolerance), |
| 2750 | 2782 |
_backward_filter(capacity, flow, tolerance), |
| 2751 | 2783 |
_arc_filter(_forward_filter, _backward_filter) |
| 2752 | 2784 |
{
|
| 2753 | 2785 |
Parent::setDigraph(_graph); |
| 2754 | 2786 |
Parent::setArcFilterMap(_arc_filter); |
| 2755 | 2787 |
} |
| 2756 | 2788 |
|
| 2757 | 2789 |
typedef typename Parent::Arc Arc; |
| 2758 | 2790 |
|
| 2759 | 2791 |
/// \brief Returns the residual capacity of the given arc. |
| 2760 | 2792 |
/// |
| 2761 | 2793 |
/// Returns the residual capacity of the given arc. |
| 2762 | 2794 |
Value residualCapacity(const Arc& a) const {
|
| 2763 | 2795 |
if (Undirected::direction(a)) {
|
| 2764 | 2796 |
return (*_capacity)[a] - (*_flow)[a]; |
| 2765 | 2797 |
} else {
|
| 2766 | 2798 |
return (*_flow)[a]; |
| 2767 | 2799 |
} |
| 2768 | 2800 |
} |
| 2769 | 2801 |
|
| 2770 |
/// \brief |
|
| 2802 |
/// \brief Augments on the given arc in the residual digraph. |
|
| 2771 | 2803 |
/// |
| 2772 |
/// |
|
| 2804 |
/// Augments on the given arc in the residual digraph. It increases |
|
| 2773 | 2805 |
/// or decreases the flow value on the original arc according to the |
| 2774 | 2806 |
/// direction of the residual arc. |
| 2775 | 2807 |
void augment(const Arc& a, const Value& v) const {
|
| 2776 | 2808 |
if (Undirected::direction(a)) {
|
| 2777 | 2809 |
_flow->set(a, (*_flow)[a] + v); |
| 2778 | 2810 |
} else {
|
| 2779 | 2811 |
_flow->set(a, (*_flow)[a] - v); |
| 2780 | 2812 |
} |
| 2781 | 2813 |
} |
| 2782 | 2814 |
|
| 2783 | 2815 |
/// \brief Returns \c true if the given residual arc is a forward arc. |
| 2784 | 2816 |
/// |
| 2785 | 2817 |
/// Returns \c true if the given residual arc has the same orientation |
| 2786 | 2818 |
/// as the original arc, i.e. it is a so called forward arc. |
| 2787 | 2819 |
static bool forward(const Arc& a) {
|
| 2788 | 2820 |
return Undirected::direction(a); |
| 2789 | 2821 |
} |
| 2790 | 2822 |
|
| 2791 | 2823 |
/// \brief Returns \c true if the given residual arc is a backward arc. |
| 2792 | 2824 |
/// |
| 2793 | 2825 |
/// Returns \c true if the given residual arc has the opposite orientation |
| 2794 | 2826 |
/// than the original arc, i.e. it is a so called backward arc. |
| 2795 | 2827 |
static bool backward(const Arc& a) {
|
| 2796 | 2828 |
return !Undirected::direction(a); |
| 2797 | 2829 |
} |
| 2798 | 2830 |
|
| 2799 | 2831 |
/// \brief Returns the forward oriented residual arc. |
| 2800 | 2832 |
/// |
| 2801 | 2833 |
/// Returns the forward oriented residual arc related to the given |
| 2802 | 2834 |
/// arc of the underlying digraph. |
| 2803 | 2835 |
static Arc forward(const typename Digraph::Arc& a) {
|
| 2804 | 2836 |
return Undirected::direct(a, true); |
| 2805 | 2837 |
} |
| 2806 | 2838 |
|
| 2807 | 2839 |
/// \brief Returns the backward oriented residual arc. |
| 2808 | 2840 |
/// |
| 2809 | 2841 |
/// Returns the backward oriented residual arc related to the given |
| 2810 | 2842 |
/// arc of the underlying digraph. |
| 2811 | 2843 |
static Arc backward(const typename Digraph::Arc& a) {
|
| 2812 | 2844 |
return Undirected::direct(a, false); |
| 2813 | 2845 |
} |
| 2814 | 2846 |
|
| 2815 | 2847 |
/// \brief Residual capacity map. |
| 2816 | 2848 |
/// |
| 2817 | 2849 |
/// This map adaptor class can be used for obtaining the residual |
| 2818 | 2850 |
/// capacities as an arc map of the residual digraph. |
| 2819 | 2851 |
/// Its value type is inherited from the capacity map. |
| 2820 | 2852 |
class ResidualCapacity {
|
0 comments (0 inline)