File: opal_graph.h

package info (click to toggle)
openmpi 5.0.8-4
  • links: PTS, VCS
  • area: main
  • in suites: sid
  • size: 201,684 kB
  • sloc: ansic: 613,078; makefile: 42,353; sh: 11,194; javascript: 9,244; f90: 7,052; java: 6,404; perl: 5,179; python: 1,859; lex: 740; fortran: 61; cpp: 20; tcl: 12
file content (356 lines) | stat: -rw-r--r-- 11,494 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
/*
 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
 *                         University Research and Technology
 *                         Corporation.  All rights reserved.
 * Copyright (c) 2004-2006 The University of Tennessee and The University
 *                         of Tennessee Research Foundation.  All rights
 *                         reserved.
 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
 *                         University of Stuttgart.  All rights reserved.
 * Copyright (c) 2004-2005 The Regents of the University of California.
 *                         All rights reserved.
 * Copyright (c) 2007      Voltaire All rights reserved.
 * $COPYRIGHT$
 *
 * Additional copyrights may follow
 *
 * $HEADER$
 */
/**
 * @file
 * The opal_graph interface is used to provide a generic graph infrastructure
 * to Open-MPI. The graph is represented as an adjacency list.
 * The graph is a list of vertices. The graph is a weighted directional graph.
 * Each vertex contains a pointer to a vertex data.
 * This pointer can point to the structure that this vertex belongs to.
 */
#ifndef OPAL_GRAPH_H
#define OPAL_GRAPH_H

#include "opal_config.h"
#include "opal/class/opal_list.h"
#include "opal/class/opal_object.h"
#include "opal/class/opal_pointer_array.h"
#include "opal/class/opal_value_array.h"
#include <stdio.h>
#include <stdlib.h>

BEGIN_C_DECLS

/* When two vertices are not connected, the distance between them is infinite. */
#define DISTANCE_INFINITY 0x7fffffff

/* A class for vertex */
OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_vertex_t);

/* A class for an edge (a connection between two verices) */
OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_edge_t);

/* A class for an adjacency list  */
OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_adjacency_list_t);

/* A class for graph */
OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_t);

/**
 * Function pointer for copying a vertex data from one vertex to
 * another
 *
 * @param dst The destination pointer of vertex_data
 * @param src The source pointer of the vertex_data
 *
 *
 */
typedef void (*opal_graph_copy_vertex_data)(void **dst, void *src);

/**
 * free vertex data.
 * @param vertex_data
 *
 * The vertex data can point to the structure that this vertex
 * belongs to.
 */
typedef void (*opal_graph_free_vertex_data)(void *vertex_data);

/**
 * Allocate vertex data.
 */
typedef void *(*opal_graph_alloc_vertex_data)(void);

/**
 * Compare two vertices data.
 *
 *@param vertex_data1
 *@param vertex_data2
 *
 *@return int The comparison results. 1- vertex_data1 is bigger
 *        then vertex_data2, 0- vertex_data1 is equal to
 *        vertex_data2 and -1- vertex_data1 is smaller the
 *        vertex_data2.
 */
typedef int (*opal_graph_compare_vertex_data)(void *vertex_data1, void *vertex_data2);

/**
 * print a vertex data.
 *
 * @param vertex_data
 */
typedef char *(*opal_graph_print_vertex)(void *vertex_data);

/**
 * A vertex class.
 */
struct opal_graph_vertex_t {
    opal_list_item_t super; /* A pointer to a vertex parent */
    void *in_graph;         /* A pointer to the graph that this vertex belongs to */
    void *in_adj_list;      /* A pointer to the adjacency that this vertex belongs to */
    void *vertex_data; /* A pointer to some data. this pointer can point to the struct the this*/
                       /* vertex belongs to*/
    struct opal_graph_vertex_t *sibling; /* A pointer to a sibling vertex. */
    /* if this vertex was copied this pointer will point to the source vertex */
    /* This pointer is for internal uses. */
    opal_graph_copy_vertex_data copy_vertex_data;   /* A function to copy vertex data */
    opal_graph_free_vertex_data free_vertex_data;   /* A function to print vertex data */
    opal_graph_alloc_vertex_data alloc_vertex_data; /* A function to allocate vertex data */
    opal_graph_compare_vertex_data
        compare_vertex;                   /* A function to compare between two vertices data */
    opal_graph_print_vertex print_vertex; /* A function to print vertex data */
};

/**
 * A type for vertex.
 */
typedef struct opal_graph_vertex_t opal_graph_vertex_t;

/**
 * An opal_adjacency_list_t class
 */
struct opal_adjacency_list_t {
    opal_list_item_t super;      /* A pointer to vertex parent */
    opal_graph_vertex_t *vertex; /* The adjacency_list is for adjacent of this vertex */
    opal_list_t *edges;          /* An edge list for all the adjacent and their weights */
};

/**
 * A type for opal_adjacency_list_t
 */
typedef struct opal_adjacency_list_t opal_adjacency_list_t;

/**
 * An edge class. (connection between two vertices.) Since the
 * graph is a directional graph, each vertex contains a start
 * and an end pointers for the start vertex and the end vertex
 * of this edge. Since the graph is a weighted graph, the edges
 * contains a weight field.
 */
struct opal_graph_edge_t {
    opal_list_item_t super;             /* A pointer to the edge parent */
    opal_graph_vertex_t *start;         /* The start vertex. */
    opal_graph_vertex_t *end;           /* The end vertex */
    uint32_t weight;                    /* The weight of this edge */
    opal_adjacency_list_t *in_adj_list; /* The adjacency list in witch this edge in.*/
    /* This adjacency list contains the start vertex of this edge*/
    /* and its for internal uses */
};

/**
 * A type for an edge
 */
