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