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