Bug Summary

File:OMCompiler/Compiler/runtime/matching_cheap.c
Warning:line 177, column 9
Assigned value is garbage or undefined

Annotated Source Code

[?] Use j/k keys for keyboard navigation

1/*
2 * File: cheap.c
3 * Content: Contains jump-start heuristics
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#include <stdio.h>
21#include <string.h>
22#include <stdlib.h>
23#include <ctype.h>
24#include <tinymt64.h>
25
26#include "matchmaker.h"
27
28struct node
29{
30 int id;
31 int degree;
32 struct node *next;
33 struct node* prvs;
34};
35
36typedef struct node Node;
37
38void old_cheap(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m) {
39 int ptr;
40 int i = 0;
41 for(; i < n; i++) {
42 int s_ptr = col_ptrs[i];
43 int e_ptr = col_ptrs[i + 1];
44 for(ptr = s_ptr; ptr < e_ptr; ptr++) {
45 int r_id = col_ids[ptr];
46 if(row_match[r_id] == -1) {
47 match[i] = r_id;
48 row_match[r_id] = i;
49 break;
50 }
51 }
52 }
53}
54
55void sk_cheap(int* col_ptrs, int* col_ids, int* row_ptrs, int* row_ids,
56 int* match, int* row_match, int n, int m){
57 int i;
58
59 int* col_stack = (int*)malloc(n * sizeof(int));
60 int* col_degrees = (int*)malloc(n * sizeof(int));
61
62 int no_of_d1_cols = 0;
63 for(i = 0; i < n; i++) {
18
Loop condition is true. Entering loop body
21
Loop condition is false. Execution continues on line 70
64 col_degrees[i] = col_ptrs[i+1] - col_ptrs[i];
65 if(col_degrees[i] == 1) {
19
Assuming the condition is false
20
Taking false branch
66 col_stack[no_of_d1_cols++] = i;
67 }
68 }
69
70 int* row_stack = (int*)malloc(m * sizeof(int));
71 int* row_degrees = (int*)malloc(m * sizeof(int));
22
Storing uninitialized value
72
73 int no_of_d1_rows = 0;
74 for(i = 0; i < m; i++) {
23
Loop condition is false. Execution continues on line 81
75 row_degrees[i] = row_ptrs[i+1] - row_ptrs[i];
76 if(row_degrees[i] == 1) {
77 row_stack[no_of_d1_rows++] = i;
78 }
79 }
80
81 int stop = 0;
82 int r_id = -1, c_id, r_id2, c_id2;
83 int sptr, eptr, ptr;
84 int sptr2, eptr2, ptr2;
85
86 int remain = 0;
87 int c_degree = 0;
88
89 while(!stop) {
24
Loop condition is true. Entering loop body
90 while(no_of_d1_rows > 0 || no_of_d1_cols > 0) {
25
Loop condition is false. Execution continues on line 146
91 if(no_of_d1_rows > 0) {
92 r_id = row_stack[--no_of_d1_rows];
93 if(row_degrees[r_id] == 1 && row_match[r_id] == -1) {
94 sptr = row_ptrs[r_id];
95 eptr = row_ptrs[r_id + 1];
96 for(ptr = sptr; ptr < eptr; ptr++) {
97 c_id = row_ids[ptr];
98 if(match[c_id] == -1) {
99 match[c_id] = r_id;
100 row_match[r_id] = c_id;
101
102 sptr2 = col_ptrs[c_id];
103 eptr2 = col_ptrs[c_id + 1];
104 for(ptr2 = sptr2; ptr2 < eptr2; ptr2++) {
105 r_id2 = col_ids[ptr2];
106 if(row_match[r_id2] == -1) {
107 if((--(row_degrees[r_id2])) == 1) {
108 row_stack[no_of_d1_rows++] = r_id2;
109 }
110 }
111 }
112 break;
113 }
114 }
115 }
116 }
117
118 if(no_of_d1_cols > 0) {
119 c_id = col_stack[--no_of_d1_cols];
120 if(col_degrees[c_id] == 1 && match[c_id] == -1) {
121 sptr = col_ptrs[c_id];
122 eptr = col_ptrs[c_id + 1];
123 for(ptr = sptr; ptr < eptr; ptr++) {
124 r_id = col_ids[ptr];
125 if(row_match[r_id] == -1) {
126 row_match[r_id] = c_id;
127 match[c_id] = r_id;
128
129 sptr2 = row_ptrs[r_id];
130 eptr2 = row_ptrs[r_id + 1];
131 for(ptr2 = sptr2; ptr2 < eptr2; ptr2++) {
132 c_id2 = row_ids[ptr2];
133 if( match[c_id2] == -1) {
134 if((--(col_degrees[c_id2])) == 1) {
135 col_stack[no_of_d1_cols++] = c_id2;
136 }
137 }
138 }
139 break;
140 }
141 }
142 }
143 }
144 }
145
146 stop = 1;
147 for(i = remain; i < n; i++) {
26
Loop condition is true. Entering loop body
148 c_id = i;
149 c_degree = col_degrees[c_id];
150
151 if(match[c_id] == -1 && c_degree != 0) {
27
Assuming the condition is true
28
Assuming 'c_degree' is not equal to 0
29
Taking true branch
152 sptr = col_ptrs[c_id];
153 eptr = col_ptrs[c_id + 1];
154
155 for(ptr = sptr; ptr < eptr; ptr++) {
30
Loop condition is false. Execution continues on line 164
156 r_id = col_ids[ptr];
157 if(row_match[r_id] == -1) {
158 match[c_id] = r_id;
159 row_match[r_id] = c_id;
160 stop = 0;
161 break;
162 }
163 }
164 ptr++;
165
166 for(;ptr < eptr; ptr++) {
31
Loop condition is false. Execution continues on line 175
167 r_id2 = col_ids[ptr];
168 if(row_match[r_id2] == -1) {
169 if((--(row_degrees[r_id2])) == 1) {
170 row_stack[no_of_d1_rows++] = r_id2;
171 }
172 }
173 }
174
175 sptr = row_ptrs[r_id];
176 eptr = row_ptrs[r_id + 1];
177 int count = row_degrees[r_id];
32
Assigned value is garbage or undefined
178 for(ptr = sptr;ptr < eptr && count > 0; ptr++) {
179 c_id2 = row_ids[ptr];
180 if(match[c_id2] == -1) {
181 count--;
182 if((--(col_degrees[c_id2])) == 1) {
183 col_stack[no_of_d1_cols++] = c_id2;
184 }
185 }
186 }
187 }
188
189 if(no_of_d1_cols + no_of_d1_rows > 0) {
190 remain = i + 1;
191 break;
192 }
193
194 if(i == n-1) {
195 stop = 1;
196 }
197 }
198 }
199
200 free(row_degrees);
201 free(row_stack);
202 free(col_degrees);
203 free(col_stack);
204}
205
206void sk_cheap_rand(int* col_ptrs, int* col_ids, int* row_ptrs, int* row_ids,
207 int* match, int* row_match, int n, int m) {
208 int i;
209 /* initialize seed */
210 tinymt64_t random_seed;
211 random_seed.mat1 = 0x8f7011ee;
212 random_seed.mat2 = 0xfc78ff1f;
213 random_seed.tmat = 0x3793fdff;
214 tinymt64_init(&random_seed,1);
215 int* col_stack = (int*)malloc(n * sizeof(int));
216 int* col_degrees = (int*)malloc(n * sizeof(int));
217
218 int no_of_d1_cols = 0;
219 for(i = 0; i < n; i++) {
220 col_degrees[i] = col_ptrs[i+1] - col_ptrs[i];
221 if(col_degrees[i] == 1) {
222 col_stack[no_of_d1_cols++] = i;
223 }
224 }
225
226 int* row_stack = (int*)malloc(m * sizeof(int));
227 int* row_degrees = (int*)malloc(m * sizeof(int));
228
229 int no_of_d1_rows = 0;
230 for(i = 0; i < m; i++) {
231 row_degrees[i] = row_ptrs[i+1] - row_ptrs[i];
232 if(row_degrees[i] == 1) {
233 row_stack[no_of_d1_rows++] = i;
234 }
235 }
236
237 int* randarr = (int*)malloc(n * sizeof(int));
238 for(i = 0; i < n; i++){randarr[i] = i;}
239 for(i = n-1; i >= 0; i--) {
240 int z = tinymt64_generate_double(&random_seed)*(i+1);
241 int temp = randarr[i]; randarr[i] = randarr[z]; randarr[z] = temp;
242 }
243
244 int stop = 0;
245 int r_id = -1, c_id, r_id2, c_id2, e_id;
246 int sptr, eptr, ptr;
247 int sptr2, eptr2, ptr2;
248
249 int remain = 0;
250 int c_degree = 0;
251
252 while(!stop) {
253 while(no_of_d1_rows > 0 || no_of_d1_cols > 0) {
254 if(no_of_d1_rows > 0) {
255 r_id = row_stack[--no_of_d1_rows];
256 if(row_degrees[r_id] == 1 && row_match[r_id] == -1) {
257 sptr = row_ptrs[r_id];
258 eptr = row_ptrs[r_id + 1];
259 for(ptr = sptr; ptr < eptr; ptr++) {
260 c_id = row_ids[ptr];
261 if(match[c_id] == -1) {
262 match[c_id] = r_id;
263 row_match[r_id] = c_id;
264
265 sptr2 = col_ptrs[c_id];
266 eptr2 = col_ptrs[c_id + 1];
267 for(ptr2 = sptr2; ptr2 < eptr2; ptr2++) {
268 r_id2 = col_ids[ptr2];
269 if(row_match[r_id2] == -1) {
270 if((--(row_degrees[r_id2])) == 1) {
271 row_stack[no_of_d1_rows++] = r_id2;
272 }
273 }
274 }
275 break;
276 }
277 }
278 }
279 }
280
281 if(no_of_d1_cols > 0) {
282 c_id = col_stack[--no_of_d1_cols];
283 if(col_degrees[c_id] == 1 && match[c_id] == -1) {
284 sptr = col_ptrs[c_id];
285 eptr = col_ptrs[c_id + 1];
286 for(ptr = sptr; ptr < eptr; ptr++) {
287 r_id = col_ids[ptr];
288 if(row_match[r_id] == -1) {
289 row_match[r_id] = c_id;
290 match[c_id] = r_id;
291
292 sptr2 = row_ptrs[r_id];
293 eptr2 = row_ptrs[r_id + 1];
294 for(ptr2 = sptr2; ptr2 < eptr2; ptr2++) {
295 c_id2 = row_ids[ptr2];
296 if( match[c_id2] == -1) {
297 if((--(col_degrees[c_id2])) == 1) {
298 col_stack[no_of_d1_cols++] = c_id2;
299 }
300 }
301 }
302 break;
303 }
304 }
305 }
306 }
307 }
308
309 stop = 1;
310 for(i = remain; i < n; i++) {
311 c_id = randarr[i];
312 c_degree = col_degrees[c_id];
313
314 if(match[c_id] == -1 && c_degree != 0) {
315 e_id = tinymt64_generate_double(&random_seed)*c_degree;
316
317 sptr = col_ptrs[c_id];
318 eptr = col_ptrs[c_id + 1];
319
320 for(ptr = sptr; ptr < eptr; ptr++) {
321 r_id = col_ids[ptr];
322 if(row_match[r_id] == -1) {
323 if(e_id == 0) {
324 match[c_id] = r_id;
325 row_match[r_id] = c_id;
326 stop = 0;
327 break;
328 } else {
329 if((--(row_degrees[r_id])) == 1) {
330 row_stack[no_of_d1_rows++] = r_id;
331 }
332 e_id--;
333 }
334 }
335 }
336 ptr++;
337
338 for(;ptr < eptr; ptr++) {
339 r_id2 = col_ids[ptr];
340 if(row_match[r_id2] == -1) {
341 if((--(row_degrees[r_id2])) == 1) {
342 row_stack[no_of_d1_rows++] = r_id2;
343 }
344 }
345 }
346
347 sptr = row_ptrs[r_id];
348 eptr = row_ptrs[r_id + 1];
349 int count = row_degrees[r_id];
350 for(ptr = sptr;ptr < eptr && count > 0; ptr++) {
351 c_id2 = row_ids[ptr];
352 if(match[c_id2] == -1) {
353 count--;
354 if((--(col_degrees[c_id2])) == 1) {
355 col_stack[no_of_d1_cols++] = c_id2;
356 }
357 }
358 }
359 }
360
361 if(no_of_d1_cols + no_of_d1_rows > 0) {
362 remain = i + 1;
363 break;
364 }
365
366 if(i == n-1) {
367 stop = 1;
368 }
369 }
370 }
371
372 free(randarr);
373 free(row_degrees);
374 free(row_stack);
375 free(col_degrees);
376 free(col_stack);
377}
378
379
380void mind_cheap(int *col_ptrs, int *col_ids, int *row_ptrs, int *row_ids, int *match, int *row_match, int n, int m)
381{
382 Node* rnodes = (Node*)malloc(sizeof(Node) * m);
383 Node* cnodes = (Node*)malloc(sizeof(Node) * n);
384 Node* tptr;
385
386 int i, deg, maxdeg = -1, cdeg, vtx, minnbr = -1, ptr, row, col, temp;
387
388 for(i=0; i<n; i++)
389 {
390 deg = col_ptrs[i+1] - col_ptrs[i];
391 cnodes[i].degree = deg;
392 cnodes[i].id = i;
393 if(deg > maxdeg)
394 maxdeg = deg;
395 }
396
397 for(i=0; i<m; i++)
398 {
399 deg = row_ptrs[i+1] - row_ptrs[i];
400 rnodes[i].degree = deg;
401 rnodes[i].id = i + n;
402 if(deg > maxdeg)
403 maxdeg = deg;
404 }
405
406 Node* lists = (Node*)malloc(sizeof(Node) * (maxdeg + 1));
407 Node* listse = (Node*)malloc(sizeof(Node) * (maxdeg + 1));
408
409 for(i=0; i<=maxdeg; i++)
410 {
411 lists[i].next = &(listse[i]); lists[i].prvs = (Node*)0;
412 listse[i].next = (Node*)0; listse[i].prvs = &(lists[i]);
413 lists[i].id = -1; listse[i].id = -1;
414 lists[i].degree = i; listse[i].degree = i;
415 }
416
417 for(i=0; i<n; i++)
418 {
419 deg = cnodes[i].degree;
420 if(deg > 0)
421 {
422 tptr = lists[deg].next;
423 tptr->prvs = lists[deg].next = &(cnodes[i]);
424 cnodes[i].next = tptr;
425 cnodes[i].prvs = &(lists[deg]);
426 }
427 }
428 for(i=0; i<m; i++)
429 {
430 deg = rnodes[i].degree;
431 if(deg > 0)
432 {
433 tptr = lists[deg].next;
434 tptr->prvs = lists[deg].next = &(rnodes[i]);
435 rnodes[i].next = tptr;
436 rnodes[i].prvs = &(lists[deg]);
437 }
438 }
439
440 cdeg = 1;
441 while(cdeg <= maxdeg)
442 {
443 if(lists[cdeg].next == &(listse[cdeg]))
444 {
445 cdeg++;
446 continue;
447 }
448
449 tptr = lists[cdeg].next;
450 lists[cdeg].next = tptr->next;
451 tptr->next->prvs = &(lists[cdeg]);
452 vtx = tptr->id;
453
454 if(vtx < n)
455 {
456 for(ptr=col_ptrs[vtx]; ptr<col_ptrs[vtx+1]; ptr++)
457 {
458 if(row_match[col_ids[ptr]] == -1)
459 {
460 minnbr = col_ids[ptr];
461 break;
462 }
463 }
464
465 for(ptr=ptr+1; ptr<col_ptrs[vtx+1]; ptr++)
466 {
467 row = col_ids[ptr];
468 if(row_match[row] == -1)
469 {
470 if(rnodes[row].degree < rnodes[minnbr].degree)
471 {
472 minnbr = col_ids[ptr];
473 }
474 }
475 }
476
477 match[vtx] = minnbr; row_match[minnbr] = vtx;
478 rnodes[minnbr].next->prvs = rnodes[minnbr].prvs;
479 rnodes[minnbr].prvs->next = rnodes[minnbr].next;
480 }
481 else
482 {
483 vtx = vtx - n;
484 for(ptr=row_ptrs[vtx]; ptr<row_ptrs[vtx+1]; ptr++)
485 {
486 if(match[row_ids[ptr]] == -1)
487 {
488 minnbr = row_ids[ptr];
489 break;
490 }
491 }
492
493 for(ptr=ptr+1; ptr<row_ptrs[vtx+1]; ptr++)
494 {
495 col = row_ids[ptr];
496 if(match[col] == -1)
497 {
498 if(cnodes[col].degree < cnodes[minnbr].degree)
499 {
500 minnbr = row_ids[ptr];
501 }
502 }
503 }
504
505 row_match[vtx] = minnbr; match[minnbr] = vtx;
506 cnodes[minnbr].next->prvs = cnodes[minnbr].prvs;
507 cnodes[minnbr].prvs->next = cnodes[minnbr].next;
508 temp = vtx; vtx = minnbr; minnbr = temp; /* swap */
509 }
510
511 for(ptr=col_ptrs[vtx]; ptr<col_ptrs[vtx+1]; ptr++)
512 {
513 row = col_ids[ptr];
514 if(row_match[row] == -1)
515 {
516 deg = --(rnodes[row].degree);
517 rnodes[row].next->prvs = rnodes[row].prvs;
518 rnodes[row].prvs->next = rnodes[row].next;
519
520 if(deg > 0)
521 {
522 tptr = lists[deg].next;
523 tptr->prvs = lists[deg].next = &(rnodes[row]);
524 rnodes[row].next = tptr;
525 rnodes[row].prvs = &(lists[deg]);
526 }
527 }
528 }
529
530 for(ptr=row_ptrs[minnbr]; ptr<row_ptrs[minnbr+1]; ptr++)
531 {
532 col = row_ids[ptr];
533 if(match[col] == -1)
534 {
535 deg = --(cnodes[col].degree);
536 cnodes[col].next->prvs = cnodes[col].prvs;
537 cnodes[col].prvs->next = cnodes[col].next;
538
539 if(deg > 0)
540 {
541 tptr = lists[deg].next;
542 tptr->prvs = lists[deg].next = &(cnodes[col]);
543 cnodes[col].next = tptr;
544 cnodes[col].prvs = &(lists[deg]);
545 }
546 }
547 }
548 cdeg--;
549 }
550
551 free(listse);
552 free(lists);
553 free(cnodes);
554 free(rnodes);
555}
556
557void cheap_matching(int *col_ptrs, int *col_ids, int *row_ptrs, int *row_ids, int *match, int *row_match, int n, int m, int cheap_id)
558{
559 if(do_old_cheap1 == cheap_id)
15
Taking false branch
560 {
561 old_cheap(col_ptrs, col_ids, match, row_match, n, m);
562 }
563 else if(do_sk_cheap2 == cheap_id)
16
Taking true branch
564 {
565 sk_cheap(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m);
17
Calling 'sk_cheap'
566 }
567 else if(do_sk_cheap_rand3 == cheap_id)
568 {
569 sk_cheap_rand(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m);
570 }
571 else if(do_mind_cheap4 == cheap_id)
572 {
573 mind_cheap(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m);
574 }
575}
576
577void cheapmatching(int* col_ptrs, int* col_ids, int* match, int* row_match, int n, int m, int cheap_id, int clear_match) {
578 int* row_ptrs;
579 int* row_ids;
580 int i;
581
582 if (clear_match==1)
1
Assuming 'clear_match' is not equal to 1
2
Taking false branch
583 {
584 for (i = 0; i < n; i++) {
585 match[i] = -1;
586 }
587 for (i = 0; i < m; i++) {
588 row_match[i] = -1;
589 }
590 }
591
592 if(cheap_id > do_old_cheap1) {
3
Assuming 'cheap_id' is > do_old_cheap
4
Taking true branch
593 row_ptrs = (int*) malloc((m+1) * sizeof(int));
594 memset(row_ptrs, 0, (m+1) * sizeof(int));
595
596 int nz = col_ptrs[n];
597
598 for(i = 0; i < nz; i++) {row_ptrs[col_ids[i]+1]++;}
5
Assuming 'i' is >= 'nz'
6
Loop condition is false. Execution continues on line 599
599 for(i = 0; i < m; i++) {row_ptrs[i+1] += row_ptrs[i];}
7
Assuming 'i' is >= 'm'
8
Loop condition is false. Execution continues on line 601
600
601 int* t_row_ptrs = (int*) malloc(m * sizeof(int));
602 memcpy(t_row_ptrs, row_ptrs, m * sizeof(int));
603
604 row_ids = (int*) malloc(nz * sizeof(int));
605
606 for(i = 0; i < n; i++) {
9
Assuming 'i' is < 'n'
10
Loop condition is true. Entering loop body
12
Assuming 'i' is >= 'n'
13
Loop condition is false. Execution continues on line 615
607 int sp = col_ptrs[i];
608 int ep = col_ptrs[i+1];
609
610 for(;sp < ep; sp++) {
11
Loop condition is false. Execution continues on line 606
611 int row = col_ids[sp];
612 row_ids[t_row_ptrs[row]++] = i;
613 }
614 }
615 free(t_row_ptrs);
616 }
617
618 cheap_matching(col_ptrs, col_ids, row_ptrs, row_ids, match, row_match, n, m, cheap_id);
14
Calling 'cheap_matching'
619
620 if(cheap_id > do_old_cheap1) {
621 free(row_ids);
622 free(row_ptrs);
623 }
624}