Bug Summary

File:OMCompiler/Compiler/runtime/matching.c
Warning:line 638, column 17
Assigned value is garbage or undefined

Annotated Source Code

[?] Use j/k keys for keyboard navigation

1/*
2 * File: matching.c
3 * Content: Contains maximum transversal algorithms
4 * Author: Kamer Kaya, Johannes Langguth and Bora Ucar
5 * Version: 0.3
6 *
7 * Please see the reports:
8 *
9 * "I. S. Duff, K. Kaya and B. Ucar.
10 * 'Design, Implementations and Analysis of Maximum Transversal Algorithms'
11 * CERFACS Tech. Report TR/PA/10/76, October, 2010."
12 *
13 * "K. Kaya, J. Langguth, F. Manne and B. Ucar.
14 * 'Experiments on Push-Relabel-based Maximum Cardinality Matching Algorithms for Bipartite Graphs'
15 * CERFACS Tech. Report TR/PA/11/33, May, 2011."
16 *
17 * for more details and cite them if you use the codes.
18 *
19 */
20
21#include <stdio.h>
22#include <string.h>
23#include <stdlib.h>
24#include <ctype.h>
25#include <math.h>
26
27#include "matchmaker.h"
28
29#define max(a, b)(a > b ? a : b) (a > b ? a : b)
30
31void match_dfs(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m) {
32 int* stack = (int*)malloc(sizeof(int) * n);
33 int* colptrs = (int*)malloc(sizeof(int) * n);
34 int* visited = (int*)malloc(sizeof(int) * m);
35
36 int stack_col, ptr, temp, next_augment_no, i, j, row, col, eptr, stack_last,
37 stack_end;
38 memset(visited, 0, sizeof(int) * m);
39 next_augment_no = 1;
40 for(i = 0; i < n; i++) {
41 if((match[i] == -1) && (col_ptrs[i] != col_ptrs[i+1])) {
42 stack[0] = i; stack_last = 0;
43 colptrs[i] = col_ptrs[i];
44 stack_end = n;
45 while(stack_last > -1) {
46 stack_col = stack[stack_last];
47
48 eptr = col_ptrs[stack_col + 1];
49 for(ptr = colptrs[stack_col]; ptr < eptr; ptr++) {
50 temp = visited[col_ids[ptr]];
51 if(temp != next_augment_no && temp != -1) {
52 break;
53 }
54 }
55 colptrs[stack_col] = ptr + 1;
56
57 if(ptr == eptr) {
58 stack[--stack_end] = stack_col;
59 --stack_last;
60 continue;
61 }
62
63 row = col_ids[ptr]; visited[row] = next_augment_no;
64 col = row_match[row];
65 if(col == -1) {
66 while(row != -1){
67 col = stack[stack_last--];
68 temp = match[col];
69 match[col] = row; row_match[row] = col;
70 row = temp;
71 }
72
73 next_augment_no++;
74 break;
75 } else {
76 stack[++stack_last] = col;
77 colptrs[col] = col_ptrs[col];
78 }
79 }
80
81 if(match[i] == -1) {
82 for(j = stack_end + 1; j < n; j++) {
83 visited[match[stack[j]]] = -1;
84 }
85 }
86 }
87 }
88 free(visited);
89 free(colptrs);
90 free(stack);
91}
92
93void match_bfs(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m) {
94 int* visited = (int*)malloc(sizeof(int) * m);
95 int* queue = (int*)malloc(sizeof(int) * n);
96 int* previous = (int*)malloc(sizeof(int) * m);
97
98 int queue_ptr, queue_col, ptr, next_augment_no, i, j, queue_size,
99 row, col, temp, eptr;
100
101 memset(visited, 0, sizeof(int) * m);
102
103 next_augment_no = 1;
104 for(i = 0; i < n; i++) {
105 if(match[i] == -1 && col_ptrs[i] != col_ptrs[i+1]) {
106 queue[0] = i; queue_ptr = 0; queue_size = 1;
107
108 while(queue_size > queue_ptr) {
109 queue_col = queue[queue_ptr++];
110 eptr = col_ptrs[queue_col + 1];
111 for(ptr = col_ptrs[queue_col]; ptr < eptr; ptr++) {
112 row = col_ids[ptr];
113 temp = visited[row];
114
115 if(temp != next_augment_no && temp != -1) {
116 previous[row] = queue_col;
117 visited[row] = next_augment_no;
118
119 col = row_match[row];
120 if(col == -1) {
121 while(row != -1) {
122 col = previous[row];
123 temp = match[col];
124 match[col] = row; row_match[row] = col;
125 row = temp;
126 }
127 next_augment_no++;
128 queue_size = 0;
129 break;
130 } else {
131 queue[queue_size++] = col;
132 }
133 }
134 }
135 }
136
137 if(match[i] == -1) {
138 for(j = 1; j < queue_size; j++) {
139 visited[match[queue[j]]] = -1;
140 }
141 }
142 }
143 }
144
145 free(previous);
146 free(queue);
147 free(visited);
148}
149
150void match_mc21(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m) {
151 int* visited = (int*)malloc(sizeof(int) * m);
152 int* stack = (int*)malloc(sizeof(int) * n);
153 int* colptrs = (int*)malloc(sizeof(int) * n);
154 int* lookahead = (int*)malloc(sizeof(int) * n);
155
156 int stack_col, stack_last, ptr, next_augment_no, i,j, row, col,
157 temp, eptr, stack_end;
158
159 memset(visited, 0, sizeof(int) * m);
160 memcpy(lookahead, col_ptrs, sizeof(int) * n);
161
162 next_augment_no = 1;
163 for(i = 0; i < n; i++) {
164 if(match[i] == -1 && col_ptrs[i] != col_ptrs[i+1]) {
165 stack[0] = i; stack_last = 0;
166 colptrs[i] = col_ptrs[i];
167
168 stack_end = n;
169
170 while(stack_last > -1) {
171 stack_col = stack[stack_last];
172
173 eptr = col_ptrs[stack_col + 1];
174 for(ptr = lookahead[stack_col]; ptr < eptr && row_match[col_ids[ptr]] != -1; ptr++){}
175 lookahead[stack_col] = ptr + 1;
176
177 if(ptr >= eptr) {
178 for(ptr = colptrs[stack_col]; ptr < eptr; ptr++) {
179 temp = visited[col_ids[ptr]];
180 if(temp != next_augment_no && temp != -1) {
181 break;
182 }
183 }
184 colptrs[stack_col] = ptr + 1;
185
186 if(ptr == eptr) {
187 --stack_last;
188 stack[--stack_end] = stack_col;
189 continue;
190 }
191
192 row = col_ids[ptr]; visited[row] = next_augment_no;
193 col = row_match[row]; stack[++stack_last] = col; colptrs[col] = col_ptrs[col];
194 } else {
195 row = col_ids[ptr]; visited[row] = next_augment_no;
196 while(row != -1){
197 col = stack[stack_last--];
198 temp = match[col];
199 match[col] = row; row_match[row] = col;
200 row = temp;
201 }
202 next_augment_no++;
203 break;
204 }
205 }
206
207 if(match[i] == -1) {
208 for(j = stack_end + 1; j < n; j++) {
209 visited[match[stack[j]]] = -1;
210 }
211 }
212 }
213 }
214
215 free(lookahead);
216 free(colptrs);
217 free(stack);
218 free(visited);
219}
220
221void match_pf(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m) {
222 int* visited = (int*)malloc(sizeof(int) * m);
223 int* stack = (int*)malloc(sizeof(int) * n);
224 int* colptrs = (int*)malloc(sizeof(int) * n);
225 int* lookahead = (int*)malloc(sizeof(int) * n);
226 int* unmatched = (int*)malloc(sizeof(int) * n);
227
228 int i, j, row, col, stack_col, temp, ptr, eptr, stack_last,
229 stop = 0, pcount = 1, stack_end_ptr, nunmatched = 0, nextunmatched = 0,
230 current_col;
231
232 memset(visited, 0, sizeof(int) * m);
233 memcpy(lookahead, col_ptrs, sizeof(int) * n);
234
235 for(i = 0; i < n; i++) {
236 if(match[i] == -1 && col_ptrs[i] != col_ptrs[i+1]) {
237 unmatched[nunmatched++] = i;
238 }
239 }
240
241 while(!stop) {
242 stop = 1;
243 stack_end_ptr = n;
244 for(i = 0; i < nunmatched; i++) {
245 current_col = unmatched[i];
246 stack[0] = current_col; stack_last = 0; colptrs[current_col] = col_ptrs[current_col];
247
248 while(stack_last > -1) {
249 stack_col = stack[stack_last];
250
251 eptr = col_ptrs[stack_col + 1];
252 for(ptr = lookahead[stack_col]; ptr < eptr && row_match[col_ids[ptr]] != -1; ptr++){}
253 lookahead[stack_col] = ptr + 1;
254
255 if(ptr >= eptr) {
256 for(ptr = colptrs[stack_col]; ptr < eptr; ptr++) {
257 temp = visited[col_ids[ptr]];
258 if(temp != pcount && temp != -1) {
259 break;
260 }
261 }
262 colptrs[stack_col] = ptr + 1;
263
264 if(ptr == eptr) {
265 if(stop) {stack[--stack_end_ptr] = stack_col;}
266 --stack_last;
267 continue;
268 }
269
270 row = col_ids[ptr]; visited[row] = pcount;
271 col = row_match[row]; stack[++stack_last] = col; colptrs[col] = col_ptrs[col];
272 } else {
273 row = col_ids[ptr]; visited[row] = pcount;
274 while(row != -1){
275 col = stack[stack_last--];
276 temp = match[col];
277 match[col] = row; row_match[row] = col;
278 row = temp;
279 }
280 stop = 0;
281 break;
282 }
283 }
284
285 if(match[current_col] == -1) {
286 if(stop) {
287 for(j = stack_end_ptr + 1; j < n; j++) {
288 visited[match[stack[j]]] = -1;
289 }
290 stack_end_ptr = n;
291 } else {
292 unmatched[nextunmatched++] = current_col;
293 }
294 }
295 }
296 pcount++; nunmatched = nextunmatched; nextunmatched = 0;
297 }
298
299 free(unmatched);
300 free(lookahead);
301 free(colptrs);
302 free(stack);
303 free(visited);
304}
305
306
307void match_pf_fair(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m) {
308 int* visited = (int*)malloc(sizeof(int) * m);
309 int* stack = (int*)malloc(sizeof(int) * n);
310 int* colptrs = (int*)malloc(sizeof(int) * n);
311 int* lookahead = (int*)malloc(sizeof(int) * n);
312 int* unmatched = (int*)malloc(sizeof(int) * n);
313
314 int i, j, row, col, stack_col, temp, ptr, eptr, stack_last,
315 stop = 0, pcount = 1, stack_end_ptr, nunmatched = 0, nextunmatched = 0,
316 current_col, inc = 1;
317
318 memset(visited, 0, sizeof(int) * m);
319 memcpy(lookahead, col_ptrs, sizeof(int) * n);
320
321 for(i = 0; i < n; i++) {
322 if(match[i] == -1 && col_ptrs[i] != col_ptrs[i+1]) {
323 unmatched[nunmatched++] = i;
324 }
325 }
326
327 while(!stop) {
328 stop = 1; stack_end_ptr = n;
329 if(inc) {
330 for(i = 0; i < nunmatched; i++) {
331 current_col = unmatched[i];
332 stack[0] = current_col; stack_last = 0; colptrs[current_col] = col_ptrs[current_col];
333
334 while(stack_last > -1) {
335 stack_col = stack[stack_last];
336
337 eptr = col_ptrs[stack_col + 1];
338 for(ptr = lookahead[stack_col]; ptr < eptr && row_match[col_ids[ptr]] != -1; ptr++){}
339 lookahead[stack_col] = ptr + 1;
340
341 if(ptr >= eptr) {
342 for(ptr = colptrs[stack_col]; ptr < eptr; ptr++) {
343 temp = visited[col_ids[ptr]];
344 if(temp != pcount && temp != -1) {
345 break;
346 }
347 }
348 colptrs[stack_col] = ptr + 1;
349
350 if(ptr == eptr) {
351 if(stop) {stack[--stack_end_ptr] = stack_col;}
352 --stack_last;
353 continue;
354 }
355
356 row = col_ids[ptr]; visited[row] = pcount;
357 col = row_match[row]; stack[++stack_last] = col; colptrs[col] = col_ptrs[col];
358 } else {
359 row = col_ids[ptr]; visited[row] = pcount;
360 while(row != -1){
361 col = stack[stack_last--];
362 temp = match[col];
363 match[col] = row; row_match[row] = col;
364 row = temp;
365 }
366 stop = 0;
367 break;
368 }
369 }
370
371 if(match[current_col] == -1) {
372 if(stop) {
373 for(j = stack_end_ptr + 1; j < n; j++) {
374 visited[match[stack[j]]] = -1;
375 }
376 stack_end_ptr = n;
377 } else {
378 unmatched[nextunmatched++] = current_col;
379 }
380 }
381 }
382 } else {
383 for(i = 0; i < nunmatched; i++) {
384 current_col = unmatched[i];
385 stack[0] = current_col; stack_last = 0; colptrs[current_col] = col_ptrs[current_col + 1] - 1;
386
387 while(stack_last > -1) {
388 stack_col = stack[stack_last];
389
390 eptr = col_ptrs[stack_col + 1];
391 for(ptr = lookahead[stack_col]; ptr < eptr && row_match[col_ids[ptr]] != -1; ptr++){}
392 lookahead[stack_col] = ptr + 1;
393
394 if(ptr >= eptr) {
395 eptr = col_ptrs[stack_col] - 1;
396 for(ptr = colptrs[stack_col]; ptr > eptr; ptr--) {
397 temp = visited[col_ids[ptr]];
398 if(temp != pcount && temp != -1) {
399 break;
400 }
401 }
402 colptrs[stack_col] = ptr - 1;
403
404 if(ptr == eptr) {
405 if(stop) {stack[--stack_end_ptr] = stack_col;}
406 --stack_last;
407 continue;
408 }
409
410 row = col_ids[ptr]; visited[row] = pcount;
411 col = row_match[row]; stack[++stack_last] = col;
412 colptrs[col] = col_ptrs[col + 1] - 1;
413
414 } else {
415 row = col_ids[ptr]; visited[row] = pcount;
416 while(row != -1){
417 col = stack[stack_last--];
418 temp = match[col];
419 match[col] = row; row_match[row] = col;
420 row = temp;
421 }
422 stop = 0;
423 break;
424 }
425 }
426
427 if(match[current_col] == -1) {
428 if(stop) {
429 for(j = stack_end_ptr + 1; j < n; j++) {
430 visited[match[stack[j]]] = -1;
431 }
432 stack_end_ptr = n;
433 } else {
434 unmatched[nextunmatched++] = current_col;
435 }
436 }
437 }
438 }
439 pcount++; nunmatched = nextunmatched; nextunmatched = 0; inc = !inc;
440 }
441
442 free(unmatched);
443 free(lookahead);
444 free(colptrs);
445 free(stack);
446 free(visited);
447}
448
449void match_hk(int* col_ptrs, int* col_ids, int* row_ptrs, int* row_ids, int* match, int* row_match, int n, int m) {
450 int* queue = (int*)malloc(sizeof(int) * n);
451 int* stack = (int*)malloc(sizeof(int) * m);
452 int* rowptrs = (int*)malloc(sizeof(int) * m);
453 int* cvisited = (int*)malloc(sizeof(int) * n);
454 int* rvisited = (int*)malloc(sizeof(int) * m);
455 int* qpos = (int*)malloc(sizeof(int) * n);
456 int* clevels = (int*)malloc(sizeof(int) * n);
457
458 int i, queue_size, queue_ptr, queue_col, row, col, temp, stack_row, ptr, eptr,
459 pcount = 1, ppcount, level_0, last_queue_size, L, desired, stack_last;
460
461 memset(rvisited, 0, sizeof(int) * m);
462 memset(cvisited, 0, sizeof(int) * n);
463
464 level_0 = 0;
465 for(i = n-1; i >= 0; i--) {
466 if(match[i] == -1 && col_ptrs[i] != col_ptrs[i+1]) {
467 qpos[i] = level_0;
468 queue[level_0++] = i;
469 }
470 }
471
472 while(1) {
473 stack_last = -1;
474 queue_size = level_0; queue_ptr = 0; L = 0;
475 while(stack_last == -1 && queue_ptr < queue_size) {
476 last_queue_size = queue_size; L += 2;
477 while(queue_ptr < last_queue_size) {
478 queue_col = queue[queue_ptr++];
479 eptr = col_ptrs[queue_col + 1];
480 for(ptr = col_ptrs[queue_col]; ptr < eptr; ptr++) {
481 row = col_ids[ptr];
482 if(rvisited[row] != pcount) {
483 rvisited[row] = pcount;
484 col = row_match[row];
485 if(col == -1) {
486 stack[++stack_last] = row;
487 rowptrs[row] = row_ptrs[row];
488 } else {
489 queue[queue_size++] = col;
490 cvisited[col] = pcount;
491 clevels[col] = L;
492 }
493 }
494 }
495 }
496 }
497 ppcount = pcount++;
498
499 if(stack_last == -1) break;
500
501 while(stack_last > -1) {
502 stack_row = stack[stack_last];
503
504 col = row_match[stack_row];
505 if(col == -1) desired = L - 2; else desired = clevels[col] - 2;
506
507 eptr = row_ptrs[stack_row + 1];
508 for(ptr = rowptrs[stack_row]; ptr < eptr; ptr++) {
509 col = row_ids[ptr];
510 if(match[col] == -1 || (clevels[col] == desired && cvisited[col] == ppcount)) {
511 cvisited[col] = pcount;
512 break;
513 }
514 }
515 rowptrs[stack_row] = ptr + 1;
516
517 if(ptr < eptr) {
518 row = match[col];
519 if(row == -1) {
520 qpos[queue[--level_0]] = qpos[col];
521 queue[qpos[col]] = queue[level_0];
522
523 while(col != -1){
524 row = stack[stack_last--];
525 temp = row_match[row];
526 row_match[row] = col; match[col] = row;
527 col = temp;
528 }
529 } else {
530 stack[++stack_last] = row;
531 rowptrs[row] = row_ptrs[row];
532 }
533 } else {
534 --stack_last;
535 continue;
536 }
537 }
538 pcount++;
539 }
540
541 free(queue);
542 free(stack);
543 free(rowptrs);
544 free(cvisited);
545 free(rvisited);
546 free(qpos);
547 free(clevels);
548}
549
550void match_hk_dw(int* col_ptrs, int* col_ids, int* row_ptrs, int* row_ids,
551 int* match, int* row_match, int n, int m) {
552
553 int* queue = (int*)malloc(sizeof(int) * n);
554 int* stack = (int*)malloc(sizeof(int) * m);
1
Storing uninitialized value
555 int* rowptrs = (int*)malloc(sizeof(int) * m);
556 int* lookahead = (int*)malloc(sizeof(int) * m);
557 int* cvisited = (int*)malloc(sizeof(int) * n);
558 int* rvisited = (int*)malloc(sizeof(int) * m);
559 int* qpos = (int*)malloc(sizeof(int) * n);
560 int* clevels = (int*)malloc(sizeof(int) * n);
561 int* unmatched = (int*)malloc(sizeof(int) * m);
562
563
564 int i, queue_size, queue_ptr, queue_col, row, col, temp, stack_row, ptr, eptr,
565 pcount = 1, ppcount, level_0, last_queue_size, stack_last, nunmatched = 0,
566 nextunmatched, current_row, desired, L;
567
568 memset(rvisited, 0, sizeof(int) * m);
569 memset(cvisited, 0, sizeof(int) * n);
570 memcpy(lookahead, row_ptrs, sizeof(int) * m);
571
572 for(i = 0; i < m; i++) {
2
Assuming 'i' is >= 'm'
3
Loop condition is false. Execution continues on line 578
573 if(row_match[i] == -1 && row_ptrs[i] != row_ptrs[i+1]) {
574 unmatched[nunmatched++] = i;
575 }
576 }
577
578 level_0 = 0;
579 for(i = n-1; i >= 0; i--) {
4
Assuming 'i' is >= 0
5
Loop condition is true. Entering loop body
6
Assuming 'i' is >= 0
7
Loop condition is true. Entering loop body
8
Assuming 'i' is >= 0
9
Loop condition is true. Entering loop body
11
Assuming 'i' is < 0
12
Loop condition is false. Execution continues on line 586
580 if(match[i] == -1 && col_ptrs[i] != col_ptrs[i+1]) {
10
Taking true branch
581 qpos[i] = level_0;
582 queue[level_0++] = i;
583 }
584 }
585
586 while(1) {
13
Loop condition is true. Entering loop body
587 stack_last = -1;
588
589 queue_size = level_0; queue_ptr = 0; L = 0;
590 while(stack_last == -1 && queue_ptr < queue_size) {
14
Loop condition is true. Entering loop body
591 last_queue_size = queue_size; L += 2;
592 while(queue_ptr < last_queue_size) {
15
Loop condition is true. Entering loop body
25
Loop condition is false. Execution continues on line 590
593 queue_col = queue[queue_ptr++];
594
595 eptr = col_ptrs[queue_col + 1];
596 for(ptr = col_ptrs[queue_col]; ptr < eptr; ptr++) {
16
Loop condition is true. Entering loop body
18
Loop condition is true. Entering loop body
20
Loop condition is true. Entering loop body
24
Loop condition is false. Execution continues on line 592
597 row = col_ids[ptr];
598 if(rvisited[row] != pcount) {
17
Taking false branch
19
Taking false branch
21
Taking true branch
599 rvisited[row] = pcount;
600 col = row_match[row];
601 if(col == -1) {
22
Assuming the condition is true
23
Taking true branch
602 stack[++stack_last] = row;
603 rowptrs[row] = row_ptrs[row];
604 } else {
605 queue[queue_size++] = col;
606 cvisited[col] = pcount;
607 clevels[col] = L;
608 }
609 }
610 }
611 }
612 }
613 ppcount = pcount++;
614 if(stack_last == -1) break;
26
Taking false branch
615
616 while(stack_last > -1) {
27
Loop condition is true. Entering loop body
617 stack_row = stack[stack_last];
618 col = row_match[stack_row];
619 if(col == -1) desired = L - 2; else desired = clevels[col] - 2;
28
Assuming the condition is false
29
Taking false branch
620
621 eptr = row_ptrs[stack_row + 1];
622 for(ptr = rowptrs[stack_row]; ptr < eptr; ptr++) {
30
Loop condition is false. Execution continues on line 629
623 col = row_ids[ptr];
624 if(match[col] == -1 || (clevels[col] == desired && cvisited[col] == ppcount)) {
625 cvisited[col] = pcount;
626 break;
627 }
628 }
629 rowptrs[stack_row] = ptr + 1;
630
631 if(ptr < eptr) {
31
Taking true branch
632 row = match[col];
633 if(row == -1) {
32
Assuming the condition is true
33
Taking true branch
634 qpos[queue[--level_0]] = qpos[col];
635 queue[qpos[col]] = queue[level_0];
636
637 while(col != -1){
34
Loop condition is true. Entering loop body
35
Assuming the condition is true
36
Loop condition is true. Entering loop body
638 row = stack[stack_last--];
37
Assigned value is garbage or undefined
639 temp = row_match[row];
640 row_match[row] = col; match[col] = row;
641 col = temp;
642 }
643 } else {
644 stack[++stack_last] = row;
645 rowptrs[row] = row_ptrs[row];
646 }
647 } else {
648 --stack_last;
649 continue;
650 }
651 }
652 pcount++;
653
654 nextunmatched = 0;
655 for(i = 0; i < nunmatched; i++) {
656 current_row = unmatched[i];
657 if(row_match[current_row] == -1) {
658 stack[0] = current_row; stack_last = 0;
659 rowptrs[current_row] = row_ptrs[current_row];
660 while(stack_last > -1) {
661 stack_row = stack[stack_last];
662
663 eptr = row_ptrs[stack_row + 1];
664 for(ptr = lookahead[stack_row]; ptr < eptr && match[row_ids[ptr]] != -1; ptr++){}
665 lookahead[stack_row] = ptr + 1;
666
667 if(ptr >= eptr) {
668 eptr = row_ptrs[stack_row + 1];
669 for(ptr = rowptrs[stack_row]; ptr < eptr && cvisited[row_ids[ptr]] == pcount; ptr++) {}
670 rowptrs[stack_row] = ptr + 1;
671
672 if(ptr == eptr) {
673 --stack_last;
674 continue;
675 }
676
677 col = row_ids[ptr]; row = match[col];
678
679 cvisited[col] = pcount;
680 stack[++stack_last] = row;
681 rowptrs[row] = row_ptrs[row];
682 } else {
683 col = row_ids[ptr]; cvisited[col] = pcount;
684
685 qpos[queue[--level_0]] = qpos[col];
686 queue[qpos[col]] = queue[level_0];
687
688 while(col != -1){
689 row = stack[stack_last--];
690 temp = row_match[row];
691 row_match[row] = col; match[col] = row;
692 col = temp;
693 }
694 break;
695 }
696 }
697
698 if(row_match[current_row] == -1) {
699 unmatched[nextunmatched++] = current_row;
700 }
701 }
702 }
703 pcount++; nunmatched = nextunmatched;
704 }
705
706 free(queue);
707 free(stack);
708 free(rowptrs);
709 free(cvisited);
710 free(rvisited);
711 free(lookahead);
712 free(qpos);
713 free(clevels);
714 free(unmatched);
715}
716
717void match_abmp(int* col_ptrs, int* col_ids, int* row_ptrs, int* row_ids, int* match, int* row_match, int n, int m) {
718 int v = max(m,n)(m > n ? m : n);
719
720 int* queue = (int*)malloc(sizeof(int) * v);
721 int* clevels = (int*)malloc(sizeof(int) * n);
722 int* rvisited = (int*)malloc(sizeof(int) * m);
723 int* colptrs = (int*)malloc(sizeof(int) * v);
724 int* unmatched = (int*)malloc(sizeof(int) * n);
725 int* qpos = (int*)malloc(sizeof(int) * m);
726 int* cvisited = (int*)malloc(sizeof(int) * n);
727 int* stack = (int*)malloc(sizeof(int) * n);
728 int* rlevels = (int*)malloc(sizeof(int) * m);
729
730 int i,queue_size, queue_ptr, queue_row, row = -1, col = -1,
731 temp, stack_col, ptr, eptr, next_col_i, start_col_i,
732 pcount = 1, desired_level, L, desired, stack_last, current_col,
733 lim = 0.1*sqrt(m + n), nunmatched = 0, level_ptr,
734 update_counter = n, counter_limit = n, tunmatched = 0,level_0, ppcount = 0;
735
736 level_0 = 0;
737 for(i = 0; i < m; i++) {
738 if(row_match[i] == -1 && row_ptrs[i] != row_ptrs[i+1]) {
739 qpos[i] = level_0;
740 queue[level_0++] = i;
741 }
742 }
743
744 for(i = 0; i < n; i++) {if(match[i] == -1) {tunmatched++;} clevels[i] = n + m;}
745
746 memset(cvisited, 0, sizeof(int) * n);
747 while(1) {
748 if(update_counter >= counter_limit) {
749 update_counter = 0; L = 1; nunmatched = 0;
750 queue_size = level_0; queue_ptr = 0;
751 while(queue_ptr < queue_size) {
752 level_ptr = queue_size;
753 while(queue_ptr < level_ptr) {
754 queue_row = queue[queue_ptr++];
755
756 eptr = row_ptrs[queue_row + 1];
757 for(ptr = row_ptrs[queue_row]; ptr < eptr; ptr++) {
758 col = row_ids[ptr];
759
760 if(cvisited[col] != pcount) {
761 cvisited[col] = pcount;
762 clevels[col] = L;
763
764 row = match[col];
765 if(row == -1) {
766 unmatched[nunmatched++] = col;
767 } else {
768 queue[queue_size++] = row;
769 }
770 }
771 }
772 }
773 L += 2; if(L > lim || 50*L > tunmatched) {break;}
774 }
775 }
776
777 if(nunmatched == 0) {
778 break;
779 }
780 start_col_i = 0; next_col_i = 0; L = clevels[unmatched[0]];
781
782 while(next_col_i < nunmatched) {
783 current_col = unmatched[next_col_i]; stack[0] = current_col; stack_last = 0;
784 colptrs[current_col] = col_ptrs[current_col];
785
786 while(stack_last > -1) {
787 stack_col = stack[stack_last];
788 desired_level = clevels[stack_col] - 2;
789
790 eptr = col_ptrs[stack_col + 1];
791 for(ptr = colptrs[stack_col]; ptr < eptr; ptr++){
792 row = col_ids[ptr];
793 col = row_match[row];
794 if(col == -1 || clevels[col] == desired_level) {break;}
795 }
796 colptrs[stack_col] = ptr + 1;
797
798 if(ptr == eptr) {
799 clevels[stack_col] += 2;
800 update_counter++;
801 --stack_last;
802 continue;
803 }
804
805 if(col == -1) {
806 qpos[queue[--level_0]] = qpos[row];
807 queue[qpos[row]] = queue[level_0];
808
809 while(row != -1) {
810 col = stack[stack_last--];
811 temp = match[col];
812 match[col] = row; row_match[row] = col;
813 row = temp;
814 }
815 break;
816 } else {
817 stack[++stack_last] = col;
818 colptrs[col] = col_ptrs[col];
819 }
820 }
821
822 if(match[current_col] != -1) {
823 tunmatched--;
824 if(50*L > tunmatched) {break;}
825 unmatched[next_col_i] = unmatched[start_col_i++];
826 }
827 next_col_i++;
828
829 if(next_col_i < nunmatched && L != clevels[unmatched[next_col_i]]) {
830 L = clevels[unmatched[start_col_i]];
831 next_col_i = start_col_i;
832 }
833 if(update_counter >= counter_limit) {break;}
834 }
835 if(next_col_i == nunmatched || 50*L > tunmatched) {break;}
836 }
837 pcount++;
838
839 memset(rvisited, 0, sizeof(int) * m);
840 memset(cvisited, 0, sizeof(int) * n);
841 while(1) {
842 stack_last = -1;
843 queue_size = level_0; queue_ptr = 0; L = 0;
844 while(stack_last == -1 && queue_ptr < queue_size) {
845 level_ptr = queue_size; L += 2;
846 while(queue_ptr < level_ptr) {
847 queue_row = queue[queue_ptr++];
848
849 eptr = row_ptrs[queue_row + 1];
850 for(ptr = row_ptrs[queue_row]; ptr < eptr; ptr++) {
851 col = row_ids[ptr];
852 if(cvisited[col] != pcount) {
853 cvisited[col] = pcount;
854 row = match[col];
855 if(row == -1) {
856 stack[++stack_last] = col;
857 colptrs[col] = col_ptrs[col];
858 } else {
859 queue[queue_size++] = row;
860 rvisited[row] = pcount;
861 rlevels[row] = L;
862 }
863 }
864 }
865 }
866 }
867 ppcount = pcount++;
868
869 if(stack_last == -1) break;
870 while(stack_last > -1) {
871 stack_col = stack[stack_last];
872
873 row = match[stack_col];
874 if(row == -1) desired = L - 2; else desired = rlevels[row] - 2;
875
876 eptr = col_ptrs[stack_col + 1];
877 for(ptr = colptrs[stack_col]; ptr < eptr; ptr++) {
878 row = col_ids[ptr];
879 if(row_match[row] == -1 || (rlevels[row] == desired && rvisited[row] == ppcount)) {
880 rvisited[row] = pcount;
881 break;
882 }
883 }
884 colptrs[stack_col] = ptr + 1;
885
886 if(ptr < eptr) {
887 col = row_match[row];
888 if(col == -1) {
889
890 qpos[queue[--level_0]] = qpos[row];
891 queue[qpos[row]] = queue[level_0];
892
893 while(row != -1){
894 col = stack[stack_last--];
895 temp = match[col];
896 row_match[row] = col; match[col] = row;
897 row = temp;
898 }
899 } else {
900 stack[++stack_last] = col;
901 colptrs[col] = col_ptrs[col];
902 }
903 } else {
904 --stack_last;
905 continue;
906 }
907 }
908 pcount++;
909 }
910
911 free(queue);
912 free(clevels);
913 free(rvisited);
914 free(colptrs);
915 free(unmatched);
916 free(qpos);
917 free(cvisited);
918 free(stack);
919 free(rlevels);
920}
921
922void match_abmp_bfs(int* col_ptrs, int* col_ids, int* row_ptrs, int* row_ids, int* match, int* row_match, int n, int m) {
923 int v = max(m,n)(m > n ? m : n);
924 int* queue = (int*)malloc(sizeof(int) * v);
925 int* visited = (int*)malloc(sizeof(int) * v);
926 int* colptrs = (int*)malloc(sizeof(int) * v);
927 int* previous = colptrs;
928 int* unmatched = (int*)malloc(sizeof(int) * n);
929 int* clevels = (int*)malloc(sizeof(int) * n);
930 int* qpos = (int*)malloc(sizeof(int) * m);
931
932 int i,j, queue_size, queue_ptr, queue_row, row = -1, col = -1,
933 temp, stack_col, ptr, eptr, next_col_i, start_col_i,
934 pcount = 1, desired_level, L, stack_last, current_col,
935 lim = 0.1*sqrt(m + n), nunmatched = 0, level_0, level_ptr,
936 update_counter = n, counter_limit = n, tunmatched = 0;
937
938 int* stack;
939
940 level_0 = 0;
941 for(i = 0; i < m; i++) {
942 if(row_match[i] == -1 && row_ptrs[i] != row_ptrs[i+1]) {
943 qpos[i] = level_0;
944 queue[level_0++] = i;
945 }
946 }
947
948 for(i = 0; i < n; i++) {if(match[i] == -1) {tunmatched++;}clevels[i] = n+m;}
949
950 memset(visited, 0, sizeof(int) * m);
951 while(1) {
952 if(update_counter >= counter_limit) {
953 L = 1; nunmatched = 0; update_counter = 0;
954 queue_size = level_0; queue_ptr = 0;
955 while(queue_ptr < queue_size) {
956 level_ptr = queue_size;
957 while(queue_ptr < level_ptr) {
958 queue_row = queue[queue_ptr++];
959
960 eptr = row_ptrs[queue_row + 1];
961 for(ptr = row_ptrs[queue_row]; ptr < eptr; ptr++) {
962 col = row_ids[ptr];
963
964 if(visited[col] != pcount) {
965 visited[col] = pcount;
966 clevels[col] = L;
967
968 row = match[col];
969 if(row == -1) {
970 unmatched[nunmatched++] = col;
971 } else {
972 queue[queue_size++] = row;
973 }
974 }
975 }
976 }
977 L += 2; if(L > lim || 50*L > tunmatched) {break;}
978 }
979 }
980
981 if(nunmatched == 0) {
982 break;
983 }
984 start_col_i = 0; next_col_i = 0; L = clevels[unmatched[0]];
985
986 stack = &(queue[level_0]);
987 while(next_col_i < nunmatched) {
988 current_col = unmatched[next_col_i]; stack[0] = current_col; stack_last = 0;
989 colptrs[current_col] = col_ptrs[current_col];
990
991 while(stack_last > -1) {
992 stack_col = stack[stack_last];
993 desired_level = clevels[stack_col] - 2;
994
995 eptr = col_ptrs[stack_col + 1];
996 for(ptr = colptrs[stack_col]; ptr < eptr; ptr++){
997 row = col_ids[ptr];
998 col = row_match[row];
999 if(col == -1 || clevels[col] == desired_level) {break;}
1000 }
1001 colptrs[stack_col] = ptr + 1;
1002
1003 if(ptr == eptr) {
1004 clevels[stack_col] += 2;
1005 update_counter++;
1006 --stack_last;
1007 continue;
1008 }
1009
1010 if(col == -1) {
1011 qpos[queue[--level_0]] = qpos[row];
1012 queue[qpos[row]] = queue[level_0];
1013
1014 while(row != -1) {
1015 col = stack[stack_last--];
1016 temp = match[col];
1017 match[col] = row; row_match[row] = col;
1018 row = temp;
1019 }
1020 break;
1021 } else {
1022 stack[++stack_last] = col;
1023 colptrs[col] = col_ptrs[col];
1024 }
1025 }
1026
1027 if(match[current_col] != -1) {
1028 tunmatched--;
1029 if(50*L > tunmatched) {break;}
1030 unmatched[next_col_i] = unmatched[start_col_i++];
1031 }
1032 next_col_i++;
1033
1034 if(next_col_i < nunmatched && L != clevels[unmatched[next_col_i]]) {
1035 L = clevels[unmatched[start_col_i]];
1036 next_col_i = start_col_i;
1037 }
1038 if(update_counter >= counter_limit) {break;}
1039 }
1040 if(next_col_i == nunmatched || 50*L > tunmatched) {break;}
1041 pcount++;
1042 }
1043
1044 memset(visited, 0, sizeof(int) * n);
1045 while(level_0 > 0) {
1046 queue_size = level_0; queue_ptr = level_0 - 1;
1047
1048 while(queue_size > queue_ptr) {
1049 queue_row = queue[queue_ptr++];
1050
1051 eptr = row_ptrs[queue_row + 1];
1052 for(ptr = row_ptrs[queue_row]; ptr < eptr; ptr++) {
1053 col = row_ids[ptr];
1054
1055 if(visited[col] != level_0 && visited[col] != -1) {
1056 previous[col] = queue_row;
1057 visited[col] = level_0;
1058
1059 row = match[col];
1060 if(row == -1) {
1061 while(col != -1) {
1062 row = previous[col];
1063 temp = row_match[row];
1064 match[col] = row; row_match[row] = col;
1065 col = temp;
1066 }
1067 queue_size = 0;
1068 break;
1069 } else {
1070 queue[queue_size++] = row;
1071 }
1072 }
1073 }
1074 }
1075
1076 if(row_match[queue[level_0-1]] == -1) {
1077 for(j = level_0; j < queue_size; j++) {
1078 visited[row_match[queue[j]]] = -1;
1079 }
1080 }
1081 level_0--;
1082 }
1083
1084 free(queue);
1085 free(visited);
1086 free(colptrs);
1087 free(unmatched);
1088 free(clevels);
1089 free(qpos);
1090}
1091
1092void pr_global_relabel(int* l_label, int* r_label, int* row_ptrs, int* row_ids, int* match, int* row_match, int n, int m) {
1093 int* queue = (int*)malloc(sizeof(int) * m);
1094 int relabel_vertex;
1095 int i;
1096 int queue_end=-1;
1097 int queue_start=0;
1098
1099 int max = n+m;
1100
1101 for(i=0; i <n; i++) {
1102 l_label[i]=max;
1103 }
1104
1105 for(i=0; i < m; i++) {
1106 if (row_match[i] == -1) {
1107 queue_end++;
1108 queue[queue_end] = i;
1109 r_label[i]=0;
1110 }
1111 else {
1112 r_label[i]=max;
1113 }
1114 }
1115
1116 while (queue_end-queue_start>=0) {
1117 relabel_vertex=queue[queue_start];
1118 queue_start++;
1119
1120 int ptr;
1121 int s_ptr = row_ptrs[relabel_vertex];
1122 int e_ptr = row_ptrs[relabel_vertex + 1];
1123 for(ptr = s_ptr; ptr < e_ptr; ptr++) {
1124 int left_vertex = row_ids[ptr];
1125 if(l_label[left_vertex] == max) {
1126 l_label[left_vertex]=r_label[relabel_vertex]+1;
1127 if (match[left_vertex]> -1) {
1128 if (r_label[match[left_vertex]] == max) {
1129 queue_end++;
1130 queue[queue_end]=match[left_vertex];
1131 r_label[match[left_vertex]]=l_label[left_vertex]+1;
1132 }
1133 }
1134 }
1135 }
1136 }
1137 free(queue);
1138}
1139
1140void match_pr_fifo_fair(int* col_ptrs, int* col_ids, int* row_ptrs, int* row_ids, int* match, int* row_match, int n, int m, double relabel_period) {
1141 int* l_label = (int*)malloc(sizeof(int) * n);
1142 int* r_label = (int*)malloc(sizeof(int) * m);
1143
1144 int* queue = (int*)malloc(sizeof(int) * n);
1145 int queue_end = -1;
1146 int queue_start = 0;
1147
1148 int max = m + n;
1149 int limit = (int)(max*relabel_period);
1150 if (relabel_period == -1) limit = m;
1151 if (relabel_period == -2) limit = n;
1152
1153 int i = 0;
1154 for(; i < n; i++) {
1155 if (match[i] == -1) {
1156 queue_end++;
1157 queue[queue_end]=i;
1158 }
1159 }
1160 pr_global_relabel(l_label, r_label, row_ptrs, row_ids, match, row_match, n, m);
1161
1162 int min_vertex,max_vertex,min_label,next_vertex;
1163 int relabels=0;
1164 int queuesize = queue_end+1;
1165
1166 while (queuesize>0) {
1167 max_vertex=queue[queue_start];
1168 queue_start = (queue_start+1)%n;
1169 queuesize--;
1170
1171 if (relabels==limit) {
1172 pr_global_relabel(l_label, r_label, row_ptrs, row_ids, match, row_match, n, m);
1173 relabels=0;
1174 }
1175
1176 min_label=max;
1177 relabels++;
1178
1179 if (l_label[max_vertex]<max) {
1180 int ptr;
1181 int s_ptr = col_ptrs[max_vertex];
1182 int e_ptr = col_ptrs[max_vertex + 1];
1183 if (l_label[max_vertex]%4==1) {
1184 for(ptr = s_ptr; ptr < e_ptr; ptr++) {
1185 if(r_label[col_ids[ptr]] < min_label) {
1186 min_label=r_label[col_ids[ptr]];
1187 min_vertex=col_ids[ptr];
1188 if (r_label[min_vertex]==l_label[max_vertex]-1){
1189 relabels--;
1190 break;
1191 }
1192 }
1193 }
1194 } else {
1195 for(ptr = e_ptr-1; ptr >= s_ptr; ptr--) {
1196 if(r_label[col_ids[ptr]] < min_label) {
1197 min_label=r_label[col_ids[ptr]];
1198 min_vertex=col_ids[ptr];
1199 if (r_label[min_vertex]==l_label[max_vertex]-1)
1200 {
1201 relabels--;
1202 break;
1203 }
1204 }
1205 }
1206 }
1207 }
1208
1209 if (min_label<max) {
1210 if (row_match[min_vertex]==-1){
1211 row_match[min_vertex]=max_vertex;
1212 match[max_vertex]=min_vertex;
1213 } else {
1214 next_vertex=row_match[min_vertex];
1215 queue_end = (queue_end+1)%n;
1216 queuesize++;
1217 queue[queue_end]=next_vertex;
1218
1219 row_match[min_vertex]=max_vertex;
1220 match[max_vertex]=min_vertex;
1221 match[next_vertex]=-1;
1222 l_label[max_vertex]=min_label+1;
1223 }
1224 r_label[min_vertex]=min_label+2;
1225 }
1226 }
1227
1228 free(queue);
1229 free(l_label);
1230 free(r_label);
1231}
1232
1233void matching(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m, int matching_id, int cheap_id, double relabel_period, int clear_match) {
1234 int* row_ptrs;
1235 int* row_ids;
1236 int i;
1237
1238 if (clear_match==1)
1239 {
1240 for (i = 0; i < n; i++) {
1241 match[i] = -1;
1242 }
1243 for (i = 0; i < m; i++) {
1244 row_match[i] = -1;
1245 }
1246 }
1247
1248 if(matching_id >= do_hk6 || cheap_id > do_old_cheap1) {
1249
1250 row_ptrs = (int*) malloc((m+1) * sizeof(int));
1251 memset(row_ptrs, 0, (m+1) * sizeof(int));
1252
1253 int nz = col_ptrs[n];
1254
1255 for(i = 0; i < nz; i++) {row_ptrs[col_ids[i]+1]++;}
1256 for(i = 0; i < m; i++) {row_ptrs[i+1] += row_ptrs[i];}
1257
1258 int* t_row_ptrs = (int*) malloc(m * sizeof(int));
1259 memcpy(t_row_ptrs, row_ptrs, m * sizeof(int));
1260
1261 row_ids = (int*) malloc(nz * sizeof(int));
1262
1263 for(i = 0; i < n; i++) {
1264 int sp = col_ptrs[i];
1265 int ep = col_ptrs[i+1];
1266
1267 for(;sp < ep; sp++) {
1268 int row = col_ids[sp];
1269 row_ids[t_row_ptrs[row]++] = i;
1270 }
1271 }
1272 free(t_row_ptrs);
1273 }
1274
1275 cheap_matching(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m, cheap_id);
1276
1277 if(matching_id == do_dfs1) {
1278 match_dfs(col_ptrs, col_ids, match, row_match, n, m);
1279 } else if(matching_id == do_bfs2) {
1280 match_bfs(col_ptrs, col_ids, match, row_match, n, m);
1281 } else if(matching_id == do_mc213) {
1282 match_mc21(col_ptrs, col_ids, match, row_match, n, m);
1283 } else if(matching_id == do_pf4) {
1284 match_pf(col_ptrs, col_ids, match, row_match, n, m);
1285 } else if(matching_id == do_pf_fair5) {
1286 match_pf_fair(col_ptrs, col_ids, match, row_match, n, m);
1287 } else if(matching_id == do_hk6) {
1288 match_hk(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m);
1289 } else if(matching_id == do_hk_dw7) {
1290 match_hk_dw(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m);
1291 } else if(matching_id == do_abmp8) {
1292 match_abmp(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m);
1293 } else if(matching_id == do_abmp_bfs9) {
1294 match_abmp_bfs(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m);
1295 } else if(matching_id == do_pr_fifo_fair10) {
1296 match_pr_fifo_fair(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m, relabel_period);
1297 }
1298 if(matching_id >= do_hk6 || cheap_id > do_old_cheap1) {
1299 free(row_ids);
1300 free(row_ptrs);
1301 }
1302}
1303