Changeset 1014:aae850a2394d in lemon0.x for src/work/marci/lp/max_flow_by_lp.cc
 Timestamp:
 11/20/04 15:23:27 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1404
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/lp/max_flow_by_lp.cc
r986 r1014 3 3 #include <fstream> 4 4 5 #include <sage_graph.h>6 5 #include <lemon/smart_graph.h> 6 #include <lemon/list_graph.h> 7 7 #include <lemon/dimacs.h> 8 8 #include <lemon/time_measure.h> 9 9 //#include <graph_wrapper.h> 10 #include <lemon/ max_flow.h>10 #include <lemon/preflow.h> 11 11 #include <augmenting_flow.h> 12 12 //#include <preflow_res.h> 13 #include <for_each_macros.h>14 13 #include <lp_solver_wrapper.h> 15 14 … … 34 33 int main(int, char **) { 35 34 36 typedef SageGraph MutableGraph; 37 //typedef SmartGraph Graph; 38 typedef SageGraph Graph; 35 typedef ListGraph MutableGraph; 36 typedef SmartGraph Graph; 39 37 typedef Graph::Node Node; 40 38 typedef Graph::EdgeIt EdgeIt; … … 48 46 Timer ts; 49 47 Graph::EdgeMap<int> flow(g); //0 flow 50 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >48 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 51 49 max_flow_test(g, s, t, cap, flow); 52 50 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > … … 61 59 std::cout << "elapsed time: " << ts << std::endl; 62 60 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 63 max_flow_test. actMinCut(cut);64 65 FOR_EACH_LOC(Graph::EdgeIt, e, g) {61 max_flow_test.minCut(cut); 62 63 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 66 64 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 67 65 std::cout << "Slackness does not hold!" << std::endl; … … 75 73 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); 76 74 // ts.reset(); 77 // max_flow_test.preflow( MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);75 // max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); 78 76 // std::cout << "elapsed time: " << ts << std::endl; 79 77 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; … … 98 96 { 99 97 std::cout << "physical blocking flow augmentation ..." << std::endl; 100 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);98 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); 101 99 ts.reset(); 102 100 int i=0; … … 106 104 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; 107 105 108 FOR_EACH_LOC(Graph::EdgeIt, e, g) {106 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 109 107 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 110 108 std::cout << "Slackness does not hold!" << std::endl; … … 127 125 { 128 126 std::cout << "onthefly blocking flow augmentation ..." << std::endl; 129 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);127 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); 130 128 ts.reset(); 131 129 int i=0; … … 135 133 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; 136 134 137 FOR_EACH_LOC(Graph::EdgeIt, e, g) {135 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 138 136 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 139 137 std::cout << "Slackness does not hold!" << std::endl; … … 187 185 EdgeIndexMap edge_index_map(g); 188 186 PrimalMap<Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map); 189 Graph::EdgeIt e; 190 for (g.first(e); g.valid(e); g.next(e)) { 187 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 191 188 ColIt col_it=lp.addCol(); 192 189 edge_index_map.set(e, col_it); 193 190 lp.setColBounds(col_it, LPX_DB, 0.0, cap[e]); 194 191 } 195 Graph::NodeIt n; 196 for (g.first(n); g.valid(n); g.next(n)) { 192 for (Graph::NodeIt n(g); n!=INVALID; ++n) { 197 193 if (n!=s) { 198 194 //hurokelek miatt 199 195 Graph::EdgeMap<int> coeffs(g, 0); 200 { 201 Graph::InEdgeIt e; 202 for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]+1); 203 } 204 { 205 Graph::OutEdgeIt e; 206 for (g.first(e, n); g.valid(e); g.next(e)) coeffs.set(e, coeffs[e]1); 207 } 196 for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e) 197 coeffs.set(e, coeffs[e]+1); 198 for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 199 coeffs.set(e, coeffs[e]1); 208 200 if (n==t) { 209 Graph::EdgeIt e; 210 //std::vector< std::pair<ColIt, double> > row; 211 for (g.first(e); g.valid(e); g.next(e)) { 201 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 212 202 if (coeffs[e]!=0) 213 203 lp.setObjCoef(edge_index_map[e], coeffs[e]); … … 215 205 } else { 216 206 RowIt row_it=lp.addRow(); 217 Graph::EdgeIt e;218 207 std::vector< std::pair<ColIt, double> > row; 219 for ( g.first(e); g.valid(e); g.next(e)) {208 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { 220 209 if (coeffs[e]!=0) 221 210 row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
Note: See TracChangeset
for help on using the changeset viewer.