860 |
861 |
861 void erase(const OutEdgeIt& e) const { |
862 void erase(const OutEdgeIt& e) const { |
862 OutEdgeIt f=e; |
863 OutEdgeIt f=e; |
863 this->next(f); |
864 this->next(f); |
864 first_out_edges->set(this->tail(e), f.e); |
865 first_out_edges->set(this->tail(e), f.e); |
|
866 } |
|
867 }; |
|
868 |
|
869 /// A wrapper for composing a bipartite graph. |
|
870 /// \c _graph have to be a reference to an undirected graph \c Graph |
|
871 /// and |
|
872 /// \c _s_false_t_true_map is an \c IterableBoolMap |
|
873 /// reference containing the elements for the |
|
874 /// color classes S and T. |
|
875 /// It results in a directed graph such that the edges are oriented from |
|
876 /// S to T. |
|
877 template<typename Graph> |
|
878 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
|
879 typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap; |
|
880 SFalseTTrueMap* s_false_t_true_map; |
|
881 |
|
882 public: |
|
883 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) |
|
884 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) { |
|
885 } |
|
886 typedef typename GraphWrapper<Graph>::Node Node; |
|
887 //using GraphWrapper<Graph>::NodeIt; |
|
888 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
889 //using GraphWrapper<Graph>::EdgeIt; |
|
890 class SNodeIt { |
|
891 Node n; |
|
892 public: |
|
893 SNodeIt() { } |
|
894 SNodeIt(const Invalid& i) : n(i) { } |
|
895 SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { |
|
896 _G.s_false_t_true_map->first(n, false); |
|
897 } |
|
898 operator Node() const { return n; } |
|
899 }; |
|
900 class TNodeIt { |
|
901 Node n; |
|
902 public: |
|
903 TNodeIt() { } |
|
904 TNodeIt(const Invalid& i) : n(i) { } |
|
905 TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { |
|
906 _G.s_false_t_true_map->first(n, true); |
|
907 } |
|
908 operator Node() const { return n; } |
|
909 }; |
|
910 class OutEdgeIt { |
|
911 public: |
|
912 typename Graph::OutEdgeIt e; |
|
913 public: |
|
914 OutEdgeIt() { } |
|
915 OutEdgeIt(const Invalid& i) : e(i) { } |
|
916 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
|
917 if (!(*(_G.s_false_t_true_map))[_n]) |
|
918 e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); |
|
919 else |
|
920 e=INVALID; |
|
921 } |
|
922 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
923 }; |
|
924 class InEdgeIt { |
|
925 public: |
|
926 typename Graph::InEdgeIt e; |
|
927 public: |
|
928 InEdgeIt() { } |
|
929 InEdgeIt(const Invalid& i) : e(i) { } |
|
930 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
|
931 if ((*(_G.s_false_t_true_map))[_n]) |
|
932 e=InEdgeIt(*(_G.graph), typename Graph::Node(_n)); |
|
933 else |
|
934 e=INVALID; |
|
935 } |
|
936 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
937 }; |
|
938 |
|
939 using GraphWrapper<Graph>::first; |
|
940 SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } |
|
941 TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } |
|
942 |
|
943 using GraphWrapper<Graph>::next; |
|
944 SNodeIt& next(SNodeIt& n) const { |
|
945 this->s_false_t_true_map->next(n); return n; |
|
946 } |
|
947 TNodeIt& next(TNodeIt& n) const { |
|
948 this->s_false_t_true_map->next(n); return n; |
|
949 } |
|
950 |
|
951 Node tail(const Edge& e) { |
|
952 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) |
|
953 return Node(this->graph->tail(e)); |
|
954 else |
|
955 return Node(this->graph->head(e)); |
|
956 } |
|
957 Node head(const Edge& e) { |
|
958 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) |
|
959 return Node(this->graph->head(e)); |
|
960 else |
|
961 return Node(this->graph->tail(e)); |
|
962 } |
|
963 |
|
964 Node aNode(const OutEdgeIt& e) const { |
|
965 return Node(this->graph->aNode(e.e)); |
|
966 } |
|
967 Node aNode(const InEdgeIt& e) const { |
|
968 return Node(this->graph->aNode(e.e)); |
|
969 } |
|
970 Node bNode(const OutEdgeIt& e) const { |
|
971 return Node(this->graph->bNode(e.e)); |
|
972 } |
|
973 Node bNode(const InEdgeIt& e) const { |
|
974 return Node(this->graph->bNode(e.e)); |
865 } |
975 } |
866 }; |
976 }; |
867 |
977 |
868 |
978 |
869 |
979 |