Changeset 672:6c7bd0edd1d7 in lemon-0.x for src
- Timestamp:
- 06/02/04 11:45:50 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@908
- Location:
- src/work
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/athos/min_cost_flow.cc
r662 r672 12 12 13 13 bool passed = true; 14 /* 14 15 15 void check(bool rc, char *msg="") { 16 16 passed = passed && rc; … … 21 21 } 22 22 } 23 */ 23 24 24 25 25 … … 91 91 min_cost_flow_test.run(); 92 92 //int k=1; 93 check(min_cost_flow_test.checkOptimality(), "Is the primal-dual solution pair really optimal?"); 93 94 94 95 /* … … 110 111 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); 111 112 112 113 */ 113 114 cout << (passed ? "All tests passed." : "Some of the tests failed!!!") 114 115 << endl; 115 116 116 117 return passed ? 0 : 1; 117 */118 118 119 } -
src/work/athos/mincostflow.h
r671 r672 100 100 typedef typename Graph::template NodeMap<Cost> PotentialMap; 101 101 PotentialMap potential; 102 //To store excess-deficit values103 SupplyDemandMap excess_deficit;104 102 105 103 … … 115 113 supply_demand(_supply_demand), 116 114 flow(_graph), 117 potential(_graph), 118 excess_deficit(_graph){ } 115 potential(_graph){ } 119 116 120 117 … … 127 124 void run() { 128 125 126 //To store excess-deficit values 127 SupplyDemandMap excess_deficit(graph); 128 129 129 //Resetting variables from previous runs 130 130 //total_cost = 0; 131 131 132 132 133 typedef typename Graph::template NodeMap<int> HeapMap; … … 197 198 //Let's construct the sugraph consisting only of the abundant edges 198 199 typedef ConstMap< typename Graph::Node, bool > ConstNodeMap; 200 199 201 ConstNodeMap const_true_map(true); 200 202 typedef SubGraphWrapper< const Graph, ConstNodeMap, … … 321 323 322 324 Node s = excess_nodes.top(); 323 SupplyDemandmax_excess = excess_nodes[s];325 max_excess = excess_nodes[s]; 324 326 Node t = deficit_nodes.top(); 325 327 if (max_excess < deficit_nodes[t]){ … … 371 373 372 374 //Update the excess_nodes heap 373 if (delta > =excess_nodes[s]){375 if (delta > excess_nodes[s]){ 374 376 if (delta > excess_nodes[s]) 375 377 deficit_nodes.push(s,delta - excess_nodes[s]); … … 381 383 } 382 384 //Update the deficit_nodes heap 383 if (delta > =deficit_nodes[t]){385 if (delta > deficit_nodes[t]){ 384 386 if (delta > deficit_nodes[t]) 385 387 excess_nodes.push(t,delta - deficit_nodes[t]); … … 445 447 ///This function checks, whether the given solution is optimal 446 448 ///Running after a \c run() should return with true 447 ///In this "state of the art" this only check optimality, doesn't bother with feasibility449 ///In this "state of the art" this only checks optimality, doesn't bother with feasibility 448 450 /// 449 451 ///\todo Is this OK here? … … 456 458 fl_e = flow[e]; 457 459 // std::cout << fl_e << std::endl; 458 if (0<fl_e && fl_e<capacity[e]){ 459 if (mod_pot != 0) 460 return false; 461 } 462 else{ 463 if (mod_pot > 0 && fl_e != 0) 464 return false; 465 if (mod_pot < 0 && fl_e != capacity[e]) 466 return false; 467 } 460 if (mod_pot > 0 && fl_e != 0) 461 return false; 462 468 463 } 469 464 return true; 470 465 } 471 466 467 /* 468 //For testing purposes only 469 //Lists the node_properties 470 void write_property_vector(const SupplyDemandMap& a, 471 char* prop_name="property"){ 472 FOR_EACH_LOC(typename Graph::NodeIt, i, graph){ 473 cout<<"Node id.: "<<graph.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl; 474 } 475 cout<<endl; 476 } 477 */ 478 bool checkFeasibility(){ 479 SupplyDemandMap supdem(graph); 480 FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){ 481 482 if ( flow[e] < 0){ 483 484 return false; 485 } 486 supdem[graph.tail(e)] += flow[e]; 487 supdem[graph.head(e)] -= flow[e]; 488 } 489 //write_property_vector(supdem, "supdem"); 490 //write_property_vector(supply_demand, "supply_demand"); 491 492 FOR_EACH_LOC(typename Graph::NodeIt, n, graph){ 493 494 if ( supdem[n] != supply_demand[n]){ 495 //cout<<"Node id.: "<<graph.id(n)<<" : "<<supdem[n]<<", should be: "<<supply_demand[n]<<endl; 496 return false; 497 } 498 } 499 500 return true; 501 } 502 503 bool checkOptimality(){ 504 return checkFeasibility() && checkComplementarySlackness(); 505 } 472 506 473 507 }; //class MinCostFlow -
src/work/makefile
r618 r672 1 1 INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos} 2 CXXFLAGS = -g - O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic2 CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic 3 3 4 4 BINARIES ?= bin_heap_demo
Note: See TracChangeset
for help on using the changeset viewer.