root/opal/class/opal_graph.c

DEFINITIONS

1. opal_graph_vertex_construct
2. opal_graph_vertex_destruct
3. opal_graph_edge_construct
4. opal_graph_edge_destruct
5. opal_graph_construct
6. opal_graph_destruct
7. opal_adjacency_list_construct
8. opal_adjacency_list_destruct
9. delete_all_edges_conceded_to_vertex
10. opal_graph_add_vertex
11. opal_graph_add_edge
12. opal_graph_remove_edge
13. opal_graph_remove_vertex
14. opal_graph_adjacent
15. opal_graph_get_order
16. opal_graph_get_size
17. opal_graph_find_vertex
18. opal_graph_get_graph_vertices
19. opal_graph_get_adjacent_vertices
20. opal_graph_spf
21. compare_vertex_distance
22. opal_graph_dijkstra
23. opal_graph_duplicate
24. opal_graph_print

   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
   2 /*
   3  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   4  *                         University Research and Technology
   5  *                         Corporation.  All rights reserved.
   6  * Copyright (c) 2004-2012 The University of Tennessee and The University
   7  *                         of Tennessee Research Foundation.  All rights
   8  *                         reserved.
   9  * Copyright (c) 2004-2007 High Performance Computing Center Stuttgart,
  10  *                         University of Stuttgart.  All rights reserved.
  11  * Copyright (c) 2004-2005 The Regents of the University of California.
  12  *                         All rights reserved.
  13  * Copyright (c) 2007      Voltaire All rights reserved.
  14  * Copyright (c) 2016-2017 Los Alamos National Security, LLC. All rights
  15  *                         reserved.
  16  * Copyright (c) 2016 Cisco Systems, Inc.  All rights reserved.
  17  * $COPYRIGHT$
  18  *
  19  * Additional copyrights may follow
  20  *
  21  * $HEADER$
  22  */
  23 
  24 #include "opal_config.h"
  25 
  26 #include "opal/class/opal_list.h"
  27 #include "opal/constants.h"
  28 #include "opal/class/opal_graph.h"
  29 #include "opal/util/output.h"
  30 
  31 static int compare_vertex_distance(const void *item1, const void *item2);
  32 
  33 /*
  34  *  Graph classes
  35  */
  36 
  37 
  38 static void opal_graph_vertex_construct(opal_graph_vertex_t *vertex);
  39 static void opal_graph_vertex_destruct(opal_graph_vertex_t *vertex);
  40 
  41 OBJ_CLASS_INSTANCE(
  42     opal_graph_vertex_t,
  43     opal_list_item_t,
  44     opal_graph_vertex_construct,
  45     opal_graph_vertex_destruct
  46 );
  47 
  48 
  49 static void opal_graph_edge_construct(opal_graph_edge_t *edge);
  50 static void opal_graph_edge_destruct(opal_graph_edge_t *edge);
  51 
  52 OBJ_CLASS_INSTANCE(
  53     opal_graph_edge_t,
  54     opal_list_item_t,
  55     opal_graph_edge_construct,
  56     opal_graph_edge_destruct
  57 );
  58 
  59 static void opal_graph_construct(opal_graph_t *graph);
  60 static void opal_graph_destruct(opal_graph_t *graph);
  61 
  62 OBJ_CLASS_INSTANCE(
  63     opal_graph_t,
  64     opal_object_t,
  65     opal_graph_construct,
  66     opal_graph_destruct
  67 );
  68 
  69 static void opal_adjacency_list_construct(opal_adjacency_list_t *aj_list);
  70 static void opal_adjacency_list_destruct(opal_adjacency_list_t *aj_list);
  71 
  72 OBJ_CLASS_INSTANCE(
  73     opal_adjacency_list_t,
  74     opal_list_item_t,
  75     opal_adjacency_list_construct,
  76     opal_adjacency_list_destruct
  77 );
  78 
  79 
  80 
  81 /*
  82  *
  83  *      opal_graph_vertex_t interface
  84  *
  85  */
  86 
  87 static void opal_graph_vertex_construct(opal_graph_vertex_t *vertex)
  88 {
  89     vertex->in_adj_list = NULL;
  90     vertex->in_graph = NULL;
  91     vertex->vertex_data = NULL;
  92     vertex->sibling = NULL;
  93     vertex->copy_vertex_data = NULL;
  94     vertex->free_vertex_data = NULL;
  95     vertex->alloc_vertex_data = NULL;
  96     vertex->compare_vertex = NULL;
  97     vertex->print_vertex = NULL;
  98 }
  99 
 100 static void opal_graph_vertex_destruct(opal_graph_vertex_t *vertex)
 101 {
 102     vertex->in_adj_list = NULL;
 103     vertex->in_graph = NULL;
 104     vertex->sibling = NULL;
 105     vertex->copy_vertex_data = NULL;
 106     vertex->alloc_vertex_data = NULL;
 107     vertex->compare_vertex = NULL;
 108     if (NULL != vertex->free_vertex_data) {
 109         vertex->free_vertex_data(vertex->vertex_data);
 110     }
 111     vertex->vertex_data = NULL;
 112     vertex->print_vertex = NULL;
 113 }
 114 
 115 
 116 /*
 117  *
 118  *      opal_graph_edge_t interface
 119  *
 120  */
 121 
 122 static void opal_graph_edge_construct(opal_graph_edge_t *edge)
 123 {
 124     edge->end = NULL;
 125     edge->start = NULL;
 126     edge->weight = 0;
 127     edge->in_adj_list = NULL;
 128 }
 129 
 130 
 131 static void opal_graph_edge_destruct(opal_graph_edge_t *edge)
 132 {
 133     edge->end = NULL;
 134     edge->start = NULL;
 135     edge->weight = 0;
 136     edge->in_adj_list = NULL;
 137 }
 138 
 139 
 140 /*
 141  *
 142  *     opal_graph_t  interface
 143  *
 144  */
 145 
 146 
 147 static void opal_graph_construct(opal_graph_t *graph)
 148 {
 149     graph->adjacency_list = OBJ_NEW(opal_list_t);
 150     graph->number_of_vertices = 0;
 151     graph->number_of_edges = 0;
 152 }
 153 
 154 static void opal_graph_destruct(opal_graph_t *graph)
 155 {
 156     OPAL_LIST_RELEASE(graph->adjacency_list);
 157     graph->number_of_vertices = 0;
 158     graph->number_of_edges = 0;
 159 }
 160 
 161 /*
 162  *
 163  *     opal_adjacency_list  interface
 164  *
 165  */
 166 
 167 static void opal_adjacency_list_construct(opal_adjacency_list_t *aj_list)
 168 {
 169     aj_list->vertex = NULL;
 170     aj_list->edges = OBJ_NEW(opal_list_t);
 171 }
 172 
 173 static void opal_adjacency_list_destruct(opal_adjacency_list_t *aj_list)
 174 {
 175    aj_list->vertex = NULL;
 176    OPAL_LIST_RELEASE(aj_list->edges);
 177 }
 178 
 179 /**
 180  * This function deletes all the edges that are connected *to* a
 181  * vertex.
 182  *
 183  * @param graph
 184  * @param vertex
 185  */
 186 static void delete_all_edges_conceded_to_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex)
 187 {
 188     opal_adjacency_list_t *aj_list;
 189     opal_graph_edge_t *edge, *next;
 190 
 191     /**
 192      * for all the adjacency list in the graph
 193      */
 194     OPAL_LIST_FOREACH(aj_list, graph->adjacency_list, opal_adjacency_list_t) {
 195         /**
 196          * for all the edges in the adjacency list
 197          */
 198         OPAL_LIST_FOREACH_SAFE(edge, next, aj_list->edges, opal_graph_edge_t) {
 199             /**
 200              * if the edge is ended in the vertex
 201              */
 202             if (edge->end == vertex) {
 203                 /* Delete this edge  */
 204                 opal_list_remove_item(edge->in_adj_list->edges, (opal_list_item_t*)edge);
 205                 /* distract this edge */
 206                 OBJ_RELEASE(edge);
 207             }
 208         }
 209     }
 210 }
 211 
 212 /**
 213  * This graph API adds a vertex to graph. The most common use
 214  * for this API is while building a graph.
 215  *
 216  * @param graph The graph that the vertex will be added to.
 217  * @param vertex The vertex we want to add.
 218  */
 219 void opal_graph_add_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex)
 220 {
 221    opal_adjacency_list_t *aj_list;
 222 
 223    /**
 224     * Find if this vertex already exists in the graph.
 225     */
 226    OPAL_LIST_FOREACH(aj_list, graph->adjacency_list, opal_adjacency_list_t) {
 227        if (aj_list->vertex == vertex) {
 228            /* If this vertex exists, dont do anything. */
 229            return;
 230        }
 231    }
 232    /* Construct a new adjacency list */
 233    aj_list = OBJ_NEW(opal_adjacency_list_t);
 234    aj_list->vertex = vertex;
 235    /* point the vertex to the adjacency list of the vertex (for easy searching) */
 236    vertex->in_adj_list = aj_list;
 237    /* Append the new creates adjacency list to the graph */
 238    opal_list_append(graph->adjacency_list, (opal_list_item_t*)aj_list);
 239    /* point the vertex to the graph it belongs to (mostly for debug uses)*/
 240    vertex->in_graph = graph;
 241    /* increase the number of vertices in the graph */
 242    graph->number_of_vertices++;
 243 }
 244 
 245 
 246 /**
 247  * This graph API adds an edge (connection between two
 248  * vertices) to a graph. The most common use
 249  * for this API is while building a graph.
 250  *
 251  * @param graph The graph that this edge will be added to.
 252  * @param edge The edge that we want to add.
 253  *
 254  * @return int Success or error. this API can return an error if
 255  *         one of the vertices is not in the graph.
 256  */
 257 int opal_graph_add_edge(opal_graph_t *graph, opal_graph_edge_t *edge)
 258 {
 259     opal_adjacency_list_t *aj_list, *start_aj_list= NULL;
 260     bool end_found = false;
 261 
 262 
 263     /**
 264      * find the vertices that this edge should connect.
 265      */
 266     OPAL_LIST_FOREACH(aj_list, graph->adjacency_list, opal_adjacency_list_t) {
 267         if (aj_list->vertex == edge->start) {
 268             start_aj_list = aj_list;
 269         }
 270         if (aj_list->vertex == edge->end) {
 271             end_found = true;
 272         }
 273     }
 274     /**
 275      * if one of the vertices either the start or the end is not
 276      * found - return an error.
 277      */
 278     if (NULL == start_aj_list || false == end_found) {
 279         return OPAL_ERROR;
 280     }
 281     /* point the edge to the adjacency list of the start vertex (for easy search) */
 282     edge->in_adj_list=start_aj_list;
 283     /* append the edge to the adjacency list of the start vertex */
 284     opal_list_append(start_aj_list->edges, (opal_list_item_t*)edge);
 285     /* increase the graph size */
 286     graph->number_of_edges++;
 287     return OPAL_SUCCESS;
 288 }
 289 
 290 
 291 /**
 292  * This graph API removes an edge (a connection between two
 293  * vertices) from the graph. The most common use of this API is
 294  * while destructing a graph or while removing vertices from a
 295  * graph. while removing vertices from a graph, we should also
 296  * remove the connections from and to the vertices that we are
 297  * removing.
 298  *
 299  * @param graph The graph that this edge will be remove from.
 300  * @param edge the edge that we want to remove.
 301  */
 302 void opal_graph_remove_edge (opal_graph_t *graph, opal_graph_edge_t *edge)
 303 {
 304     /* remove the edge from the list it belongs to */
 305     opal_list_remove_item(edge->in_adj_list->edges, (opal_list_item_t*)edge);
 306     /* decrees the number of edges in the graph */
 307     graph->number_of_edges--;
 308     /* Note that the edge is not destructed - the caller should destruct this edge. */
 309 }
 310 
 311 /**
 312  * This graph API remove a vertex from graph. The most common
 313  * use for this API is while distracting a graph or while
 314  * removing relevant vertices from a graph.
 315  *
 316  * @param graph The graph that the vertex will be remove from.
 317  * @param vertex The vertex we want to remove.
 318  */
 319 
 320 void opal_graph_remove_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex)
 321 {
 322     opal_adjacency_list_t *adj_list;
 323 
 324     /* do not need to remove all the edges of this vertex and destruct them as
 325      * they will be released in the destructor for adj_list */
 326     adj_list = vertex->in_adj_list;
 327     /**
 328      * remove the adjscency list of this vertex from the graph and
 329      * destruct it.
 330      */
 331     opal_list_remove_item(graph->adjacency_list, (opal_list_item_t*)adj_list);
 332     OBJ_RELEASE(adj_list);
 333     /**
 334      * delete all the edges that connected *to* the vertex.
 335      */
 336     delete_all_edges_conceded_to_vertex(graph, vertex);
 337     /* destruct the vertex */
 338     OBJ_RELEASE(vertex);
 339     /* decrease the number of vertices in the graph. */
 340     graph->number_of_vertices--;
 341 }
 342 
 343 /**
 344  * This graph API tell us if two vertices are adjacent
 345  *
 346  * @param graph The graph that the vertices belongs to.
 347  * @param vertex1 first vertex.
 348  * @param vertex2 second vertex.
 349  *
 350  * @return uint32_t the weight of the connection between the two
 351  *         vertices or infinity if the vertices are not
 352  *         connected.
 353  */
 354 uint32_t opal_graph_adjacent(opal_graph_t *graph, opal_graph_vertex_t *vertex1, opal_graph_vertex_t *vertex2)
 355 {
 356     opal_adjacency_list_t *adj_list;
 357     opal_graph_edge_t *edge;
 358 
 359     /**
 360      * Verify that the first vertex belongs to the graph.
 361      */
 362     if (graph != vertex1->in_graph) {
 363         OPAL_OUTPUT((0,"opal_graph_adjacent 1 Vertex1 %p not in the graph %p\n",(void *)vertex1,(void *)graph));
 364         return DISTANCE_INFINITY;
 365     }
 366     /**
 367      * Verify that the second vertex belongs to the graph.
 368      */
 369     if (graph != vertex2->in_graph) {
 370         OPAL_OUTPUT((0,"opal_graph_adjacent 2 Vertex2 %p not in the graph %p\n",(void *)vertex2,(void *)graph));
 371         return DISTANCE_INFINITY;
 372     }
 373     /**
 374      * If the first vertex and the second vertex are the same
 375      * vertex, the distance between the is 0.
 376      */
 377     if (vertex1 == vertex2) {
 378         return 0;
 379     }
 380     /**
 381      * find the second vertex in the adjacency list of the first
 382      * vertex.
 383      */
 384     adj_list = (opal_adjacency_list_t *) vertex1->in_adj_list;
 385     OPAL_LIST_FOREACH(edge, adj_list->edges, opal_graph_edge_t) {
 386         if (edge->end == vertex2) {
 387             /* if the second vertex was found in the adjacency list of the first one, return the weight */
 388             return edge->weight;
 389         }
 390     }
 391     /* if the second vertex was not found in the adjacency list of the first one, return infinity */
 392     return DISTANCE_INFINITY;
 393 }
 394 
 395 /**
 396  * This Graph API returns the order of the graph (number of
 397  * vertices)
 398  *
 399  * @param graph
 400  *
 401  * @return int
 402  */
 403 int opal_graph_get_order(opal_graph_t *graph)
 404 {
 405     return graph->number_of_vertices;
 406 }
 407 
 408 /**
 409  * This Graph API returns the size of the graph (number of
 410  * edges)
 411  *
 412  * @param graph
 413  *
 414  * @return int
 415  */
 416 int opal_graph_get_size(opal_graph_t *graph)
 417 {
 418     return graph->number_of_edges;
 419 }
 420 
 421 /**
 422  * This graph API finds a vertex in the graph according the
 423  * vertex data.
 424  * @param graph the graph we searching in.
 425  * @param vertex_data the vertex data we are searching according
 426  *                    to.
 427  *
 428  * @return opal_graph_vertex_t* The vertex founded or NULL.
 429  */
 430 opal_graph_vertex_t *opal_graph_find_vertex(opal_graph_t *graph, void *vertex_data)
 431 {
 432     opal_adjacency_list_t *aj_list;
 433 
 434     /**
 435      * Run on all the vertices of the graph
 436      */
 437     OPAL_LIST_FOREACH(aj_list, graph->adjacency_list, opal_adjacency_list_t) {
 438         if (NULL != aj_list->vertex->compare_vertex) {
 439             /* if the vertex data of a vertex is equal to the vertex data */
 440             if (0 == aj_list->vertex->compare_vertex(aj_list->vertex->vertex_data, vertex_data)) {
 441                 /* return the found vertex */
 442                 return aj_list->vertex;
 443             }
 444         }
 445     }
 446     /* if a vertex is not found, return NULL */
 447     return NULL;
 448 }
 449 
 450 
 451 /**
 452  * This graph API returns an array of pointers of all the
 453  * vertices in the graph.
 454  *
 455  *
 456  * @param graph
 457  * @param vertices_list an array of pointers of all the
 458  *         vertices in the graph vertices.
 459  *
 460  * @return int returning the graph order (the
 461  *                    number of vertices in the returned array)
 462  */
 463 int opal_graph_get_graph_vertices(opal_graph_t *graph, opal_pointer_array_t *vertices_list)
 464 {
 465     opal_adjacency_list_t *aj_list;
 466 
 467     /**
 468      * If the graph order is 0, return NULL.
 469      */
 470     if (0 == graph->number_of_vertices) {
 471         return 0;
 472     }
 473     /* Run on all the vertices of the graph */
 474     OPAL_LIST_FOREACH(aj_list, graph->adjacency_list, opal_adjacency_list_t) {
 475         /* Add the vertex to the vertices array */
 476         opal_pointer_array_add(vertices_list,(void *)aj_list->vertex);
 477     }
 478     /* return the vertices list */
 479     return graph->number_of_vertices;
 480 }
 481 
 482 /**
 483  * This graph API returns all the adjacents of a vertex and the
 484  * distance (weight) of those adjacents and the vertex.
 485  *
 486  * @param graph
 487  * @param vertex The reference vertex
 488  * @param adjacents An allocated pointer array of vertices and
 489  *                  their distance from the reference vertex.
 490  *                  Note that this pointer should be free after
 491  *                  usage by the user
 492  *
 493  * @return int the number of adjacents in the list.
 494  */
 495 int opal_graph_get_adjacent_vertices(opal_graph_t *graph, opal_graph_vertex_t *vertex, opal_value_array_t *adjacents)
 496 {
 497     opal_adjacency_list_t *adj_list;
 498     opal_graph_edge_t *edge;
 499     int adjacents_number;
 500     vertex_distance_from_t distance_from;
 501 
 502     /**
 503      * Verify that the vertex belongs to the graph.
 504      */
 505     if (graph != vertex->in_graph) {
 506         OPAL_OUTPUT((0,"Vertex %p not in the graph %p\n", (void *)vertex, (void *)graph));
 507         return 0;
 508     }
 509     /**
 510      * find the adjacency list that this vertex belongs to
 511      */
 512     adj_list = (opal_adjacency_list_t *) vertex->in_adj_list;
 513     /* find the number of adjcents of this vertex */
 514     adjacents_number = opal_list_get_size(adj_list->edges);
 515     /* Run on all the edges from this vertex */
 516     OPAL_LIST_FOREACH(edge, adj_list->edges, opal_graph_edge_t) {
 517         /* assign vertices and their weight in the adjcents list */
 518         distance_from.vertex = edge->end;
 519         distance_from.weight = edge->weight;
 520         opal_value_array_append_item(adjacents, &distance_from);
 521     }
 522     /* return the number of the adjacents in the list */
 523     return adjacents_number;
 524 }
 525 
 526 /**
 527  * This graph API finds the shortest path between two vertices.
 528  *
 529  * @param graph
 530  * @param vertex1 The start vertex.
 531  * @param vertex2 The end vertex.
 532  *
 533  * @return uint32_t the distance between the two vertices.
 534  */
 535 
 536 uint32_t opal_graph_spf(opal_graph_t *graph, opal_graph_vertex_t *vertex1, opal_graph_vertex_t *vertex2)
 537 {
 538     opal_value_array_t *distance_array;
 539     uint32_t items_in_distance_array, spf = DISTANCE_INFINITY;
 540     vertex_distance_from_t *vertex_distance;
 541     uint32_t i;
 542 
 543     /**
 544      * Verify that the first vertex belongs to the graph.
 545      */
 546     if (graph != vertex1->in_graph) {
 547         OPAL_OUTPUT((0,"opal_graph_spf 1 Vertex1 %p not in the graph %p\n",(void *)vertex1,(void *)graph));
 548         return DISTANCE_INFINITY;
 549     }
 550     /**
 551      * Verify that the second vertex belongs to the graph.
 552      */
 553     if (graph != vertex2->in_graph) {
 554         OPAL_OUTPUT((0,"opal_graph_spf 2 Vertex2 %p not in the graph %p\n",(void *)vertex2,(void *)graph));
 555         return DISTANCE_INFINITY;
 556     }
 557     /**
 558      * Run Dijkstra algorithm on the graph from the start vertex.
 559      */
 560     distance_array = OBJ_NEW(opal_value_array_t);
 561     opal_value_array_init(distance_array, sizeof(vertex_distance_from_t));
 562     opal_value_array_reserve(distance_array,50);
 563     items_in_distance_array = opal_graph_dijkstra(graph, vertex1, distance_array);
 564     /**
 565      * find the end vertex in the distance array that Dijkstra
 566      * algorithm returned.
 567      */
 568     for (i = 0; i < items_in_distance_array; i++) {
 569         vertex_distance = opal_value_array_get_item(distance_array, i);
 570         if (vertex_distance->vertex == vertex2) {
 571             spf = vertex_distance->weight;
 572             break;
 573         }
 574     }
 575     OBJ_RELEASE(distance_array);
 576     /* return the distance (weight) to the end vertex */
 577     return spf;
 578 }
 579 
 580 /**
 581  * Compare the distance between two vertex distance items. this
 582  * function is used for sorting an array of vertices distance by
 583  * qsort function.
 584  *
 585  * @param item1 a void pointer to vertex distance structure
 586  * @param item2 a void pointer to vertex distance structure
 587  *
 588  * @return int 1 - the first item weight is higher then the
 589  *         second item weight. 0 - the weights are equal. -1 -
 590  *         the second item weight is higher the the first item
 591  *         weight.
 592  */
 593 static int compare_vertex_distance(const void *item1, const void *item2)
 594 {
 595     vertex_distance_from_t *vertex_dist1, *vertex_dist2;
 596 
 597     /* convert the void pointers to vertex distance pointers. */
 598     vertex_dist1 = (vertex_distance_from_t *)item1;
 599     vertex_dist2 = (vertex_distance_from_t *)item2;
 600 
 601     /* If the first item weight is higher then the second item weight return 1*/
 602     if (vertex_dist1->weight > vertex_dist2->weight) {
 603         return 1;
 604     }
 605     /* If they are equal return 0 */
 606     else if (vertex_dist1->weight == vertex_dist2->weight) {
 607         return 0;
 608     }
 609     /* if you reached here then the second item weight is higher the the first item weight */
 610     return -1;
 611 }
 612 
 613 
 614 /**
 615  * This graph API returns the distance (weight) from a reference
 616  * vertex to all other vertices in the graph using the Dijkstra
 617  * algorithm
 618  *
 619  * @param graph
 620  * @param vertex The reference vertex.
 621  * @param distance_array An array of vertices and
 622  *         their distance from the reference vertex.
 623  *
 624  * @return uint32_t the size of the distance array
 625  */
 626 uint32_t opal_graph_dijkstra(opal_graph_t *graph, opal_graph_vertex_t *vertex, opal_value_array_t *distance_array)
 627 {
 628     int graph_order;
 629     vertex_distance_from_t *Q, *q_start, *current_vertex;
 630     opal_adjacency_list_t *adj_list;
 631     int number_of_items_in_q;
 632     int i;
 633     uint32_t weight;
 634 
 635 
 636     /**
 637      * Verify that the reference vertex belongs to the graph.
 638      */
 639     if (graph != vertex->in_graph) {
 640         OPAL_OUTPUT((0,"opal:graph:dijkstra: vertex %p not in the graph %p\n",(void *)vertex,(void *)graph));
 641         return 0;
 642     }
 643     /* get the order of the graph and allocate a working queue accordingly */
 644     graph_order = opal_graph_get_order(graph);
 645     Q = (vertex_distance_from_t *)malloc(graph_order * sizeof(vertex_distance_from_t));
 646     /* assign a pointer to the start of the queue */
 647     q_start = Q;
 648     /* run on all the vertices of the graph */
 649     i = 0;
 650     OPAL_LIST_FOREACH(adj_list, graph->adjacency_list, opal_adjacency_list_t) {
 651         /* insert the vertices pointes to the working queue */
 652         Q[i].vertex = adj_list->vertex;
 653         /**
 654          * assign an infinity distance to all the vertices in the queue
 655          * except the reference vertex which its distance should be 0.
 656          */
 657         Q[i++].weight = (adj_list->vertex == vertex) ? 0 : DISTANCE_INFINITY;
 658     }
 659     number_of_items_in_q = i;
 660     /* sort the working queue according the distance from the reference vertex */
 661     qsort(q_start, number_of_items_in_q, sizeof(vertex_distance_from_t), compare_vertex_distance);
 662     /* while the working queue is not empty */
 663     while (number_of_items_in_q > 0) {
 664         /* start to work with the first vertex in the working queue */
 665         current_vertex = q_start;
 666         /* remove the first vertex from the queue */
 667         q_start++;
 668         /* decrees the number of vertices in the queue */
 669         number_of_items_in_q--;
 670         /* find the distance of all other vertices in the queue from the first vertex in the queue */
 671         for (i = 0; i < number_of_items_in_q; i++) {
 672             weight = opal_graph_adjacent(graph, current_vertex->vertex, q_start[i].vertex);
 673             /**
 674              * if the distance from the first vertex in the queue to the I
 675              * vertex in the queue plus the distance of the first vertex in
 676              * the queue from the referenced vertex is smaller than the
 677              * distance of the I vertex from the referenced vertex, assign
 678              * the lower distance to the I vertex.
 679              */
 680             if (current_vertex->weight + weight < q_start[i].weight) {
 681                 q_start[i].weight = weight + current_vertex->weight;
 682             }
 683         }
 684         /* sort again the working queue */
 685         qsort(q_start, number_of_items_in_q, sizeof(vertex_distance_from_t), compare_vertex_distance);
 686     }
 687     /* copy the working queue the the returned distance array */
 688     for (i = 0; i < graph_order-1; i++) {
 689         opal_value_array_append_item(distance_array, (void *)&(Q[i+1]));
 690     }
 691     /* free the working queue */
 692     free(Q);
 693     /* assign the distance array size. */
 694     return graph_order - 1;
 695 }
 696 
 697 
 698 /**
 699  * This graph API duplicates a graph. Note that this API does
 700  * not copy the graph but builds a new graph while coping just
 701  * the vertex data.
 702  *
 703  * @param dest The new created graph.
 704  * @param src The graph we want to duplicate.
 705  */
 706 void opal_graph_duplicate(opal_graph_t **dest, opal_graph_t *src)
 707 {
 708     opal_adjacency_list_t *aj_list;
 709     opal_graph_vertex_t *vertex;
 710     opal_graph_edge_t *edge, *new_edge;
 711 
 712     /* construct a new graph */
 713     *dest = OBJ_NEW(opal_graph_t);
 714     /* Run on all the vertices of the src graph */
 715     OPAL_LIST_FOREACH(aj_list, src->adjacency_list, opal_adjacency_list_t) {
 716         /* for each vertex in the src graph, construct a new vertex */
 717         vertex = OBJ_NEW(opal_graph_vertex_t);
 718         /* associate the new vertex to a vertex from the original graph */
 719         vertex->sibling = aj_list->vertex;
 720         /* associate the original vertex to the new constructed vertex */
 721         aj_list->vertex->sibling = vertex;
 722         /* allocate space to vertex data in the new vertex */
 723         if (NULL != aj_list->vertex->alloc_vertex_data) {
 724             vertex->vertex_data = aj_list->vertex->alloc_vertex_data();
 725             vertex->alloc_vertex_data = aj_list->vertex->alloc_vertex_data;
 726         }
 727         /* copy the vertex data from the original vertex  to the new vertex */
 728         if (NULL != aj_list->vertex->copy_vertex_data) {
 729             aj_list->vertex->copy_vertex_data(&(vertex->vertex_data), aj_list->vertex->vertex_data);
 730             vertex->copy_vertex_data = aj_list->vertex->copy_vertex_data;
 731         }
 732         /* copy all the fields of the original vertex to the new vertex. */
 733         vertex->free_vertex_data = aj_list->vertex->free_vertex_data;
 734         vertex->print_vertex = aj_list->vertex->print_vertex;
 735         vertex->compare_vertex = aj_list->vertex->compare_vertex;
 736         vertex->in_graph = *dest;
 737         /* add the new vertex to the new graph */
 738         opal_graph_add_vertex(*dest, vertex);
 739     }
 740     /**
 741      * Now, copy all the edges from the source graph
 742      */
 743     /* Run on all the adjscency lists in the graph */
 744     OPAL_LIST_FOREACH(aj_list, src->adjacency_list, opal_adjacency_list_t) {
 745         /* for all the edges in the adjscency list */
 746         OPAL_LIST_FOREACH(edge, aj_list->edges, opal_graph_edge_t) {
 747             /* construct new edge for the new graph */
 748             new_edge = OBJ_NEW(opal_graph_edge_t);
 749             /* copy the edge weight from the original edge */
 750             new_edge->weight = edge->weight;
 751             /* connect the new edge according to start and end associations to the vertices of the src graph */
 752             new_edge->start = edge->start->sibling;
 753             new_edge->end = edge->end->sibling;
 754             /* add the new edge to the new graph */
 755             opal_graph_add_edge(*dest, new_edge);
 756         }
 757     }
 758 }
 759 
 760 /**
 761  * This graph API prints a graph - mostly for debug uses.
 762  * @param graph
 763  */
 764 void opal_graph_print(opal_graph_t *graph)
 765 {
 766     opal_adjacency_list_t *aj_list;
 767     opal_graph_edge_t *edge;
 768     char *tmp_str1, *tmp_str2;
 769     bool need_free1, need_free2;
 770 
 771     /* print header */
 772     opal_output(0, "      Graph         ");
 773     opal_output(0, "====================");
 774     /* run on all the vertices of the graph */
 775     OPAL_LIST_FOREACH(aj_list, graph->adjacency_list, opal_adjacency_list_t) {
 776         /* print vertex data to temporary string*/
 777         if (NULL != aj_list->vertex->print_vertex) {
 778             need_free1 = true;
 779             tmp_str1 = aj_list->vertex->print_vertex(aj_list->vertex->vertex_data);
 780         }
 781         else {
 782             need_free1 = false;
 783             tmp_str1 = "";
 784         }
 785         /* print vertex */
 786         opal_output(0, "V(%s) Connections:",tmp_str1);
 787         /* run on all the edges of the vertex */
 788         OPAL_LIST_FOREACH(edge, aj_list->edges, opal_graph_edge_t) {
 789             /* print the vertex data of the vertex in the end of the edge to a temporary string */
 790             if (NULL != edge->end->print_vertex) {
 791                 need_free2 = true;
 792                 tmp_str2 = edge->end->print_vertex(edge->end->vertex_data);
 793             }
 794             else {
 795                 need_free2 = false;
 796                 tmp_str2 = "";
 797             }
 798             /* print the edge */
 799             opal_output(0, "    E(%s -> %d -> %s)",tmp_str1, edge->weight, tmp_str2);
 800             if (need_free2) {
 801                 free(tmp_str2);
 802             }
 803         }
 804         if (need_free1) {
 805             free(tmp_str1);
 806         }
 807     }
 808 }
 809