1 /* 2 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana 3 * University Research and Technology 4 * Corporation. All rights reserved. 5 * Copyright (c) 2004-2006 The University of Tennessee and The University 6 * of Tennessee Research Foundation. All rights 7 * reserved. 8 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, 9 * University of Stuttgart. All rights reserved. 10 * Copyright (c) 2004-2005 The Regents of the University of California. 11 * All rights reserved. 12 * Copyright (c) 2007 Voltaire All rights reserved. 13 * $COPYRIGHT$ 14 * 15 * Additional copyrights may follow 16 * 17 * $HEADER$ 18 */ 19 /** 20 * @file 21 * The opal_graph interface is used to provide a generic graph infrastructure 22 * to Open-MPI. The graph is represented as an adjacentcy list. 23 * The graph is a list of vertices. The graph is a weighted directional graph. 24 * Each vertex contains a pointer to a vertex data. 25 * This pointer can point to the structure that this vertex belongs to. 26 */ 27 #ifndef OPAL_GRAPH_H 28 #define OPAL_GRAPH_H 29 30 #include "opal_config.h" 31 #include <stdio.h> 32 #include <stdlib.h> 33 #include "opal/class/opal_object.h" 34 #include "opal/class/opal_list.h" 35 #include "opal/class/opal_pointer_array.h" 36 #include "opal/class/opal_value_array.h" 37 38 BEGIN_C_DECLS 39 40 /* When two vertices are not connected, the distance between them is infinite. */ 41 #define DISTANCE_INFINITY 0x7fffffff 42 43 /* A class for vertex */ 44 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_vertex_t); 45 46 /* A class for an edge (a connection between two verices) */ 47 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_edge_t); 48 49 /* A class for an adjacency list */ 50 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_adjacency_list_t); 51 52 /* A class for graph */ 53 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_t); 54 55 /** 56 * Function pointer for coping a vertex data from one vertex to 57 * another 58 * 59 * @param dst The destination pointer of vertex_data 60 * @param src The source pointer of the vertex_data 61 * 62 * 63 */ 64 typedef void (*opal_graph_copy_vertex_data)(void **dst, void *src); 65 66 /** 67 * free vertex data. 68 * @param vertex_data 69 * 70 * The vertex data can point to the structure that this vertex 71 * belongs to. 72 */ 73 typedef void (*opal_graph_free_vertex_data)(void *vertex_data); 74 75 /** 76 * Allocate vertex data. 77 */ 78 typedef void *(*opal_graph_alloc_vertex_data)(void); 79 80 /** 81 * Compare two vertices data. 82 * 83 *@param vertex_data1 84 *@param vertex_data2 85 * 86 *@return int The comparition results. 1- vertex_data1 is bigger 87 * then vertex_data2, 0- vertex_data1 is equal to 88 * vertex_data2 and -1- vertex_data1 is smaller the 89 * vertex_data2. 90 */ 91 typedef int (*opal_graph_compare_vertex_data)(void *vertex_data1, void *vertex_data2); 92 93 /** 94 * print a vertex data. 95 * 96 * @param vertex_data 97 */ 98 typedef char *(*opal_graph_print_vertex)(void *vertex_data); 99 100 101 /** 102 * A vertex class. 103 */ 104 struct opal_graph_vertex_t { 105 opal_list_item_t super; /* A pointer to a vertex parent */ 106 void *in_graph; /* A pointer to the graph that this vertex belongs to */ 107 void *in_adj_list; /* A pointer to the adjacency that this vertex belongs to */ 108 void *vertex_data;/* A pointer to some data. this pointer can point to the struct the this*/ 109 /* vertex belongs to*/ 110 struct opal_graph_vertex_t *sibling;/* A pointer to a sibling vertex. */ 111 /* if this vertex was copied this pointer will point to the source vertex */ 112 /* This pointer is for internal uses. */ 113 opal_graph_copy_vertex_data copy_vertex_data; /* A function to copy vertex data */ 114 opal_graph_free_vertex_data free_vertex_data; /* A function to print vertex data */ 115 opal_graph_alloc_vertex_data alloc_vertex_data;/* A function to allocate vertex data */ 116 opal_graph_compare_vertex_data compare_vertex; /* A function to compare between two vertices data */ 117 opal_graph_print_vertex print_vertex; /* A function to print vertex data */ 118 }; 119 120 /** 121 * A type for vertex. 122 */ 123 typedef struct opal_graph_vertex_t opal_graph_vertex_t; 124 125 /** 126 * An opal_adjacency_list_t class 127 */ 128 struct opal_adjacency_list_t { 129 opal_list_item_t super; /* A pointer to vertex parent */ 130 opal_graph_vertex_t *vertex; /* The adjacency_list is for adjacent of this vertex */ 131 opal_list_t *edges; /* An edge list for all the adjacent and their weights */ 132 }; 133 134 /** 135 * A type for opal_adjacency_list_t 136 */ 137 typedef struct opal_adjacency_list_t opal_adjacency_list_t; 138 139 /** 140 * An edge class. (connection between two vertices.) Since the 141 * graph is a directional graph, each vertex contains a start 142 * and an end pointers for the start vertex and the end vertex 143 * of this edge. Since the graph is a weighted graph, the edges 144 * contains a weight field. 145 */ 146 struct opal_graph_edge_t { 147 opal_list_item_t super; /* A pointer to the edge parent */ 148 opal_graph_vertex_t *start; /* The start vertex. */ 149 opal_graph_vertex_t *end; /* The end vertex */ 150 uint32_t weight; /* The weight of this edge */ 151 opal_adjacency_list_t *in_adj_list; /* The adjacency list in witch this edge in.*/ 152 /* This adjacency list contains the start vertex of this edge*/ 153 /* and its for internal uses */ 154 }; 155 156 /** 157 * A type for an edge 158 */ 159 typedef struct opal_graph_edge_t opal_graph_edge_t; 160 161 162 /** 163 * A graph class. 164 */ 165 struct opal_graph_t { 166 opal_object_t super; 167 opal_list_t *adjacency_list; 168 int number_of_edges; 169 int number_of_vertices; 170 }; 171 172 /** 173 * A type for graph class 174 */ 175 typedef struct opal_graph_t opal_graph_t; 176 177 /** 178 * This structure represent the distance (weight) of a vertex 179 * from some point in the graph. 180 */ 181 struct vertex_distance_from_t { 182 opal_graph_vertex_t *vertex; 183 uint32_t weight; 184 }; 185 186 /** 187 * A type for vertex distance. 188 */ 189 typedef struct vertex_distance_from_t vertex_distance_from_t; 190 191 /** 192 * This graph API adds a vertex to graph. The most common use 193 * for this API is while building a graph. 194 * 195 * @param graph The graph that the vertex will be added to. 196 * @param vertex The vertex we want to add. 197 */ 198 OPAL_DECLSPEC void opal_graph_add_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex); 199 200 /** 201 * This graph API remove a vertex from graph. The most common 202 * use for this API is while distracting a graph or while 203 * removing relevant vertices from a graph. 204 * 205 * @param graph The graph that the vertex will be remove from. 206 * @param vertex The vertex we want to remove. 207 */ 208 OPAL_DECLSPEC void opal_graph_remove_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex); 209 210 /** 211 * This graph API adds an edge (connection between two 212 * vertices) to a graph. The most common use 213 * for this API is while building a graph. 214 * 215 * @param graph The graph that this edge will be added to. 216 * @param edge The edge that we want to add. 217 * 218 * @return int Success or error. this API can return an error if 219 * one of the vertices is not in the graph. 220 */ 221 OPAL_DECLSPEC int opal_graph_add_edge(opal_graph_t *graph, opal_graph_edge_t *edge); 222 223 /** 224 * This graph API removes an edge (a connection between two 225 * vertices) from the graph. The most common use of this API is 226 * while destructing a graph or while removing vertices from a 227 * graph. while removing vertices from a graph, we should also 228 * remove the connections from and to the vertices that we are 229 * removing. 230 * 231 * @param graph The graph that this edge will be remove from. 232 * @param edge the edge that we want to remove. 233 */ 234 OPAL_DECLSPEC void opal_graph_remove_edge (opal_graph_t *graph, opal_graph_edge_t *edge); 235 236 /** 237 * This graph API tell us if two vertices are adjacent 238 * 239 * @param graph The graph that the vertices belongs to. 240 * @param vertex1 first vertex. 241 * @param vertex2 second vertex. 242 * 243 * @return uint32_t the weight of the connection between the two 244 * vertices or infinity if the vertices are not 245 * connected. 246 */ 247 OPAL_DECLSPEC uint32_t opal_graph_adjacent(opal_graph_t *graph, opal_graph_vertex_t *vertex1, opal_graph_vertex_t *vertex2); 248 249 /** 250 * This Graph API returns the order of the graph (number of 251 * vertices) 252 * 253 * @param graph 254 * 255 * @return int 256 */ 257 OPAL_DECLSPEC int opal_graph_get_order(opal_graph_t *graph); 258 259 /** 260 * This Graph API returns the size of the graph (number of 261 * edges) 262 * 263 * @param graph 264 * 265 * @return int 266 */ 267 OPAL_DECLSPEC int opal_graph_get_size(opal_graph_t *graph); 268 269 /** 270 * This graph API finds a vertex in the graph according the 271 * vertex data. 272 * @param graph the graph we searching in. 273 * @param vertex_data the vertex data we are searching according 274 * to. 275 * 276 * @return opal_graph_vertex_t* The vertex founded or NULL. 277 */ 278 OPAL_DECLSPEC opal_graph_vertex_t *opal_graph_find_vertex(opal_graph_t *graph, void *vertex_data); 279 280 281 /** 282 * This graph API returns an array of pointers of all the 283 * vertices in the graph. 284 * 285 * 286 * @param graph 287 * @param vertices_list an array of pointers of all the 288 * vertices in the graph vertices. 289 * 290 * @return int returning the graph order (the 291 * number of vertices in the returned array) 292 */ 293 OPAL_DECLSPEC int opal_graph_get_graph_vertices(opal_graph_t *graph, opal_pointer_array_t *vertices_list); 294 295 /** 296 * This graph API returns all the adjacent of a vertex and the 297 * distance (weight) of those adjacent and the vertex. 298 * 299 * @param graph 300 * @param vertex The reference vertex 301 * @param adjacent An allocated pointer array of vertices and 302 * their distance from the reference vertex. 303 * Note that this pointer should be free after 304 * usage by the user 305 * 306 * @return int the number of adjacent in the list. 307 */ 308 OPAL_DECLSPEC int opal_graph_get_adjacent_vertices(opal_graph_t *graph, opal_graph_vertex_t *vertex, opal_value_array_t *adjacent); 309 310 /** 311 * This graph API duplicates a graph. Note that this API does 312 * not copy the graph but builds a new graph while coping just 313 * the vertices data. 314 * 315 * @param dest The new created graph. 316 * @param src The graph we want to duplicate. 317 */ 318 OPAL_DECLSPEC void opal_graph_duplicate(opal_graph_t **dest, opal_graph_t *src); 319 320 /** 321 * This graph API finds the shortest path between two vertices. 322 * 323 * @param graph 324 * @param vertex1 The start vertex. 325 * @param vertex2 The end vertex. 326 * 327 * @return uint32_t the distance between the two vertices. 328 */ 329 OPAL_DECLSPEC uint32_t opal_graph_spf(opal_graph_t *graph, opal_graph_vertex_t *vertex1, opal_graph_vertex_t *vertex2); 330 331 /** 332 * This graph API returns the distance (weight) from a reference 333 * vertex to all other vertices in the graph using the Dijkstra 334 * algorithm 335 * 336 * @param graph 337 * @param vertex The reference vertex. 338 * @param distance_array An array of vertices and 339 * their distance from the reference vertex. 340 * 341 * @return uint32_t the size of the distance array 342 */ 343 OPAL_DECLSPEC uint32_t opal_graph_dijkstra(opal_graph_t *graph, opal_graph_vertex_t *vertex, opal_value_array_t *distance_array); 344 345 /** 346 * This graph API prints a graph - mostly for debug uses. 347 * @param graph 348 */ 349 OPAL_DECLSPEC void opal_graph_print(opal_graph_t *graph); 350 351 END_C_DECLS 352 353 354 #endif /* OPAL_GRAPH_H */ 355