test/util/bipartite

/* [<][>][^][v][top][bottom][index][help] */
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  * Copyright (c) 2014      Cisco Systems, Inc.  All rights reserved.
   3  * $COPYRIGHT$
   4  *
   5  * Additional copyrights may follow
   6  *
   7  * $HEADER$
   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 /* just use check_int_eq for now, no public error code to string routine
  48  * exists (opal_err2str is static) */
  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 /* Check the given path for sanity and that it does not have a cycle.  Uses
  74  * the "racing pointers" approach for cycle checking. */
  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 /* a utility function for comparing integer pairs, useful for sorting the edge
 109  * list returned by opal_bp_graph_solve_bipartite_assignment */
 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 { /* ia[0] == ib[0] */
 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 /* Simple time function so that we don't have to deal with the
 135    complexity of finding mpi.h to use MPI_Wtime */
 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     /* TEST CASE: check zero-vertex case */
 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     /* TEST CASE: check nonzero-vertex case with no cleanup routines */
 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     /* TEST CASE: make sure cleanup routines are invoked properly */
 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, /*u=*/0, /*v=*/3, /*cost=*/1,
 198                                      /*capacity=*/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     /* TEST CASE: make sure that simple cloning works fine */
 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     /* add 5 edges */
 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     /* and two edges */
 236     err = opal_bp_graph_add_edge(g, /*u=*/0, /*v=*/3, /*cost=*/1,
 237                                      /*capacity=*/2, &user_data);
 238     check_err_code(err, OPAL_SUCCESS);
 239     check_graph_is_consistent(g);
 240     err = opal_bp_graph_add_edge(g, /*u=*/3, /*v=*/1, /*cost=*/2,
 241                                      /*capacity=*/100, &user_data);
 242     check_err_code(err, OPAL_SUCCESS);
 243     check_graph_is_consistent(g);
 244 
 245     /* now clone it and ensure that we get the same kind of graph */
 246     gx = NULL;
 247     err = opal_bp_graph_clone(g, /*copy_user_data=*/false, &gx);
 248     check_err_code(err, OPAL_SUCCESS);
 249     check(gx != NULL);
 250 
 251     /* double check that cleanups still happen as expected after cloning */
 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     /* TEST CASE: check _indegree/_outdegree/_order work correctly */
 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, /*u=*/0, /*v=*/2, /*cost=*/2,
 286                                      /*capacity=*/1, NULL);
 287     err = opal_bp_graph_add_edge(g, /*u=*/0, /*v=*/1, /*cost=*/2,
 288                                      /*capacity=*/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     /* TEST CASE: check that simple cases are solved correctly
 316      *
 317      * 0 --> 2
 318      * 1 --> 3
 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, /*u=*/0, /*v=*/2, /*cost=*/10,
 330                                      /*capacity=*/1, NULL);
 331     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/3, /*cost=*/2,
 332                                      /*capacity=*/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     /* TEST CASE: left side has more vertices than the right side
 350      *
 351      * 0 --> 3
 352      * 1 --> 4
 353      * 2 --> 4
 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, /*u=*/0, /*v=*/3, /*cost=*/10,
 365                                      /*capacity=*/1, NULL);
 366     check_err_code(err, OPAL_SUCCESS);
 367     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/4, /*cost=*/2,
 368                                      /*capacity=*/1, NULL);
 369     check_err_code(err, OPAL_SUCCESS);
 370     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/1,
 371                                      /*capacity=*/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     /* test Christian's case:
 391      * 0 --> 2
 392      * 0 --> 3
 393      * 1 --> 3
 394      *
 395      * make sure that 0-->2 & 1-->3 get chosen.
 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, /*u=*/0, /*v=*/2, /*cost=*/10,
 407                                      /*capacity=*/1, NULL);
 408     check_err_code(err, OPAL_SUCCESS);
 409     err = opal_bp_graph_add_edge(g, /*u=*/0, /*v=*/3, /*cost=*/1,
 410                                      /*capacity=*/1, NULL);
 411     check_err_code(err, OPAL_SUCCESS);
 412     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/3, /*cost=*/5,
 413                                      /*capacity=*/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     /* Also need to do this version of it to be safe:
 432      * 0 --> 2
 433      * 1 --> 2
 434      * 1 --> 3
 435      *
 436      * Should choose 0-->2 & 1-->3 here too.
 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, /*u=*/0, /*v=*/2, /*cost=*/10,
 448                                      /*capacity=*/1, NULL);
 449     check_err_code(err, OPAL_SUCCESS);
 450     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/2, /*cost=*/1,
 451                                      /*capacity=*/1, NULL);
 452     check_err_code(err, OPAL_SUCCESS);
 453     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/3, /*cost=*/5,
 454                                      /*capacity=*/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     /* TEST CASE: test Christian's case with negative weights:
 473      * 0 --> 2
 474      * 0 --> 3
 475      * 1 --> 3
 476      *
 477      * make sure that 0-->2 & 1-->3 get chosen.
 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, /*u=*/0, /*v=*/2, /*cost=*/-1,
 489                                      /*capacity=*/1, NULL);
 490     check_err_code(err, OPAL_SUCCESS);
 491     err = opal_bp_graph_add_edge(g, /*u=*/0, /*v=*/3, /*cost=*/-10,
 492                                      /*capacity=*/1, NULL);
 493     check_err_code(err, OPAL_SUCCESS);
 494     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/3, /*cost=*/-5,
 495                                      /*capacity=*/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     /* TEST CASE: add some disconnected vertices
 515      * 0 --> 2
 516      * 0 --> 3
 517      * 1 --> 3
 518      * x --> 4
 519      *
 520      * make sure that 0-->2 & 1-->3 get chosen.
 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, /*u=*/0, /*v=*/2, /*cost=*/-1,
 532                                      /*capacity=*/1, NULL);
 533     check_err_code(err, OPAL_SUCCESS);
 534     err = opal_bp_graph_add_edge(g, /*u=*/0, /*v=*/3, /*cost=*/-10,
 535                                      /*capacity=*/1, NULL);
 536     check_err_code(err, OPAL_SUCCESS);
 537     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/3, /*cost=*/-5,
 538                                      /*capacity=*/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     /* TEST CASE: sample UDP graph from bldsb005 + bldsb007
 557      * 0 --> 2 (cost -4294967296)
 558      * 1 --> 2 (cost -4294967296)
 559      * 0 --> 3 (cost -4294967296)
 560      * 1 --> 3 (cost -4294967296)
 561      *
 562      * Make sure that either (0-->2 && 1-->3) or (0-->3 && 1-->2) get chosen.
 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, /*u=*/0, /*v=*/2, /*cost=*/-4294967296,
 574                                      /*capacity=*/1, NULL);
 575     check_err_code(err, OPAL_SUCCESS);
 576     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/2, /*cost=*/-4294967296,
 577                                      /*capacity=*/1, NULL);
 578     check_err_code(err, OPAL_SUCCESS);
 579     err = opal_bp_graph_add_edge(g, /*u=*/0, /*v=*/3, /*cost=*/-4294967296,
 580                                      /*capacity=*/1, NULL);
 581     check_err_code(err, OPAL_SUCCESS);
 582     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/3, /*cost=*/-4294967296,
 583                                      /*capacity=*/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     /* TEST CASE: check that simple cases are solved correctly
 608      *
 609      * 0 --> 2
 610      * 1 --> 2
 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, /*u=*/0, /*v=*/2, /*cost=*/-100,
 622                                      /*capacity=*/1, NULL);
 623     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/2, /*cost=*/-100,
 624                                      /*capacity=*/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     /* TEST CASE: performance sanity check
 641      *
 642      * Construct this graph and ensure that it doesn't take too long on a large
 643      * cluster (1000 nodes).
 644      * 0 --> 3
 645      * 1 --> 4
 646      * 2 --> 4
 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, /*u=*/0, /*v=*/3, /*cost=*/10,
 661                                         /*capacity=*/1, NULL);
 662         check_err_code(err, OPAL_SUCCESS);
 663         err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/4, /*cost=*/2,
 664                                         /*capacity=*/1, NULL);
 665         check_err_code(err, OPAL_SUCCESS);
 666         err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/1,
 667                                         /*capacity=*/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     /* ensure that this operation on a 1000 node cluster will take less than one second */
 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     /* TEST CASE: check that simple cases are solved correctly
 705      *    -> 0 --> 2
 706      *   /           \
 707      * 4              --> 5
 708      *   \            /
 709      *    -> 1 --> 3 /
 710      *
 711      * should yield the path 5,1,3,6 (see costs in code below)
 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, /*u=*/0, /*v=*/2, /*cost=*/10,
 723                                      /*capacity=*/1, NULL);
 724     check_err_code(err, OPAL_SUCCESS);
 725     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/3, /*cost=*/2,
 726                                      /*capacity=*/1, NULL);
 727     check_err_code(err, OPAL_SUCCESS);
 728     err = opal_bp_graph_add_edge(g, /*u=*/4, /*v=*/0, /*cost=*/0,
 729                                      /*capacity=*/1, NULL);
 730     check_err_code(err, OPAL_SUCCESS);
 731     err = opal_bp_graph_add_edge(g, /*u=*/4, /*v=*/1, /*cost=*/0,
 732                                      /*capacity=*/1, NULL);
 733     check_err_code(err, OPAL_SUCCESS);
 734     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/5, /*cost=*/0,
 735                                      /*capacity=*/1, NULL);
 736     check_err_code(err, OPAL_SUCCESS);
 737     err = opal_bp_graph_add_edge(g, /*u=*/3, /*v=*/5, /*cost=*/0,
 738                                      /*capacity=*/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, /*source=*/4, /*target=*/5, pred);
 744     check(path_found);
 745     check_path_cycle(6, /*source=*/4, /*target=*/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     /* TEST CASE: left side has more vertices than the right side, then
 756      * convert to a flow network
 757      *
 758      * 0 --> 3
 759      * 1 --> 4
 760      * 2 --> 4
 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, /*u=*/0, /*v=*/3, /*cost=*/10,
 772                                      /*capacity=*/1, NULL);
 773     check_err_code(err, OPAL_SUCCESS);
 774     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/4, /*cost=*/2,
 775                                      /*capacity=*/1, NULL);
 776     check_err_code(err, OPAL_SUCCESS);
 777     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/1,
 778                                      /*capacity=*/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, /*source=*/5, /*target=*/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, /*source=*/5, /*target=*/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     /* TEST CASE: same as previous, but with very large cost values (try to
 800      * catch incorrect integer conversions)
 801      *
 802      * 0 --> 3
 803      * 1 --> 4
 804      * 2 --> 4
 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, /*u=*/0, /*v=*/3, /*cost=*/INT32_MAX+10LL,
 816                                      /*capacity=*/1, NULL);
 817     check_err_code(err, OPAL_SUCCESS);
 818     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/4, /*cost=*/INT32_MAX+2LL,
 819                                      /*capacity=*/1, NULL);
 820     check_err_code(err, OPAL_SUCCESS);
 821     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/INT32_MAX+1LL,
 822                                      /*capacity=*/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, /*source=*/5, /*target=*/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, /*source=*/5, /*target=*/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     /* TEST CASE: left side has more vertices than the right side, then
 844      * convert to a flow network.  Negative costs are used, but should not
 845      * result in a negative cycle.
 846      *
 847      * 0 --> 3
 848      * 1 --> 4
 849      * 2 --> 4
 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, /*u=*/0, /*v=*/3, /*cost=*/-1,
 861                                      /*capacity=*/1, NULL);
 862     check_err_code(err, OPAL_SUCCESS);
 863     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/4, /*cost=*/-2,
 864                                      /*capacity=*/1, NULL);
 865     check_err_code(err, OPAL_SUCCESS);
 866     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/-10,
 867                                      /*capacity=*/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, /*source=*/5, /*target=*/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, /*source=*/5, /*target=*/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     /* TEST CASE: left side has more vertices than the right side, then
 898      * convert to a flow network
 899      *
 900      * 0 --> 3
 901      * 1 --> 4
 902      * 2 --> 4
 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, /*u=*/0, /*v=*/3, /*cost=*/10,
 914                                      /*capacity=*/1, NULL);
 915     check_err_code(err, OPAL_SUCCESS);
 916     err = opal_bp_graph_add_edge(g, /*u=*/1, /*v=*/4, /*cost=*/2,
 917                                      /*capacity=*/1, NULL);
 918     check_err_code(err, OPAL_SUCCESS);
 919     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/1,
 920                                      /*capacity=*/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, /*exp_indeg=*/0, /*exp_outdeg=*/1);
 925     check_has_in_out_degree(g, 1, /*exp_indeg=*/0, /*exp_outdeg=*/1);
 926     check_has_in_out_degree(g, 2, /*exp_indeg=*/0, /*exp_outdeg=*/1);
 927     check_has_in_out_degree(g, 3, /*exp_indeg=*/1, /*exp_outdeg=*/0);
 928     check_has_in_out_degree(g, 4, /*exp_indeg=*/2, /*exp_outdeg=*/0);
 929 
 930     /* this should add two nodes and a bunch of edges */
 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, /*exp_indeg=*/2, /*exp_outdeg=*/2);
 936     check_has_in_out_degree(g, 1, /*exp_indeg=*/2, /*exp_outdeg=*/2);
 937     check_has_in_out_degree(g, 2, /*exp_indeg=*/2, /*exp_outdeg=*/2);
 938     check_has_in_out_degree(g, 3, /*exp_indeg=*/2, /*exp_outdeg=*/2);
 939     check_has_in_out_degree(g, 4, /*exp_indeg=*/3, /*exp_outdeg=*/3);
 940     check_has_in_out_degree(g, 5, /*exp_indeg=*/3, /*exp_outdeg=*/3);
 941     check_has_in_out_degree(g, 6, /*exp_indeg=*/2, /*exp_outdeg=*/2);
 942 
 943     err = opal_bp_graph_free(g);
 944     check_err_code(err, OPAL_SUCCESS);
 945 
 946 
 947     /* TEST CASE: empty graph
 948      *
 949      * there's no reason that the code should bother to support this, it's not
 950      * useful
 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     /* try with no vertices */
 975     err = opal_bp_graph_add_edge(g, /*u=*/3, /*v=*/5, /*cost=*/0,
 976                                      /*capacity=*/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     /* try u out of range */
 985     err = opal_bp_graph_add_edge(g, /*u=*/9, /*v=*/5, /*cost=*/0,
 986                                      /*capacity=*/1, NULL);
 987     check_err_code(err, OPAL_ERR_BAD_PARAM);
 988     err = opal_bp_graph_add_edge(g, /*u=*/6, /*v=*/5, /*cost=*/0,
 989                                      /*capacity=*/1, NULL);
 990     check_err_code(err, OPAL_ERR_BAD_PARAM);
 991 
 992     /* try v out of range */
 993     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/8, /*cost=*/0,
 994                                      /*capacity=*/1, NULL);
 995     check_err_code(err, OPAL_ERR_BAD_PARAM);
 996     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/6, /*cost=*/0,
 997                                      /*capacity=*/1, NULL);
 998     check_err_code(err, OPAL_ERR_BAD_PARAM);
 999 
1000     /* try adding an edge that already exists */
1001     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/0,
1002                                      /*capacity=*/1, NULL);
1003     check_err_code(err, OPAL_SUCCESS);
1004     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/4, /*cost=*/0,
1005                                      /*capacity=*/1, NULL);
1006     check_err_code(err, OPAL_EXISTS);
1007 
1008     /* try an edge with an out of range cost */
1009     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/3, /*cost=*/INT64_MAX,
1010                                      /*capacity=*/1, NULL);
1011     check_err_code(err, OPAL_ERR_BAD_PARAM);
1012     err = opal_bp_graph_add_edge(g, /*u=*/2, /*v=*/3, /*cost=*/INT64_MAX-1,
1013                                      /*capacity=*/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     /* TEST CASE: make sure that an empty path does not cause any edges to be
1041      * visited */
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     /* TEST CASE: make sure that every edge in the given path gets visited */
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     /* not technically a macro, but make sure that the pair comparison function
1076      * isn't broken (because it was in an earlier revision...) */
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 }
/* [<][>][^][v][top][bottom][index][help] */
root/test/util/bipartite_graph.c

DEFINITIONS
