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 } |
|