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
opal_graph_vertex_construct(opal_graph_vertex_t * vertex)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
opal_graph_vertex_destruct(opal_graph_vertex_t * vertex)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
opal_graph_edge_construct(opal_graph_edge_t * edge)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
opal_graph_edge_destruct(opal_graph_edge_t * edge)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
opal_graph_construct(opal_graph_t * graph)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
opal_graph_destruct(opal_graph_t * graph)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
opal_adjacency_list_construct(opal_adjacency_list_t * aj_list)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
opal_adjacency_list_destruct(opal_adjacency_list_t * aj_list)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 */
delete_all_edges_conceded_to_vertex(opal_graph_t * graph,opal_graph_vertex_t * vertex)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 */
opal_graph_add_vertex(opal_graph_t * graph,opal_graph_vertex_t * vertex)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 */
opal_graph_add_edge(opal_graph_t * graph,opal_graph_edge_t * edge)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 */
opal_graph_remove_edge(opal_graph_t * graph,opal_graph_edge_t * edge)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
opal_graph_remove_vertex(opal_graph_t * graph,opal_graph_vertex_t * vertex)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 */
opal_graph_adjacent(opal_graph_t * graph,opal_graph_vertex_t * vertex1,opal_graph_vertex_t * vertex2)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 */
opal_graph_get_order(opal_graph_t * graph)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 */
opal_graph_get_size(opal_graph_t * graph)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 */
opal_graph_find_vertex(opal_graph_t * graph,void * vertex_data)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 */
opal_graph_get_graph_vertices(opal_graph_t * graph,opal_pointer_array_t * vertices_list)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 */
opal_graph_get_adjacent_vertices(opal_graph_t * graph,opal_graph_vertex_t * vertex,opal_value_array_t * adjacents)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
opal_graph_spf(opal_graph_t * graph,opal_graph_vertex_t * vertex1,opal_graph_vertex_t * vertex2)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 */
compare_vertex_distance(const void * item1,const void * item2)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 */
opal_graph_dijkstra(opal_graph_t * graph,opal_graph_vertex_t * vertex,opal_value_array_t * distance_array)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 */
opal_graph_duplicate(opal_graph_t ** dest,opal_graph_t * src)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 */
opal_graph_print(opal_graph_t * graph)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
810