COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow_res_comp.cc @ 441:bb61e80e8aa1

Last change on this file since 441:bb61e80e8aa1 was 388:8aca0af3f30b, checked in by jacint, 20 years ago

ResGraphWrapper? running time comparison test.

File size: 3.8 KB
Line 
1/*
2The only difference between preflow.h and preflow_res.h is that the latter
3uses the ResGraphWrapper, while the first does not. (Bfs is implemented by
4hand in both.) This test program runs Preflow and PreflowRes on the same
5graph, tests the result of these implementations and writes the running time
6of them.  */
7#include <iostream>
8
9#include <smart_graph.h>
10#include <dimacs.h>
11#include <preflow.h>
12#include <preflow_res.h>
13#include <time_measure.h>
14
15using namespace hugo;
16
17int main(int, char **) {
18 
19  typedef SmartGraph Graph;
20 
21  typedef Graph::Node Node;
22  typedef Graph::EdgeIt EdgeIt;
23
24  Graph G;
25  Node s, t;
26  Graph::EdgeMap<int> cap(G);
27  readDimacsMaxFlow(std::cin, G, s, t, cap);
28  Timer ts;
29 
30  std::cout <<
31    "\n  In which way are we faster: using ResGraphWrapper or not?"
32            <<std::endl;
33  std::cout <<
34    "\n  Running preflow.h on a graph with " <<
35    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
36           << std::endl<<std::endl;
37
38
39 
40  Graph::EdgeMap<int> flow(G,0);
41  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1);
42  ts.reset();
43  max_flow_test.run();
44  std::cout << "Elapsed time NOT using the ResGraphWrapper: " << std::endl
45            <<ts << std::endl;
46 
47  Graph::NodeMap<bool> mincut(G);
48  max_flow_test.minMinCut(mincut);
49  int min_min_cut_value=0;
50  EdgeIt e;
51  for(G.first(e); G.valid(e); G.next(e)) {
52    if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
53  }
54
55  Graph::NodeMap<bool> cut(G);
56  max_flow_test.minCut(cut);
57  int min_cut_value=0;
58  for(G.first(e); G.valid(e); G.next(e)) {
59    if (cut[G.tail(e)] && !cut[G.head(e)])
60      min_cut_value+=cap[e];
61  }
62
63  Graph::NodeMap<bool> maxcut(G);
64  max_flow_test.maxMinCut(maxcut);
65  int max_min_cut_value=0;
66  for(G.first(e); G.valid(e); G.next(e)) {
67    if (maxcut[G.tail(e)] && !maxcut[G.head(e)])
68      max_min_cut_value+=cap[e];
69      }
70
71  std::cout << "\n Checking the result: " <<std::endl; 
72  std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
73  std::cout << "Min cut value: "<< min_cut_value << std::endl;
74  std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
75  std::cout << "Max min cut value: "<< max_min_cut_value <<
76    std::endl;
77
78  if ( max_flow_test.flowValue() == min_cut_value &&
79       min_cut_value == min_min_cut_value &&
80       min_min_cut_value == max_min_cut_value )
81    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; 
82 
83  Graph::EdgeMap<int> flow2(G,0);
84  PreflowRes<Graph, int> max_flow_test2(G, s, t, cap, flow2, 1);
85  ts.reset();
86  max_flow_test2.run();
87  std::cout << "Elapsed time using the ResGraphWrapper: " << std::endl
88            << ts << std::endl;
89 
90  Graph::NodeMap<bool> mincut2(G);
91  max_flow_test2.minMinCut(mincut2);
92  int min_min_cut_value2=0;
93    for(G.first(e); G.valid(e); G.next(e)) {
94    if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
95  }
96
97  Graph::NodeMap<bool> cut2(G);
98  max_flow_test2.minCut(cut2);
99  int min_cut_value2=0;
100  for(G.first(e); G.valid(e); G.next(e)) {
101    if (cut2[G.tail(e)] && !cut2[G.head(e)])
102      min_cut_value2+=cap[e];
103  }
104
105  Graph::NodeMap<bool> maxcut2(G);
106  max_flow_test2.maxMinCut(maxcut2);
107  int max_min_cut_value2=0;
108  for(G.first(e); G.valid(e); G.next(e)) {
109    if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)])
110      max_min_cut_value2+=cap[e];
111      }
112 
113  std::cout << "\n Checking the result: " <<std::endl; 
114  std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl;
115  std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
116  std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
117  std::cout << "Max min cut value: "<< max_min_cut_value2 <<
118    std::endl; 
119  if ( max_flow_test.flowValue() == min_cut_value &&
120       min_cut_value == min_min_cut_value &&
121       min_min_cut_value == max_min_cut_value )
122    std::cout << "They are equal! " <<std::endl<<"/n"; 
123 
124  return 0;
125}
Note: See TracBrowser for help on using the repository browser.