894 // }; |
894 // }; |
895 |
895 |
896 |
896 |
897 |
897 |
898 |
898 |
899 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
899 template<typename Graph, typename Number, |
|
900 typename CapacityMap, typename FlowMap> |
900 class ResGraphWrapper : public GraphWrapper<Graph> { |
901 class ResGraphWrapper : public GraphWrapper<Graph> { |
901 protected: |
902 protected: |
902 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
903 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
903 // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
904 // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
904 // typedef typename Graph::Edge GraphEdge; |
905 // typedef typename Graph::Edge GraphEdge; |
|
906 const CapacityMap* capacity; |
905 FlowMap* flow; |
907 FlowMap* flow; |
906 const CapacityMap* capacity; |
|
907 public: |
908 public: |
908 |
909 |
909 ResGraphWrapper(Graph& _graph, FlowMap& _flow, |
910 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
910 const CapacityMap& _capacity) : |
911 FlowMap& _flow) : |
911 GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { } |
912 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { } |
912 |
913 |
913 class Edge; |
914 class Edge; |
914 class OutEdgeIt; |
915 class OutEdgeIt; |
915 friend class Edge; |
916 friend class Edge; |
916 friend class OutEdgeIt; |
917 friend class OutEdgeIt; |
917 |
918 |
918 typedef typename GraphWrapper<Graph>::Node Node; |
919 typedef typename GraphWrapper<Graph>::Node Node; |
919 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
920 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
920 class Edge : public Graph::Edge { |
921 class Edge : public Graph::Edge { |
921 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
922 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
922 protected: |
923 protected: |
923 bool forward; //true, iff forward |
924 bool forward; //true, iff forward |
924 // typename Graph::Edge e; |
925 // typename Graph::Edge e; |
925 public: |
926 public: |
926 Edge() { } |
927 Edge() { } |
938 static_cast<typename Graph::Edge>(u)!= |
939 static_cast<typename Graph::Edge>(u)!= |
939 static_cast<typename Graph::Edge>(v)); |
940 static_cast<typename Graph::Edge>(v)); |
940 } |
941 } |
941 }; |
942 }; |
942 // class Edge { |
943 // class Edge { |
943 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
944 // friend class ResGraphWrapper<Graph, Number,lksd FlowMap, CapacityMap>; |
944 // protected: |
945 // protected: |
945 // bool out_or_in; //true, iff out |
946 // bool out_or_in; //true, iff out |
946 // GraphOutEdgeIt out; |
947 // GraphOutEdgeIt out; |
947 // GraphInEdgeIt in; |
948 // GraphInEdgeIt in; |
948 // public: |
949 // public: |
965 // operator GraphEdge() const { |
966 // operator GraphEdge() const { |
966 // if (out_or_in) return(out); else return(in); |
967 // if (out_or_in) return(out); else return(in); |
967 // } |
968 // } |
968 // }; |
969 // }; |
969 class OutEdgeIt { |
970 class OutEdgeIt { |
970 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
971 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
971 protected: |
972 protected: |
972 typename Graph::OutEdgeIt out; |
973 typename Graph::OutEdgeIt out; |
973 typename Graph::InEdgeIt in; |
974 typename Graph::InEdgeIt in; |
974 bool forward; |
975 bool forward; |
975 public: |
976 public: |
976 OutEdgeIt() { } |
977 OutEdgeIt() { } |
977 //FIXME |
978 //FIXME |
978 // OutEdgeIt(const Edge& e) : Edge(e) { } |
979 // OutEdgeIt(const Edge& e) : Edge(e) { } |
979 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
980 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
980 //the unique invalid iterator |
981 //the unique invalid iterator |
981 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) { |
982 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { |
982 forward=true; |
983 forward=true; |
983 resG.graph->first(out, v); |
984 resG.graph->first(out, v); |
984 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } |
985 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } |
985 if (!resG.graph->valid(out)) { |
986 if (!resG.graph->valid(out)) { |
986 forward=false; |
987 forward=false; |
998 else |
999 else |
999 return Edge(in, this->forward); |
1000 return Edge(in, this->forward); |
1000 } |
1001 } |
1001 }; |
1002 }; |
1002 // class OutEdgeIt : public Edge { |
1003 // class OutEdgeIt : public Edge { |
1003 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
1004 // friend class ResGraphWrapper<Graph, Number, FkklowMap, CapacityMap>; |
1004 // public: |
1005 // public: |
1005 // OutEdgeIt() { } |
1006 // OutEdgeIt() { } |
1006 // //FIXME |
1007 // //FIXME |
1007 // OutEdgeIt(const Edge& e) : Edge(e) { } |
1008 // OutEdgeIt(const Edge& e) : Edge(e) { } |
1008 // OutEdgeIt(const Invalid& i) : Edge(i) { } |
1009 // OutEdgeIt(const Invalid& i) : Edge(i) { } |
1009 // OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { |
1010 // OutEdgeIt(const ResGraphWrapper<Graph, Number, FdfvlowMap, CapacityMap>& resG, Node v) : Edge() { |
1010 // resG.graph->first(out, v); |
1011 // resG.graph->first(out, v); |
1011 // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
1012 // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
1012 // if (!resG.graph->valid(out)) { |
1013 // if (!resG.graph->valid(out)) { |
1013 // out_or_in=0; |
1014 // out_or_in=0; |
1014 // resG.graph->first(in, v); |
1015 // resG.graph->first(in, v); |
1036 |
1037 |
1037 //FIXME This is just for having InEdgeIt |
1038 //FIXME This is just for having InEdgeIt |
1038 // class InEdgeIt : public Edge { }; |
1039 // class InEdgeIt : public Edge { }; |
1039 |
1040 |
1040 class InEdgeIt { |
1041 class InEdgeIt { |
1041 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
1042 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
1042 protected: |
1043 protected: |
1043 typename Graph::OutEdgeIt out; |
1044 typename Graph::OutEdgeIt out; |
1044 typename Graph::InEdgeIt in; |
1045 typename Graph::InEdgeIt in; |
1045 bool forward; |
1046 bool forward; |
1046 public: |
1047 public: |
1047 InEdgeIt() { } |
1048 InEdgeIt() { } |
1048 //FIXME |
1049 //FIXME |
1049 // OutEdgeIt(const Edge& e) : Edge(e) { } |
1050 // OutEdgeIt(const Edge& e) : Edge(e) { } |
1050 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
1051 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
1051 //the unique invalid iterator |
1052 //the unique invalid iterator |
1052 InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) { |
1053 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { |
1053 forward=true; |
1054 forward=true; |
1054 resG.graph->first(in, v); |
1055 resG.graph->first(in, v); |
1055 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } |
1056 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } |
1056 if (!resG.graph->valid(in)) { |
1057 if (!resG.graph->valid(in)) { |
1057 forward=false; |
1058 forward=false; |
1070 return Edge(out, this->forward); |
1071 return Edge(out, this->forward); |
1071 } |
1072 } |
1072 }; |
1073 }; |
1073 |
1074 |
1074 class EdgeIt { |
1075 class EdgeIt { |
1075 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
1076 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
1076 protected: |
1077 protected: |
1077 typename Graph::EdgeIt e; |
1078 typename Graph::EdgeIt e; |
1078 bool forward; |
1079 bool forward; |
1079 public: |
1080 public: |
1080 EdgeIt() { } |
1081 EdgeIt() { } |
1081 EdgeIt(const Invalid& i) : e(i), forward(false) { } |
1082 EdgeIt(const Invalid& i) : e(i), forward(false) { } |
1082 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) { |
1083 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { |
1083 forward=true; |
1084 forward=true; |
1084 resG.graph->first(e); |
1085 resG.graph->first(e); |
1085 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
1086 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
1086 if (!resG.graph->valid(e)) { |
1087 if (!resG.graph->valid(e)) { |
1087 forward=false; |
1088 forward=false; |
1092 operator Edge() const { |
1093 operator Edge() const { |
1093 return Edge(e, this->forward); |
1094 return Edge(e, this->forward); |
1094 } |
1095 } |
1095 }; |
1096 }; |
1096 // class EdgeIt : public Edge { |
1097 // class EdgeIt : public Edge { |
1097 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
1098 // friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>; |
1098 // NodeIt v; |
1099 // NodeIt v; |
1099 // public: |
1100 // public: |
1100 // EdgeIt() { } |
1101 // EdgeIt() { } |
1101 // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
1102 // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
1102 // EdgeIt(const Invalid& i) : Edge(i) { } |
1103 // EdgeIt(const Invalid& i) : Edge(i) { } |
1103 // EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { |
1104 // EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() { |
1104 // resG.graph->first(v); |
1105 // resG.graph->first(v); |
1105 // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; |
1106 // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; |
1106 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
1107 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
1107 // while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
1108 // while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
1108 // resG.graph->next(v); |
1109 // resG.graph->next(v); |
1315 // return ((*flow)[in]); |
1316 // return ((*flow)[in]); |
1316 // } |
1317 // } |
1317 |
1318 |
1318 // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
1319 // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
1319 // public: |
1320 // public: |
1320 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) |
1321 // NodeMap(const ResGraphWrapper<Graph, Number, FlovwMap, CapacityMap>& _G) |
1321 // : Graph::NodeMap<T>(_G.gw) { } |
1322 // : Graph::NodeMap<T>(_G.gw) { } |
1322 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, |
1323 // NodeMap(const ResGraphWrapper<Graph, Number, FlowvMap, CapacityMap>& _G, |
1323 // T a) : Graph::NodeMap<T>(_G.gw, a) { } |
1324 // T a) : Graph::NodeMap<T>(_G.gw, a) { } |
1324 // }; |
1325 // }; |
1325 |
1326 |
1326 // template <typename T> |
1327 // template <typename T> |
1327 // class NodeMap { |
1328 // class NodeMap { |
1335 |
1336 |
1336 template <typename T> |
1337 template <typename T> |
1337 class EdgeMap { |
1338 class EdgeMap { |
1338 typename Graph::EdgeMap<T> forward_map, backward_map; |
1339 typename Graph::EdgeMap<T> forward_map, backward_map; |
1339 public: |
1340 public: |
1340 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
1341 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
1341 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
1342 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
1342 void set(Edge e, T a) { |
1343 void set(Edge e, T a) { |
1343 if (e.forward) |
1344 if (e.forward) |
1344 forward_map.set(e.out, a); |
1345 forward_map.set(e.out, a); |
1345 else |
1346 else |
1346 backward_map.set(e.in, a); |
1347 backward_map.set(e.in, a); |