311 } |
311 } |
312 |
312 |
313 return _augment; |
313 return _augment; |
314 } |
314 } |
315 |
315 |
|
316 // template<typename MutableGraph> bool augmentOnBlockingFlow() { |
|
317 // bool _augment=false; |
|
318 |
|
319 // AugGraph res_graph(*G, *flow, *capacity); |
|
320 |
|
321 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
322 // BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); |
|
323 |
|
324 // bfs.pushAndSetReached(s); |
|
325 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
326 // while ( !bfs.finished() ) { |
|
327 // AugOutEdgeIt e=bfs; |
|
328 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
329 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
330 // } |
|
331 |
|
332 // ++bfs; |
|
333 // } //computing distances from s in the residual graph |
|
334 |
|
335 // MutableGraph F; |
|
336 // typename AugGraph::NodeMap<typename MutableGraph::Node> |
|
337 // res_graph_to_F(res_graph); |
|
338 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
339 // res_graph_to_F.set(n, F.addNode()); |
|
340 // } |
|
341 |
|
342 // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
|
343 // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
|
344 |
|
345 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
|
346 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
347 |
|
348 // //Making F to the graph containing the edges of the residual graph |
|
349 // //which are in some shortest paths |
|
350 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
|
351 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
|
352 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
353 // original_edge.update(); |
|
354 // original_edge.set(f, e); |
|
355 // residual_capacity.update(); |
|
356 // residual_capacity.set(f, res_graph.free(e)); |
|
357 // } |
|
358 // } |
|
359 |
|
360 // bool __augment=true; |
|
361 |
|
362 // while (__augment) { |
|
363 // __augment=false; |
|
364 // //computing blocking flow with dfs |
|
365 // typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
|
366 // DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
|
367 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
|
368 // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
|
369 // //invalid iterators for sources |
|
370 |
|
371 // typename MutableGraph::NodeMap<Number> free(F); |
|
372 |
|
373 // dfs.pushAndSetReached(sF); |
|
374 // while (!dfs.finished()) { |
|
375 // ++dfs; |
|
376 // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
|
377 // if (dfs.isBNodeNewlyReached()) { |
|
378 // typename MutableGraph::Node v=F.aNode(dfs); |
|
379 // typename MutableGraph::Node w=F.bNode(dfs); |
|
380 // pred.set(w, dfs); |
|
381 // if (F.valid(pred.get(v))) { |
|
382 // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
|
383 // } else { |
|
384 // free.set(w, residual_capacity.get(dfs)); |
|
385 // } |
|
386 // if (w==tF) { |
|
387 // __augment=true; |
|
388 // _augment=true; |
|
389 // break; |
|
390 // } |
|
391 |
|
392 // } else { |
|
393 // F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
|
394 // } |
|
395 // } |
|
396 // } |
|
397 |
|
398 // if (__augment) { |
|
399 // typename MutableGraph::Node n=tF; |
|
400 // Number augment_value=free.get(tF); |
|
401 // while (F.valid(pred.get(n))) { |
|
402 // typename MutableGraph::Edge e=pred.get(n); |
|
403 // res_graph.augment(original_edge.get(e), augment_value); |
|
404 // n=F.tail(e); |
|
405 // if (residual_capacity.get(e)==augment_value) |
|
406 // F.erase(e); |
|
407 // else |
|
408 // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
|
409 // } |
|
410 // } |
|
411 |
|
412 // } |
|
413 |
|
414 // return _augment; |
|
415 // } |
|
416 |
|
417 template<typename GraphWrapper> |
|
418 class DistanceMap { |
|
419 protected: |
|
420 GraphWrapper gw; |
|
421 typename GraphWrapper::NodeMap<int> dist; |
|
422 public: |
|
423 DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } |
|
424 //NodeMap(const ListGraph& _G, T a) : |
|
425 //G(_G), container(G.node_id, a) { } |
|
426 void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; } |
|
427 int get(const typename GraphWrapper::Node& n) const { return dist[n]; } |
|
428 bool get(const typename GraphWrapper::Edge& e) const { |
|
429 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); |
|
430 } |
|
431 //typename std::vector<T>::reference operator[](Node n) { |
|
432 //return container[/*G.id(n)*/n.node->id]; } |
|
433 //typename std::vector<T>::const_reference operator[](Node n) const { |
|
434 //return container[/*G.id(n)*/n.node->id]; |
|
435 }; |
|
436 |
316 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
437 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
317 bool _augment=false; |
438 bool _augment=false; |
318 |
439 |
319 AugGraph res_graph(*G, *flow, *capacity); |
440 AugGraph res_graph(*G, *flow, *capacity); |
320 |
441 |
321 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
442 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
322 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); |
443 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); |
323 |
444 |
324 bfs.pushAndSetReached(s); |
445 bfs.pushAndSetReached(s); |
325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
446 //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
447 DistanceMap<AugGraph> dist(res_graph); |
326 while ( !bfs.finished() ) { |
448 while ( !bfs.finished() ) { |
327 AugOutEdgeIt e=bfs; |
449 AugOutEdgeIt e=bfs; |
328 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
450 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
329 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
451 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
330 } |
452 } |
331 |
|
332 ++bfs; |
453 ++bfs; |
333 } //computing distances from s in the residual graph |
454 } //computing distances from s in the residual graph |
334 |
455 |
|
456 // MutableGraph F; |
|
457 // typename AugGraph::NodeMap<typename MutableGraph::Node> |
|
458 // res_graph_to_F(res_graph); |
|
459 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
460 // res_graph_to_F.set(n, F.addNode()); |
|
461 // } |
|
462 |
|
463 // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
|
464 // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
|
465 |
|
466 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
|
467 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
468 |
|
469 // //Making F to the graph containing the edges of the residual graph |
|
470 // //which are in some shortest paths |
|
471 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
|
472 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
|
473 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
474 // original_edge.update(); |
|
475 // original_edge.set(f, e); |
|
476 // residual_capacity.update(); |
|
477 // residual_capacity.set(f, res_graph.free(e)); |
|
478 // } |
|
479 // } |
|
480 |
335 MutableGraph F; |
481 MutableGraph F; |
|
482 typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph; |
|
483 FilterResGraph filter_res_graph(res_graph, dist); |
336 typename AugGraph::NodeMap<typename MutableGraph::Node> |
484 typename AugGraph::NodeMap<typename MutableGraph::Node> |
337 res_graph_to_F(res_graph); |
485 res_graph_to_F(res_graph); |
338 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
486 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
339 res_graph_to_F.set(n, F.addNode()); |
487 res_graph_to_F.set(n, F.addNode()); |
340 } |
488 } |