1.1 --- a/src/work/marci/lp/min_cost_gen_flow.h Thu Dec 02 17:36:07 2004 +0000
1.2 +++ b/src/work/marci/lp/min_cost_gen_flow.h Thu Dec 02 19:59:30 2004 +0000
1.3 @@ -10,10 +10,11 @@
1.4 //#include <lemon/time_measure.h>
1.5 //#include <graph_wrapper.h>
1.6 #include <lemon/preflow.h>
1.7 +#include <lemon/min_cost_flow.h>
1.8 //#include <augmenting_flow.h>
1.9 //#include <preflow_res.h>
1.10 -#include <../merge_node_graph_wrapper.h>
1.11 -#include <lemon/../work/marci/lp/lp_solver_wrapper.h>
1.12 +#include <work/marci/merge_node_graph_wrapper.h>
1.13 +#include <work/marci/lp/lp_solver_wrapper.h>
1.14
1.15 namespace lemon {
1.16
1.17 @@ -30,7 +31,7 @@
1.18 }
1.19 };
1.20
1.21 - // excess: rho-delta
1.22 + // excess: rho-delta egyelore csak =0-ra.
1.23 template <typename Graph, typename Num,
1.24 typename Excess=typename Graph::template NodeMap<Num>,
1.25 typename LCapMap=typename Graph::template EdgeMap<Num>,
1.26 @@ -74,9 +75,12 @@
1.27 // std::cout << "making new edges..." << std::endl;
1.28 typename GWWW::template EdgeMap<Num> translated_cap(gwww);
1.29
1.30 - for (typename GW::EdgeIt e(gw); e!=INVALID; ++e)
1.31 - translated_cap.set(typename GWWW::Edge(e,INVALID,false),
1.32 - capacity[e]-lcapacity[e]);
1.33 + for (typename GW::EdgeIt e(gw); e!=INVALID; ++e) {
1.34 + translated_cap.set(typename GWWW::Edge(e,INVALID,false),
1.35 + capacity[e]-lcapacity[e]);
1.36 + // cout << "t_cap " << gw.id(e) << " "
1.37 + // << translated_cap[typename GWWW::Edge(e,INVALID,false)] << endl;
1.38 + }
1.39
1.40 Num expected=0;
1.41
1.42 @@ -92,6 +96,7 @@
1.43 gww.addEdge(typename GW::Node(n,INVALID,false), t);
1.44 translated_cap.set(typename GWWW::Edge(INVALID, e, true),
1.45 excess[n]-a);
1.46 + // std::cout << g.id(n) << "->t " << excess[n]-a << std::endl;
1.47 }
1.48 if (excess[n]<a) {
1.49 typename GWW::Edge e=
1.50 @@ -99,6 +104,7 @@
1.51 translated_cap.set(typename GWWW::Edge(INVALID, e, true),
1.52 a-excess[n]);
1.53 expected+=a-excess[n];
1.54 + // std::cout << "s->" << g.id(n) << " "<< a-excess[n] <<std:: endl;
1.55 }
1.56 }
1.57
1.58 @@ -117,7 +123,94 @@
1.59 }
1.60 return (expected>=preflow.flowValue());
1.61 }
1.62 - void run() {
1.63 + // for nonnegative costs
1.64 + bool run() {
1.65 + // std::cout << "making new vertices..." << std::endl;
1.66 + typedef ListGraph Graph2;
1.67 + Graph2 g2;
1.68 + typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
1.69 + // std::cout << "merging..." << std::endl;
1.70 + GW gw(g, g2);
1.71 + typename GW::Node s(INVALID, g2.addNode(), true);
1.72 + typename GW::Node t(INVALID, g2.addNode(), true);
1.73 + typedef SmartGraph Graph3;
1.74 + // std::cout << "making extender graph..." << std::endl;
1.75 + typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
1.76 +// {
1.77 +// checkConcept<StaticGraph, GWW>();
1.78 +// }
1.79 + GWW gww(gw);
1.80 + typedef AugmentingGraphWrapper<GW, GWW> GWWW;
1.81 + GWWW gwww(gw, gww);
1.82 +
1.83 + // std::cout << "making new edges..." << std::endl;
1.84 + typename GWWW::template EdgeMap<Num> translated_cap(gwww);
1.85 +
1.86 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.87 + typename GW::Edge ew(e, INVALID, false);
1.88 + typename GWWW::Edge ewww(ew, INVALID, false);
1.89 + translated_cap.set(ewww, capacity[e]-lcapacity[e]);
1.90 + // cout << "t_cap " << g.id(e) << " "
1.91 + // << translated_cap[ewww] << endl;
1.92 + }
1.93 +
1.94 + Num expected=0;
1.95 +
1.96 + // std::cout << "making new edges 2..." << std::endl;
1.97 + for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
1.98 + // std::cout << "node: " << g.id(n) << std::endl;
1.99 + Num a=0;
1.100 + for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
1.101 + a+=lcapacity[e];
1.102 + // std::cout << "bee: " << g.id(e) << " " << lcapacity[e] << std::endl;
1.103 + }
1.104 + for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
1.105 + a-=lcapacity[e];
1.106 + // std::cout << "kie: " << g.id(e) << " " << lcapacity[e] << std::endl;
1.107 + }
1.108 + // std::cout << "excess " << g.id(n) << ": " << a << std::endl;
1.109 + if (0>a) {
1.110 + typename GWW::Edge e=
1.111 + gww.addEdge(typename GW::Node(n,INVALID,false), t);
1.112 + translated_cap.set(typename GWWW::Edge(INVALID, e, true),
1.113 + -a);
1.114 + // std::cout << g.id(n) << "->t " << -a << std::endl;
1.115 + }
1.116 + if (0<a) {
1.117 + typename GWW::Edge e=
1.118 + gww.addEdge(s, typename GW::Node(n,INVALID,false));
1.119 + translated_cap.set(typename GWWW::Edge(INVALID, e, true),
1.120 + a);
1.121 + expected+=a;
1.122 + // std::cout << "s->" << g.id(n) << " "<< a <<std:: endl;
1.123 + }
1.124 + }
1.125 +
1.126 + // std::cout << "preflow..." << std::endl;
1.127 + typename GWWW::template EdgeMap<Num> translated_cost(gwww, 0);
1.128 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.129 + translated_cost.set(typename GWWW::Edge(
1.130 + typename GW::Edge(e, INVALID, false), INVALID, false), cost[e]);
1.131 + }
1.132 + // typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
1.133 + MinCostFlow<GWWW, typename GWWW::template EdgeMap<Num>,
1.134 + typename GWWW::template EdgeMap<Num> >
1.135 + min_cost_flow(gwww, translated_cost, translated_cap,
1.136 + s, t);
1.137 + while (min_cost_flow.augment()) { }
1.138 + std::cout << "fv: " << min_cost_flow.flowValue() << std::endl;
1.139 + std::cout << "expected: " << expected << std::endl;
1.140 +
1.141 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.142 + typename GW::Edge ew(e, INVALID, false);
1.143 + typename GWWW::Edge ewww(ew, INVALID, false);
1.144 + // std::cout << g.id(e) << " " << flow[e] << std::endl;
1.145 + flow.set(e, lcapacity[e]+
1.146 + min_cost_flow.getFlow()[ewww]);
1.147 + }
1.148 + return (expected>=min_cost_flow.flowValue());
1.149 + }
1.150 + void runByLP() {
1.151 LPSolverWrapper lp;
1.152 lp.setMinimize();
1.153 typedef LPSolverWrapper::ColIt ColIt;