[73] | 1 | #include <iostream> |
---|

| 2 | #include <string> |
---|

| 3 | |
---|

| 4 | #include <boost/config.hpp> |
---|

| 5 | #include <boost/graph/edmunds_karp_max_flow.hpp> |
---|

| 6 | #include <boost/graph/adjacency_list.hpp> |
---|

| 7 | #include <boost/graph/read_dimacs.hpp> |
---|

| 8 | #include <boost/graph/graph_utility.hpp> |
---|

| 9 | |
---|

| 10 | #include <time_measure.h> |
---|

| 11 | |
---|

| 12 | // Use a DIMACS network flow file as stdin. |
---|

| 13 | // max_flow < max_flow.dat |
---|

| 14 | int main() |
---|

| 15 | { |
---|

| 16 | using namespace boost; |
---|

| 17 | |
---|

| 18 | typedef adjacency_list_traits<vecS, vecS, directedS> Traits; |
---|

| 19 | typedef adjacency_list<listS, vecS, directedS, |
---|

| 20 | property<vertex_name_t, std::string>, |
---|

| 21 | property<edge_capacity_t, long, |
---|

| 22 | property<edge_residual_capacity_t, long, |
---|

| 23 | property<edge_reverse_t, Traits::edge_descriptor> > > |
---|

| 24 | > Graph; |
---|

| 25 | |
---|

| 26 | Graph g; |
---|

| 27 | |
---|

| 28 | property_map<Graph, edge_capacity_t>::type |
---|

| 29 | capacity = get(edge_capacity, g); |
---|

| 30 | property_map<Graph, edge_reverse_t>::type |
---|

| 31 | rev = get(edge_reverse, g); |
---|

| 32 | property_map<Graph, edge_residual_capacity_t>::type |
---|

| 33 | residual_capacity = get(edge_residual_capacity, g); |
---|

| 34 | |
---|

| 35 | Traits::vertex_descriptor s, t; |
---|

| 36 | read_dimacs_max_flow(g, capacity, rev, s, t); |
---|

| 37 | |
---|

| 38 | std::cout << "edmonds karp demo (BOOST)..." << endl; |
---|

| 39 | double pre_time=currTime(); |
---|

| 40 | long flow = edmunds_karp_max_flow(g, s, t); |
---|

| 41 | double post_time=currTime(); |
---|

| 42 | |
---|

| 43 | //std::cout << "maximum flow: " << std::endl; |
---|

| 44 | //graph_traits<Graph>::vertex_iterator u_iter, u_end; |
---|

| 45 | //graph_traits<Graph>::out_edge_iterator ei, e_end; |
---|

| 46 | //for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) |
---|

| 47 | // for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) |
---|

| 48 | // if (capacity[*ei] > 0) |
---|

| 49 | // std::cout << "f " << *u_iter << " " << target(*ei, g) << " " |
---|

| 50 | // << (capacity[*ei] - residual_capacity[*ei]) << std::endl; |
---|

| 51 | // |
---|

| 52 | //std::cout << std::endl; |
---|

| 53 | std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
---|

| 54 | std::cout << "flow value: " << flow << std::endl; |
---|

| 55 | |
---|

| 56 | return 0; |
---|

| 57 | } |
---|