Changeset 220:7deda4d6a07a in lemon-0.x for src/work/jacint/preflow.cc
- Timestamp:
- 03/20/04 21:06:23 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@316
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/preflow.cc
r211 r220 2 2 #include <fstream> 3 3 4 #include <smart_graph.h> 4 5 #include <list_graph.h> 5 6 #include <dimacs.h> … … 12 13 // read_dimacs_demo < dimacs_max_flow_file 13 14 int main(int, char **) { 14 typedef ListGraph::Node Node;15 typedef ListGraph::EdgeIt EdgeIt;15 typedef SmartGraph::Node Node; 16 typedef SmartGraph::EdgeIt EdgeIt; 16 17 17 ListGraph G;18 SmartGraph G; 18 19 Node s, t; 19 ListGraph::EdgeMap<int> cap(G);20 SmartGraph::EdgeMap<int> cap(G); 20 21 readDimacsMaxFlow(std::cin, G, s, t, cap); 21 22 … … 25 26 26 27 for ( int i=1; i!=11; ++i ) { 27 ListGraph::EdgeMap<int> flow(G);28 SmartGraph::EdgeMap<int> flow(G); 28 29 double pre_time=currTime(); 29 Preflow< ListGraph, int> max_flow_test(G, s, t, cap, flow);30 Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow); 30 31 max_flow_test.run(); 31 32 double post_time=currTime(); … … 33 34 } 34 35 35 ListGraph::EdgeMap<int> flow(G);36 Preflow< ListGraph, int> max_flow_test(G, s, t, cap, flow);36 SmartGraph::EdgeMap<int> flow(G); 37 Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow); 37 38 max_flow_test.run(); 38 39 39 ListGraph::NodeMap<bool> cut(G);40 SmartGraph::NodeMap<bool> cut(G); 40 41 max_flow_test.minCut(cut); 41 42 int min_cut_value=0; 42 43 EdgeIt e; 43 44 for(G.first(e); G.valid(e); G.next(e)) { 44 if (cut .get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);45 if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=cap[e]; 45 46 } 46 47 47 ListGraph::NodeMap<bool> cut1(G);48 SmartGraph::NodeMap<bool> cut1(G); 48 49 max_flow_test.minMinCut(cut1); 49 50 int min_min_cut_value=0; 50 51 for(G.first(e); G.valid(e); G.next(e)) { 51 if (cut .get(G.tail(e)) && !cut.get(G.head(e)))52 min_min_cut_value+=cap .get(e);52 if (cut[G.tail(e)] && !cut[G.head(e)]) 53 min_min_cut_value+=cap[e]; 53 54 } 54 55 55 ListGraph::NodeMap<bool> cut2(G);56 SmartGraph::NodeMap<bool> cut2(G); 56 57 max_flow_test.maxMinCut(cut2); 57 58 int max_min_cut_value=0; 58 59 for(G.first(e); G.valid(e); G.next(e)) { 59 if (cut2 .get(G.tail(e)) && !cut2.get(G.head(e)))60 max_min_cut_value+=cap .get(e);60 if (cut2[G.tail(e)] && !cut2[G.head(e)]) 61 max_min_cut_value+=cap[e]; 61 62 } 62 63
Note: See TracChangeset
for help on using the changeset viewer.