OpenMPI  0.1.1
opal_graph.h
Go to the documentation of this file.
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"
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 */
45 
46  /* A class for an edge (a connection between two verices) */
48 
49  /* A class for an adjacency list */
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  */
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  */
124 
125 /**
126  * An opal_adjacency_list_t class
127  */
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  */
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  */
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  */
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  */
182  opal_graph_vertex_t *vertex;
183  uint32_t weight;
184 };
185 
186 /**
187  * A type for vertex distance.
188  */
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 
OPAL_DECLSPEC int opal_graph_get_size(opal_graph_t *graph)
This Graph API returns the size of the graph (number of edges)
Definition: opal_graph.c:454
This structure represent the distance (weight) of a vertex from some point in the graph...
Definition: opal_graph.h:181
dynamic pointer array
Definition: opal_pointer_array.h:45
OPAL_DECLSPEC int opal_graph_get_graph_vertices(opal_graph_t *graph, opal_pointer_array_t *vertices_list)
This graph API returns an array of pointers of all the vertices in the graph.
Definition: opal_graph.c:505
OPAL_DECLSPEC opal_graph_vertex_t * opal_graph_find_vertex(opal_graph_t *graph, void *vertex_data)
This graph API finds a vertex in the graph according the vertex data.
Definition: opal_graph.c:468
OPAL_DECLSPEC void opal_graph_remove_edge(opal_graph_t *graph, opal_graph_edge_t *edge)
This graph API removes an edge (a connection between two vertices) from the graph.
Definition: opal_graph.c:330
OPAL_DECLSPEC void opal_graph_remove_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex)
This graph API remove a vertex from graph.
Definition: opal_graph.c:348
The opal_list_t interface is used to provide a generic doubly-linked list container for Open MPI...
See opal_bitmap.h for an explanation of why there is a split between OPAL and ORTE for this generic c...
int(* opal_graph_compare_vertex_data)(void *vertex_data1, void *vertex_data2)
Compare two vertices data.
Definition: opal_graph.h:91
void *(* opal_graph_alloc_vertex_data)(void)
Allocate vertex data.
Definition: opal_graph.h:78
Definition: opal_list.h:98
A vertex class.
Definition: opal_graph.h:104
OPAL_DECLSPEC int opal_graph_get_order(opal_graph_t *graph)
This Graph API returns the order of the graph (number of vertices)
Definition: opal_graph.c:441
OPAL_DECLSPEC void opal_graph_duplicate(opal_graph_t **dest, opal_graph_t *src)
This graph API duplicates a graph.
Definition: opal_graph.c:766
An edge class.
Definition: opal_graph.h:146
OPAL_DECLSPEC void opal_graph_print(opal_graph_t *graph)
This graph API prints a graph - mostly for debug uses.
Definition: opal_graph.c:834
OPAL_DECLSPEC int opal_graph_add_edge(opal_graph_t *graph, opal_graph_edge_t *edge)
This graph API adds an edge (connection between two vertices) to a graph.
Definition: opal_graph.c:279
An opal_adjacency_list_t class.
Definition: opal_graph.h:128
Base object.
Definition: opal_object.h:182
A graph class.
Definition: opal_graph.h:165
char *(* opal_graph_print_vertex)(void *vertex_data)
print a vertex data.
Definition: opal_graph.h:98
Definition: opal_list.h:147
void(* opal_graph_free_vertex_data)(void *vertex_data)
free vertex data.
Definition: opal_graph.h:73
OPAL_DECLSPEC void opal_graph_add_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex)
This graph API adds a vertex to graph.
Definition: opal_graph.c:237
Definition: opal_value_array.h:38
A simple C-language object-oriented system with single inheritance and ownership-based memory managem...
OPAL_DECLSPEC uint32_t opal_graph_adjacent(opal_graph_t *graph, opal_graph_vertex_t *vertex1, opal_graph_vertex_t *vertex2)
This graph API tell us if two vertices are adjacent.
Definition: opal_graph.c:388
OPAL_DECLSPEC uint32_t opal_graph_spf(opal_graph_t *graph, opal_graph_vertex_t *vertex1, opal_graph_vertex_t *vertex2)
This graph API finds the shortest path between two vertices.
Definition: opal_graph.c:588
OPAL_DECLSPEC int opal_graph_get_adjacent_vertices(opal_graph_t *graph, opal_graph_vertex_t *vertex, opal_value_array_t *adjacent)
This graph API returns all the adjacent of a vertex and the distance (weight) of those adjacent and t...
Definition: opal_graph.c:542
void(* opal_graph_copy_vertex_data)(void **dst, void *src)
Function pointer for coping a vertex data from one vertex to another.
Definition: opal_graph.h:64
#define OBJ_CLASS_DECLARATION(NAME)
Declaration for class descriptor.
Definition: opal_object.h:236
OPAL_DECLSPEC uint32_t opal_graph_dijkstra(opal_graph_t *graph, opal_graph_vertex_t *vertex, opal_value_array_t *distance_array)
This graph API returns the distance (weight) from a reference vertex to all other vertices in the gra...
Definition: opal_graph.c:678