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 }