[494] | 1 | #include <iostream> |
---|
| 2 | #include <vector> |
---|
| 3 | #include <string> |
---|
| 4 | |
---|
| 5 | #include <list_graph.h> |
---|
| 6 | #include <edmonds.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::Node Node; |
---|
| 15 | typedef ListGraph::Edge Edge; |
---|
| 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 | Node s=flow_test.addNode(); |
---|
| 23 | Node v1=flow_test.addNode(); |
---|
| 24 | Node v2=flow_test.addNode(); |
---|
| 25 | Node v3=flow_test.addNode(); |
---|
| 26 | Node v4=flow_test.addNode(); |
---|
| 27 | Node v5=flow_test.addNode(); |
---|
| 28 | Node 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 | Edge s_v1=flow_test.addEdge(s, v1); |
---|
| 40 | Edge s_v2=flow_test.addEdge(s, v2); |
---|
| 41 | Edge s_v3=flow_test.addEdge(s, v3); |
---|
| 42 | Edge v2_v4=flow_test.addEdge(v2, v4); |
---|
| 43 | Edge v2_v5=flow_test.addEdge(v2, v5); |
---|
| 44 | Edge v3_v5=flow_test.addEdge(v3, v5); |
---|
| 45 | Edge v4_t=flow_test.addEdge(v4, t); |
---|
| 46 | Edge v5_t=flow_test.addEdge(v5, t); |
---|
| 47 | Edge 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 | Edmonds<ListGraph> edmonds(flow_test); |
---|
| 62 | std::vector<Edge> matching(0); |
---|
| 63 | std::cout<< edmonds.run(matching); |
---|
| 64 | |
---|
| 65 | |
---|
| 66 | /* //Marci példája, maxflowvalue=23 |
---|
| 67 | Node s=flow_test.addNode(); |
---|
| 68 | Node v1=flow_test.addNode(); |
---|
| 69 | Node v2=flow_test.addNode(); |
---|
| 70 | Node v3=flow_test.addNode(); |
---|
| 71 | Node v4=flow_test.addNode(); |
---|
| 72 | Node t=flow_test.addNode(); |
---|
| 73 | Node z=flow_test.addNode(); |
---|
| 74 | |
---|
| 75 | |
---|
| 76 | ListGraph::NodeMap<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(z, "z"); |
---|
| 84 | |
---|
| 85 | Edge s_v1=flow_test.addEdge(s, v1); |
---|
| 86 | Edge s_v2=flow_test.addEdge(s, v2); |
---|
| 87 | Edge v1_v2=flow_test.addEdge(v1, v2); |
---|
| 88 | Edge v2_v1=flow_test.addEdge(v2, v1); |
---|
| 89 | Edge v1_v3=flow_test.addEdge(v1, v3); |
---|
| 90 | Edge v3_v2=flow_test.addEdge(v3, v2); |
---|
| 91 | Edge v2_v4=flow_test.addEdge(v2, v4); |
---|
| 92 | Edge v4_v3=flow_test.addEdge(v4, v3); |
---|
| 93 | Edge v3_t=flow_test.addEdge(v3, t); |
---|
| 94 | Edge v4_t=flow_test.addEdge(v4, t); |
---|
| 95 | Edge v3_v3=flow_test.addEdge(v3, v3); |
---|
| 96 | Edge s_z=flow_test.addEdge(s, z); |
---|
| 97 | // Edge v2_s=flow_test.addEdge(v2, s); |
---|
| 98 | |
---|
| 99 | |
---|
| 100 | |
---|
| 101 | ListGraph::EdgeMap<int> cap(flow_test); |
---|
| 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_z, 4); |
---|
| 114 | // cap.set(v2_s, 0); |
---|
| 115 | |
---|
| 116 | */ |
---|
| 117 | |
---|
| 118 | //pelda 3, maxflowvalue=4 |
---|
| 119 | /* Node s=flow_test.addNode(); |
---|
| 120 | Node v1=flow_test.addNode(); |
---|
| 121 | Node v2=flow_test.addNode(); |
---|
| 122 | Node t=flow_test.addNode(); |
---|
| 123 | Node w=flow_test.addNode(); |
---|
| 124 | |
---|
| 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"); |
---|
| 131 | |
---|
| 132 | Edge s_v1=flow_test.addEdge(s, v1); |
---|
| 133 | Edge v1_v2=flow_test.addEdge(v1, v2); |
---|
| 134 | Edge v2_t=flow_test.addEdge(v2, t); |
---|
| 135 | Edge v1_v1=flow_test.addEdge(v1, v1); |
---|
| 136 | Edge s_w=flow_test.addEdge(s, w); |
---|
| 137 | |
---|
| 138 | |
---|
| 139 | EdgeMap<ListGraph, int> cap(flow_test); |
---|
| 140 | |
---|
| 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); |
---|
| 146 | */ |
---|
| 147 | |
---|
| 148 | |
---|
| 149 | |
---|
| 150 | /* |
---|
| 151 | std::cout << "Testing reverse_bfs..." << std::endl; |
---|
| 152 | |
---|
| 153 | reverse_bfs<ListGraph> bfs_test(flow_test, t); |
---|
| 154 | |
---|
| 155 | bfs_test.run(); |
---|
| 156 | |
---|
| 157 | for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { |
---|
| 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 | |
---|
| 167 | preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap); |
---|
| 168 | |
---|
| 169 | preflow_push_test.run(); |
---|
| 170 | |
---|
| 171 | std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl; |
---|
| 172 | |
---|
| 173 | std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl; |
---|
| 174 | |
---|
| 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; |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | std::cout << "A minimum cut: " <<std::endl; |
---|
| 181 | ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut(); |
---|
| 182 | |
---|
| 183 | for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { |
---|
| 184 | if (mincut.get(v)) std::cout <<Node_name.get(v)<< " "; |
---|
| 185 | } |
---|
| 186 | |
---|
| 187 | std::cout<<"\n\n"<<std::endl; |
---|
| 188 | |
---|
| 189 | |
---|
| 190 | |
---|
| 191 | |
---|
| 192 | std::cout << "Testing preflow_push_max_flow..." << std::endl; |
---|
| 193 | |
---|
| 194 | preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap); |
---|
| 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; |
---|
| 201 | ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut(); |
---|
| 202 | |
---|
| 203 | for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { |
---|
| 204 | if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " "; |
---|
| 205 | } |
---|
| 206 | |
---|
| 207 | std::cout << std::endl <<std::endl; |
---|
| 208 | */ |
---|
| 209 | |
---|
| 210 | return 0; |
---|
| 211 | } |
---|
| 212 | |
---|
| 213 | |
---|
| 214 | |
---|
| 215 | |
---|
| 216 | |
---|
| 217 | |
---|
| 218 | |
---|
| 219 | |
---|
| 220 | |
---|