marci@73: #include <iostream> marci@73: #include <string> marci@73: marci@73: #include <boost/config.hpp> marci@73: #include <boost/graph/push_relabel_max_flow.hpp> marci@73: #include <boost/graph/adjacency_list.hpp> marci@73: #include <boost/graph/read_dimacs.hpp> marci@73: #include <boost/graph/graph_utility.hpp> marci@73: marci@73: #include <time_measure.h> marci@73: marci@73: // Use a DIMACS network flow file as stdin. marci@73: // max_flow < max_flow.dat marci@73: int main() marci@73: { marci@73: using namespace boost; marci@73: marci@73: typedef adjacency_list_traits<vecS, vecS, directedS> Traits; marci@73: typedef adjacency_list<listS, vecS, directedS, marci@73: property<vertex_name_t, std::string>, marci@73: property<edge_capacity_t, long, marci@73: property<edge_residual_capacity_t, long, marci@73: property<edge_reverse_t, Traits::edge_descriptor> > > marci@73: > Graph; marci@73: marci@73: Graph g; marci@73: marci@73: property_map<Graph, edge_capacity_t>::type marci@73: capacity = get(edge_capacity, g); marci@73: property_map<Graph, edge_reverse_t>::type marci@73: rev = get(edge_reverse, g); marci@73: property_map<Graph, edge_residual_capacity_t>::type marci@73: residual_capacity = get(edge_residual_capacity, g); marci@73: marci@73: Traits::vertex_descriptor s, t; marci@73: read_dimacs_max_flow(g, capacity, rev, s, t); marci@73: marci@73: std::cout << "preflow demo (BOOST)..." << endl; marci@73: double pre_time=currTime(); marci@73: long flow = push_relabel_max_flow(g, s, t); marci@73: double post_time=currTime(); marci@73: marci@73: //std::cout << "maximum flow: " << std::endl; marci@73: //graph_traits<Graph>::vertex_iterator u_iter, u_end; marci@73: //graph_traits<Graph>::out_edge_iterator ei, e_end; marci@73: //for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) marci@73: // for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) marci@73: // if (capacity[*ei] > 0) marci@73: // std::cout << "f " << *u_iter << " " << target(*ei, g) << " " marci@73: // << (capacity[*ei] - residual_capacity[*ei]) << std::endl; marci@73: // marci@73: //std::cout << std::endl; marci@73: std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; marci@73: std::cout << "flow value: " << flow << std::endl; marci@73: marci@73: return 0; marci@73: }