Changeset 602:580b329c2a0c in lemon-0.x for src
- Timestamp:
- 05/10/04 18:59:20 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@782
- Location:
- src/work
- Files:
-
- 1 added
- 1 deleted
- 8 edited
-
jacint/max_flow.h (modified) (4 diffs)
-
marci/bfs_dfs.h (added)
-
marci/bfs_dfs_misc.h (modified) (1 diff)
-
marci/bfs_iterator.h (deleted)
-
marci/bfsit_vs_byhand.cc (modified) (1 diff)
-
marci/bipartite_graph_wrapper_test.cc (modified) (1 diff)
-
marci/bipartite_matching_try.cc (modified) (1 diff)
-
marci/bipartite_matching_try_2.cc (modified) (1 diff)
-
marci/bipartite_matching_try_3.cc (modified) (1 diff)
-
marci/iterator_bfs_demo.cc (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/max_flow.h
r586 r602 45 45 46 46 #include <hugo/graph_wrapper.h> 47 #include <bfs_ iterator.h>47 #include <bfs_dfs.h> 48 48 #include <hugo/invalid.h> 49 49 #include <hugo/maps.h> … … 56 56 57 57 58 // ///\author Marton Makai, Jacint Szabo58 // ///\author Marton Makai, Jacint Szabo 59 59 /// A class for computing max flows and related quantities. 60 60 template <typename Graph, typename Num, … … 89 89 //typename Graph::template NodeMap<int> level; 90 90 typename Graph::template NodeMap<Num> excess; 91 // protected:92 // MaxFlow() { }93 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,94 // FlowMap& _flow)95 // {96 // g=&_G;97 // s=_s;98 // t=_t;99 // capacity=&_capacity;100 // flow=&_flow;101 // n=_G.nodeNum;102 // level.set (_G); //kellene vmi ilyesmi fv103 // excess(_G,0); //itt is104 // }91 // protected: 92 // MaxFlow() { } 93 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 94 // FlowMap& _flow) 95 // { 96 // g=&_G; 97 // s=_s; 98 // t=_t; 99 // capacity=&_capacity; 100 // flow=&_flow; 101 // n=_G.nodeNum; 102 // level.set (_G); //kellene vmi ilyesmi fv 103 // excess(_G,0); //itt is 104 // } 105 105 106 106 public: … … 363 363 364 364 void preflowPreproc ( flowEnum fe, VecStack& active, 365 VecNode& level_list, NNMap& left, NNMap& right ) { 366 367 std::queue<Node> bfs_queue; 368 369 switch ( fe ) { 370 case ZERO_FLOW: 371 { 372 //Reverse_bfs from t, to find the starting level. 373 level.set(t,0); 374 bfs_queue.push(t); 375 376 while (!bfs_queue.empty()) { 377 378 Node v=bfs_queue.front(); 379 bfs_queue.pop(); 380 int l=level[v]+1; 381 382 InEdgeIt e; 383 for(g->first(e,v); g->valid(e); g->next(e)) { 384 Node w=g->tail(e); 385 if ( level[w] == n && w != s ) { 386 bfs_queue.push(w); 387 Node first=level_list[l]; 388 if ( g->valid(first) ) left.set(first,w); 389 right.set(w,first); 390 level_list[l]=w; 391 level.set(w, l); 392 } 393 } 394 } 395 396 //the starting flow 397 OutEdgeIt e; 398 for(g->first(e,s); g->valid(e); g->next(e)) 399 { 400 Num c=(*capacity)[e]; 401 if ( c <= 0 ) continue; 402 Node w=g->head(e); 403 if ( level[w] < n ) { 404 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); 405 flow->set(e, c); 406 excess.set(w, excess[w]+c); 407 } 408 } 409 break; 410 } 411 412 case GEN_FLOW: 413 case PREFLOW: 414 { 415 //Reverse_bfs from t in the residual graph, 416 //to find the starting level. 417 level.set(t,0); 418 bfs_queue.push(t); 419 420 while (!bfs_queue.empty()) { 421 422 Node v=bfs_queue.front(); 423 bfs_queue.pop(); 424 int l=level[v]+1; 425 426 InEdgeIt e; 427 for(g->first(e,v); g->valid(e); g->next(e)) { 428 if ( (*capacity)[e] <= (*flow)[e] ) continue; 429 Node w=g->tail(e); 430 if ( level[w] == n && w != s ) { 431 bfs_queue.push(w); 432 Node first=level_list[l]; 433 if ( g->valid(first) ) left.set(first,w); 434 right.set(w,first); 435 level_list[l]=w; 436 level.set(w, l); 437 } 438 } 439 440 OutEdgeIt f; 441 for(g->first(f,v); g->valid(f); g->next(f)) { 442 if ( 0 >= (*flow)[f] ) continue; 443 Node w=g->head(f); 444 if ( level[w] == n && w != s ) { 445 bfs_queue.push(w); 446 Node first=level_list[l]; 447 if ( g->valid(first) ) left.set(first,w); 448 right.set(w,first); 449 level_list[l]=w; 450 level.set(w, l); 451 } 452 } 453 } 454 455 456 //the starting flow 457 OutEdgeIt e; 458 for(g->first(e,s); g->valid(e); g->next(e)) 459 { 460 Num rem=(*capacity)[e]-(*flow)[e]; 461 if ( rem <= 0 ) continue; 462 Node w=g->head(e); 463 if ( level[w] < n ) { 464 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); 465 flow->set(e, (*capacity)[e]); 466 excess.set(w, excess[w]+rem); 467 } 468 } 469 470 InEdgeIt f; 471 for(g->first(f,s); g->valid(f); g->next(f)) 472 { 473 if ( (*flow)[f] <= 0 ) continue; 474 Node w=g->tail(f); 475 if ( level[w] < n ) { 476 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); 477 excess.set(w, excess[w]+(*flow)[f]); 478 flow->set(f, 0); 479 } 480 } 481 break; 482 } //case PREFLOW 483 } 484 } //preflowPreproc 365 VecNode& level_list, NNMap& left, NNMap& right ) 366 { 367 368 std::queue<Node> bfs_queue; 369 370 switch ( fe ) { 371 case ZERO_FLOW: 372 { 373 //Reverse_bfs from t, to find the starting level. 374 level.set(t,0); 375 bfs_queue.push(t); 376 377 while (!bfs_queue.empty()) { 378 379 Node v=bfs_queue.front(); 380 bfs_queue.pop(); 381 int l=level[v]+1; 382 383 InEdgeIt e; 384 for(g->first(e,v); g->valid(e); g->next(e)) { 385 Node w=g->tail(e); 386 if ( level[w] == n && w != s ) { 387 bfs_queue.push(w); 388 Node first=level_list[l]; 389 if ( g->valid(first) ) left.set(first,w); 390 right.set(w,first); 391 level_list[l]=w; 392 level.set(w, l); 393 } 394 } 395 } 396 397 //the starting flow 398 OutEdgeIt e; 399 for(g->first(e,s); g->valid(e); g->next(e)) 400 { 401 Num c=(*capacity)[e]; 402 if ( c <= 0 ) continue; 403 Node w=g->head(e); 404 if ( level[w] < n ) { 405 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); 406 flow->set(e, c); 407 excess.set(w, excess[w]+c); 408 } 409 } 410 break; 411 } 412 413 case GEN_FLOW: 414 case PREFLOW: 415 { 416 //Reverse_bfs from t in the residual graph, 417 //to find the starting level. 418 level.set(t,0); 419 bfs_queue.push(t); 420 421 while (!bfs_queue.empty()) { 422 423 Node v=bfs_queue.front(); 424 bfs_queue.pop(); 425 int l=level[v]+1; 426 427 InEdgeIt e; 428 for(g->first(e,v); g->valid(e); g->next(e)) { 429 if ( (*capacity)[e] <= (*flow)[e] ) continue; 430 Node w=g->tail(e); 431 if ( level[w] == n && w != s ) { 432 bfs_queue.push(w); 433 Node first=level_list[l]; 434 if ( g->valid(first) ) left.set(first,w); 435 right.set(w,first); 436 level_list[l]=w; 437 level.set(w, l); 438 } 439 } 440 441 OutEdgeIt f; 442 for(g->first(f,v); g->valid(f); g->next(f)) { 443 if ( 0 >= (*flow)[f] ) continue; 444 Node w=g->head(f); 445 if ( level[w] == n && w != s ) { 446 bfs_queue.push(w); 447 Node first=level_list[l]; 448 if ( g->valid(first) ) left.set(first,w); 449 right.set(w,first); 450 level_list[l]=w; 451 level.set(w, l); 452 } 453 } 454 } 455 456 457 //the starting flow 458 OutEdgeIt e; 459 for(g->first(e,s); g->valid(e); g->next(e)) 460 { 461 Num rem=(*capacity)[e]-(*flow)[e]; 462 if ( rem <= 0 ) continue; 463 Node w=g->head(e); 464 if ( level[w] < n ) { 465 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); 466 flow->set(e, (*capacity)[e]); 467 excess.set(w, excess[w]+rem); 468 } 469 } 470 471 InEdgeIt f; 472 for(g->first(f,s); g->valid(f); g->next(f)) 473 { 474 if ( (*flow)[f] <= 0 ) continue; 475 Node w=g->tail(f); 476 if ( level[w] < n ) { 477 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); 478 excess.set(w, excess[w]+(*flow)[f]); 479 flow->set(f, 0); 480 } 481 } 482 break; 483 } //case PREFLOW 484 } 485 } //preflowPreproc 485 486 486 487 -
src/work/marci/bfs_dfs_misc.h
r577 r602 3 3 #define HUGO_BFS_DFS_MISC_H 4 4 5 #include <bfs_ iterator.h>5 #include <bfs_dfs.h> 6 6 #include <for_each_macros.h> 7 7 -
src/work/marci/bfsit_vs_byhand.cc
r577 r602 8 8 #include <hugo/time_measure.h> 9 9 #include <for_each_macros.h> 10 #include <bfs_ iterator.h>10 #include <bfs_dfs.h> 11 11 12 12 using namespace hugo; -
src/work/marci/bipartite_graph_wrapper_test.cc
r557 r602 9 9 #include <hugo/time_measure.h> 10 10 #include <for_each_macros.h> 11 #include <bfs_ iterator.h>11 #include <bfs_dfs.h> 12 12 #include <hugo/graph_wrapper.h> 13 13 #include <bipartite_graph_wrapper.h> -
src/work/marci/bipartite_matching_try.cc
r557 r602 10 10 #include <hugo/time_measure.h> 11 11 #include <for_each_macros.h> 12 #include <bfs_ iterator.h>12 #include <bfs_dfs.h> 13 13 #include <hugo/graph_wrapper.h> 14 14 #include <bipartite_graph_wrapper.h> -
src/work/marci/bipartite_matching_try_2.cc
r555 r602 10 10 #include <hugo/time_measure.h> 11 11 #include <for_each_macros.h> 12 #include <bfs_ iterator.h>12 #include <bfs_dfs.h> 13 13 #include <bipartite_graph_wrapper.h> 14 14 #include <hugo/maps.h> -
src/work/marci/bipartite_matching_try_3.cc
r559 r602 9 9 #include <hugo/time_measure.h> 10 10 #include <for_each_macros.h> 11 #include <bfs_ iterator.h>11 #include <bfs_dfs.h> 12 12 #include <bipartite_graph_wrapper.h> 13 13 #include <hugo/maps.h> -
src/work/marci/iterator_bfs_demo.cc
r569 r602 6 6 #include <list_graph.h> 7 7 //#include <smart_graph.h> 8 #include <bfs_ iterator.h>8 #include <bfs_dfs.h> 9 9 #include <hugo/graph_wrapper.h> 10 10
Note: See TracChangeset
for help on using the changeset viewer.