typedef struct opal_graph_edge_t opal_graph_edge_t;

/**
 * A graph class.
 */
struct opal_graph_t {
    opal_object_t super;
    opal_list_t *adjacency_list;
    int number_of_edges;
    int number_of_vertices;
};

/**
 * A type for graph class
 */
typedef struct opal_graph_t opal_graph_t;

/**
 * This structure represent the distance (weight) of a vertex
 * from some point in the graph.
 */
struct vertex_distance_from_t {
    opal_graph_vertex_t *vertex;
    uint32_t weight;
};

/**
 * A type for vertex distance.
 */
typedef struct vertex_distance_from_t vertex_distance_from_t;

/**
 * This graph API adds a vertex to graph. The most common use
 * for this API is while building a graph.
 *
 * @param graph The graph that the vertex will be added to.
 * @param vertex The vertex we want to add.
 */
OPAL_DECLSPEC void opal_graph_add_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex);

/**
 * This graph API remove a vertex from graph. The most common
 * use for this API is while distracting a graph or while
 * removing relevant vertices from a graph.
 *
 * @param graph The graph that the vertex will be remove from.
 * @param vertex The vertex we want to remove.
 */
OPAL_DECLSPEC void opal_graph_remove_vertex(opal_graph_t *graph, opal_graph_vertex_t *vertex);

/**
 * This graph API adds an edge (connection between two
 * vertices) to a graph. The most common use
 * for this API is while building a graph.
 *
 * @param graph The graph that this edge will be added to.
 * @param edge The edge that we want to add.
 *
 * @return int Success or error. this API can return an error if
 *         one of the vertices is not in the graph.
 */
OPAL_DECLSPEC int opal_graph_add_edge(opal_graph_t *graph, opal_graph_edge_t *edge);

/**
 * This graph API removes an edge (a connection between two
 * vertices) from the graph. The most common use of this API is
 * while destructing a graph or while removing vertices from a
 * graph. while removing vertices from a graph, we should also
 * remove the connections from and to the vertices that we are
 * removing.
 *
 * @param graph The graph that this edge will be remove from.
 * @param edge the edge that we want to remove.
 */
OPAL_DECLSPEC void opal_graph_remove_edge(opal_graph_t *graph, opal_graph_edge_t *edge);

/**
 * This graph API tell us if two vertices are adjacent
 *
 * @param graph The graph that the vertices belongs to.
 * @param vertex1 first vertex.
 * @param vertex2 second vertex.
 *
 * @return uint32_t the weight of the connection between the two
 *         vertices or infinity if the vertices are not
 *         connected.
 */
OPAL_DECLSPEC uint32_t opal_graph_adjacent(opal_graph_t *graph, opal_graph_vertex_t *vertex1,
                                           opal_graph_vertex_t *vertex2);

/**
 * This Graph API returns the order of the graph (number of
 * vertices)
 *
 * @param graph
 *
 * @return int
 */
OPAL_DECLSPEC int opal_graph_get_order(opal_graph_t *graph);

/**
 * This Graph API returns the size of the graph (number of
 * edges)
 *
 * @param graph
 *
 * @return int
 */
OPAL_DECLSPEC int opal_graph_get_size(opal_graph_t *graph);

/**
 * This graph API finds a vertex in the graph according the
 * vertex data.
 * @param graph the graph we searching in.
 * @param vertex_data the vertex data we are searching according
 *                    to.
 *
 * @return opal_graph_vertex_t* The vertex founded or NULL.
 */
OPAL_DECLSPEC opal_graph_vertex_t *opal_graph_find_vertex(opal_graph_t *graph, void *vertex_data);

/**
 * This graph API returns an array of pointers of all the
 * vertices in the graph.
 *
 *
 * @param graph
 * @param vertices_list an array of pointers of all the
 *         vertices in the graph vertices.
 *
 * @return int returning the graph order (the
 *                    number of vertices in the returned array)
 */
OPAL_DECLSPEC int opal_graph_get_graph_vertices(opal_graph_t *graph,
                                                opal_pointer_array_t *vertices_list);

/**
 * This graph API returns all the adjacent of a vertex and the
 * distance (weight) of those adjacent and the vertex.
 *
 * @param graph
 * @param vertex The reference vertex
 * @param adjacent An allocated pointer array of vertices and
 *                  their distance from the reference vertex.
 *                  Note that this pointer should be free after
 *                  usage by the user
 *
 * @return int the number of adjacent in the list.
 */
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 duplicates a graph. Note that this API does
 * not copy the graph but builds a new graph while copying just
 * the vertices data.
 *
 * @param dest The new created graph.
 * @param src The graph we want to duplicate.
 */
OPAL_DECLSPEC void opal_graph_duplicate(opal_graph_t **dest, opal_graph_t *src);

/**
 * This graph API finds the shortest path between two vertices.
 *
 * @param graph
 * @param vertex1 The start vertex.
 * @param vertex2 The end vertex.
 *
 * @return uint32_t the distance between the two vertices.
 */
OPAL_DECLSPEC uint32_t opal_graph_spf(opal_graph_t *graph, opal_graph_vertex_t *vertex1,
                                      opal_graph_vertex_t *vertex2);

/**
 * This graph API returns the distance (weight) from a reference
 * vertex to all other vertices in the graph using the Dijkstra
 * algorithm
 *
 * @param graph
 * @param vertex The reference vertex.
 * @param distance_array An array of vertices and
 *         their distance from the reference vertex.
 *
 * @return uint32_t the size of the distance array
 */
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 prints a graph - mostly for debug uses.
 * @param graph
 */
OPAL_DECLSPEC void opal_graph_print(opal_graph_t *graph);

END_C_DECLS

#endif /* OPAL_GRAPH_H */