COIN-OR::LEMON - Graph Library

Changeset 672:6c7bd0edd1d7 in lemon-0.x for src/work/athos


Ignore:
Timestamp:
06/02/04 11:45:50 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@908
Message:

Seems to work. More tests required.

Location:
src/work/athos
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/min_cost_flow.cc

    r662 r672  
    1212
    1313bool passed = true;
    14 /*
     14
    1515void check(bool rc, char *msg="") {
    1616  passed = passed && rc;
     
    2121  }
    2222}
    23 */
     23
    2424
    2525
     
    9191  min_cost_flow_test.run();
    9292  //int k=1;
     93  check(min_cost_flow_test.checkOptimality(), "Is the primal-dual solution pair really optimal?");
    9394
    9495  /*
     
    110111  check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
    111112
    112 
     113  */
    113114  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    114115       << endl;
    115116
    116117  return passed ? 0 : 1;
    117   */
     118 
    118119}
  • src/work/athos/mincostflow.h

    r671 r672  
    100100    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    101101    PotentialMap potential;
    102     //To store excess-deficit values
    103     SupplyDemandMap excess_deficit;
    104102   
    105103
     
    115113     supply_demand(_supply_demand),
    116114     flow(_graph),
    117      potential(_graph),
    118      excess_deficit(_graph){ }
     115     potential(_graph){ }
    119116
    120117   
     
    127124    void run() {
    128125
     126      //To store excess-deficit values
     127      SupplyDemandMap excess_deficit(graph);
     128
    129129      //Resetting variables from previous runs
    130130      //total_cost = 0;
     131
    131132
    132133      typedef typename Graph::template NodeMap<int> HeapMap;
     
    197198      //Let's construct the sugraph consisting only of the abundant edges
    198199      typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;
     200
    199201      ConstNodeMap const_true_map(true);
    200202      typedef SubGraphWrapper< const Graph, ConstNodeMap,
     
    321323
    322324        Node s = excess_nodes.top();
    323         SupplyDemand max_excess = excess_nodes[s];
     325        max_excess = excess_nodes[s];
    324326        Node t = deficit_nodes.top();
    325327        if (max_excess < deficit_nodes[t]){
     
    371373
    372374          //Update the excess_nodes heap
    373           if (delta >= excess_nodes[s]){
     375          if (delta > excess_nodes[s]){
    374376            if (delta > excess_nodes[s])
    375377              deficit_nodes.push(s,delta - excess_nodes[s]);
     
    381383          }
    382384          //Update the deficit_nodes heap
    383           if (delta >= deficit_nodes[t]){
     385          if (delta > deficit_nodes[t]){
    384386            if (delta > deficit_nodes[t])
    385387              excess_nodes.push(t,delta - deficit_nodes[t]);
     
    445447    ///This function checks, whether the given solution is optimal
    446448    ///Running after a \c run() should return with true
    447     ///In this "state of the art" this only check optimality, doesn't bother with feasibility
     449    ///In this "state of the art" this only checks optimality, doesn't bother with feasibility
    448450    ///
    449451    ///\todo Is this OK here?
     
    456458        fl_e = flow[e];
    457459        //      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
    468463      }
    469464      return true;
    470465    }
    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    }
    472506
    473507  }; //class MinCostFlow
Note: See TracChangeset for help on using the changeset viewer.