1.1 --- a/src/work/edmonds_karp.h Wed Mar 17 14:50:01 2004 +0000
1.2 +++ b/src/work/edmonds_karp.h Wed Mar 17 15:01:04 2004 +0000
1.3 @@ -527,6 +527,306 @@
1.4 }
1.5 };
1.6
1.7 +
1.8 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.9 + class MaxMatching {
1.10 + public:
1.11 + typedef typename Graph::Node Node;
1.12 + typedef typename Graph::Edge Edge;
1.13 + typedef typename Graph::EdgeIt EdgeIt;
1.14 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.15 + typedef typename Graph::InEdgeIt InEdgeIt;
1.16 +
1.17 + typedef typename Graph::NodeMap<bool> SMap;
1.18 + typedef typename Graph::NodeMap<bool> TMap;
1.19 + private:
1.20 + const Graph* G;
1.21 + SMap* S;
1.22 + TMap* T;
1.23 + //Node s;
1.24 + //Node t;
1.25 + FlowMap* flow;
1.26 + const CapacityMap* capacity;
1.27 + typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.28 + typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.29 + typedef typename AugGraph::Edge AugEdge;
1.30 +
1.31 + public:
1.32 + MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
1.33 + G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
1.34 + bool augmentOnShortestPath() {
1.35 + AugGraph res_graph(*G, *flow, *capacity);
1.36 + bool _augment=false;
1.37 +
1.38 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.39 + BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.40 + typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.41 + for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.42 + Number f=0;
1.43 + for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e))
1.44 + f+=flow->get(e);
1.45 + if (f<1) {
1.46 + res_bfs.pushAndSetReached(s);
1.47 + pred.set(s, AugEdge(INVALID));
1.48 + }
1.49 + }
1.50 +
1.51 + typename AugGraph::NodeMap<Number> free(res_graph);
1.52 +
1.53 + Node n;
1.54 + //searching for augmenting path
1.55 + while ( !res_bfs.finished() ) {
1.56 + AugOutEdgeIt e=res_bfs;
1.57 + if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
1.58 + Node v=res_graph.tail(e);
1.59 + Node w=res_graph.head(e);
1.60 + pred.set(w, e);
1.61 + if (res_graph.valid(pred.get(v))) {
1.62 + free.set(w, std::min(free.get(v), res_graph.free(e)));
1.63 + } else {
1.64 + free.set(w, res_graph.free(e));
1.65 + }
1.66 + if (TMap(res_graph.head(e))) {
1.67 + n=res_graph.head(e);
1.68 + _augment=true;
1.69 + break;
1.70 + }
1.71 + }
1.72 +
1.73 + ++res_bfs;
1.74 + } //end of searching augmenting path
1.75 +
1.76 + if (_augment) {
1.77 + //Node n=t;
1.78 + Number augment_value=free.get(t);
1.79 + while (res_graph.valid(pred.get(n))) {
1.80 + AugEdge e=pred.get(n);
1.81 + res_graph.augment(e, augment_value);
1.82 + n=res_graph.tail(e);
1.83 + }
1.84 + }
1.85 +
1.86 + return _augment;
1.87 + }
1.88 +
1.89 +// template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.90 +// bool _augment=false;
1.91 +
1.92 +// AugGraph res_graph(*G, *flow, *capacity);
1.93 +
1.94 +// typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.95 +// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.96 +
1.97 +// bfs.pushAndSetReached(s);
1.98 +// typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.99 +// while ( !bfs.finished() ) {
1.100 +// AugOutEdgeIt e=bfs;
1.101 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.102 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.103 +// }
1.104 +
1.105 +// ++bfs;
1.106 +// } //computing distances from s in the residual graph
1.107 +
1.108 +// MutableGraph F;
1.109 +// typename AugGraph::NodeMap<typename MutableGraph::Node>
1.110 +// res_graph_to_F(res_graph);
1.111 +// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.112 +// res_graph_to_F.set(n, F.addNode());
1.113 +// }
1.114 +
1.115 +// typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.116 +// typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.117 +
1.118 +// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.119 +// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.120 +
1.121 +// //Making F to the graph containing the edges of the residual graph
1.122 +// //which are in some shortest paths
1.123 +// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.124 +// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.125 +// typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.126 +// original_edge.update();
1.127 +// original_edge.set(f, e);
1.128 +// residual_capacity.update();
1.129 +// residual_capacity.set(f, res_graph.free(e));
1.130 +// }
1.131 +// }
1.132 +
1.133 +// bool __augment=true;
1.134 +
1.135 +// while (__augment) {
1.136 +// __augment=false;
1.137 +// //computing blocking flow with dfs
1.138 +// typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
1.139 +// DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
1.140 +// typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.141 +// pred.set(sF, typename MutableGraph::Edge(INVALID));
1.142 +// //invalid iterators for sources
1.143 +
1.144 +// typename MutableGraph::NodeMap<Number> free(F);
1.145 +
1.146 +// dfs.pushAndSetReached(sF);
1.147 +// while (!dfs.finished()) {
1.148 +// ++dfs;
1.149 +// if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.150 +// if (dfs.isBNodeNewlyReached()) {
1.151 +// typename MutableGraph::Node v=F.aNode(dfs);
1.152 +// typename MutableGraph::Node w=F.bNode(dfs);
1.153 +// pred.set(w, dfs);
1.154 +// if (F.valid(pred.get(v))) {
1.155 +// free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.156 +// } else {
1.157 +// free.set(w, residual_capacity.get(dfs));
1.158 +// }
1.159 +// if (w==tF) {
1.160 +// __augment=true;
1.161 +// _augment=true;
1.162 +// break;
1.163 +// }
1.164 +
1.165 +// } else {
1.166 +// F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.167 +// }
1.168 +// }
1.169 +// }
1.170 +
1.171 +// if (__augment) {
1.172 +// typename MutableGraph::Node n=tF;
1.173 +// Number augment_value=free.get(tF);
1.174 +// while (F.valid(pred.get(n))) {
1.175 +// typename MutableGraph::Edge e=pred.get(n);
1.176 +// res_graph.augment(original_edge.get(e), augment_value);
1.177 +// n=F.tail(e);
1.178 +// if (residual_capacity.get(e)==augment_value)
1.179 +// F.erase(e);
1.180 +// else
1.181 +// residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.182 +// }
1.183 +// }
1.184 +
1.185 +// }
1.186 +
1.187 +// return _augment;
1.188 +// }
1.189 +// bool augmentOnBlockingFlow2() {
1.190 +// bool _augment=false;
1.191 +
1.192 +// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.193 +// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.194 +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.195 +// typedef typename EAugGraph::Edge EAugEdge;
1.196 +
1.197 +// EAugGraph res_graph(*G, *flow, *capacity);
1.198 +
1.199 +// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.200 +// BfsIterator4<
1.201 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.202 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
1.203 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.204 +
1.205 +// bfs.pushAndSetReached(s);
1.206 +
1.207 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.208 +// NodeMap<int>& dist=res_graph.dist;
1.209 +
1.210 +// while ( !bfs.finished() ) {
1.211 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.212 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.213 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.214 +// }
1.215 +// ++bfs;
1.216 +// } //computing distances from s in the residual graph
1.217 +
1.218 +// bool __augment=true;
1.219 +
1.220 +// while (__augment) {
1.221 +
1.222 +// __augment=false;
1.223 +// //computing blocking flow with dfs
1.224 +// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.225 +// DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
1.226 +// dfs(res_graph);
1.227 +// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
1.228 +// pred.set(s, EAugEdge(INVALID));
1.229 +// //invalid iterators for sources
1.230 +
1.231 +// typename EAugGraph::NodeMap<Number> free(res_graph);
1.232 +
1.233 +// dfs.pushAndSetReached(s);
1.234 +// while (!dfs.finished()) {
1.235 +// ++dfs;
1.236 +// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.237 +// if (dfs.isBNodeNewlyReached()) {
1.238 +
1.239 +// typename EAugGraph::Node v=res_graph.aNode(dfs);
1.240 +// typename EAugGraph::Node w=res_graph.bNode(dfs);
1.241 +
1.242 +// pred.set(w, EAugOutEdgeIt(dfs));
1.243 +// if (res_graph.valid(pred.get(v))) {
1.244 +// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.245 +// } else {
1.246 +// free.set(w, res_graph.free(dfs));
1.247 +// }
1.248 +
1.249 +// if (w==t) {
1.250 +// __augment=true;
1.251 +// _augment=true;
1.252 +// break;
1.253 +// }
1.254 +// } else {
1.255 +// res_graph.erase(dfs);
1.256 +// }
1.257 +// }
1.258 +
1.259 +// }
1.260 +
1.261 +// if (__augment) {
1.262 +// typename EAugGraph::Node n=t;
1.263 +// Number augment_value=free.get(t);
1.264 +// while (res_graph.valid(pred.get(n))) {
1.265 +// EAugEdge e=pred.get(n);
1.266 +// res_graph.augment(e, augment_value);
1.267 +// n=res_graph.tail(e);
1.268 +// if (res_graph.free(e)==0)
1.269 +// res_graph.erase(e);
1.270 +// }
1.271 +// }
1.272 +
1.273 +// }
1.274 +
1.275 +// return _augment;
1.276 +// }
1.277 + void run() {
1.278 + //int num_of_augmentations=0;
1.279 + while (augmentOnShortestPath()) {
1.280 + //while (augmentOnBlockingFlow<MutableGraph>()) {
1.281 + //std::cout << ++num_of_augmentations << " ";
1.282 + //std::cout<<std::endl;
1.283 + }
1.284 + }
1.285 + template<typename MutableGraph> void run() {
1.286 + //int num_of_augmentations=0;
1.287 + //while (augmentOnShortestPath()) {
1.288 + while (augmentOnBlockingFlow<MutableGraph>()) {
1.289 + //std::cout << ++num_of_augmentations << " ";
1.290 + //std::cout<<std::endl;
1.291 + }
1.292 + }
1.293 + Number flowValue() {
1.294 + Number a=0;
1.295 + OutEdgeIt e;
1.296 + for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
1.297 + a+=flow->get(e);
1.298 + }
1.299 + return a;
1.300 + }
1.301 + };
1.302 +
1.303 +
1.304 +
1.305 +
1.306 +
1.307
1.308 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.309 // class MaxFlow2 {