Changes in lemon/full_graph.h [956:141f9c0db4a3:1193:c8fa41fcc4a7] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/full_graph.h
r956 r1193 622 622 }; 623 623 624 class FullBpGraphBase { 625 626 protected: 627 628 int _red_num, _blue_num; 629 int _node_num, _edge_num; 630 631 public: 632 633 typedef FullBpGraphBase Graph; 634 635 class Node; 636 class Arc; 637 class Edge; 638 639 class Node { 640 friend class FullBpGraphBase; 641 protected: 642 643 int _id; 644 explicit Node(int id) { _id = id;} 645 646 public: 647 Node() {} 648 Node (Invalid) { _id = -1; } 649 bool operator==(const Node& node) const {return _id == node._id;} 650 bool operator!=(const Node& node) const {return _id != node._id;} 651 bool operator<(const Node& node) const {return _id < node._id;} 652 }; 653 654 class RedNode : public Node { 655 friend class FullBpGraphBase; 656 protected: 657 658 explicit RedNode(int pid) : Node(pid) {} 659 660 public: 661 RedNode() {} 662 RedNode(const RedNode& node) : Node(node) {} 663 RedNode(Invalid) : Node(INVALID){} 664 }; 665 666 class BlueNode : public Node { 667 friend class FullBpGraphBase; 668 protected: 669 670 explicit BlueNode(int pid) : Node(pid) {} 671 672 public: 673 BlueNode() {} 674 BlueNode(const BlueNode& node) : Node(node) {} 675 BlueNode(Invalid) : Node(INVALID){} 676 }; 677 678 class Edge { 679 friend class FullBpGraphBase; 680 protected: 681 682 int _id; 683 explicit Edge(int id) { _id = id;} 684 685 public: 686 Edge() {} 687 Edge (Invalid) { _id = -1; } 688 bool operator==(const Edge& arc) const {return _id == arc._id;} 689 bool operator!=(const Edge& arc) const {return _id != arc._id;} 690 bool operator<(const Edge& arc) const {return _id < arc._id;} 691 }; 692 693 class Arc { 694 friend class FullBpGraphBase; 695 protected: 696 697 int _id; 698 explicit Arc(int id) { _id = id;} 699 700 public: 701 operator Edge() const { 702 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 703 } 704 705 Arc() {} 706 Arc (Invalid) { _id = -1; } 707 bool operator==(const Arc& arc) const {return _id == arc._id;} 708 bool operator!=(const Arc& arc) const {return _id != arc._id;} 709 bool operator<(const Arc& arc) const {return _id < arc._id;} 710 }; 711 712 713 protected: 714 715 FullBpGraphBase() 716 : _red_num(0), _blue_num(0), _node_num(0), _edge_num(0) {} 717 718 void construct(int redNum, int blueNum) { 719 _red_num = redNum; _blue_num = blueNum; 720 _node_num = redNum + blueNum; _edge_num = redNum * blueNum; 721 } 722 723 public: 724 725 typedef True NodeNumTag; 726 typedef True EdgeNumTag; 727 typedef True ArcNumTag; 728 729 int nodeNum() const { return _node_num; } 730 int redNum() const { return _red_num; } 731 int blueNum() const { return _blue_num; } 732 int edgeNum() const { return _edge_num; } 733 int arcNum() const { return 2 * _edge_num; } 734 735 int maxNodeId() const { return _node_num - 1; } 736 int maxRedId() const { return _red_num - 1; } 737 int maxBlueId() const { return _blue_num - 1; } 738 int maxEdgeId() const { return _edge_num - 1; } 739 int maxArcId() const { return 2 * _edge_num - 1; } 740 741 bool red(Node n) const { return n._id < _red_num; } 742 bool blue(Node n) const { return n._id >= _red_num; } 743 744 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } 745 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } 746 747 Node source(Arc a) const { 748 if (a._id & 1) { 749 return Node((a._id >> 1) % _red_num); 750 } else { 751 return Node((a._id >> 1) / _red_num + _red_num); 752 } 753 } 754 Node target(Arc a) const { 755 if (a._id & 1) { 756 return Node((a._id >> 1) / _red_num + _red_num); 757 } else { 758 return Node((a._id >> 1) % _red_num); 759 } 760 } 761 762 RedNode redNode(Edge e) const { 763 return RedNode(e._id % _red_num); 764 } 765 BlueNode blueNode(Edge e) const { 766 return BlueNode(e._id / _red_num + _red_num); 767 } 768 769 static bool direction(Arc a) { 770 return (a._id & 1) == 1; 771 } 772 773 static Arc direct(Edge e, bool d) { 774 return Arc(e._id * 2 + (d ? 1 : 0)); 775 } 776 777 void first(Node& node) const { 778 node._id = _node_num - 1; 779 } 780 781 static void next(Node& node) { 782 --node._id; 783 } 784 785 void first(RedNode& node) const { 786 node._id = _red_num - 1; 787 } 788 789 static void next(RedNode& node) { 790 --node._id; 791 } 792 793 void first(BlueNode& node) const { 794 if (_red_num == _node_num) node._id = -1; 795 else node._id = _node_num - 1; 796 } 797 798 void next(BlueNode& node) const { 799 if (node._id == _red_num) node._id = -1; 800 else --node._id; 801 } 802 803 void first(Arc& arc) const { 804 arc._id = 2 * _edge_num - 1; 805 } 806 807 static void next(Arc& arc) { 808 --arc._id; 809 } 810 811 void first(Edge& arc) const { 812 arc._id = _edge_num - 1; 813 } 814 815 static void next(Edge& arc) { 816 --arc._id; 817 } 818 819 void firstOut(Arc &a, const Node& v) const { 820 if (v._id < _red_num) { 821 a._id = 2 * (v._id + _red_num * (_blue_num - 1)) + 1; 822 } else { 823 a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)); 824 } 825 } 826 void nextOut(Arc &a) const { 827 if (a._id & 1) { 828 a._id -= 2 * _red_num; 829 if (a._id < 0) a._id = -1; 830 } else { 831 if (a._id % (2 * _red_num) == 0) a._id = -1; 832 else a._id -= 2; 833 } 834 } 835 836 void firstIn(Arc &a, const Node& v) const { 837 if (v._id < _red_num) { 838 a._id = 2 * (v._id + _red_num * (_blue_num - 1)); 839 } else { 840 a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)) + 1; 841 } 842 } 843 void nextIn(Arc &a) const { 844 if (a._id & 1) { 845 if (a._id % (2 * _red_num) == 1) a._id = -1; 846 else a._id -= 2; 847 } else { 848 a._id -= 2 * _red_num; 849 if (a._id < 0) a._id = -1; 850 } 851 } 852 853 void firstInc(Edge &e, bool& d, const Node& v) const { 854 if (v._id < _red_num) { 855 d = true; 856 e._id = v._id + _red_num * (_blue_num - 1); 857 } else { 858 d = false; 859 e._id = _red_num - 1 + _red_num * (v._id - _red_num); 860 } 861 } 862 void nextInc(Edge &e, bool& d) const { 863 if (d) { 864 e._id -= _red_num; 865 if (e._id < 0) e._id = -1; 866 } else { 867 if (e._id % _red_num == 0) e._id = -1; 868 else --e._id; 869 } 870 } 871 872 static int id(const Node& v) { return v._id; } 873 int id(const RedNode& v) const { return v._id; } 874 int id(const BlueNode& v) const { return v._id - _red_num; } 875 static int id(Arc e) { return e._id; } 876 static int id(Edge e) { return e._id; } 877 878 static Node nodeFromId(int id) { return Node(id);} 879 static Arc arcFromId(int id) { return Arc(id);} 880 static Edge edgeFromId(int id) { return Edge(id);} 881 882 bool valid(Node n) const { 883 return n._id >= 0 && n._id < _node_num; 884 } 885 bool valid(Arc a) const { 886 return a._id >= 0 && a._id < 2 * _edge_num; 887 } 888 bool valid(Edge e) const { 889 return e._id >= 0 && e._id < _edge_num; 890 } 891 892 RedNode redNode(int index) const { 893 return RedNode(index); 894 } 895 896 int index(RedNode n) const { 897 return n._id; 898 } 899 900 BlueNode blueNode(int index) const { 901 return BlueNode(index + _red_num); 902 } 903 904 int index(BlueNode n) const { 905 return n._id - _red_num; 906 } 907 908 void clear() { 909 _red_num = 0; _blue_num = 0; 910 _node_num = 0; _edge_num = 0; 911 } 912 913 Edge edge(const Node& u, const Node& v) const { 914 if (u._id < _red_num) { 915 if (v._id < _red_num) { 916 return Edge(-1); 917 } else { 918 return Edge(u._id + _red_num * (v._id - _red_num)); 919 } 920 } else { 921 if (v._id < _red_num) { 922 return Edge(v._id + _red_num * (u._id - _red_num)); 923 } else { 924 return Edge(-1); 925 } 926 } 927 } 928 929 Arc arc(const Node& u, const Node& v) const { 930 if (u._id < _red_num) { 931 if (v._id < _red_num) { 932 return Arc(-1); 933 } else { 934 return Arc(2 * (u._id + _red_num * (v._id - _red_num)) + 1); 935 } 936 } else { 937 if (v._id < _red_num) { 938 return Arc(2 * (v._id + _red_num * (u._id - _red_num))); 939 } else { 940 return Arc(-1); 941 } 942 } 943 } 944 945 typedef True FindEdgeTag; 946 typedef True FindArcTag; 947 948 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { 949 return prev != INVALID ? INVALID : edge(u, v); 950 } 951 952 Arc findArc(Node s, Node t, Arc prev = INVALID) const { 953 return prev != INVALID ? INVALID : arc(s, t); 954 } 955 956 }; 957 958 typedef BpGraphExtender<FullBpGraphBase> ExtendedFullBpGraphBase; 959 960 /// \ingroup graphs 961 /// 962 /// \brief An undirected full bipartite graph class. 963 /// 964 /// FullBpGraph is a simple and fast implmenetation of undirected 965 /// full bipartite graphs. It contains an edge between every 966 /// red-blue pairs of nodes, therefore the number of edges is 967 /// <tt>nr*nb</tt>. This class is completely static and it needs 968 /// constant memory space. Thus you can neither add nor delete 969 /// nodes or edges, however the structure can be resized using 970 /// resize(). 971 /// 972 /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept". 973 /// Most of its member functions and nested classes are documented 974 /// only in the concept class. 975 /// 976 /// This class provides constant time counting for nodes, edges and arcs. 977 /// 978 /// \sa FullGraph 979 class FullBpGraph : public ExtendedFullBpGraphBase { 980 public: 981 982 typedef ExtendedFullBpGraphBase Parent; 983 984 /// \brief Default constructor. 985 /// 986 /// Default constructor. The number of nodes and edges will be zero. 987 FullBpGraph() { construct(0, 0); } 988 989 /// \brief Constructor 990 /// 991 /// Constructor. 992 /// \param redNum The number of the red nodes. 993 /// \param blueNum The number of the blue nodes. 994 FullBpGraph(int redNum, int blueNum) { construct(redNum, blueNum); } 995 996 /// \brief Resizes the graph 997 /// 998 /// This function resizes the graph. It fully destroys and 999 /// rebuilds the structure, therefore the maps of the graph will be 1000 /// reallocated automatically and the previous values will be lost. 1001 void resize(int redNum, int blueNum) { 1002 Parent::notifier(Arc()).clear(); 1003 Parent::notifier(Edge()).clear(); 1004 Parent::notifier(Node()).clear(); 1005 Parent::notifier(BlueNode()).clear(); 1006 Parent::notifier(RedNode()).clear(); 1007 construct(redNum, blueNum); 1008 Parent::notifier(RedNode()).build(); 1009 Parent::notifier(BlueNode()).build(); 1010 Parent::notifier(Node()).build(); 1011 Parent::notifier(Edge()).build(); 1012 Parent::notifier(Arc()).build(); 1013 } 1014 1015 using Parent::redNode; 1016 using Parent::blueNode; 1017 1018 /// \brief Returns the red node with the given index. 1019 /// 1020 /// Returns the red node with the given index. Since this 1021 /// structure is completely static, the red nodes can be indexed 1022 /// with integers from the range <tt>[0..redNum()-1]</tt>. 1023 /// \sa redIndex() 1024 RedNode redNode(int index) const { return Parent::redNode(index); } 1025 1026 /// \brief Returns the index of the given red node. 1027 /// 1028 /// Returns the index of the given red node. Since this structure 1029 /// is completely static, the red nodes can be indexed with 1030 /// integers from the range <tt>[0..redNum()-1]</tt>. 1031 /// 1032 /// \sa operator()() 1033 int index(RedNode node) const { return Parent::index(node); } 1034 1035 /// \brief Returns the blue node with the given index. 1036 /// 1037 /// Returns the blue node with the given index. Since this 1038 /// structure is completely static, the blue nodes can be indexed 1039 /// with integers from the range <tt>[0..blueNum()-1]</tt>. 1040 /// \sa blueIndex() 1041 BlueNode blueNode(int index) const { return Parent::blueNode(index); } 1042 1043 /// \brief Returns the index of the given blue node. 1044 /// 1045 /// Returns the index of the given blue node. Since this structure 1046 /// is completely static, the blue nodes can be indexed with 1047 /// integers from the range <tt>[0..blueNum()-1]</tt>. 1048 /// 1049 /// \sa operator()() 1050 int index(BlueNode node) const { return Parent::index(node); } 1051 1052 /// \brief Returns the edge which connects the given nodes. 1053 /// 1054 /// Returns the edge which connects the given nodes. 1055 Edge edge(const Node& u, const Node& v) const { 1056 return Parent::edge(u, v); 1057 } 1058 1059 /// \brief Returns the arc which connects the given nodes. 1060 /// 1061 /// Returns the arc which connects the given nodes. 1062 Arc arc(const Node& u, const Node& v) const { 1063 return Parent::arc(u, v); 1064 } 1065 1066 /// \brief Number of nodes. 1067 int nodeNum() const { return Parent::nodeNum(); } 1068 /// \brief Number of red nodes. 1069 int redNum() const { return Parent::redNum(); } 1070 /// \brief Number of blue nodes. 1071 int blueNum() const { return Parent::blueNum(); } 1072 /// \brief Number of arcs. 1073 int arcNum() const { return Parent::arcNum(); } 1074 /// \brief Number of edges. 1075 int edgeNum() const { return Parent::edgeNum(); } 1076 }; 1077 624 1078 625 1079 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.