42 #include <vector> |
42 #include <vector> |
43 #include <queue> |
43 #include <queue> |
44 #include <stack> |
44 #include <stack> |
45 |
45 |
46 #include <hugo/graph_wrapper.h> |
46 #include <hugo/graph_wrapper.h> |
47 #include <bfs_iterator.h> |
47 #include <bfs_dfs.h> |
48 #include <hugo/invalid.h> |
48 #include <hugo/invalid.h> |
49 #include <hugo/maps.h> |
49 #include <hugo/maps.h> |
50 #include <for_each_macros.h> |
50 #include <for_each_macros.h> |
51 |
51 |
52 /// \file |
52 /// \file |
53 /// \brief Dimacs file format reader. |
53 /// \brief Dimacs file format reader. |
54 |
54 |
55 namespace hugo { |
55 namespace hugo { |
56 |
56 |
57 |
57 |
58 // ///\author Marton Makai, Jacint Szabo |
58 // ///\author Marton Makai, Jacint Szabo |
59 /// A class for computing max flows and related quantities. |
59 /// A class for computing max flows and related quantities. |
60 template <typename Graph, typename Num, |
60 template <typename Graph, typename Num, |
61 typename CapMap=typename Graph::template EdgeMap<Num>, |
61 typename CapMap=typename Graph::template EdgeMap<Num>, |
62 typename FlowMap=typename Graph::template EdgeMap<Num> > |
62 typename FlowMap=typename Graph::template EdgeMap<Num> > |
63 class MaxFlow { |
63 class MaxFlow { |
86 //level works as a bool map in augmenting path algorithms |
86 //level works as a bool map in augmenting path algorithms |
87 //and is used by bfs for storing reached information. |
87 //and is used by bfs for storing reached information. |
88 //In preflow, it shows levels of nodes. |
88 //In preflow, it shows levels of nodes. |
89 //typename Graph::template NodeMap<int> level; |
89 //typename Graph::template NodeMap<int> level; |
90 typename Graph::template NodeMap<Num> excess; |
90 typename Graph::template NodeMap<Num> excess; |
91 // protected: |
91 // protected: |
92 // MaxFlow() { } |
92 // MaxFlow() { } |
93 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
93 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
94 // FlowMap& _flow) |
94 // FlowMap& _flow) |
95 // { |
95 // { |
96 // g=&_G; |
96 // g=&_G; |
97 // s=_s; |
97 // s=_s; |
98 // t=_t; |
98 // t=_t; |
99 // capacity=&_capacity; |
99 // capacity=&_capacity; |
100 // flow=&_flow; |
100 // flow=&_flow; |
101 // n=_G.nodeNum; |
101 // n=_G.nodeNum; |
102 // level.set (_G); //kellene vmi ilyesmi fv |
102 // level.set (_G); //kellene vmi ilyesmi fv |
103 // excess(_G,0); //itt is |
103 // excess(_G,0); //itt is |
104 // } |
104 // } |
105 |
105 |
106 public: |
106 public: |
107 |
107 |
108 ///\todo Document this. |
108 ///\todo Document this. |
109 ///\todo Maybe, it should be PRE_FLOW instead. |
109 ///\todo Maybe, it should be PRE_FLOW instead. |
360 return newlevel; |
360 return newlevel; |
361 } |
361 } |
362 |
362 |
363 |
363 |
364 void preflowPreproc ( flowEnum fe, VecStack& active, |
364 void preflowPreproc ( flowEnum fe, VecStack& active, |
365 VecNode& level_list, NNMap& left, NNMap& right ) { |
365 VecNode& level_list, NNMap& left, NNMap& right ) |
366 |
366 { |
367 std::queue<Node> bfs_queue; |
367 |
368 |
368 std::queue<Node> bfs_queue; |
369 switch ( fe ) { |
369 |
370 case ZERO_FLOW: |
370 switch ( fe ) { |
371 { |
371 case ZERO_FLOW: |
372 //Reverse_bfs from t, to find the starting level. |
372 { |
373 level.set(t,0); |
373 //Reverse_bfs from t, to find the starting level. |
374 bfs_queue.push(t); |
374 level.set(t,0); |
375 |
375 bfs_queue.push(t); |
376 while (!bfs_queue.empty()) { |
376 |
377 |
377 while (!bfs_queue.empty()) { |
378 Node v=bfs_queue.front(); |
378 |
379 bfs_queue.pop(); |
379 Node v=bfs_queue.front(); |
380 int l=level[v]+1; |
380 bfs_queue.pop(); |
381 |
381 int l=level[v]+1; |
382 InEdgeIt e; |
382 |
383 for(g->first(e,v); g->valid(e); g->next(e)) { |
383 InEdgeIt e; |
384 Node w=g->tail(e); |
384 for(g->first(e,v); g->valid(e); g->next(e)) { |
385 if ( level[w] == n && w != s ) { |
385 Node w=g->tail(e); |
386 bfs_queue.push(w); |
386 if ( level[w] == n && w != s ) { |
387 Node first=level_list[l]; |
387 bfs_queue.push(w); |
388 if ( g->valid(first) ) left.set(first,w); |
388 Node first=level_list[l]; |
389 right.set(w,first); |
389 if ( g->valid(first) ) left.set(first,w); |
390 level_list[l]=w; |
390 right.set(w,first); |
391 level.set(w, l); |
391 level_list[l]=w; |
392 } |
392 level.set(w, l); |
393 } |
393 } |
394 } |
394 } |
395 |
395 } |
396 //the starting flow |
396 |
397 OutEdgeIt e; |
397 //the starting flow |
398 for(g->first(e,s); g->valid(e); g->next(e)) |
398 OutEdgeIt e; |
399 { |
399 for(g->first(e,s); g->valid(e); g->next(e)) |
400 Num c=(*capacity)[e]; |
400 { |
401 if ( c <= 0 ) continue; |
401 Num c=(*capacity)[e]; |
402 Node w=g->head(e); |
402 if ( c <= 0 ) continue; |
403 if ( level[w] < n ) { |
403 Node w=g->head(e); |
404 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); |
404 if ( level[w] < n ) { |
405 flow->set(e, c); |
405 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); |
406 excess.set(w, excess[w]+c); |
406 flow->set(e, c); |
407 } |
407 excess.set(w, excess[w]+c); |
408 } |
408 } |
409 break; |
409 } |
410 } |
410 break; |
411 |
411 } |
412 case GEN_FLOW: |
412 |
413 case PREFLOW: |
413 case GEN_FLOW: |
414 { |
414 case PREFLOW: |
415 //Reverse_bfs from t in the residual graph, |
415 { |
416 //to find the starting level. |
416 //Reverse_bfs from t in the residual graph, |
417 level.set(t,0); |
417 //to find the starting level. |
418 bfs_queue.push(t); |
418 level.set(t,0); |
419 |
419 bfs_queue.push(t); |
420 while (!bfs_queue.empty()) { |
420 |
421 |
421 while (!bfs_queue.empty()) { |
422 Node v=bfs_queue.front(); |
422 |
423 bfs_queue.pop(); |
423 Node v=bfs_queue.front(); |
424 int l=level[v]+1; |
424 bfs_queue.pop(); |
425 |
425 int l=level[v]+1; |
426 InEdgeIt e; |
426 |
427 for(g->first(e,v); g->valid(e); g->next(e)) { |
427 InEdgeIt e; |
428 if ( (*capacity)[e] <= (*flow)[e] ) continue; |
428 for(g->first(e,v); g->valid(e); g->next(e)) { |
429 Node w=g->tail(e); |
429 if ( (*capacity)[e] <= (*flow)[e] ) continue; |
430 if ( level[w] == n && w != s ) { |
430 Node w=g->tail(e); |
431 bfs_queue.push(w); |
431 if ( level[w] == n && w != s ) { |
432 Node first=level_list[l]; |
432 bfs_queue.push(w); |
433 if ( g->valid(first) ) left.set(first,w); |
433 Node first=level_list[l]; |
434 right.set(w,first); |
434 if ( g->valid(first) ) left.set(first,w); |
435 level_list[l]=w; |
435 right.set(w,first); |
436 level.set(w, l); |
436 level_list[l]=w; |
437 } |
437 level.set(w, l); |
438 } |
438 } |
439 |
439 } |
440 OutEdgeIt f; |
440 |
441 for(g->first(f,v); g->valid(f); g->next(f)) { |
441 OutEdgeIt f; |
442 if ( 0 >= (*flow)[f] ) continue; |
442 for(g->first(f,v); g->valid(f); g->next(f)) { |
443 Node w=g->head(f); |
443 if ( 0 >= (*flow)[f] ) continue; |
444 if ( level[w] == n && w != s ) { |
444 Node w=g->head(f); |
445 bfs_queue.push(w); |
445 if ( level[w] == n && w != s ) { |
446 Node first=level_list[l]; |
446 bfs_queue.push(w); |
447 if ( g->valid(first) ) left.set(first,w); |
447 Node first=level_list[l]; |
448 right.set(w,first); |
448 if ( g->valid(first) ) left.set(first,w); |
449 level_list[l]=w; |
449 right.set(w,first); |
450 level.set(w, l); |
450 level_list[l]=w; |
451 } |
451 level.set(w, l); |
452 } |
452 } |
453 } |
453 } |
454 |
454 } |
455 |
455 |
456 //the starting flow |
456 |
457 OutEdgeIt e; |
457 //the starting flow |
458 for(g->first(e,s); g->valid(e); g->next(e)) |
458 OutEdgeIt e; |
459 { |
459 for(g->first(e,s); g->valid(e); g->next(e)) |
460 Num rem=(*capacity)[e]-(*flow)[e]; |
460 { |
461 if ( rem <= 0 ) continue; |
461 Num rem=(*capacity)[e]-(*flow)[e]; |
462 Node w=g->head(e); |
462 if ( rem <= 0 ) continue; |
463 if ( level[w] < n ) { |
463 Node w=g->head(e); |
464 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); |
464 if ( level[w] < n ) { |
465 flow->set(e, (*capacity)[e]); |
465 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); |
466 excess.set(w, excess[w]+rem); |
466 flow->set(e, (*capacity)[e]); |
467 } |
467 excess.set(w, excess[w]+rem); |
468 } |
468 } |
469 |
469 } |
470 InEdgeIt f; |
470 |
471 for(g->first(f,s); g->valid(f); g->next(f)) |
471 InEdgeIt f; |
472 { |
472 for(g->first(f,s); g->valid(f); g->next(f)) |
473 if ( (*flow)[f] <= 0 ) continue; |
473 { |
474 Node w=g->tail(f); |
474 if ( (*flow)[f] <= 0 ) continue; |
475 if ( level[w] < n ) { |
475 Node w=g->tail(f); |
476 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); |
476 if ( level[w] < n ) { |
477 excess.set(w, excess[w]+(*flow)[f]); |
477 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); |
478 flow->set(f, 0); |
478 excess.set(w, excess[w]+(*flow)[f]); |
479 } |
479 flow->set(f, 0); |
480 } |
480 } |
481 break; |
481 } |
482 } //case PREFLOW |
482 break; |
483 } |
483 } //case PREFLOW |
484 } //preflowPreproc |
484 } |
|
485 } //preflowPreproc |
485 |
486 |
486 |
487 |
487 |
488 |
488 void relabel(Node w, int newlevel, VecStack& active, |
489 void relabel(Node w, int newlevel, VecStack& active, |
489 VecNode& level_list, NNMap& left, |
490 VecNode& level_list, NNMap& left, |