Changeset 334:63703ea7d02f in lemon0.x for src/work/marci/lg_vs_sg.cc
 Timestamp:
 04/15/04 22:50:03 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@453
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/lg_vs_sg.cc
r174 r334 8 8 #include <dimacs.h> 9 9 #include <edmonds_karp.h> 10 #include <preflow.h> 10 11 #include <time_measure.h> 11 #include < graph_wrapper.h>12 #include <for_each_macros.h> 12 13 13 14 using namespace hugo; … … 32 33 readDimacsMaxFlow(ins, G, s, t, cap); 33 34 35 Timer ts; 36 Graph::EdgeMap<int> flow(G); //0 flow 37 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 38 pre_flow_test(G, s, t, cap, flow); 39 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 40 max_flow_test(G, s, t, cap, flow); 41 42 std::cout << "ListGraph ..." << std::endl; 43 34 44 { 35 std::cout << "ListGraph..." << std::endl; 36 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; 37 Graph::EdgeMap<int> flow(G); //0 flow 45 std::cout << "preflow ..." << std::endl; 46 ts.reset(); 47 pre_flow_test.run(); 48 std::cout << "elapsed time: " << ts << std::endl; 49 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 50 } 38 51 39 Timer ts; 52 { 53 std::cout << "physical blocking flow augmentation ..." << std::endl; 54 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 40 55 ts.reset(); 41 42 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);43 56 int i=0; 44 57 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 45 46 58 std::cout << "elapsed time: " << ts << std::endl; 47 59 std::cout << "number of augmentation phases: " << i << std::endl; … … 50 62 51 63 { 52 std::cout << "edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl; 53 Graph::EdgeMap<int> flow(G); //0 flow 54 55 Timer ts; 64 std::cout << "faster physical blocking flow augmentation ..." << std::endl; 65 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 56 66 ts.reset(); 57 58 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);59 67 int i=0; 60 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 61 68 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 62 69 std::cout << "elapsed time: " << ts << std::endl; 63 70 std::cout << "number of augmentation phases: " << i << std::endl; … … 66 73 67 74 { 68 std::cout << "edmonds karp demo (onthefly shortest path augmentation)..." << std::endl; 69 Graph::EdgeMap<int> flow(G); //0 flow 75 std::cout << "onthefly blocking flow augmentation ..." << std::endl; 76 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 77 ts.reset(); 78 int i=0; 79 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 80 std::cout << "elapsed time: " << ts << std::endl; 81 std::cout << "number of augmentation phases: " << i << std::endl; 82 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 83 } 70 84 71 Timer ts; 85 { 86 std::cout << "onthefly shortest path augmentation ..." << std::endl; 87 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 72 88 ts.reset(); 73 74 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);75 89 int i=0; 76 90 while (max_flow_test.augmentOnShortestPath()) { ++i; } 77 78 91 std::cout << "elapsed time: " << ts << std::endl; 79 92 std::cout << "number of augmentation phases: " << i << std::endl; … … 94 107 readDimacsMaxFlow(ins, G, s, t, cap); 95 108 109 Timer ts; 110 Graph::EdgeMap<int> flow(G); //0 flow 111 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 112 pre_flow_test(G, s, t, cap, flow); 113 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 114 max_flow_test(G, s, t, cap, flow); 115 116 std::cout << "SmatrGraph ..." << std::endl; 117 96 118 { 97 std::cout << "SmartGraph..." << std::endl; 98 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; 99 Graph::EdgeMap<int> flow(G); //0 flow 119 std::cout << "preflow ..." << std::endl; 120 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 121 ts.reset(); 122 pre_flow_test.run(); 123 std::cout << "elapsed time: " << ts << std::endl; 124 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 125 } 100 126 101 Timer ts; 127 { 128 std::cout << "physical blocking flow augmentation ..." << std::endl; 129 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 102 130 ts.reset(); 103 104 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);105 131 int i=0; 106 132 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 107 108 133 std::cout << "elapsed time: " << ts << std::endl; 109 134 std::cout << "number of augmentation phases: " << i << std::endl; … … 112 137 113 138 { 114 std::cout << "edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl; 115 Graph::EdgeMap<int> flow(G); //0 flow 116 117 Timer ts; 139 std::cout << "faster physical blocking flow augmentation ..." << std::endl; 140 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 118 141 ts.reset(); 119 120 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);121 142 int i=0; 122 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 123 143 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 124 144 std::cout << "elapsed time: " << ts << std::endl; 125 145 std::cout << "number of augmentation phases: " << i << std::endl; … … 128 148 129 149 { 130 std::cout << "edmonds karp demo (onthefly shortest path augmentation)..." << std::endl; 131 Graph::EdgeMap<int> flow(G); //0 flow 150 std::cout << "onthefly blocking flow augmentation ..." << std::endl; 151 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 152 ts.reset(); 153 int i=0; 154 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 155 std::cout << "elapsed time: " << ts << std::endl; 156 std::cout << "number of augmentation phases: " << i << std::endl; 157 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 158 } 132 159 133 Timer ts; 160 { 161 std::cout << "onthefly shortest path augmentation ..." << std::endl; 162 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 134 163 ts.reset(); 135 136 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);137 164 int i=0; 138 165 while (max_flow_test.augmentOnShortestPath()) { ++i; } 139 140 166 std::cout << "elapsed time: " << ts << std::endl; 141 167 std::cout << "number of augmentation phases: " << i << std::endl; … … 144 170 } 145 171 172 173 174 146 175 return 0; 147 176 }
Note: See TracChangeset
for help on using the changeset viewer.