1 #include <iostream> |
|
2 #include <fstream> |
|
3 |
|
4 #include "smart_graph.h" |
|
5 |
|
6 #include "../list_graph.hh" |
|
7 #include "../marci/dimacs.hh" |
|
8 #include "f_ed_ka.h" |
|
9 #include "../marci/time_measure.h" |
|
10 |
|
11 using namespace lemon; |
|
12 |
|
13 // Use a DIMACS max flow file as stdin. |
|
14 // read_dimacs_demo < dimacs_max_flow_file |
|
15 |
|
16 int main(int, char **) { |
|
17 typedef SmartGraph Graph; |
|
18 //typedef ListGraph Graph; |
|
19 |
|
20 typedef Graph::NodeIt NodeIt; |
|
21 typedef Graph::EachNodeIt EachNodeIt; |
|
22 typedef Graph::EachEdgeIt EachEdgeIt; |
|
23 |
|
24 Graph G; |
|
25 NodeIt s, t; |
|
26 Timer ts; |
|
27 Graph::DynEdgeMap<int> cap(G); |
|
28 readDimacsMaxFlow(std::cin, G, s, t, cap); |
|
29 |
|
30 std::cout << "loading time: " << ts << std::endl; |
|
31 ts.reset(); |
|
32 std::cout << "edmonds karp demo..." << std::endl; |
|
33 Graph::DynEdgeMap<int> flow(G); //0 flow |
|
34 |
|
35 int ret; |
|
36 // double pre_time=currTime(); |
|
37 |
|
38 ret = maxFlow(G,flow,cap,s,t); |
|
39 // double post_time=currTime(); |
|
40 std::cout << "running time: " << ts << std::endl; |
|
41 |
|
42 //std::cout << "maximum flow: "<< std::endl; |
|
43 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
|
44 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
45 //} |
|
46 //std::cout<<std::endl; |
|
47 // std::cout<<"elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
|
48 std::cout << "flow value: "<< ret << std::endl; |
|
49 |
|
50 return 0; |
|
51 } |
|