4 #include <boost/config.hpp>
5 #include <boost/graph/push_relabel_max_flow.hpp>
6 #include <boost/graph/adjacency_list.hpp>
7 #include <boost/graph/read_dimacs.hpp>
8 #include <boost/graph/graph_utility.hpp>
10 #include <time_measure.h>
12 // Use a DIMACS network flow file as stdin.
13 // max_flow < max_flow.dat
16 using namespace boost;
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> > >
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);
35 Traits::vertex_descriptor s, t;
36 read_dimacs_max_flow(g, capacity, rev, s, t);
38 std::cout << "preflow demo (BOOST)..." << endl;
39 double pre_time=currTime();
40 long flow = push_relabel_max_flow(g, s, t);
41 double post_time=currTime();
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;
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;