1 | #include <iostream> |
---|

2 | #include <fstream> |
---|

3 | |
---|

4 | #include <list_graph.hh> |
---|

5 | #include <dimacs.hh> |
---|

6 | #include <edmonds_karp.hh> |
---|

7 | #include <time_measure.h> |
---|

8 | |
---|

9 | using namespace hugo; |
---|

10 | |
---|

11 | // Use a DIMACS max flow file as stdin. |
---|

12 | // read_dimacs_demo < dimacs_max_flow_file |
---|

13 | int main(int, char **) { |
---|

14 | typedef ListGraph::NodeIt NodeIt; |
---|

15 | typedef ListGraph::EachEdgeIt EachEdgeIt; |
---|

16 | |
---|

17 | ListGraph G; |
---|

18 | NodeIt s, t; |
---|

19 | ListGraph::EdgeMap<int> cap(G); |
---|

20 | readDimacsMaxFlow(std::cin, G, s, t, cap); |
---|

21 | |
---|

22 | { |
---|

23 | std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl; |
---|

24 | ListGraph::EdgeMap<int> flow(G); //0 flow |
---|

25 | |
---|

26 | double pre_time=currTime(); |
---|

27 | MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
---|

28 | //max_flow_test.augmentWithBlockingFlow<ListGraph>(); |
---|

29 | max_flow_test.run<ListGraph>(); |
---|

30 | double post_time=currTime(); |
---|

31 | |
---|

32 | //std::cout << "maximum flow: "<< std::endl; |
---|

33 | //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
---|

34 | // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
---|

35 | //} |
---|

36 | //std::cout<<std::endl; |
---|

37 | std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
---|

38 | std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|

39 | } |
---|

40 | |
---|

41 | { |
---|

42 | std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl; |
---|

43 | ListGraph::EdgeMap<int> flow(G); //0 flow |
---|

44 | |
---|

45 | double pre_time=currTime(); |
---|

46 | MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
---|

47 | //max_flow_test.augmentWithBlockingFlow<ListGraph>(); |
---|

48 | max_flow_test.run(); |
---|

49 | double post_time=currTime(); |
---|

50 | |
---|

51 | //std::cout << "maximum flow: "<< std::endl; |
---|

52 | //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
---|

53 | // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
---|

54 | //} |
---|

55 | //std::cout<<std::endl; |
---|

56 | std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
---|

57 | std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
---|

58 | } |
---|

59 | |
---|

60 | return 0; |
---|

61 | } |
---|