Seems to work. More tests required.
1.1 --- a/src/work/athos/min_cost_flow.cc Tue Jun 01 11:00:24 2004 +0000
1.2 +++ b/src/work/athos/min_cost_flow.cc Wed Jun 02 09:45:50 2004 +0000
1.3 @@ -11,7 +11,7 @@
1.4
1.5
1.6 bool passed = true;
1.7 -/*
1.8 +
1.9 void check(bool rc, char *msg="") {
1.10 passed = passed && rc;
1.11 if(!rc) {
1.12 @@ -20,7 +20,7 @@
1.13
1.14 }
1.15 }
1.16 -*/
1.17 +
1.18
1.19
1.20 int main()
1.21 @@ -90,6 +90,7 @@
1.22
1.23 min_cost_flow_test.run();
1.24 //int k=1;
1.25 + check(min_cost_flow_test.checkOptimality(), "Is the primal-dual solution pair really optimal?");
1.26
1.27 /*
1.28 check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
1.29 @@ -109,10 +110,10 @@
1.30
1.31 check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.32
1.33 -
1.34 + */
1.35 cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
1.36 << endl;
1.37
1.38 return passed ? 0 : 1;
1.39 - */
1.40 +
1.41 }
2.1 --- a/src/work/athos/mincostflow.h Tue Jun 01 11:00:24 2004 +0000
2.2 +++ b/src/work/athos/mincostflow.h Wed Jun 02 09:45:50 2004 +0000
2.3 @@ -99,8 +99,6 @@
2.4 //To store the potential (dual variables)
2.5 typedef typename Graph::template NodeMap<Cost> PotentialMap;
2.6 PotentialMap potential;
2.7 - //To store excess-deficit values
2.8 - SupplyDemandMap excess_deficit;
2.9
2.10
2.11 Cost total_cost;
2.12 @@ -114,8 +112,7 @@
2.13 cost(_cost),
2.14 supply_demand(_supply_demand),
2.15 flow(_graph),
2.16 - potential(_graph),
2.17 - excess_deficit(_graph){ }
2.18 + potential(_graph){ }
2.19
2.20
2.21 ///Runs the algorithm.
2.22 @@ -126,9 +123,13 @@
2.23 /// feasible primal-dual solution pair as well.
2.24 void run() {
2.25
2.26 + //To store excess-deficit values
2.27 + SupplyDemandMap excess_deficit(graph);
2.28 +
2.29 //Resetting variables from previous runs
2.30 //total_cost = 0;
2.31
2.32 +
2.33 typedef typename Graph::template NodeMap<int> HeapMap;
2.34 typedef BinHeap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
2.35 std::greater<SupplyDemand> > HeapType;
2.36 @@ -196,6 +197,7 @@
2.37
2.38 //Let's construct the sugraph consisting only of the abundant edges
2.39 typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;
2.40 +
2.41 ConstNodeMap const_true_map(true);
2.42 typedef SubGraphWrapper< const Graph, ConstNodeMap,
2.43 typename Graph::template EdgeMap<bool> >
2.44 @@ -320,7 +322,7 @@
2.45
2.46
2.47 Node s = excess_nodes.top();
2.48 - SupplyDemand max_excess = excess_nodes[s];
2.49 + max_excess = excess_nodes[s];
2.50 Node t = deficit_nodes.top();
2.51 if (max_excess < deficit_nodes[t]){
2.52 max_excess = deficit_nodes[t];
2.53 @@ -370,7 +372,7 @@
2.54
2.55
2.56 //Update the excess_nodes heap
2.57 - if (delta >= excess_nodes[s]){
2.58 + if (delta > excess_nodes[s]){
2.59 if (delta > excess_nodes[s])
2.60 deficit_nodes.push(s,delta - excess_nodes[s]);
2.61 excess_nodes.pop();
2.62 @@ -380,7 +382,7 @@
2.63 excess_nodes.set(s, excess_nodes[s] - delta);
2.64 }
2.65 //Update the deficit_nodes heap
2.66 - if (delta >= deficit_nodes[t]){
2.67 + if (delta > deficit_nodes[t]){
2.68 if (delta > deficit_nodes[t])
2.69 excess_nodes.push(t,delta - deficit_nodes[t]);
2.70 deficit_nodes.pop();
2.71 @@ -444,7 +446,7 @@
2.72
2.73 ///This function checks, whether the given solution is optimal
2.74 ///Running after a \c run() should return with true
2.75 - ///In this "state of the art" this only check optimality, doesn't bother with feasibility
2.76 + ///In this "state of the art" this only checks optimality, doesn't bother with feasibility
2.77 ///
2.78 ///\todo Is this OK here?
2.79 bool checkComplementarySlackness(){
2.80 @@ -455,20 +457,52 @@
2.81 mod_pot = cost[e]-potential[graph.head(e)]+potential[graph.tail(e)];
2.82 fl_e = flow[e];
2.83 // std::cout << fl_e << std::endl;
2.84 - if (0<fl_e && fl_e<capacity[e]){
2.85 - if (mod_pot != 0)
2.86 - return false;
2.87 - }
2.88 - else{
2.89 - if (mod_pot > 0 && fl_e != 0)
2.90 - return false;
2.91 - if (mod_pot < 0 && fl_e != capacity[e])
2.92 - return false;
2.93 - }
2.94 + if (mod_pot > 0 && fl_e != 0)
2.95 + return false;
2.96 +
2.97 }
2.98 return true;
2.99 }
2.100 -
2.101 +
2.102 + /*
2.103 + //For testing purposes only
2.104 + //Lists the node_properties
2.105 + void write_property_vector(const SupplyDemandMap& a,
2.106 + char* prop_name="property"){
2.107 + FOR_EACH_LOC(typename Graph::NodeIt, i, graph){
2.108 + cout<<"Node id.: "<<graph.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
2.109 + }
2.110 + cout<<endl;
2.111 + }
2.112 + */
2.113 + bool checkFeasibility(){
2.114 + SupplyDemandMap supdem(graph);
2.115 + FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
2.116 +
2.117 + if ( flow[e] < 0){
2.118 +
2.119 + return false;
2.120 + }
2.121 + supdem[graph.tail(e)] += flow[e];
2.122 + supdem[graph.head(e)] -= flow[e];
2.123 + }
2.124 + //write_property_vector(supdem, "supdem");
2.125 + //write_property_vector(supply_demand, "supply_demand");
2.126 +
2.127 + FOR_EACH_LOC(typename Graph::NodeIt, n, graph){
2.128 +
2.129 + if ( supdem[n] != supply_demand[n]){
2.130 + //cout<<"Node id.: "<<graph.id(n)<<" : "<<supdem[n]<<", should be: "<<supply_demand[n]<<endl;
2.131 + return false;
2.132 + }
2.133 + }
2.134 +
2.135 + return true;
2.136 + }
2.137 +
2.138 + bool checkOptimality(){
2.139 + return checkFeasibility() && checkComplementarySlackness();
2.140 + }
2.141
2.142 }; //class MinCostFlow
2.143
3.1 --- a/src/work/makefile Tue Jun 01 11:00:24 2004 +0000
3.2 +++ b/src/work/makefile Wed Jun 02 09:45:50 2004 +0000
3.3 @@ -1,5 +1,5 @@
3.4 INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos}
3.5 -CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
3.6 +CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
3.7
3.8 BINARIES ?= bin_heap_demo
3.9