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