Concept modification to resolve the item by its ID.
3 #include <lemon/list_graph.h>
4 #include <lemon/dimacs.h>
6 #include <max_flow_no_stack.h>
7 #include <lemon/time_measure.h>
11 int main(int, char **) {
13 typedef ListGraph Graph;
15 typedef Graph::Node Node;
16 typedef Graph::EdgeIt EdgeIt;
20 Graph::EdgeMap<int> cap(G);
21 readDimacs(std::cin, G, cap, s, t);
25 "\n Running max_flow.h on a graph with " <<
26 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
27 << std::endl<<std::endl;
29 Graph::EdgeMap<int> flowstack(G,0);
30 MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flowstack);
33 std::cout << "Elapsed time of run() with stl stack: " << std::endl
36 Graph::EdgeMap<int> flow(G,0);
37 MaxFlowNoStack<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow);
39 max_flow_test_no_stack.run();
40 std::cout << "Elapsed time of run() without stack: " << std::endl
43 Graph::NodeMap<bool> mincut(G);
44 max_flow_test_no_stack.minMinCut(mincut);
45 int min_min_cut_value=0;
47 for(G.first(e); G.valid(e); G.next(e)) {
48 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e];
51 Graph::NodeMap<bool> cut(G);
52 max_flow_test_no_stack.minCut(cut);
54 for(G.first(e); G.valid(e); G.next(e)) {
55 if (cut[G.source(e)] && !cut[G.target(e)])
56 min_cut_value+=cap[e];
59 Graph::NodeMap<bool> maxcut(G);
60 max_flow_test_no_stack.maxMinCut(maxcut);
61 int max_min_cut_value=0;
62 for(G.first(e); G.valid(e); G.next(e)) {
63 if (maxcut[G.source(e)] && !maxcut[G.target(e)])
64 max_min_cut_value+=cap[e];
67 std::cout << "\n Checking the result without stack: " <<std::endl;
68 std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl;
69 std::cout << "Min cut value: "<< min_cut_value << std::endl;
70 std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
71 std::cout << "Max min cut value: "<< max_min_cut_value <<
74 if ( max_flow_test_no_stack.flowValue() == min_cut_value &&
75 min_cut_value == min_min_cut_value &&
76 min_min_cut_value == max_min_cut_value )
77 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";
81 Graph::EdgeMap<int> flow2(G,0);
82 std::cout << "Calling resetFlow() " << std::endl
84 max_flow_test.setFlow(flow2);
86 max_flow_test.preflow(max_flow_test.PRE_FLOW);
87 std::cout << "Elapsed time of preflow(PRE_FLOW) starting from the zero flow: " << std::endl
90 Graph::NodeMap<bool> mincut2(G);
91 max_flow_test.minMinCut(mincut2);
92 int min_min_cut_value2=0;
93 for(G.first(e); G.valid(e); G.next(e)) {
94 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e];
97 Graph::NodeMap<bool> cut2(G);
98 max_flow_test.minCut(cut2);
100 for(G.first(e); G.valid(e); G.next(e)) {
101 if (cut2[G.source(e)] && !cut2[G.target(e)])
102 min_cut_value2+=cap[e];
105 Graph::NodeMap<bool> maxcut2(G);
106 max_flow_test.maxMinCut(maxcut2);
107 int max_min_cut_value2=0;
108 for(G.first(e); G.valid(e); G.next(e)) {
109 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)])
110 max_min_cut_value2+=cap[e];
113 std::cout << "\n Checking the result: " <<std::endl;
114 std::cout << "Flow value: "<< max_flow_test.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 <<
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;
125 MaxFlow<Graph, int> max_flow_test3(G, s, t, cap, flow2);
126 max_flow_test3.run(max_flow_test3.GEN_FLOW);
127 std::cout << "Calling run(GEN_FLOW) from the max flow found before. " <<std::endl;
129 Graph::NodeMap<bool> mincut3(G);
130 max_flow_test3.minMinCut(mincut3);
131 int min_min_cut_value3=0;
132 for(G.first(e); G.valid(e); G.next(e)) {
133 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e];
136 Graph::NodeMap<bool> cut3(G);
137 max_flow_test3.minCut(cut3);
138 int min_cut_value3=0;
139 for(G.first(e); G.valid(e); G.next(e)) {
140 if (cut3[G.source(e)] && !cut3[G.target(e)])
141 min_cut_value3+=cap[e];
144 Graph::NodeMap<bool> maxcut3(G);
145 max_flow_test3.maxMinCut(maxcut3);
146 int max_min_cut_value3=0;
147 for(G.first(e); G.valid(e); G.next(e)) {
148 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)])
149 max_min_cut_value3+=cap[e];
152 std::cout << "\n Checking the result: " <<std::endl;
153 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;
154 std::cout << "Min cut value: "<< min_cut_value3 << std::endl;
155 std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;
156 std::cout << "Max min cut value: "<< max_min_cut_value3 <<
159 if ( max_flow_test3.flowValue() == min_cut_value3 &&
160 min_cut_value3 == min_min_cut_value3 &&
161 min_min_cut_value3 == max_min_cut_value3 )
162 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";