Changeset 1025:3b1ad8bc21da in lemon0.x for src/work/marci/lp/min_cost_gen_flow.h
 Timestamp:
 11/29/04 18:55:46 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1415
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/lp/min_cost_gen_flow.h
r1017 r1025 2 2 #ifndef LEMON_MIN_COST_GEN_FLOW_H 3 3 #define LEMON_MIN_COST_GEN_FLOW_H 4 //#include <iostream>4 #include <iostream> 5 5 //#include <fstream> 6 6 7 //#include <lemon/smart_graph.h>8 //#include <lemon/list_graph.h>7 #include <lemon/smart_graph.h> 8 #include <lemon/list_graph.h> 9 9 //#include <lemon/dimacs.h> 10 10 //#include <lemon/time_measure.h> 11 11 //#include <graph_wrapper.h> 12 //#include <lemon/preflow.h>12 #include <lemon/preflow.h> 13 13 //#include <augmenting_flow.h> 14 14 //#include <preflow_res.h> 15 #include <../merge_node_graph_wrapper.h> 15 16 #include <lemon/../work/marci/lp/lp_solver_wrapper.h> 16 17 … … 52 53 g(_g), excess(_excess), lcapacity(_lcapacity), 53 54 capacity(_capacity), flow(_flow), cost(_cost) { } 55 bool feasible() { 56 // std::cout << "making new vertices..." << std::endl; 57 typedef ListGraph Graph2; 58 Graph2 g2; 59 typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW; 60 // std::cout << "merging..." << std::endl; 61 GW gw(g, g2); 62 typename GW::Node s(INVALID, g2.addNode(), true); 63 typename GW::Node t(INVALID, g2.addNode(), true); 64 typedef SmartGraph Graph3; 65 // std::cout << "making extender graph..." << std::endl; 66 typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW; 67 // { 68 // checkConcept<StaticGraph, GWW>(); 69 // } 70 GWW gww(gw); 71 typedef AugmentingGraphWrapper<GW, GWW> GWWW; 72 GWWW gwww(gw, gww); 73 74 // std::cout << "making new edges..." << std::endl; 75 typename GWWW::template EdgeMap<Num> translated_cap(gwww); 76 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]); 80 81 Num expected=0; 82 83 // std::cout << "making new edges 2..." << std::endl; 84 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { 85 Num a=0; 86 for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) 87 a+=lcapacity[e]; 88 for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 89 a=lcapacity[e]; 90 if (excess[n]>a) { 91 typename GWW::Edge e= 92 gww.addEdge(typename GW::Node(n,INVALID,false), t); 93 translated_cap.set(typename GWWW::Edge(INVALID, e, true), 94 excess[n]a); 95 } 96 if (excess[n]<a) { 97 typename GWW::Edge e= 98 gww.addEdge(s, typename GW::Node(n,INVALID,false)); 99 translated_cap.set(typename GWWW::Edge(INVALID, e, true), 100 aexcess[n]); 101 expected+=aexcess[n]; 102 } 103 } 104 105 // std::cout << "preflow..." << std::endl; 106 typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0); 107 Preflow<GWWW, Num> preflow(gwww, s, t, 108 translated_cap, translated_flow); 109 preflow.run(); 110 // std::cout << "fv: " << preflow.flowValue() << std::endl; 111 // std::cout << "expected: " << expected << std::endl; 112 113 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { 114 typename GW::Edge ew(e, INVALID, false); 115 typename GWWW::Edge ewww(ew, INVALID, false); 116 flow.set(e, translated_flow[ewww]+lcapacity[e]); 117 } 118 return (expected>=preflow.flowValue()); 119 } 54 120 void run() { 55 121 LPSolverWrapper lp;
Note: See TracChangeset
for help on using the changeset viewer.