Context Navigation

Back to Ticket #168

Ticket #168: res2.txt

File res2.txt, 17.8 KB (added by Poroszkai Daniel, 14 years ago)
Benchmark result (extended with min cost flow)

Line
1	------------------------------------------------------------------
2	./unweighted-bp-gen -red 1000 -blue 1000 -density 2000 -seed 1
3
4	Benchmarking in unweighted case, using a bipartite graph
5	with 1000 red, 1000 blue nodes, and 2000 edges.
6	--------------------------------------------------------
7	Algorithm used Matching size Time
8	Hopcroft-Karp 784 0.000739098
9	General matching 784 0.000475883
10	Preflow 784 0.00199008
11	------------------------------------------------------------------
12	./unweighted-bp-gen -red 1000 -blue 1000 -density 2000 -seed 10
13
14	Benchmarking in unweighted case, using a bipartite graph
15	with 1000 red, 1000 blue nodes, and 2000 edges.
16	--------------------------------------------------------
17	Algorithm used Matching size Time
18	Hopcroft-Karp 784 0.00112009
19	General matching 784 0.000510931
20	Preflow 784 0.00170302
21	------------------------------------------------------------------
22	./unweighted-bp-gen -red 1000 -blue 1000 -density 20000 -seed 1
23
24	Benchmarking in unweighted case, using a bipartite graph
25	with 1000 red, 1000 blue nodes, and 20000 edges.
26	--------------------------------------------------------
27	Algorithm used Matching size Time
28	Hopcroft-Karp 1000 0.000752211
29	General matching 1000 0.00172114
30	Preflow 1000 0.00203085
31	------------------------------------------------------------------
32	./unweighted-bp-gen -red 1000 -blue 1000 -density 20000 -seed 10
33
34	Benchmarking in unweighted case, using a bipartite graph
35	with 1000 red, 1000 blue nodes, and 20000 edges.
36	--------------------------------------------------------
37	Algorithm used Matching size Time
38	Hopcroft-Karp 1000 0.00080514
39	General matching 1000 0.00175405
40	Preflow 1000 0.00201392
41	------------------------------------------------------------------
42	./unweighted-bp-gen -red 1000 -blue 5000 -density 10000 -seed 1
43
44	Benchmarking in unweighted case, using a bipartite graph
45	with 1000 red, 5000 blue nodes, and 10000 edges.
46	--------------------------------------------------------
47	Algorithm used Matching size Time
48	Hopcroft-Karp 1000 0.000276089
49	General matching 1000 0.00143814
50	Preflow 1000 0.00099206
51	------------------------------------------------------------------
52	./unweighted-bp-gen -red 1000 -blue 5000 -density 10000 -seed 10
53
54	Benchmarking in unweighted case, using a bipartite graph
55	with 1000 red, 5000 blue nodes, and 10000 edges.
56	--------------------------------------------------------
57	Algorithm used Matching size Time
58	Hopcroft-Karp 1000 0.000265121
59	General matching 1000 0.00148916
60	Preflow 1000 0.000981092
61	------------------------------------------------------------------
62	./unweighted-bp-gen -red 5000 -blue 1000 -density 10000 -seed 1
63
64	Benchmarking in unweighted case, using a bipartite graph
65	with 5000 red, 1000 blue nodes, and 10000 edges.
66	--------------------------------------------------------
67	Algorithm used Matching size Time
68	Hopcroft-Karp 1000 0.000825882
69	General matching 1000 0.001441
70	Preflow 1000 0.00522804
71	------------------------------------------------------------------
72	./unweighted-bp-gen -red 5000 -blue 1000 -density 10000 -seed 10
73
74	Benchmarking in unweighted case, using a bipartite graph
75	with 5000 red, 1000 blue nodes, and 10000 edges.
76	--------------------------------------------------------
77	Algorithm used Matching size Time
78	Hopcroft-Karp 1000 0.000828981
79	General matching 1000 0.00143099
80	Preflow 1000 0.00503492
81	------------------------------------------------------------------
82	./unweighted-bp-gen -red 5000 -blue 5000 -density 10000 -seed 1
83
84	Benchmarking in unweighted case, using a bipartite graph
85	with 5000 red, 5000 blue nodes, and 10000 edges.
86	--------------------------------------------------------
87	Algorithm used Matching size Time
88	Hopcroft-Karp 3948 0.00673199
89	General matching 3948 0.00218701
90	Preflow 3948 0.0176799
91	------------------------------------------------------------------
92	./unweighted-bp-gen -red 5000 -blue 5000 -density 10000 -seed 10
93
94	Benchmarking in unweighted case, using a bipartite graph
95	with 5000 red, 5000 blue nodes, and 10000 edges.
96	--------------------------------------------------------
97	Algorithm used Matching size Time
98	Hopcroft-Karp 3941 0.00656819
99	General matching 3941 0.00237894
100	Preflow 3941 0.018575
101	------------------------------------------------------------------
102	./unweighted-bp-gen -red 5000 -blue 5000 -density 50000 -seed 1
103
104	Benchmarking in unweighted case, using a bipartite graph
105	with 5000 red, 5000 blue nodes, and 50000 edges.
106	--------------------------------------------------------
107	Algorithm used Matching size Time
108	Hopcroft-Karp 5000 0.00694299
109	General matching 5000 0.01403
110	Preflow 5000 0.0148079
111	------------------------------------------------------------------
112	./unweighted-bp-gen -red 5000 -blue 5000 -density 50000 -seed 10
113
114	Benchmarking in unweighted case, using a bipartite graph
115	with 5000 red, 5000 blue nodes, and 50000 edges.
116	--------------------------------------------------------
117	Algorithm used Matching size Time
118	Hopcroft-Karp 4999 0.0068872
119	General matching 4999 0.0141132
120	Preflow 4999 0.014971
121	------------------------------------------------------------------
122	./unweighted-bp-gen -red 10000 -blue 10000 -density 50000 -seed 1
123
124	Benchmarking in unweighted case, using a bipartite graph
125	with 10000 red, 10000 blue nodes, and 50000 edges.
126	--------------------------------------------------------
127	Algorithm used Matching size Time
128	Hopcroft-Karp 9934 0.0315061
129	General matching 9934 0.0357502
130	Preflow 9934 0.114448
131	------------------------------------------------------------------
132	./unweighted-bp-gen -red 10000 -blue 10000 -density 50000 -seed 10
133
134	Benchmarking in unweighted case, using a bipartite graph
135	with 10000 red, 10000 blue nodes, and 50000 edges.
136	--------------------------------------------------------
137	Algorithm used Matching size Time
138	Hopcroft-Karp 9920 0.0244858
139	General matching 9920 0.0659032
140	Preflow 9920 0.0363429
141	------------------------------------------------------------------
142	./unweighted-bp-gen -red 10000 -blue 10000 -density 100000 -seed 1
143
144	Benchmarking in unweighted case, using a bipartite graph
145	with 10000 red, 10000 blue nodes, and 100000 edges.
146	--------------------------------------------------------
147	Algorithm used Matching size Time
148	Hopcroft-Karp 10000 0.026413
149	General matching 10000 0.032402
150	Preflow 10000 0.0555508
151	------------------------------------------------------------------
152	./unweighted-bp-gen -red 10000 -blue 10000 -density 100000 -seed 10
153
154	Benchmarking in unweighted case, using a bipartite graph
155	with 10000 red, 10000 blue nodes, and 100000 edges.
156	--------------------------------------------------------
157	Algorithm used Matching size Time
158	Hopcroft-Karp 9999 0.0207119
159	General matching 9999 0.0564229
160	Preflow 9999 0.054014
161	-----------------------------------------------------------------------------------------------
162	./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 1
163
164	Benchmarking on weighted bipartite matching problem on a graph
165	with 1000 red, 1000 blue nodes and 2000 edges
166	--------------------------------------------------------
167	Algorithm used Maximum weight Time
168	Bipartite matching 472576 0.139076
169	General matching 472576 0.00326991
170	Capacity scaling 472576 0.0879331
171	Cost scaling 472576 0.0118301
172	Network simplex 472576 0.00567198
173	-----------------------------------------------------------------------------------------------
174	./weighted-bp-gen -red 1000 -blue 1000 -density 2000 -minweight 10 -maxweight 1000 -seed 10
175
176	Benchmarking on weighted bipartite matching problem on a graph
177	with 1000 red, 1000 blue nodes and 2000 edges
178	--------------------------------------------------------
179	Algorithm used Maximum weight Time
180	Bipartite matching 490695 0.136649
181	General matching 490695 0.00336504
182	Capacity scaling 490695 0.088218
183	Cost scaling 490695 0.0123198
184	Network simplex 490695 0.00531006
185	-----------------------------------------------------------------------------------------------
186	./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 1
187
188	Benchmarking on weighted bipartite matching problem on a graph
189	with 1000 red, 1000 blue nodes and 20000 edges
190	--------------------------------------------------------
191	Algorithm used Maximum weight Time
192	Bipartite matching 914524 0.197766
193	General matching 914524 0.027005
194	Capacity scaling 914524 0.100053
195	Cost scaling 914524 0.0668819
196	Network simplex 914524 0.0146241
197	-----------------------------------------------------------------------------------------------
198	./weighted-bp-gen -red 1000 -blue 1000 -density 20000 -minweight 10 -maxweight 1000 -seed 10
199
200	Benchmarking on weighted bipartite matching problem on a graph
201	with 1000 red, 1000 blue nodes and 20000 edges
202	--------------------------------------------------------
203	Algorithm used Maximum weight Time
204	Bipartite matching 919943 0.181663
205	General matching 919943 0.022315
206	Capacity scaling 919943 0.0937889
207	Cost scaling 919943 0.074887
208	Network simplex 919943 0.0133469
209	-----------------------------------------------------------------------------------------------
210	./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
211
212	Benchmarking on weighted bipartite matching problem on a graph
213	with 1000 red, 5000 blue nodes and 10000 edges
214	--------------------------------------------------------
215	Algorithm used Maximum weight Time
216	Bipartite matching 890836 0.505637
217	General matching 890836 0.0145609
218	Capacity scaling 890836 1.70609
219	Cost scaling 890836 0.0605259
220	Network simplex 890836 0.00779986
221	-----------------------------------------------------------------------------------------------
222	./weighted-bp-gen -red 1000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
223
224	Benchmarking on weighted bipartite matching problem on a graph
225	with 1000 red, 5000 blue nodes and 10000 edges
226	--------------------------------------------------------
227	Algorithm used Maximum weight Time
228	Bipartite matching 897412 0.502237
229	General matching 897412 0.0146611
230	Capacity scaling 897412 1.71704
231	Cost scaling 897412 0.0664949
232	Network simplex 897412 0.00781202
233	-----------------------------------------------------------------------------------------------
234	./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
235
236	Benchmarking on weighted bipartite matching problem on a graph
237	with 5000 red, 1000 blue nodes and 10000 edges
238	--------------------------------------------------------
239	Algorithm used Maximum weight Time
240	Bipartite matching 895469 0.202065
241	General matching 895469 0.014302
242	Capacity scaling 895469 0.134837
243	Cost scaling 895469 0.0462389
244	Network simplex 895469 0.00812817
245	-----------------------------------------------------------------------------------------------
246	./weighted-bp-gen -red 5000 -blue 1000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
247
248	Benchmarking on weighted bipartite matching problem on a graph
249	with 5000 red, 1000 blue nodes and 10000 edges
250	--------------------------------------------------------
251	Algorithm used Maximum weight Time
252	Bipartite matching 893040 0.192539
253	General matching 893040 0.014688
254	Capacity scaling 893040 0.142115
255	Cost scaling 893040 0.0465879
256	Network simplex 893040 0.00778508
257	-----------------------------------------------------------------------------------------------
258	./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 1
259
260	Benchmarking on weighted bipartite matching problem on a graph
261	with 5000 red, 5000 blue nodes and 10000 edges
262	--------------------------------------------------------
263	Algorithm used Maximum weight Time
264	Bipartite matching 2383509 1.52556
265	General matching 2383509 0.0276449
266	Capacity scaling 2383509 2.19282
267	Cost scaling 2383509 0.129686
268	Network simplex 2383509 0.22806
269	-----------------------------------------------------------------------------------------------
270	./weighted-bp-gen -red 5000 -blue 5000 -density 10000 -minweight 10 -maxweight 1000 -seed 10
271
272	Benchmarking on weighted bipartite matching problem on a graph
273	with 5000 red, 5000 blue nodes and 10000 edges
274	--------------------------------------------------------
275	Algorithm used Maximum weight Time
276	Bipartite matching 2394615 1.48321
277	General matching 2394615 0.0271301
278	Capacity scaling 2394615 2.19058
279	Cost scaling 2394615 0.152851
280	Network simplex 2394615 0.263314
281	-----------------------------------------------------------------------------------------------
282	./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 1
283
284	Benchmarking on weighted bipartite matching problem on a graph
285	with 5000 red, 5000 blue nodes and 50000 edges
286	--------------------------------------------------------
287	Algorithm used Maximum weight Time
288	Bipartite matching 4205491 2.20795
289	General matching 4205491 0.128231
290	Capacity scaling 4205491 1.58734
291	Cost scaling 4205491 0.489221
292	Network simplex 4205491 0.091192
293	-----------------------------------------------------------------------------------------------
294	./weighted-bp-gen -red 5000 -blue 5000 -density 50000 -minweight 10 -maxweight 1000 -seed 10
295
296	Benchmarking on weighted bipartite matching problem on a graph
297	with 5000 red, 5000 blue nodes and 50000 edges
298	--------------------------------------------------------
299	Algorithm used Maximum weight Time
300	Bipartite matching 4197432 2.46947
301	General matching 4197432 0.140808
302	Capacity scaling 4197432 1.59073
303	Cost scaling 4197432 0.682716
304	Network simplex 4197432 0.0957692
305	-----------------------------------------------------------------------------------------------
306	./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 1
307
308	Benchmarking on weighted bipartite matching problem on a graph
309	with 10000 red, 10000 blue nodes and 50000 edges
310	--------------------------------------------------------
311	Algorithm used Maximum weight Time
312	Bipartite matching 7029959 6.61569
313	General matching 7029959 0.170723
314	Capacity scaling 7029959 10.8181
315	Cost scaling 7029959 0.831383
316	Network simplex 7029959 0.240637
317	-----------------------------------------------------------------------------------------------
318	./weighted-bp-gen -red 10000 -blue 10000 -density 50000 -minweight 10 -maxweight 1000 -seed 10
319
320	Benchmarking on weighted bipartite matching problem on a graph
321	with 10000 red, 10000 blue nodes and 50000 edges
322	--------------------------------------------------------
323	Algorithm used Maximum weight Time
324	Bipartite matching 7056257 6.26456
325	General matching 7056257 0.167678
326	Capacity scaling 7056257 10.9781
327	Cost scaling 7056257 0.889265
328	Network simplex 7056257 0.25909
329	-----------------------------------------------------------------------------------------------
330	./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 1
331
332	Benchmarking on weighted bipartite matching problem on a graph
333	with 10000 red, 10000 blue nodes and 100000 edges
334	--------------------------------------------------------
335	Algorithm used Maximum weight Time
336	Bipartite matching 8396190 8.96618
337	General matching 8396190 0.441941
338	Capacity scaling 8396190 6.48904
339	Cost scaling 8396190 1.83858
340	Network simplex 8396190 0.317024
341	-----------------------------------------------------------------------------------------------
342	./weighted-bp-gen -red 10000 -blue 10000 -density 100000 -minweight 10 -maxweight 1000 -seed 10
343
344	Benchmarking on weighted bipartite matching problem on a graph
345	with 10000 red, 10000 blue nodes and 100000 edges
346	--------------------------------------------------------
347	Algorithm used Maximum weight Time
348	Bipartite matching 8393092 9.69202
349	General matching 8393092 0.444463
350	Capacity scaling 8393092 6.55828
351	Cost scaling 8393092 1.99005
352	Network simplex 8393092 0.313474

Download in other formats:

Original Format