558 UndirGraph() : UndirGraphWrapper<Graph>() { |
564 UndirGraph() : UndirGraphWrapper<Graph>() { |
559 Parent::setGraph(gr); |
565 Parent::setGraph(gr); |
560 } |
566 } |
561 }; |
567 }; |
562 |
568 |
563 |
569 |
564 |
570 |
565 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
571 /// A wrapper for composing bidirected graph from a directed one. |
566 |
572 /// experimental, for fezso's sake. |
567 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
573 template<typename Graph> |
568 template<typename Graph, typename Number, |
574 class BidirGraphWrapper : public GraphWrapper<Graph> { |
569 typename CapacityMap, typename FlowMap> |
|
570 class ResGraphWrapper : public GraphWrapper<Graph> { |
|
571 protected: |
575 protected: |
572 const CapacityMap* capacity; |
576 //const CapacityMap* capacity; |
573 FlowMap* flow; |
577 //FlowMap* flow; |
574 |
578 |
575 ResGraphWrapper() : GraphWrapper<Graph>(0), |
579 BidirGraphWrapper() : GraphWrapper<Graph>()/*, |
576 capacity(0), flow(0) { } |
580 capacity(0), flow(0)*/ { } |
577 void setCapacityMap(const CapacityMap& _capacity) { |
581 // void setCapacityMap(const CapacityMap& _capacity) { |
578 capacity=&_capacity; |
582 // capacity=&_capacity; |
579 } |
583 // } |
580 void setFlowMap(FlowMap& _flow) { |
584 // void setFlowMap(FlowMap& _flow) { |
581 flow=&_flow; |
585 // flow=&_flow; |
582 } |
586 // } |
583 |
587 |
584 public: |
588 public: |
585 |
589 |
586 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
590 BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, |
587 FlowMap& _flow) : |
591 FlowMap& _flow*/) : |
588 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { } |
592 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } |
589 |
593 |
590 class Edge; |
594 class Edge; |
591 class OutEdgeIt; |
595 class OutEdgeIt; |
592 friend class Edge; |
596 friend class Edge; |
593 friend class OutEdgeIt; |
597 friend class OutEdgeIt; |
594 |
598 |
595 typedef typename GraphWrapper<Graph>::Node Node; |
599 typedef typename GraphWrapper<Graph>::Node Node; |
596 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
600 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
597 class Edge : public Graph::Edge { |
601 class Edge : public Graph::Edge { |
598 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
602 friend class BidirGraphWrapper<Graph>; |
599 protected: |
603 protected: |
600 bool backward; //true, iff backward |
604 bool backward; //true, iff backward |
601 // typename Graph::Edge e; |
605 // typename Graph::Edge e; |
602 public: |
606 public: |
603 Edge() { } |
607 Edge() { } |
684 return Edge(in, this->backward); |
688 return Edge(in, this->backward); |
685 } |
689 } |
686 }; |
690 }; |
687 |
691 |
688 class EdgeIt { |
692 class EdgeIt { |
|
693 friend class BidirGraphWrapper<Graph>; |
|
694 protected: |
|
695 typename Graph::EdgeIt e; |
|
696 bool backward; |
|
697 public: |
|
698 EdgeIt() { } |
|
699 EdgeIt(const Invalid& i) : e(i), backward(true) { } |
|
700 EdgeIt(const BidirGraphWrapper<Graph>& _G) { |
|
701 backward=false; |
|
702 _G.graph->first(e); |
|
703 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); |
|
704 if (!_G.graph->valid(e)) { |
|
705 backward=true; |
|
706 _G.graph->first(e); |
|
707 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); |
|
708 } |
|
709 } |
|
710 operator Edge() const { |
|
711 return Edge(e, this->backward); |
|
712 } |
|
713 }; |
|
714 |
|
715 using GraphWrapper<Graph>::first; |
|
716 // NodeIt& first(NodeIt& i) const { |
|
717 // i=NodeIt(*this); return i; |
|
718 // } |
|
719 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
720 i=OutEdgeIt(*this, p); return i; |
|
721 } |
|
722 // FIXME not tested |
|
723 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
724 i=InEdgeIt(*this, p); return i; |
|
725 } |
|
726 EdgeIt& first(EdgeIt& i) const { |
|
727 i=EdgeIt(*this); return i; |
|
728 } |
|
729 |
|
730 using GraphWrapper<Graph>::next; |
|
731 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
|
732 OutEdgeIt& next(OutEdgeIt& e) const { |
|
733 if (!e.backward) { |
|
734 Node v=this->graph->aNode(e.out); |
|
735 this->graph->next(e.out); |
|
736 while(this->graph->valid(e.out) && !enabled(e)) { |
|
737 this->graph->next(e.out); } |
|
738 if (!this->graph->valid(e.out)) { |
|
739 e.backward=true; |
|
740 this->graph->first(e.in, v); |
|
741 while(this->graph->valid(e.in) && !enabled(e)) { |
|
742 this->graph->next(e.in); } |
|
743 } |
|
744 } else { |
|
745 this->graph->next(e.in); |
|
746 while(this->graph->valid(e.in) && !enabled(e)) { |
|
747 this->graph->next(e.in); } |
|
748 } |
|
749 return e; |
|
750 } |
|
751 // FIXME Not tested |
|
752 InEdgeIt& next(InEdgeIt& e) const { |
|
753 if (!e.backward) { |
|
754 Node v=this->graph->aNode(e.in); |
|
755 this->graph->next(e.in); |
|
756 while(this->graph->valid(e.in) && !enabled(e)) { |
|
757 this->graph->next(e.in); } |
|
758 if (!this->graph->valid(e.in)) { |
|
759 e.backward=true; |
|
760 this->graph->first(e.out, v); |
|
761 while(this->graph->valid(e.out) && !enabled(e)) { |
|
762 this->graph->next(e.out); } |
|
763 } |
|
764 } else { |
|
765 this->graph->next(e.out); |
|
766 while(this->graph->valid(e.out) && !enabled(e)) { |
|
767 this->graph->next(e.out); } |
|
768 } |
|
769 return e; |
|
770 } |
|
771 EdgeIt& next(EdgeIt& e) const { |
|
772 if (!e.backward) { |
|
773 this->graph->next(e.e); |
|
774 while(this->graph->valid(e.e) && !enabled(e)) { |
|
775 this->graph->next(e.e); } |
|
776 if (!this->graph->valid(e.e)) { |
|
777 e.backward=true; |
|
778 this->graph->first(e.e); |
|
779 while(this->graph->valid(e.e) && !enabled(e)) { |
|
780 this->graph->next(e.e); } |
|
781 } |
|
782 } else { |
|
783 this->graph->next(e.e); |
|
784 while(this->graph->valid(e.e) && !enabled(e)) { |
|
785 this->graph->next(e.e); } |
|
786 } |
|
787 return e; |
|
788 } |
|
789 |
|
790 Node tail(Edge e) const { |
|
791 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } |
|
792 Node head(Edge e) const { |
|
793 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } |
|
794 |
|
795 Node aNode(OutEdgeIt e) const { |
|
796 return ((!e.backward) ? this->graph->aNode(e.out) : |
|
797 this->graph->aNode(e.in)); } |
|
798 Node bNode(OutEdgeIt e) const { |
|
799 return ((!e.backward) ? this->graph->bNode(e.out) : |
|
800 this->graph->bNode(e.in)); } |
|
801 |
|
802 Node aNode(InEdgeIt e) const { |
|
803 return ((!e.backward) ? this->graph->aNode(e.in) : |
|
804 this->graph->aNode(e.out)); } |
|
805 Node bNode(InEdgeIt e) const { |
|
806 return ((!e.backward) ? this->graph->bNode(e.in) : |
|
807 this->graph->bNode(e.out)); } |
|
808 |
|
809 // int nodeNum() const { return graph->nodeNum(); } |
|
810 //FIXME |
|
811 void edgeNum() const { } |
|
812 //int edgeNum() const { return graph->edgeNum(); } |
|
813 |
|
814 |
|
815 // int id(Node v) const { return graph->id(v); } |
|
816 |
|
817 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } |
|
818 bool valid(Edge e) const { |
|
819 return this->graph->valid(e); |
|
820 //return e.forward ? graph->valid(e.out) : graph->valid(e.in); |
|
821 } |
|
822 |
|
823 bool forward(const Edge& e) const { return !e.backward; } |
|
824 bool backward(const Edge& e) const { return e.backward; } |
|
825 |
|
826 // void augment(const Edge& e, Number a) const { |
|
827 // if (!e.backward) |
|
828 // // flow->set(e.out, flow->get(e.out)+a); |
|
829 // flow->set(e, (*flow)[e]+a); |
|
830 // else |
|
831 // // flow->set(e.in, flow->get(e.in)-a); |
|
832 // flow->set(e, (*flow)[e]-a); |
|
833 // } |
|
834 |
|
835 bool enabled(const Edge& e) const { |
|
836 if (!e.backward) |
|
837 // return (capacity->get(e.out)-flow->get(e.out)); |
|
838 //return ((*capacity)[e]-(*flow)[e]); |
|
839 return true; |
|
840 else |
|
841 // return (flow->get(e.in)); |
|
842 //return ((*flow)[e]); |
|
843 return true; |
|
844 } |
|
845 |
|
846 // Number enabled(typename Graph::OutEdgeIt out) const { |
|
847 // // return (capacity->get(out)-flow->get(out)); |
|
848 // return ((*capacity)[out]-(*flow)[out]); |
|
849 // } |
|
850 |
|
851 // Number enabled(typename Graph::InEdgeIt in) const { |
|
852 // // return (flow->get(in)); |
|
853 // return ((*flow)[in]); |
|
854 // } |
|
855 |
|
856 template <typename T> |
|
857 class EdgeMap { |
|
858 typename Graph::template EdgeMap<T> forward_map, backward_map; |
|
859 public: |
|
860 EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
|
861 EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
|
862 void set(Edge e, T a) { |
|
863 if (!e.backward) |
|
864 forward_map.set(e.out, a); |
|
865 else |
|
866 backward_map.set(e.in, a); |
|
867 } |
|
868 T operator[](Edge e) const { |
|
869 if (!e.backward) |
|
870 return forward_map[e.out]; |
|
871 else |
|
872 return backward_map[e.in]; |
|
873 } |
|
874 // T get(Edge e) const { |
|
875 // if (e.out_or_in) |
|
876 // return forward_map.get(e.out); |
|
877 // else |
|
878 // return backward_map.get(e.in); |
|
879 // } |
|
880 }; |
|
881 }; |
|
882 |
|
883 |
|
884 |
|
885 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
|
886 |
|
887 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
|
888 template<typename Graph, typename Number, |
|
889 typename CapacityMap, typename FlowMap> |
|
890 class ResGraphWrapper : public GraphWrapper<Graph> { |
|
891 protected: |
|
892 const CapacityMap* capacity; |
|
893 FlowMap* flow; |
|
894 |
|
895 ResGraphWrapper() : GraphWrapper<Graph>(0), |
|
896 capacity(0), flow(0) { } |
|
897 void setCapacityMap(const CapacityMap& _capacity) { |
|
898 capacity=&_capacity; |
|
899 } |
|
900 void setFlowMap(FlowMap& _flow) { |
|
901 flow=&_flow; |
|
902 } |
|
903 |
|
904 public: |
|
905 |
|
906 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
|
907 FlowMap& _flow) : |
|
908 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { } |
|
909 |
|
910 class Edge; |
|
911 class OutEdgeIt; |
|
912 friend class Edge; |
|
913 friend class OutEdgeIt; |
|
914 |
|
915 typedef typename GraphWrapper<Graph>::Node Node; |
|
916 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
917 class Edge : public Graph::Edge { |
|
918 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
|
919 protected: |
|
920 bool backward; //true, iff backward |
|
921 // typename Graph::Edge e; |
|
922 public: |
|
923 Edge() { } |
|
924 Edge(const typename Graph::Edge& _e, bool _backward) : |
|
925 Graph::Edge(_e), backward(_backward) { } |
|
926 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } |
|
927 //the unique invalid iterator |
|
928 friend bool operator==(const Edge& u, const Edge& v) { |
|
929 return (v.backward==u.backward && |
|
930 static_cast<typename Graph::Edge>(u)== |
|
931 static_cast<typename Graph::Edge>(v)); |
|
932 } |
|
933 friend bool operator!=(const Edge& u, const Edge& v) { |
|
934 return (v.backward!=u.backward || |
|
935 static_cast<typename Graph::Edge>(u)!= |
|
936 static_cast<typename Graph::Edge>(v)); |
|
937 } |
|
938 }; |
|
939 |
|
940 class OutEdgeIt { |
|
941 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
|
942 protected: |
|
943 typename Graph::OutEdgeIt out; |
|
944 typename Graph::InEdgeIt in; |
|
945 bool backward; |
|
946 public: |
|
947 OutEdgeIt() { } |
|
948 //FIXME |
|
949 // OutEdgeIt(const Edge& e) : Edge(e) { } |
|
950 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } |
|
951 //the unique invalid iterator |
|
952 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { |
|
953 backward=false; |
|
954 _G.graph->first(out, v); |
|
955 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); } |
|
956 if (!_G.graph->valid(out)) { |
|
957 backward=true; |
|
958 _G.graph->first(in, v); |
|
959 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); } |
|
960 } |
|
961 } |
|
962 operator Edge() const { |
|
963 // Edge e; |
|
964 // e.forward=this->forward; |
|
965 // if (this->forward) e=out; else e=in; |
|
966 // return e; |
|
967 if (this->backward) |
|
968 return Edge(in, this->backward); |
|
969 else |
|
970 return Edge(out, this->backward); |
|
971 } |
|
972 }; |
|
973 |
|
974 class InEdgeIt { |
|
975 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
|
976 protected: |
|
977 typename Graph::OutEdgeIt out; |
|
978 typename Graph::InEdgeIt in; |
|
979 bool backward; |
|
980 public: |
|
981 InEdgeIt() { } |
|
982 //FIXME |
|
983 // OutEdgeIt(const Edge& e) : Edge(e) { } |
|
984 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } |
|
985 //the unique invalid iterator |
|
986 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { |
|
987 backward=false; |
|
988 _G.graph->first(in, v); |
|
989 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); } |
|
990 if (!_G.graph->valid(in)) { |
|
991 backward=true; |
|
992 _G.graph->first(out, v); |
|
993 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); } |
|
994 } |
|
995 } |
|
996 operator Edge() const { |
|
997 // Edge e; |
|
998 // e.forward=this->forward; |
|
999 // if (this->forward) e=out; else e=in; |
|
1000 // return e; |
|
1001 if (this->backward) |
|
1002 return Edge(out, this->backward); |
|
1003 else |
|
1004 return Edge(in, this->backward); |
|
1005 } |
|
1006 }; |
|
1007 |
|
1008 class EdgeIt { |
689 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
1009 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
690 protected: |
1010 protected: |
691 typename Graph::EdgeIt e; |
1011 typename Graph::EdgeIt e; |
692 bool backward; |
1012 bool backward; |
693 public: |
1013 public: |
694 EdgeIt() { } |
1014 EdgeIt() { } |
695 EdgeIt(const Invalid& i) : e(i), backward(true) { } |
1015 EdgeIt(const Invalid& i) : e(i), backward(true) { } |
696 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { |
1016 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { |
697 backward=false; |
1017 backward=false; |
698 resG.graph->first(e); |
1018 _G.graph->first(e); |
699 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
1019 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e); |
700 if (!resG.graph->valid(e)) { |
1020 if (!_G.graph->valid(e)) { |
701 backward=true; |
1021 backward=true; |
702 resG.graph->first(e); |
1022 _G.graph->first(e); |
703 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
1023 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e); |
704 } |
1024 } |
705 } |
1025 } |
706 operator Edge() const { |
1026 operator Edge() const { |
707 return Edge(e, this->backward); |
1027 return Edge(e, this->backward); |
708 } |
1028 } |