Changeset 160:f1a7005e9dff in lemon-0.x for src
- Timestamp:
- 03/09/04 16:53:19 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@226
- Location:
- src/work/jacint
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/dijkstra.cc
r159 r160 1 1 #include <iostream> 2 #include <vector> 3 #include <string> 2 #include <fstream> 4 3 5 4 #include <list_graph.hh> 5 #include <dimacs.hh> 6 6 #include <dijkstra.h> 7 #include <time_measure.h> 7 8 8 9 using namespace hugo; 9 10 10 int main (int, char*[]) 11 { 11 int main(int, char **) { 12 12 typedef ListGraph::NodeIt NodeIt; 13 typedef ListGraph::EdgeIt EdgeIt;14 typedef ListGraph::EachNodeIt EachNodeIt;15 13 typedef ListGraph::EachEdgeIt EachEdgeIt; 16 typedef ListGraph::OutEdgeIt OutEdgeIt; 17 typedef ListGraph::InEdgeIt InEdgeIt; 14 15 ListGraph G; 16 NodeIt s, t; 17 ListGraph::EdgeMap<int> cap(G); 18 readDimacsMaxFlow(std::cin, G, s, t, cap); 19 20 std::cout << "dijkstra demo ..." << std::endl; 18 21 19 ListGraph flow_test; 22 double pre_time=currTime(); 23 Dijkstra<ListGraph, int> dijkstra_test(G, s, cap); 24 double post_time=currTime(); 25 26 std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl; 20 27 21 /* //Ahuja könyv példája, maxflowvalue=13 22 NodeIt s=flow_test.addNode(); 23 NodeIt v1=flow_test.addNode(); 24 NodeIt v2=flow_test.addNode(); 25 NodeIt v3=flow_test.addNode(); 26 NodeIt v4=flow_test.addNode(); 27 NodeIt v5=flow_test.addNode(); 28 NodeIt t=flow_test.addNode(); 29 30 ListGraph::NodeMap<std::string> Node_name(flow_test); 31 Node_name.set(s, "s"); 32 Node_name.set(v1, "v1"); 33 Node_name.set(v2, "v2"); 34 Node_name.set(v3, "v3"); 35 Node_name.set(v4, "v4"); 36 Node_name.set(v5, "v5"); 37 Node_name.set(t, "t"); 28 EachEdgeIt e; 38 29 39 EdgeIt s_v1=flow_test.addEdge(s, v1); 40 EdgeIt s_v2=flow_test.addEdge(s, v2); 41 EdgeIt s_v3=flow_test.addEdge(s, v3); 42 EdgeIt v2_v4=flow_test.addEdge(v2, v4); 43 EdgeIt v2_v5=flow_test.addEdge(v2, v5); 44 EdgeIt v3_v5=flow_test.addEdge(v3, v5); 45 EdgeIt v4_t=flow_test.addEdge(v4, t); 46 EdgeIt v5_t=flow_test.addEdge(v5, t); 47 EdgeIt v2_s=flow_test.addEdge(v2, s); 48 49 ListGraph::EdgeMap<int> cap(flow_test); 50 cap.set(s_v1, 0); 51 cap.set(s_v2, 10); 52 cap.set(s_v3, 10); 53 cap.set(v2_v4, 5); 54 cap.set(v2_v5, 8); 55 cap.set(v3_v5, 5); 56 cap.set(v4_t, 8); 57 cap.set(v5_t, 8); 58 cap.set(v2_s, 0); 59 */ 60 61 62 //Marci példája, maxflowvalue=23 63 NodeIt s=flow_test.addNode(); 64 NodeIt v1=flow_test.addNode(); 65 NodeIt v2=flow_test.addNode(); 66 NodeIt v3=flow_test.addNode(); 67 NodeIt v4=flow_test.addNode(); 68 NodeIt t=flow_test.addNode(); 69 NodeIt z=flow_test.addNode(); 70 71 72 ListGraph::NodeMap<std::string> Node_name(flow_test); 73 Node_name.set(s, "s"); 74 Node_name.set(v1, "v1"); 75 Node_name.set(v2, "v2"); 76 Node_name.set(v3, "v3"); 77 Node_name.set(v4, "v4"); 78 Node_name.set(t, "t"); 79 Node_name.set(z, "z"); 80 81 EdgeIt s_v1=flow_test.addEdge(s, v1); 82 EdgeIt s_v2=flow_test.addEdge(s, v2); 83 EdgeIt v1_v2=flow_test.addEdge(v1, v2); 84 EdgeIt v2_v1=flow_test.addEdge(v2, v1); 85 EdgeIt v1_v3=flow_test.addEdge(v1, v3); 86 EdgeIt v3_v2=flow_test.addEdge(v3, v2); 87 EdgeIt v2_v4=flow_test.addEdge(v2, v4); 88 EdgeIt v4_v3=flow_test.addEdge(v4, v3); 89 EdgeIt v3_t=flow_test.addEdge(v3, t); 90 EdgeIt v4_t=flow_test.addEdge(v4, t); 91 EdgeIt v3_v3=flow_test.addEdge(v3, v3); 92 EdgeIt s_z=flow_test.addEdge(s, z); 93 // EdgeIt v2_s=flow_test.addEdge(v2, s); 94 95 96 97 ListGraph::EdgeMap<int> cap(flow_test); 98 cap.set(s_v1, 16); 99 cap.set(s_v2, 13); 100 cap.set(v1_v2, 10); 101 cap.set(v2_v1, 4); 102 cap.set(v1_v3, 12); 103 cap.set(v3_v2, 9); 104 cap.set(v2_v4, 14); 105 cap.set(v4_v3, 7); 106 cap.set(v3_t, 20); 107 cap.set(v4_t, 4); 108 cap.set(v3_v3, 4); 109 cap.set(s_z, 4); 110 // cap.set(v2_s, 0); 111 112 113 114 //pelda 3, maxflowvalue=4 115 /* NodeIt s=flow_test.addNode(); 116 NodeIt v1=flow_test.addNode(); 117 NodeIt v2=flow_test.addNode(); 118 NodeIt t=flow_test.addNode(); 119 NodeIt w=flow_test.addNode(); 120 121 NodeMap<ListGraph, std::string> Node_name(flow_test); 122 Node_name.set(s, "s"); 123 Node_name.set(v1, "v1"); 124 Node_name.set(v2, "v2"); 125 Node_name.set(t, "t"); 126 Node_name.set(w, "w"); 127 128 EdgeIt s_v1=flow_test.addEdge(s, v1); 129 EdgeIt v1_v2=flow_test.addEdge(v1, v2); 130 EdgeIt v2_t=flow_test.addEdge(v2, t); 131 EdgeIt v1_v1=flow_test.addEdge(v1, v1); 132 EdgeIt s_w=flow_test.addEdge(s, w); 133 134 135 EdgeMap<ListGraph, int> cap(flow_test); 136 137 cap.set(s_v1, 16); 138 cap.set(v1_v2, 10); 139 cap.set(v2_t, 4); 140 cap.set(v1_v1, 3); 141 cap.set(s_w, 5); 142 */ 143 144 145 146 /* 147 std::cout << "Testing reverse_bfs..." << std::endl; 148 149 reverse_bfs<ListGraph> bfs_test(flow_test, t); 150 151 bfs_test.run(); 152 153 for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { 154 std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl; 155 } 156 157 */ 158 159 160 /* 161 std::cout << "Testing preflow_push_hl..." << std::endl; 162 163 preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap); 164 165 preflow_push_test.run(); 166 167 std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl; 168 169 std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl; 170 171 ListGraph::EdgeMap<int> flow=preflow_push_test.allflow(); 172 for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) { 173 std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl; 174 } 175 176 std::cout << "A minimum cut: " <<std::endl; 177 ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut(); 178 179 for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { 180 if (mincut.get(v)) std::cout <<Node_name.get(v)<< " "; 181 } 182 183 std::cout<<"\n\n"<<std::endl; 184 185 186 187 188 std::cout << "Testing preflow_push_max_flow..." << std::endl; 189 190 preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap); 191 192 max_flow_test.run(); 193 194 std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl; 195 196 std::cout << "A minimum cut: " <<std::endl; 197 ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut(); 198 199 for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { 200 if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " "; 30 for ( G.getFirst(e) ; G.valid(e); G.next(e) ) { 31 NodeIt u=G.tail(e); 32 NodeIt v=G.head(e); 33 assert ( dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap.get(e) ); 201 34 } 202 203 std::cout << std::endl <<std::endl;204 */205 206 207 std::cout << "Testing dijkstra..." << std::endl;208 209 NodeIt root=s;210 211 Dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);212 213 dijkstra_test.run();214 215 EachNodeIt w;216 217 for ( flow_test.getFirst(w); flow_test.valid(w) ; flow_test.next(w) ) {218 if (dijkstra_test.reach(w)) {219 std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);220 if (dijkstra_test.pred(w).valid()) {221 std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;222 } else {223 std::cout <<", this is the root."<<std::endl; }224 225 } else {226 std::cout << w << " is not reachable from " << root <<std::endl;227 }228 }229 230 231 35 232 36 return 0; 233 37 } 234 235 236 237 238 239 240 241 242 -
src/work/jacint/dijkstra.h
r159 r160 82 82 OutEdgeIt e; 83 83 for( G.getFirst(e,v); G.valid(e); G.next(e)) { 84 NodeIt w=G. head(e);84 NodeIt w=G.bNode(e); 85 85 86 86 if ( !scanned.get(w) ) {
Note: See TracChangeset
for help on using the changeset viewer.