Changeset 333:e0a80761dfd9 in lemon0.x
 Timestamp:
 04/15/04 22:19:26 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@452
 Location:
 src/work/marci
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/edmonds_karp_demo.cc
r330 r333 10 10 //#include <graph_wrapper.h> 11 11 #include <preflow.h> 12 #include <for_each_macros.h> 12 13 13 14 using namespace hugo; … … 67 68 Graph::EdgeMap<int> cap(G); 68 69 readDimacsMaxFlow(std::cin, G, s, t, cap); 70 Timer ts; 71 Graph::EdgeMap<int> flow(G); //0 flow 72 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 73 pre_flow_test(G, s, t, cap, flow); 74 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 75 max_flow_test(G, s, t, cap, flow); 69 76 70 77 { 71 78 std::cout << "preflow ..." << std::endl; 72 Graph::EdgeMap<int> flow(G); //0 flow73 74 Timer ts;75 79 ts.reset(); 76 77 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 78 max_flow_test(G, s, t, cap, flow); 79 max_flow_test.run(); 80 // int i=0; 81 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 82 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 83 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 84 // } 85 // std::cout<<std::endl; 86 // ++i; 87 // } 88 89 // std::cout << "maximum flow: "<< std::endl; 90 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 91 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 92 // } 93 // std::cout<<std::endl; 80 pre_flow_test.run(); 94 81 std::cout << "elapsed time: " << ts << std::endl; 95 // std::cout << "number of augmentation phases: " << i << std::endl; 96 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 82 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; 97 83 } 98 84 99 85 { 100 86 std::cout << "physical blocking flow augmentation ..." << std::endl; 101 Graph::EdgeMap<int> flow(G); //0 flow 102 103 Timer ts; 87 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 104 88 ts.reset(); 105 106 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >107 max_flow_test(G, s, t, cap, flow);108 89 int i=0; 109 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 110 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 111 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 112 // } 113 // std::cout<<std::endl; 114 ++i; 115 } 116 117 // std::cout << "maximum flow: "<< std::endl; 118 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 119 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 120 // } 121 // std::cout<<std::endl; 90 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } 122 91 std::cout << "elapsed time: " << ts << std::endl; 123 92 std::cout << "number of augmentation phases: " << i << std::endl; … … 127 96 { 128 97 std::cout << "faster physical blocking flow augmentation ..." << std::endl; 129 Graph::EdgeMap<int> flow(G); //0 flow 130 131 Timer ts; 98 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 132 99 ts.reset(); 133 134 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >135 max_flow_test(G, s, t, cap, flow);136 100 int i=0; 137 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 138 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 139 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 140 // } 141 // std::cout<<std::endl; 142 ++i; 143 } 144 145 // std::cout << "maximum flow: "<< std::endl; 146 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 147 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 148 // } 149 // std::cout<<std::endl; 101 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } 150 102 std::cout << "elapsed time: " << ts << std::endl; 151 103 std::cout << "number of augmentation phases: " << i << std::endl; … … 155 107 { 156 108 std::cout << "onthefly blocking flow augmentation ..." << std::endl; 157 Graph::EdgeMap<int> flow(G); //0 flow 158 159 Timer ts; 109 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 160 110 ts.reset(); 161 162 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >163 max_flow_test(G, s, t, cap, flow);164 111 int i=0; 165 while (max_flow_test.augmentOnBlockingFlow2()) { 166 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 167 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 168 // } 169 // std::cout<<std::endl; 170 ++i; 171 } 172 173 // std::cout << "maximum flow: "<< std::endl; 174 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 175 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 176 // } 177 // std::cout<<std::endl; 112 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } 178 113 std::cout << "elapsed time: " << ts << std::endl; 179 114 std::cout << "number of augmentation phases: " << i << std::endl; … … 183 118 { 184 119 std::cout << "onthefly shortest path augmentation ..." << std::endl; 185 Graph::EdgeMap<int> flow(G); //0 flow 186 187 Timer ts; 120 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); 188 121 ts.reset(); 189 190 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >191 max_flow_test(G, s, t, cap, flow);192 122 int i=0; 193 while (max_flow_test.augmentOnShortestPath()) { 194 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 195 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 196 // } 197 // std::cout<<std::endl; 198 ++i; 199 } 200 201 // std::cout << "maximum flow: "<< std::endl; 202 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 203 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 204 // } 205 // std::cout<<std::endl; 123 while (max_flow_test.augmentOnShortestPath()) { ++i; } 206 124 std::cout << "elapsed time: " << ts << std::endl; 207 125 std::cout << "number of augmentation phases: " << i << std::endl; 
src/work/marci/for_each_macros.h
r330 r333 44 44 //FIXME ezt hogy a gorcsbe birja levezetni. Csak ugy leveszi a constot?? 45 45 template<typename It, typename Graph> 46 It loopFirst(const It& i, const Graph& g) {47 It e =i; g.first(e); return e;46 It loopFirst(const It&, const Graph& g) { 47 It e; g.first(e); return e; 48 48 } 49 49 50 50 template<typename It, typename Graph, typename Node> 51 It loopFirst(const It& i, const Graph& g, const Node& v) {52 It e =i; g.first(e, v); return e;51 It loopFirst(const It&, const Graph& g, const Node& v) { 52 It e; g.first(e, v); return e; 53 53 } 54 54 … … 72 72 // } 73 73 74 #define FOR_EACH_LOC(Ittype, e, g) for(Ittype (e)=loopFirst(Ittype(), (g)); (g).valid((e)); (g).next((e)))75 #define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype (e)=loopFirst(Ittype(), (g), (v)); (g).valid((e)); (g).next((e)))74 #define FOR_EACH_LOC(Ittype, e, g) for(Ittype e=loopFirst(Ittype(), (g)); (g).valid(e); (g).next(e)) 75 #define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype e=loopFirst(Ittype(), (g), (v)); (g).valid(e); (g).next(e)) 76 76 77 // #define FOR_EACH_EDGE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))77 // #define FOR_EACH_EDGE_LOC(e, g) ezt nem tom hogy kell for((g).first((e)); (g).valid((e)); (g).next((e))) 78 78 // #define FOR_EACH_NODE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e))) 79 79 // #define FOR_EACH_INEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e))) 
src/work/marci/graph_concept.h
r332 r333 365 365 }; 366 366 367 /// An empty graph class which provides a function to get the number 368 /// of its nodes. 367 /// An empty nodeeraseable graph class. 368 369 /// An empty graph class which provides a function to 370 /// delete any of its nodes. 371 class NodeEraseableGraphSkeleturo : public GraphSkeleturo 372 { 373 public: 374 /// Deletes a node. 375 void erase(Node n) {} 376 }; 377 378 /// An empty edgeeraseable graph class. 379 380 /// An empty graph class which provides a function to delete any 381 /// of its edges. 382 class EdgeEraseableGraphSkeleturo : public GraphSkeleturo 383 { 384 public: 385 /// Deletes a node. 386 void erase(Edge n) {} 387 }; 388 389 /// An empty graph class which provides a function to get the number of its nodes. 369 390 370 391 /// This graph class provides a function for getting the number of its … … 374 395 /// the implementation can be circumstantial, that is why this composes a 375 396 /// separate concept. 376 class NodeCountingGraphSkeleturo 397 class NodeCountingGraphSkeleturo : public GraphSkeleturo 377 398 { 378 399 public: … … 381 402 }; 382 403 383 /// An empty graph class which provides a function to get the number of its 384 /// edges. 404 /// An empty graph class which provides a function to get the number of its edges. 385 405 386 406 /// This graph class provides a function for getting the number of its … … 390 410 /// the implementation can be circumstantial, that is why this composes a 391 411 /// separate concept. 392 class EdgeCountingGraphSkeleturo 412 class EdgeCountingGraphSkeleturo : public GraphSkeleturo 393 413 { 394 414 public:
Note: See TracChangeset
for help on using the changeset viewer.