Changeset 1028:2497336d7e14 in lemon0.x for src/work/marci/lp/min_cost_gen_flow.h
 Timestamp:
 12/02/04 20:59:30 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1418
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/lp/min_cost_gen_flow.h
r1025 r1028 11 11 //#include <graph_wrapper.h> 12 12 #include <lemon/preflow.h> 13 #include <lemon/min_cost_flow.h> 13 14 //#include <augmenting_flow.h> 14 15 //#include <preflow_res.h> 15 #include < ../merge_node_graph_wrapper.h>16 #include < lemon/../work/marci/lp/lp_solver_wrapper.h>16 #include <work/marci/merge_node_graph_wrapper.h> 17 #include <work/marci/lp/lp_solver_wrapper.h> 17 18 18 19 namespace lemon { … … 31 32 }; 32 33 33 // excess: rhodelta 34 // excess: rhodelta egyelore csak =0ra. 34 35 template <typename Graph, typename Num, 35 36 typename Excess=typename Graph::template NodeMap<Num>, … … 75 76 typename GWWW::template EdgeMap<Num> translated_cap(gwww); 76 77 77 for (typename GW::EdgeIt e(gw); e!=INVALID; ++e) 78 translated_cap.set(typename GWWW::Edge(e,INVALID,false), 79 capacity[e]lcapacity[e]); 78 for (typename GW::EdgeIt e(gw); e!=INVALID; ++e) { 79 translated_cap.set(typename GWWW::Edge(e,INVALID,false), 80 capacity[e]lcapacity[e]); 81 // cout << "t_cap " << gw.id(e) << " " 82 // << translated_cap[typename GWWW::Edge(e,INVALID,false)] << endl; 83 } 80 84 81 85 Num expected=0; … … 93 97 translated_cap.set(typename GWWW::Edge(INVALID, e, true), 94 98 excess[n]a); 99 // std::cout << g.id(n) << ">t " << excess[n]a << std::endl; 95 100 } 96 101 if (excess[n]<a) { … … 100 105 aexcess[n]); 101 106 expected+=aexcess[n]; 107 // std::cout << "s>" << g.id(n) << " "<< aexcess[n] <<std:: endl; 102 108 } 103 109 } … … 118 124 return (expected>=preflow.flowValue()); 119 125 } 120 void run() { 126 // for nonnegative costs 127 bool run() { 128 // std::cout << "making new vertices..." << std::endl; 129 typedef ListGraph Graph2; 130 Graph2 g2; 131 typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW; 132 // std::cout << "merging..." << std::endl; 133 GW gw(g, g2); 134 typename GW::Node s(INVALID, g2.addNode(), true); 135 typename GW::Node t(INVALID, g2.addNode(), true); 136 typedef SmartGraph Graph3; 137 // std::cout << "making extender graph..." << std::endl; 138 typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW; 139 // { 140 // checkConcept<StaticGraph, GWW>(); 141 // } 142 GWW gww(gw); 143 typedef AugmentingGraphWrapper<GW, GWW> GWWW; 144 GWWW gwww(gw, gww); 145 146 // std::cout << "making new edges..." << std::endl; 147 typename GWWW::template EdgeMap<Num> translated_cap(gwww); 148 149 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { 150 typename GW::Edge ew(e, INVALID, false); 151 typename GWWW::Edge ewww(ew, INVALID, false); 152 translated_cap.set(ewww, capacity[e]lcapacity[e]); 153 // cout << "t_cap " << g.id(e) << " " 154 // << translated_cap[ewww] << endl; 155 } 156 157 Num expected=0; 158 159 // std::cout << "making new edges 2..." << std::endl; 160 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { 161 // std::cout << "node: " << g.id(n) << std::endl; 162 Num a=0; 163 for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) { 164 a+=lcapacity[e]; 165 // std::cout << "bee: " << g.id(e) << " " << lcapacity[e] << std::endl; 166 } 167 for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) { 168 a=lcapacity[e]; 169 // std::cout << "kie: " << g.id(e) << " " << lcapacity[e] << std::endl; 170 } 171 // std::cout << "excess " << g.id(n) << ": " << a << std::endl; 172 if (0>a) { 173 typename GWW::Edge e= 174 gww.addEdge(typename GW::Node(n,INVALID,false), t); 175 translated_cap.set(typename GWWW::Edge(INVALID, e, true), 176 a); 177 // std::cout << g.id(n) << ">t " << a << std::endl; 178 } 179 if (0<a) { 180 typename GWW::Edge e= 181 gww.addEdge(s, typename GW::Node(n,INVALID,false)); 182 translated_cap.set(typename GWWW::Edge(INVALID, e, true), 183 a); 184 expected+=a; 185 // std::cout << "s>" << g.id(n) << " "<< a <<std:: endl; 186 } 187 } 188 189 // std::cout << "preflow..." << std::endl; 190 typename GWWW::template EdgeMap<Num> translated_cost(gwww, 0); 191 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { 192 translated_cost.set(typename GWWW::Edge( 193 typename GW::Edge(e, INVALID, false), INVALID, false), cost[e]); 194 } 195 // typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0); 196 MinCostFlow<GWWW, typename GWWW::template EdgeMap<Num>, 197 typename GWWW::template EdgeMap<Num> > 198 min_cost_flow(gwww, translated_cost, translated_cap, 199 s, t); 200 while (min_cost_flow.augment()) { } 201 std::cout << "fv: " << min_cost_flow.flowValue() << std::endl; 202 std::cout << "expected: " << expected << std::endl; 203 204 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { 205 typename GW::Edge ew(e, INVALID, false); 206 typename GWWW::Edge ewww(ew, INVALID, false); 207 // std::cout << g.id(e) << " " << flow[e] << std::endl; 208 flow.set(e, lcapacity[e]+ 209 min_cost_flow.getFlow()[ewww]); 210 } 211 return (expected>=min_cost_flow.flowValue()); 212 } 213 void runByLP() { 121 214 LPSolverWrapper lp; 122 215 lp.setMinimize();
Note: See TracChangeset
for help on using the changeset viewer.