|
marci@82
|
1 |
#include <iostream>
|
|
marci@82
|
2 |
#include <fstream>
|
|
marci@82
|
3 |
|
|
marci@82
|
4 |
#include <list_graph.hh>
|
|
marci@82
|
5 |
#include <dimacs.hh>
|
|
marci@82
|
6 |
#include <preflow_push_max_flow.h>
|
|
marci@87
|
7 |
#include <preflow_push_hl.h>
|
|
marci@82
|
8 |
#include <time_measure.h>
|
|
marci@82
|
9 |
|
|
alpar@921
|
10 |
using namespace lemon;
|
|
marci@82
|
11 |
|
|
marci@82
|
12 |
// Use a DIMACS max flow file as stdin.
|
|
marci@82
|
13 |
// read_dimacs_demo < dimacs_max_flow_file
|
|
marci@82
|
14 |
int main(int, char **) {
|
|
marci@82
|
15 |
typedef ListGraph::NodeIt NodeIt;
|
|
marci@82
|
16 |
typedef ListGraph::EachEdgeIt EachEdgeIt;
|
|
marci@82
|
17 |
|
|
marci@82
|
18 |
ListGraph G;
|
|
marci@82
|
19 |
NodeIt s, t;
|
|
marci@82
|
20 |
ListGraph::EdgeMap<int> cap(G);
|
|
marci@82
|
21 |
readDimacsMaxFlow(std::cin, G, s, t, cap);
|
|
marci@82
|
22 |
|
|
marci@87
|
23 |
{
|
|
marci@87
|
24 |
std::cout << "preflow demo (preflow_push_max_flow by JACINT)..." << std::endl;
|
|
marci@82
|
25 |
//ListGraph::EdgeMap<int> flow(G); //0 flow
|
|
marci@82
|
26 |
|
|
marci@82
|
27 |
double pre_time=currTime();
|
|
marci@82
|
28 |
preflow_push_max_flow<ListGraph, int> max_flow_test(G, s, t, cap);
|
|
marci@82
|
29 |
max_flow_test.run();
|
|
marci@100
|
30 |
ListGraph::NodeMap<bool> cut(G);
|
|
marci@100
|
31 |
max_flow_test.mincut(cut);
|
|
marci@82
|
32 |
int cut_value=0;
|
|
marci@82
|
33 |
for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
|
|
marci@82
|
34 |
if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);
|
|
marci@82
|
35 |
}
|
|
marci@82
|
36 |
double post_time=currTime();
|
|
marci@82
|
37 |
//std::cout << "maximum flow: "<< std::endl;
|
|
marci@82
|
38 |
//for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
|
|
marci@82
|
39 |
// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
|
|
marci@82
|
40 |
//}
|
|
marci@82
|
41 |
//std::cout<<std::endl;
|
|
marci@82
|
42 |
std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
|
|
marci@82
|
43 |
std::cout << "flow value: "<< max_flow_test.maxflow() << std::endl;
|
|
marci@82
|
44 |
std::cout << "cut value: "<< cut_value << std::endl;
|
|
marci@87
|
45 |
}
|
|
marci@87
|
46 |
|
|
marci@87
|
47 |
{
|
|
marci@87
|
48 |
std::cout << "preflow demo (preflow_push_hl by JACINT)..." << std::endl;
|
|
marci@87
|
49 |
//ListGraph::EdgeMap<int> flow(G); //0 flow
|
|
marci@87
|
50 |
|
|
marci@87
|
51 |
double pre_time=currTime();
|
|
marci@87
|
52 |
preflow_push_hl<ListGraph, int> max_flow_test(G, s, t, cap);
|
|
marci@87
|
53 |
max_flow_test.run();
|
|
marci@100
|
54 |
ListGraph::NodeMap<bool> cut(G);
|
|
marci@100
|
55 |
max_flow_test.mincut(cut);
|
|
marci@87
|
56 |
int cut_value=0;
|
|
marci@87
|
57 |
for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
|
|
marci@87
|
58 |
if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);
|
|
marci@87
|
59 |
}
|
|
marci@87
|
60 |
double post_time=currTime();
|
|
marci@87
|
61 |
//std::cout << "maximum flow: "<< std::endl;
|
|
marci@87
|
62 |
//for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
|
|
marci@87
|
63 |
// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
|
|
marci@87
|
64 |
//}
|
|
marci@87
|
65 |
//std::cout<<std::endl;
|
|
marci@87
|
66 |
std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
|
|
marci@87
|
67 |
std::cout << "flow value: "<< max_flow_test.maxflow() << std::endl;
|
|
marci@87
|
68 |
std::cout << "cut value: "<< cut_value << std::endl;
|
|
marci@87
|
69 |
}
|
|
marci@89
|
70 |
|
|
marci@82
|
71 |
|
|
marci@82
|
72 |
return 0;
|
|
marci@82
|
73 |
}
|