16 #include <time_measure.h> |
16 #include <time_measure.h> |
17 #include <for_each_macros.h> |
17 #include <for_each_macros.h> |
18 //#include <bfs_iterator.h> |
18 //#include <bfs_iterator.h> |
19 #include <graph_wrapper.h> |
19 #include <graph_wrapper.h> |
20 #include <maps.h> |
20 #include <maps.h> |
21 #include <edmonds_karp.h> |
21 #include <max_flow.h> |
22 #include <preflow.h> |
|
23 |
22 |
24 /** |
23 /** |
25 * Inicializalja a veletlenszamgeneratort. |
24 * Inicializalja a veletlenszamgeneratort. |
26 * Figyelem, ez nem jo igazi random szamokhoz, |
25 * Figyelem, ez nem jo igazi random szamokhoz, |
27 * erre ne bizzad a titkaidat! |
26 * erre ne bizzad a titkaidat! |
99 typedef stGraphWrapper<BGW> stGW; |
98 typedef stGraphWrapper<BGW> stGW; |
100 stGW stgw(bgw); |
99 stGW stgw(bgw); |
101 ConstMap<stGW::Edge, int> const1map(1); |
100 ConstMap<stGW::Edge, int> const1map(1); |
102 |
101 |
103 Timer ts; |
102 Timer ts; |
|
103 stGW::EdgeMap<int> flow(stgw); |
|
104 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
|
105 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); |
|
106 |
104 ts.reset(); |
107 ts.reset(); |
105 stGW::EdgeMap<int> max_flow(stgw); |
108 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
106 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
|
107 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow); |
|
108 // while (max_flow_test.augmentOnShortestPath()) { } |
109 // while (max_flow_test.augmentOnShortestPath()) { } |
109 typedef ListGraph MutableGraph; |
110 typedef ListGraph MutableGraph; |
110 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
111 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
111 while (max_flow_test.augmentOnBlockingFlow2()) { |
112 while (max_flow_test.augmentOnBlockingFlow2()) { |
112 std::cout << max_flow_test.flowValue() << std::endl; |
113 std::cout << max_flow_test.flowValue() << std::endl; |
113 } |
114 } |
114 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; |
115 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; |
115 std::cout << "elapsed time: " << ts << std::endl; |
116 std::cout << "elapsed time: " << ts << std::endl; |
116 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
|
117 // std::cout << e << ": " << max_flow[e] << "\n"; |
|
118 // } |
|
119 // std::cout << "\n"; |
|
120 |
117 |
121 ts.reset(); |
118 ts.reset(); |
122 stGW::EdgeMap<int> pre_flow(stgw); |
119 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
123 Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
120 max_flow_test.run(); |
124 pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/); |
|
125 pre_flow_test.run(); |
|
126 std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl; |
121 std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl; |
127 std::cout << "elapsed time: " << ts << std::endl; |
122 std::cout << "elapsed time: " << ts << std::endl; |
128 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
|
129 // std::cout << e << ": " << pre_flow[e] << "\n"; |
|
130 // } |
|
131 // std::cout << "\n"; |
|
132 |
123 |
133 ts.reset(); |
124 ts.reset(); |
134 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); |
125 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); |
135 // stGW::EdgeMap<int> pre_flow(stgw); |
|
136 //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
|
137 // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true); |
|
138 //pre_flow_test.run(); |
|
139 std::cout << "leda matching value: " << ml.size() << std::endl; |
126 std::cout << "leda matching value: " << ml.size() << std::endl; |
140 std::cout << "elapsed time: " << ts << std::endl; |
127 std::cout << "elapsed time: " << ts << std::endl; |
141 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
|
142 // std::cout << e << ": " << pre_flow[e] << "\n"; |
|
143 // } |
|
144 // std::cout << "\n"; |
|
145 |
128 |
146 return 0; |
129 return 0; |
147 } |
130 } |