[159] | 1 | #include <iostream> |
---|
| 2 | #include <vector> |
---|
| 3 | #include <string> |
---|
| 4 | |
---|
| 5 | #include <list_graph.hh> |
---|
| 6 | #include <dijkstra.h> |
---|
| 7 | |
---|
| 8 | using namespace hugo; |
---|
| 9 | |
---|
| 10 | int main (int, char*[]) |
---|
| 11 | { |
---|
| 12 | typedef ListGraph::NodeIt NodeIt; |
---|
| 13 | typedef ListGraph::EdgeIt EdgeIt; |
---|
| 14 | typedef ListGraph::EachNodeIt EachNodeIt; |
---|
| 15 | typedef ListGraph::EachEdgeIt EachEdgeIt; |
---|
| 16 | typedef ListGraph::OutEdgeIt OutEdgeIt; |
---|
| 17 | typedef ListGraph::InEdgeIt InEdgeIt; |
---|
| 18 | |
---|
| 19 | ListGraph flow_test; |
---|
| 20 | |
---|
| 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"); |
---|
| 38 | |
---|
| 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)<< " "; |
---|
| 201 | } |
---|
| 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 | |
---|
| 232 | return 0; |
---|
| 233 | } |
---|
| 234 | |
---|
| 235 | |
---|
| 236 | |
---|
| 237 | |
---|
| 238 | |
---|
| 239 | |
---|
| 240 | |
---|
| 241 | |
---|
| 242 | |
---|