This source file includes following definitions.
- v_cleanup
- e_cleanup
- cmp_int_pair
- gettime
- test_graph_create
- test_graph_clone
- test_graph_accessors
- test_graph_assignment_solver
- test_graph_bellman_ford
- test_graph_flow_conversion
- test_graph_param_checking
- test_graph_helper_macros
- main
1
2
3
4
5
6
7
8
9
10 #include "opal_config.h"
11
12 #include <stdlib.h>
13 #include <sys/time.h>
14
15 #include "opal/constants.h"
16 #include "opal/class/opal_list.h"
17 #include "opal/class/opal_pointer_array.h"
18 #include "opal/util/bipartite_graph.h"
19 #include "opal/util/bipartite_graph_internal.h"
20
21 # define test_out(...) fprintf(stderr, __VA_ARGS__)
22 # define check(a) \
23 do { \
24 if (!(a)) { \
25 test_out("%s:%d: check failed, '%s'\n", __func__, __LINE__, #a); \
26 return 1; \
27 } \
28 } while (0)
29 # define check_str_eq(a,b) \
30 do { \
31 const char *a_ = (a); \
32 const char *b_ = (b); \
33 if (0 != strcmp(a_,b_)) { \
34 test_out("%s:%d: check failed, \"%s\" != \"%s\"\n", \
35 __func__, __LINE__, a_, b_); \
36 return 1; \
37 } \
38 } while (0)
39 # define check_int_eq(got, expected) \
40 do { \
41 if ((got) != (expected)) { \
42 test_out("%s:%d: check failed, \"%s\" != \"%s\", got %d\n", \
43 __func__, __LINE__, #got, #expected, (got)); \
44 return 1; \
45 } \
46 } while (0)
47
48
49 # define check_err_code(got, expected) \
50 check_int_eq(got, expected)
51 # define check_msg(a, msg) \
52 do { \
53 if (!(a)) { \
54 test_out("%s:%d: check failed, \"%s\" (%s)\n", \
55 __func__, __LINE__, #a, (msg)); \
56 return 1; \
57 } \
58 } while (0)
59
60 #define check_graph_is_consistent(g) \
61 do { \
62 check(opal_bp_graph_order(g) <= opal_pointer_array_get_size(&g->vertices)); \
63 check(g->source_idx >= -1 || g->source_idx < opal_bp_graph_order(g)); \
64 check(g->sink_idx >= -1 || g->sink_idx < opal_bp_graph_order(g)); \
65 } while (0)
66
67 #define check_has_in_out_degree(g, u, expected_indegree, expected_outdegree) \
68 do { \
69 check_int_eq(opal_bp_graph_indegree(g, (u)), expected_indegree); \
70 check_int_eq(opal_bp_graph_outdegree(g, (u)), expected_outdegree); \
71 } while (0)
72
73
74
75 #define check_path_cycle(n, source, sink, pred) \
76 do { \
77 int i_, j_; \
78 check_int_eq(pred[source], -1); \
79 for (i_ = 0; i_ < n; ++i_) { \
80 check(pred[i_] >= -1); \
81 check(pred[i_] < n); \
82 } \
83 i_ = (sink); \
84 j_ = pred[(sink)]; \
85 while (i_ != -1 && j_ != -1) { \
86 check_msg(i_ != j_, "CYCLE DETECTED"); \
87 i_ = pred[i_]; \
88 j_ = pred[j_]; \
89 if (j_ != -1) { \
90 j_ = pred[j_]; \
91 } \
92 } \
93 } while (0)
94
95 static int v_cleanup_count = 0;
96 static int e_cleanup_count = 0;
97
98 static void v_cleanup(void *v_data)
99 {
100 ++v_cleanup_count;
101 }
102
103 static void e_cleanup(void *e_data)
104 {
105 ++e_cleanup_count;
106 }
107
108
109
110 static int cmp_int_pair(const void *a, const void *b)
111 {
112 int *ia = (int *)a;
113 int *ib = (int *)b;
114
115 if (ia[0] < ib[0]) {
116 return -1;
117 }
118 else if (ia[0] > ib[0]) {
119 return 1;
120 }
121 else {
122 if (ia[1] < ib[1]) {
123 return -1;
124 }
125 else if (ia[1] > ib[1]) {
126 return 1;
127 }
128 else {
129 return 0;
130 }
131 }
132 }
133
134
135
136 static double gettime(void)
137 {
138 double wtime;
139 struct timeval tv;
140 gettimeofday(&tv, NULL);
141 wtime = tv.tv_sec;
142 wtime += (double)tv.tv_usec / 1000000.0;
143
144 return wtime;
145 }
146
147 static int test_graph_create(void *ctx)
148 {
149 opal_bp_graph_t *g;
150 int i;
151 int err;
152 int user_data;
153 int index;
154
155
156 g = NULL;
157 err = opal_bp_graph_create(NULL, NULL, &g);
158 check_err_code(err, OPAL_SUCCESS);
159 check(g != NULL);
160 check(opal_bp_graph_order(g) == 0);
161 check_graph_is_consistent(g);
162 err = opal_bp_graph_free(g);
163 check_err_code(err, OPAL_SUCCESS);
164
165
166 g = NULL;
167 err = opal_bp_graph_create(NULL, NULL, &g);
168 check_err_code(err, OPAL_SUCCESS);
169 check(g != NULL);
170 check_graph_is_consistent(g);
171 for (i = 0; i < 4; ++i) {
172 index = -1;
173 err = opal_bp_graph_add_vertex(g, &user_data, &index);
174 check_err_code(err, OPAL_SUCCESS);
175 check(index == i);
176 }
177 check(opal_bp_graph_order(g) == 4);
178 check_graph_is_consistent(g);
179 err = opal_bp_graph_free(g);
180 check_err_code(err, OPAL_SUCCESS);
181
182
183 g = NULL;
184 v_cleanup_count = 0;
185 e_cleanup_count = 0;
186 err = opal_bp_graph_create(&v_cleanup, &e_cleanup, &g);
187 check_err_code(err, OPAL_SUCCESS);
188 check(g != NULL);
189 check_graph_is_consistent(g);
190 for (i = 0; i < 5; ++i) {
191 err = opal_bp_graph_add_vertex(g, &user_data, &index);
192 check_err_code(err, OPAL_SUCCESS);
193 check(index == i);
194 }
195 check(opal_bp_graph_order(g) == 5);
196 check_graph_is_consistent(g);
197 err = opal_bp_graph_add_edge(g, 0, 3, 1,
198 2, &user_data);
199 check_graph_is_consistent(g);
200 check(v_cleanup_count == 0);
201 check(e_cleanup_count == 0);
202 err = opal_bp_graph_free(g);
203 check_err_code(err, OPAL_SUCCESS);
204 check(v_cleanup_count == 5);
205 check(e_cleanup_count == 1);
206
207 return 0;
208 }
209
210 static int test_graph_clone(void *ctx)
211 {
212 opal_bp_graph_t *g, *gx;
213 int i;
214 int err;
215 int user_data;
216 int index;
217
218
219 g = NULL;
220 v_cleanup_count = 0;
221 e_cleanup_count = 0;
222 err = opal_bp_graph_create(&v_cleanup, &e_cleanup, &g);
223 check_err_code(err, OPAL_SUCCESS);
224 check(g != NULL);
225 check_graph_is_consistent(g);
226
227
228 for (i = 0; i < 5; ++i) {
229 err = opal_bp_graph_add_vertex(g, &user_data, &index);
230 check_err_code(err, OPAL_SUCCESS);
231 }
232 check(opal_bp_graph_order(g) == 5);
233 check_graph_is_consistent(g);
234
235
236 err = opal_bp_graph_add_edge(g, 0, 3, 1,
237 2, &user_data);
238 check_err_code(err, OPAL_SUCCESS);
239 check_graph_is_consistent(g);
240 err = opal_bp_graph_add_edge(g, 3, 1, 2,
241 100, &user_data);
242 check_err_code(err, OPAL_SUCCESS);
243 check_graph_is_consistent(g);
244
245
246 gx = NULL;
247 err = opal_bp_graph_clone(g, false, &gx);
248 check_err_code(err, OPAL_SUCCESS);
249 check(gx != NULL);
250
251
252 err = opal_bp_graph_free(gx);
253 check_err_code(err, OPAL_SUCCESS);
254 check(v_cleanup_count == 0);
255 check(e_cleanup_count == 0);
256 err = opal_bp_graph_free(g);
257 check_err_code(err, OPAL_SUCCESS);
258 check(v_cleanup_count == 5);
259 check(e_cleanup_count == 2);
260
261 return 0;
262 }
263
264 static int test_graph_accessors(void *ctx)
265 {
266 opal_bp_graph_t *g;
267 int i;
268 int err;
269
270
271 err = opal_bp_graph_create(NULL, NULL, &g);
272 check_err_code(err, OPAL_SUCCESS);
273 check(g != NULL);
274
275 for (i = 0; i < 4; ++i) {
276 err = opal_bp_graph_add_vertex(g, NULL, NULL);
277 check_err_code(err, OPAL_SUCCESS);
278
279 check(opal_bp_graph_indegree(g, i) == 0);
280 check(opal_bp_graph_outdegree(g, i) == 0);
281 }
282
283 check(opal_bp_graph_order(g) == 4);
284
285 err = opal_bp_graph_add_edge(g, 0, 2, 2,
286 1, NULL);
287 err = opal_bp_graph_add_edge(g, 0, 1, 2,
288 1, NULL);
289
290 check(opal_bp_graph_indegree(g, 0) == 0);
291 check(opal_bp_graph_outdegree(g, 0) == 2);
292 check(opal_bp_graph_indegree(g, 1) == 1);
293 check(opal_bp_graph_outdegree(g, 1) == 0);
294 check(opal_bp_graph_indegree(g, 2) == 1);
295 check(opal_bp_graph_outdegree(g, 2) == 0);
296 check(opal_bp_graph_indegree(g, 3) == 0);
297 check(opal_bp_graph_outdegree(g, 3) == 0);
298
299 err = opal_bp_graph_free(g);
300 check_err_code(err, OPAL_SUCCESS);
301
302 return 0;
303 }
304
305 static int test_graph_assignment_solver(void *ctx)
306 {
307 opal_bp_graph_t *g;
308 int i;
309 int err;
310 int nme;
311 int *me;
312 int iter;
313 double start, end;
314
315
316
317
318
319
320 err = opal_bp_graph_create(NULL, NULL, &g);
321 check_err_code(err, OPAL_SUCCESS);
322 check(g != NULL);
323
324 for (i = 0; i < 4; ++i) {
325 err = opal_bp_graph_add_vertex(g, NULL, NULL);
326 check_err_code(err, OPAL_SUCCESS);
327 }
328
329 err = opal_bp_graph_add_edge(g, 0, 2, 10,
330 1, NULL);
331 err = opal_bp_graph_add_edge(g, 1, 3, 2,
332 1, NULL);
333
334 me = NULL;
335 err = opal_bp_graph_solve_bipartite_assignment(g,
336 &nme,
337 &me);
338 check_err_code(err, OPAL_SUCCESS);
339 check_int_eq(nme, 2);
340 check(me != NULL);
341 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
342 check(me[0] == 0 && me[1] == 2);
343 check(me[2] == 1 && me[3] == 3);
344
345 err = opal_bp_graph_free(g);
346 check_err_code(err, OPAL_SUCCESS);
347
348
349
350
351
352
353
354
355 err = opal_bp_graph_create(NULL, NULL, &g);
356 check_err_code(err, OPAL_SUCCESS);
357 check(g != NULL);
358
359 for (i = 0; i < 5; ++i) {
360 err = opal_bp_graph_add_vertex(g, NULL, NULL);
361 check_err_code(err, OPAL_SUCCESS);
362 }
363
364 err = opal_bp_graph_add_edge(g, 0, 3, 10,
365 1, NULL);
366 check_err_code(err, OPAL_SUCCESS);
367 err = opal_bp_graph_add_edge(g, 1, 4, 2,
368 1, NULL);
369 check_err_code(err, OPAL_SUCCESS);
370 err = opal_bp_graph_add_edge(g, 2, 4, 1,
371 1, NULL);
372 check_err_code(err, OPAL_SUCCESS);
373
374 me = NULL;
375 err = opal_bp_graph_solve_bipartite_assignment(g,
376 &nme,
377 &me);
378 check_err_code(err, OPAL_SUCCESS);
379 check_int_eq(nme, 2);
380 check(me != NULL);
381 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
382 check(me[0] == 0 && me[1] == 3);
383 check(me[2] == 2 && me[3] == 4);
384 free(me);
385
386 err = opal_bp_graph_free(g);
387 check_err_code(err, OPAL_SUCCESS);
388
389
390
391
392
393
394
395
396
397 err = opal_bp_graph_create(NULL, NULL, &g);
398 check_err_code(err, OPAL_SUCCESS);
399 check(g != NULL);
400
401 for (i = 0; i < 4; ++i) {
402 err = opal_bp_graph_add_vertex(g, NULL, NULL);
403 check_err_code(err, OPAL_SUCCESS);
404 }
405
406 err = opal_bp_graph_add_edge(g, 0, 2, 10,
407 1, NULL);
408 check_err_code(err, OPAL_SUCCESS);
409 err = opal_bp_graph_add_edge(g, 0, 3, 1,
410 1, NULL);
411 check_err_code(err, OPAL_SUCCESS);
412 err = opal_bp_graph_add_edge(g, 1, 3, 5,
413 1, NULL);
414 check_err_code(err, OPAL_SUCCESS);
415
416 me = NULL;
417 err = opal_bp_graph_solve_bipartite_assignment(g,
418 &nme,
419 &me);
420 check_err_code(err, OPAL_SUCCESS);
421 check_int_eq(nme, 2);
422 check(me != NULL);
423 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
424 check(me[0] == 0 && me[1] == 2);
425 check(me[2] == 1 && me[3] == 3);
426 free(me);
427
428 err = opal_bp_graph_free(g);
429 check_err_code(err, OPAL_SUCCESS);
430
431
432
433
434
435
436
437
438 err = opal_bp_graph_create(NULL, NULL, &g);
439 check_err_code(err, OPAL_SUCCESS);
440 check(g != NULL);
441
442 for (i = 0; i < 4; ++i) {
443 err = opal_bp_graph_add_vertex(g, NULL, NULL);
444 check_err_code(err, OPAL_SUCCESS);
445 }
446
447 err = opal_bp_graph_add_edge(g, 0, 2, 10,
448 1, NULL);
449 check_err_code(err, OPAL_SUCCESS);
450 err = opal_bp_graph_add_edge(g, 1, 2, 1,
451 1, NULL);
452 check_err_code(err, OPAL_SUCCESS);
453 err = opal_bp_graph_add_edge(g, 1, 3, 5,
454 1, NULL);
455 check_err_code(err, OPAL_SUCCESS);
456
457 me = NULL;
458 err = opal_bp_graph_solve_bipartite_assignment(g,
459 &nme,
460 &me);
461 check_err_code(err, OPAL_SUCCESS);
462 check_int_eq(nme, 2);
463 check(me != NULL);
464 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
465 check(me[0] == 0 && me[1] == 2);
466 check(me[2] == 1 && me[3] == 3);
467 free(me);
468
469 err = opal_bp_graph_free(g);
470 check_err_code(err, OPAL_SUCCESS);
471
472
473
474
475
476
477
478
479 err = opal_bp_graph_create(NULL, NULL, &g);
480 check_err_code(err, OPAL_SUCCESS);
481 check(g != NULL);
482
483 for (i = 0; i < 4; ++i) {
484 err = opal_bp_graph_add_vertex(g, NULL, NULL);
485 check_err_code(err, OPAL_SUCCESS);
486 }
487
488 err = opal_bp_graph_add_edge(g, 0, 2, -1,
489 1, NULL);
490 check_err_code(err, OPAL_SUCCESS);
491 err = opal_bp_graph_add_edge(g, 0, 3, -10,
492 1, NULL);
493 check_err_code(err, OPAL_SUCCESS);
494 err = opal_bp_graph_add_edge(g, 1, 3, -5,
495 1, NULL);
496 check_err_code(err, OPAL_SUCCESS);
497
498 me = NULL;
499 err = opal_bp_graph_solve_bipartite_assignment(g,
500 &nme,
501 &me);
502 check_err_code(err, OPAL_SUCCESS);
503 check_int_eq(nme, 2);
504 check(me != NULL);
505 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
506 check(me[0] == 0 && me[1] == 2);
507 check(me[2] == 1 && me[3] == 3);
508 free(me);
509
510 err = opal_bp_graph_free(g);
511 check_err_code(err, OPAL_SUCCESS);
512
513
514
515
516
517
518
519
520
521
522 err = opal_bp_graph_create(NULL, NULL, &g);
523 check_err_code(err, OPAL_SUCCESS);
524 check(g != NULL);
525
526 for (i = 0; i < 5; ++i) {
527 err = opal_bp_graph_add_vertex(g, NULL, NULL);
528 check_err_code(err, OPAL_SUCCESS);
529 }
530
531 err = opal_bp_graph_add_edge(g, 0, 2, -1,
532 1, NULL);
533 check_err_code(err, OPAL_SUCCESS);
534 err = opal_bp_graph_add_edge(g, 0, 3, -10,
535 1, NULL);
536 check_err_code(err, OPAL_SUCCESS);
537 err = opal_bp_graph_add_edge(g, 1, 3, -5,
538 1, NULL);
539 check_err_code(err, OPAL_SUCCESS);
540
541 me = NULL;
542 err = opal_bp_graph_solve_bipartite_assignment(g,
543 &nme,
544 &me);
545 check_err_code(err, OPAL_SUCCESS);
546 check_int_eq(nme, 2);
547 check(me != NULL);
548 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
549 check(me[0] == 0 && me[1] == 2);
550 check(me[2] == 1 && me[3] == 3);
551 free(me);
552
553 err = opal_bp_graph_free(g);
554 check_err_code(err, OPAL_SUCCESS);
555
556
557
558
559
560
561
562
563
564 err = opal_bp_graph_create(NULL, NULL, &g);
565 check_err_code(err, OPAL_SUCCESS);
566 check(g != NULL);
567
568 for (i = 0; i < 4; ++i) {
569 err = opal_bp_graph_add_vertex(g, NULL, NULL);
570 check_err_code(err, OPAL_SUCCESS);
571 }
572
573 err = opal_bp_graph_add_edge(g, 0, 2, -4294967296,
574 1, NULL);
575 check_err_code(err, OPAL_SUCCESS);
576 err = opal_bp_graph_add_edge(g, 1, 2, -4294967296,
577 1, NULL);
578 check_err_code(err, OPAL_SUCCESS);
579 err = opal_bp_graph_add_edge(g, 0, 3, -4294967296,
580 1, NULL);
581 check_err_code(err, OPAL_SUCCESS);
582 err = opal_bp_graph_add_edge(g, 1, 3, -4294967296,
583 1, NULL);
584 check_err_code(err, OPAL_SUCCESS);
585
586 me = NULL;
587 err = opal_bp_graph_solve_bipartite_assignment(g,
588 &nme,
589 &me);
590 check_err_code(err, OPAL_SUCCESS);
591 check_int_eq(nme, 2);
592 check(me != NULL);
593 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
594 if (me[1] == 2) {
595 check(me[0] == 0 && me[1] == 2);
596 check(me[2] == 1 && me[3] == 3);
597 } else {
598 check(me[0] == 0 && me[1] == 3);
599 check(me[2] == 1 && me[3] == 2);
600 }
601 free(me);
602
603 err = opal_bp_graph_free(g);
604 check_err_code(err, OPAL_SUCCESS);
605
606
607
608
609
610
611
612 err = opal_bp_graph_create(NULL, NULL, &g);
613 check_err_code(err, OPAL_SUCCESS);
614 check(g != NULL);
615
616 for (i = 0; i < 3; ++i) {
617 err = opal_bp_graph_add_vertex(g, NULL, NULL);
618 check_err_code(err, OPAL_SUCCESS);
619 }
620
621 err = opal_bp_graph_add_edge(g, 0, 2, -100,
622 1, NULL);
623 err = opal_bp_graph_add_edge(g, 1, 2, -100,
624 1, NULL);
625
626 me = NULL;
627 err = opal_bp_graph_solve_bipartite_assignment(g,
628 &nme,
629 &me);
630 check_err_code(err, OPAL_SUCCESS);
631 check_int_eq(nme, 1);
632 check(me != NULL);
633 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
634 check((me[0] == 0 || me[0] == 1) && me[1] == 2);
635
636 err = opal_bp_graph_free(g);
637 check_err_code(err, OPAL_SUCCESS);
638
639
640
641
642
643
644
645
646
647
648 #define NUM_ITER (10000)
649 start = gettime();
650 for (iter = 0; iter < NUM_ITER; ++iter) {
651 err = opal_bp_graph_create(NULL, NULL, &g);
652 check_err_code(err, OPAL_SUCCESS);
653 check(g != NULL);
654
655 for (i = 0; i < 5; ++i) {
656 err = opal_bp_graph_add_vertex(g, NULL, NULL);
657 check_err_code(err, OPAL_SUCCESS);
658 }
659
660 err = opal_bp_graph_add_edge(g, 0, 3, 10,
661 1, NULL);
662 check_err_code(err, OPAL_SUCCESS);
663 err = opal_bp_graph_add_edge(g, 1, 4, 2,
664 1, NULL);
665 check_err_code(err, OPAL_SUCCESS);
666 err = opal_bp_graph_add_edge(g, 2, 4, 1,
667 1, NULL);
668 check_err_code(err, OPAL_SUCCESS);
669
670 me = NULL;
671 err = opal_bp_graph_solve_bipartite_assignment(g,
672 &nme,
673 &me);
674 check_err_code(err, OPAL_SUCCESS);
675 check_int_eq(nme, 2);
676 check(me != NULL);
677 qsort(me, nme, 2*sizeof(int), &cmp_int_pair);
678 check(me[0] == 0 && me[1] == 3);
679 check(me[2] == 2 && me[3] == 4);
680 free(me);
681
682 err = opal_bp_graph_free(g);
683 check_err_code(err, OPAL_SUCCESS);
684 }
685 end = gettime();
686
687 check(((end - start) / NUM_ITER) < 0.001);
688 #if 0
689 fprintf(stderr, "timing for %d iterations is %f seconds (%f s/iter)\n",
690 NUM_ITER, end - start, (end - start) / NUM_ITER);
691 #endif
692
693 return 0;
694 }
695
696 static int test_graph_bellman_ford(void *ctx)
697 {
698 opal_bp_graph_t *g;
699 int i;
700 int err;
701 bool path_found;
702 int *pred;
703
704
705
706
707
708
709
710
711
712
713 err = opal_bp_graph_create(NULL, NULL, &g);
714 check_err_code(err, OPAL_SUCCESS);
715 check(g != NULL);
716
717 for (i = 0; i < 6; ++i) {
718 err = opal_bp_graph_add_vertex(g, NULL, NULL);
719 check_err_code(err, OPAL_SUCCESS);
720 }
721
722 err = opal_bp_graph_add_edge(g, 0, 2, 10,
723 1, NULL);
724 check_err_code(err, OPAL_SUCCESS);
725 err = opal_bp_graph_add_edge(g, 1, 3, 2,
726 1, NULL);
727 check_err_code(err, OPAL_SUCCESS);
728 err = opal_bp_graph_add_edge(g, 4, 0, 0,
729 1, NULL);
730 check_err_code(err, OPAL_SUCCESS);
731 err = opal_bp_graph_add_edge(g, 4, 1, 0,
732 1, NULL);
733 check_err_code(err, OPAL_SUCCESS);
734 err = opal_bp_graph_add_edge(g, 2, 5, 0,
735 1, NULL);
736 check_err_code(err, OPAL_SUCCESS);
737 err = opal_bp_graph_add_edge(g, 3, 5, 0,
738 1, NULL);
739 check_err_code(err, OPAL_SUCCESS);
740
741 pred = malloc(6*sizeof(*pred));
742 check(pred != NULL);
743 path_found = opal_bp_graph_bellman_ford(g, 4, 5, pred);
744 check(path_found);
745 check_path_cycle(6, 4, 5, pred);
746 check_int_eq(pred[5], 3);
747 check_int_eq(pred[3], 1);
748 check_int_eq(pred[1], 4);
749 free(pred);
750
751 err = opal_bp_graph_free(g);
752 check_err_code(err, OPAL_SUCCESS);
753
754
755
756
757
758
759
760
761
762 err = opal_bp_graph_create(NULL, NULL, &g);
763 check_err_code(err, OPAL_SUCCESS);
764 check(g != NULL);
765
766 for (i = 0; i < 5; ++i) {
767 err = opal_bp_graph_add_vertex(g, NULL, NULL);
768 check_err_code(err, OPAL_SUCCESS);
769 }
770
771 err = opal_bp_graph_add_edge(g, 0, 3, 10,
772 1, NULL);
773 check_err_code(err, OPAL_SUCCESS);
774 err = opal_bp_graph_add_edge(g, 1, 4, 2,
775 1, NULL);
776 check_err_code(err, OPAL_SUCCESS);
777 err = opal_bp_graph_add_edge(g, 2, 4, 1,
778 1, NULL);
779 check_err_code(err, OPAL_SUCCESS);
780
781 err = opal_bp_graph_bipartite_to_flow(g);
782 check_err_code(err, OPAL_SUCCESS);
783
784 pred = malloc(7*sizeof(*pred));
785 check(pred != NULL);
786 path_found = opal_bp_graph_bellman_ford(g, 5, 6, pred);
787 check(path_found);
788 check_int_eq(g->source_idx, 5);
789 check_int_eq(g->sink_idx, 6);
790 check_path_cycle(7, 5, 6, pred);
791 check_int_eq(pred[6], 4);
792 check_int_eq(pred[4], 2);
793 check_int_eq(pred[2], 5);
794 free(pred);
795
796 err = opal_bp_graph_free(g);
797 check_err_code(err, OPAL_SUCCESS);
798
799
800
801
802
803
804
805
806 err = opal_bp_graph_create(NULL, NULL, &g);
807 check_err_code(err, OPAL_SUCCESS);
808 check(g != NULL);
809
810 for (i = 0; i < 5; ++i) {
811 err = opal_bp_graph_add_vertex(g, NULL, NULL);
812 check_err_code(err, OPAL_SUCCESS);
813 }
814
815 err = opal_bp_graph_add_edge(g, 0, 3, INT32_MAX+10LL,
816 1, NULL);
817 check_err_code(err, OPAL_SUCCESS);
818 err = opal_bp_graph_add_edge(g, 1, 4, INT32_MAX+2LL,
819 1, NULL);
820 check_err_code(err, OPAL_SUCCESS);
821 err = opal_bp_graph_add_edge(g, 2, 4, INT32_MAX+1LL,
822 1, NULL);
823 check_err_code(err, OPAL_SUCCESS);
824
825 err = opal_bp_graph_bipartite_to_flow(g);
826 check_err_code(err, OPAL_SUCCESS);
827
828 pred = malloc(7*sizeof(*pred));
829 check(pred != NULL);
830 path_found = opal_bp_graph_bellman_ford(g, 5, 6, pred);
831 check(path_found);
832 check_int_eq(g->source_idx, 5);
833 check_int_eq(g->sink_idx, 6);
834 check_path_cycle(7, 5, 6, pred);
835 check_int_eq(pred[6], 4);
836 check_int_eq(pred[4], 2);
837 check_int_eq(pred[2], 5);
838 free(pred);
839
840 err = opal_bp_graph_free(g);
841 check_err_code(err, OPAL_SUCCESS);
842
843
844
845
846
847
848
849
850
851 err = opal_bp_graph_create(NULL, NULL, &g);
852 check_err_code(err, OPAL_SUCCESS);
853 check(g != NULL);
854
855 for (i = 0; i < 5; ++i) {
856 err = opal_bp_graph_add_vertex(g, NULL, NULL);
857 check_err_code(err, OPAL_SUCCESS);
858 }
859
860 err = opal_bp_graph_add_edge(g, 0, 3, -1,
861 1, NULL);
862 check_err_code(err, OPAL_SUCCESS);
863 err = opal_bp_graph_add_edge(g, 1, 4, -2,
864 1, NULL);
865 check_err_code(err, OPAL_SUCCESS);
866 err = opal_bp_graph_add_edge(g, 2, 4, -10,
867 1, NULL);
868 check_err_code(err, OPAL_SUCCESS);
869
870 err = opal_bp_graph_bipartite_to_flow(g);
871 check_err_code(err, OPAL_SUCCESS);
872
873 pred = malloc(7*sizeof(*pred));
874 check(pred != NULL);
875 path_found = opal_bp_graph_bellman_ford(g, 5, 6, pred);
876 check(path_found);
877 check_int_eq(g->source_idx, 5);
878 check_int_eq(g->sink_idx, 6);
879 check_path_cycle(7, 5, 6, pred);
880 check_int_eq(pred[6], 4);
881 check_int_eq(pred[4], 2);
882 check_int_eq(pred[2], 5);
883 free(pred);
884
885 err = opal_bp_graph_free(g);
886 check_err_code(err, OPAL_SUCCESS);
887
888 return 0;
889 }
890
891 static int test_graph_flow_conversion(void *ctx)
892 {
893 opal_bp_graph_t *g;
894 int i;
895 int err;
896
897
898
899
900
901
902
903
904 err = opal_bp_graph_create(NULL, NULL, &g);
905 check_err_code(err, OPAL_SUCCESS);
906 check(g != NULL);
907
908 for (i = 0; i < 5; ++i) {
909 err = opal_bp_graph_add_vertex(g, NULL, NULL);
910 check_err_code(err, OPAL_SUCCESS);
911 }
912
913 err = opal_bp_graph_add_edge(g, 0, 3, 10,
914 1, NULL);
915 check_err_code(err, OPAL_SUCCESS);
916 err = opal_bp_graph_add_edge(g, 1, 4, 2,
917 1, NULL);
918 check_err_code(err, OPAL_SUCCESS);
919 err = opal_bp_graph_add_edge(g, 2, 4, 1,
920 1, NULL);
921 check_err_code(err, OPAL_SUCCESS);
922
923 check_int_eq(opal_bp_graph_order(g), 5);
924 check_has_in_out_degree(g, 0, 0, 1);
925 check_has_in_out_degree(g, 1, 0, 1);
926 check_has_in_out_degree(g, 2, 0, 1);
927 check_has_in_out_degree(g, 3, 1, 0);
928 check_has_in_out_degree(g, 4, 2, 0);
929
930
931 err = opal_bp_graph_bipartite_to_flow(g);
932 check_err_code(err, OPAL_SUCCESS);
933
934 check_int_eq(opal_bp_graph_order(g), 7);
935 check_has_in_out_degree(g, 0, 2, 2);
936 check_has_in_out_degree(g, 1, 2, 2);
937 check_has_in_out_degree(g, 2, 2, 2);
938 check_has_in_out_degree(g, 3, 2, 2);
939 check_has_in_out_degree(g, 4, 3, 3);
940 check_has_in_out_degree(g, 5, 3, 3);
941 check_has_in_out_degree(g, 6, 2, 2);
942
943 err = opal_bp_graph_free(g);
944 check_err_code(err, OPAL_SUCCESS);
945
946
947
948
949
950
951
952 err = opal_bp_graph_create(NULL, NULL, &g);
953 check_err_code(err, OPAL_SUCCESS);
954 check(g != NULL);
955 check_int_eq(opal_bp_graph_order(g), 0);
956 err = opal_bp_graph_bipartite_to_flow(g);
957 check_err_code(err, OPAL_ERR_BAD_PARAM);
958 err = opal_bp_graph_free(g);
959 check_err_code(err, OPAL_SUCCESS);
960
961 return 0;
962 }
963
964 static int test_graph_param_checking(void *ctx)
965 {
966 opal_bp_graph_t *g;
967 int i;
968 int err;
969
970 err = opal_bp_graph_create(NULL, NULL, &g);
971 check_err_code(err, OPAL_SUCCESS);
972 check(g != NULL);
973
974
975 err = opal_bp_graph_add_edge(g, 3, 5, 0,
976 1, NULL);
977 check_err_code(err, OPAL_ERR_BAD_PARAM);
978
979 for (i = 0; i < 6; ++i) {
980 err = opal_bp_graph_add_vertex(g, NULL, NULL);
981 check_err_code(err, OPAL_SUCCESS);
982 }
983
984
985 err = opal_bp_graph_add_edge(g, 9, 5, 0,
986 1, NULL);
987 check_err_code(err, OPAL_ERR_BAD_PARAM);
988 err = opal_bp_graph_add_edge(g, 6, 5, 0,
989 1, NULL);
990 check_err_code(err, OPAL_ERR_BAD_PARAM);
991
992
993 err = opal_bp_graph_add_edge(g, 2, 8, 0,
994 1, NULL);
995 check_err_code(err, OPAL_ERR_BAD_PARAM);
996 err = opal_bp_graph_add_edge(g, 2, 6, 0,
997 1, NULL);
998 check_err_code(err, OPAL_ERR_BAD_PARAM);
999
1000
1001 err = opal_bp_graph_add_edge(g, 2, 4, 0,
1002 1, NULL);
1003 check_err_code(err, OPAL_SUCCESS);
1004 err = opal_bp_graph_add_edge(g, 2, 4, 0,
1005 1, NULL);
1006 check_err_code(err, OPAL_EXISTS);
1007
1008
1009 err = opal_bp_graph_add_edge(g, 2, 3, INT64_MAX,
1010 1, NULL);
1011 check_err_code(err, OPAL_ERR_BAD_PARAM);
1012 err = opal_bp_graph_add_edge(g, 2, 3, INT64_MAX-1,
1013 1, NULL);
1014 check_err_code(err, OPAL_SUCCESS);
1015
1016 err = opal_bp_graph_free(g);
1017 check_err_code(err, OPAL_SUCCESS);
1018
1019 return 0;
1020 }
1021
1022 static int test_graph_helper_macros(void *ctx)
1023 {
1024 int u, v;
1025 int pred[6];
1026 bool visited[6][6];
1027 int pair1[2];
1028 int pair2[2];
1029
1030 #define RESET_ARRAYS(n, pred, visited) \
1031 do { \
1032 for (u = 0; u < 6; ++u) { \
1033 pred[u] = -1; \
1034 for (v = 0; v < 6; ++v) { \
1035 visited[u][v] = false; \
1036 } \
1037 } \
1038 } while (0)
1039
1040
1041
1042 RESET_ARRAYS(6, pred, visited);
1043 FOREACH_UV_ON_PATH(pred, 3, 5, u, v) {
1044 visited[u][v] = true;
1045 }
1046 for (u = 0; u < 6; ++u) {
1047 for (v = 0; v < 6; ++v) {
1048 check(visited[u][v] == false);
1049 }
1050 }
1051
1052
1053 RESET_ARRAYS(6, pred, visited);
1054 pred[5] = 2;
1055 pred[2] = 1;
1056 pred[1] = 3;
1057 FOREACH_UV_ON_PATH(pred, 3, 5, u, v) {
1058 visited[u][v] = true;
1059 }
1060 for (u = 0; u < 6; ++u) {
1061 for (v = 0; v < 6; ++v) {
1062 if ((u == 2 && v == 5) ||
1063 (u == 1 && v == 2) ||
1064 (u == 3 && v == 1)) {
1065 check(visited[u][v] == true);
1066 }
1067 else {
1068 check(visited[u][v] == false);
1069 }
1070 }
1071 }
1072
1073 #undef RESET_ARRAYS
1074
1075
1076
1077 pair1[0] = 0; pair1[1] = 1;
1078 pair2[0] = 0; pair2[1] = 1;
1079 check(cmp_int_pair(&pair1[0], &pair2[0]) == 0);
1080
1081 pair1[0] = 1; pair1[1] = 1;
1082 pair2[0] = 0; pair2[1] = 1;
1083 check(cmp_int_pair(pair1, pair2) > 0);
1084
1085 pair1[0] = 0; pair1[1] = 1;
1086 pair2[0] = 1; pair2[1] = 1;
1087 check(cmp_int_pair(pair1, pair2) < 0);
1088
1089 pair1[0] = 1; pair1[1] = 0;
1090 pair2[0] = 1; pair2[1] = 1;
1091 check(cmp_int_pair(pair1, pair2) < 0);
1092
1093 pair1[0] = 1; pair1[1] = 1;
1094 pair2[0] = 1; pair2[1] = 0;
1095 check(cmp_int_pair(pair1, pair2) > 0);
1096
1097 return 0;
1098 }
1099
1100 int main(int argc, char *argv[])
1101 {
1102 check(test_graph_create(NULL) == 0);
1103 check(test_graph_clone(NULL) == 0);
1104 check(test_graph_accessors(NULL) == 0);
1105 check(test_graph_assignment_solver(NULL) == 0);
1106 check(test_graph_bellman_ford(NULL) == 0);
1107 check(test_graph_flow_conversion(NULL) == 0);
1108 check(test_graph_param_checking(NULL) == 0);
1109 check(test_graph_helper_macros(NULL) == 0);
1110
1111 return 0;
1112 }