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