COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo_boost.cc @ 409:7ab7f083760a

Last change on this file since 409:7ab7f083760a was 73:1b4a25e49222, checked in by marci, 17 years ago

.

File size: 1.8 KB
Line 
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
14int 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}
Note: See TracBrowser for help on using the repository browser.