Completions.
3 //#include <lemon/list_graph.h>
4 #include <sage_graph.h>
5 #include <lemon/dimacs.h>
6 #include <lemon/max_flow.h>
7 //#include <max_flow_no_stack.h>
8 #include <lemon/time_measure.h>
10 using namespace lemon;
12 int main(int, char **) {
14 // typedef ListGraph Graph;
15 typedef SageGraph Graph;
17 typedef Graph::Node Node;
18 typedef Graph::EdgeIt EdgeIt;
22 Graph::EdgeMap<int> cap(G);
23 Graph::EdgeMap<int> flow(G,0);
25 readDimacs(std::cin, G, cap, s, t, flow);
29 "\n Running max_flow.h on a graph with " <<
30 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
31 << std::endl<<std::endl;
34 MaxFlow<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow);
36 max_flow_test_no_stack.preflowPhase1(MaxFlow<Graph, int>::PRE_FLOW);
37 std::cout << "Elapsed time of run() without stack: " << std::endl
40 Graph::NodeMap<bool> mincut(G);
41 max_flow_test_no_stack.minMinCut(mincut);
42 int min_min_cut_value=0;
44 for(G.first(e); G.valid(e); G.next(e)) {
45 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e];
48 Graph::NodeMap<bool> cut(G);
49 max_flow_test_no_stack.minCut(cut);
51 for(G.first(e); G.valid(e); G.next(e)) {
52 if (cut[G.source(e)] && !cut[G.target(e)])
53 min_cut_value+=cap[e];
56 Graph::NodeMap<bool> maxcut(G);
57 max_flow_test_no_stack.maxMinCut(maxcut);
58 int max_min_cut_value=0;
59 for(G.first(e); G.valid(e); G.next(e)) {
60 if (maxcut[G.source(e)] && !maxcut[G.target(e)])
61 max_min_cut_value+=cap[e];
64 std::cout << "\n Checking the result without stack: " <<std::endl;
65 std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl;
66 std::cout << "Min cut value: "<< min_cut_value << std::endl;
67 std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
68 std::cout << "Max min cut value: "<< max_min_cut_value <<
71 if ( max_flow_test_no_stack.flowValue() == min_cut_value &&
72 min_cut_value == min_min_cut_value &&
73 min_min_cut_value == max_min_cut_value )
74 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";
78 Graph::EdgeMap<int> flow2(G,0);
79 std::cout << "Calling setFlow() " << std::endl
81 max_flow_test.setFlow(flow2);
83 max_flow_test.preflow(max_flow_test.PRE_FLOW);
84 std::cout << "Elapsed time of preflow(PRE_FLOW) starting from the zero flow: " << std::endl
87 Graph::NodeMap<bool> mincut2(G);
88 max_flow_test.minMinCut(mincut2);
89 int min_min_cut_value2=0;
90 for(G.first(e); G.valid(e); G.next(e)) {
91 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e];
94 Graph::NodeMap<bool> cut2(G);
95 max_flow_test.minCut(cut2);
97 for(G.first(e); G.valid(e); G.next(e)) {
98 if (cut2[G.source(e)] && !cut2[G.target(e)])
99 min_cut_value2+=cap[e];
102 Graph::NodeMap<bool> maxcut2(G);
103 max_flow_test.maxMinCut(maxcut2);
104 int max_min_cut_value2=0;
105 for(G.first(e); G.valid(e); G.next(e)) {
106 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)])
107 max_min_cut_value2+=cap[e];
110 std::cout << "\n Checking the result: " <<std::endl;
111 std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
112 std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
113 std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
114 std::cout << "Max min cut value: "<< max_min_cut_value2 <<
116 if ( max_flow_test.flowValue() == min_cut_value &&
117 min_cut_value == min_min_cut_value &&
118 min_min_cut_value == max_min_cut_value )
119 std::cout << "They are equal! " <<std::endl;
122 MaxFlow<Graph, int> max_flow_test3(G, s, t, cap, flow2);
123 max_flow_test3.run(max_flow_test3.GEN_FLOW);
124 std::cout << "Calling run(GEN_FLOW) from the max flow found before. " <<std::endl;
126 Graph::NodeMap<bool> mincut3(G);
127 max_flow_test3.minMinCut(mincut3);
128 int min_min_cut_value3=0;
129 for(G.first(e); G.valid(e); G.next(e)) {
130 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e];
133 Graph::NodeMap<bool> cut3(G);
134 max_flow_test3.minCut(cut3);
135 int min_cut_value3=0;
136 for(G.first(e); G.valid(e); G.next(e)) {
137 if (cut3[G.source(e)] && !cut3[G.target(e)])
138 min_cut_value3+=cap[e];
141 Graph::NodeMap<bool> maxcut3(G);
142 max_flow_test3.maxMinCut(maxcut3);
143 int max_min_cut_value3=0;
144 for(G.first(e); G.valid(e); G.next(e)) {
145 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)])
146 max_min_cut_value3+=cap[e];
149 std::cout << "\n Checking the result: " <<std::endl;
150 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;
151 std::cout << "Min cut value: "<< min_cut_value3 << std::endl;
152 std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;
153 std::cout << "Max min cut value: "<< max_min_cut_value3 <<
156 if ( max_flow_test3.flowValue() == min_cut_value3 &&
157 min_cut_value3 == min_min_cut_value3 &&
158 min_min_cut_value3 == max_min_cut_value3 )
159 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";