OpenMPI
0.1.1
|
The opal_graph interface is used to provide a generic graph infrastructure to Open-MPI. More...
#include "opal_config.h"
#include <stdio.h>
#include <stdlib.h>
#include "opal/class/opal_object.h"
#include "opal/class/opal_list.h"
#include "opal/class/opal_pointer_array.h"
#include "opal/class/opal_value_array.h"
Go to the source code of this file.
Data Structures | |
struct | opal_graph_vertex_t |
A vertex class. More... | |
struct | opal_adjacency_list_t |
An opal_adjacency_list_t class. More... | |
struct | opal_graph_edge_t |
An edge class. More... | |
struct | opal_graph_t |
A graph class. More... | |
struct | vertex_distance_from_t |
This structure represent the distance (weight) of a vertex from some point in the graph. More... | |
Macros | |
#define | DISTANCE_INFINITY 0x7fffffff |
Typedefs | |
typedef void(* | opal_graph_copy_vertex_data )(void **dst, void *src) |
Function pointer for coping a vertex data from one vertex to another. More... | |
typedef void(* | opal_graph_free_vertex_data )(void *vertex_data) |
free vertex data. More... | |
typedef void *(* | opal_graph_alloc_vertex_data )(void) |
Allocate vertex data. | |
typedef int(* | opal_graph_compare_vertex_data )(void *vertex_data1, void *vertex_data2) |
Compare two vertices data. More... | |
typedef char *(* | opal_graph_print_vertex )(void *vertex_data) |
print a vertex data. More... | |
typedef struct opal_graph_vertex_t | opal_graph_vertex_t |
A type for vertex. | |
typedef struct opal_adjacency_list_t | opal_adjacency_list_t |
A type for opal_adjacency_list_t. | |
typedef struct opal_graph_edge_t | opal_graph_edge_t |
A type for an edge. | |
typedef struct opal_graph_t | opal_graph_t |
A type for graph class. | |
typedef struct vertex_distance_from_t | vertex_distance_from_t |
A type for vertex distance. | |
Functions | |
OPAL_DECLSPEC | OBJ_CLASS_DECLARATION (opal_graph_vertex_t) |
OPAL_DECLSPEC | OBJ_CLASS_DECLARATION (opal_graph_edge_t) |
OPAL_DECLSPEC | OBJ_CLASS_DECLARATION (opal_adjacency_list_t) |
OPAL_DECLSPEC | OBJ_CLASS_DECLARATION (opal_graph_t) |
OPAL_DECLSPEC void | opal_graph_add_vertex (opal_graph_t *graph, opal_graph_vertex_t *vertex) |
This graph API adds a vertex to graph. More... | |
OPAL_DECLSPEC void | opal_graph_remove_vertex (opal_graph_t *graph, opal_graph_vertex_t *vertex) |
This graph API remove a vertex from graph. More... | |
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. More... | |
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. More... | |
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. More... | |
OPAL_DECLSPEC int | opal_graph_get_order (opal_graph_t *graph) |
This Graph API returns the order of the graph (number of vertices) More... | |
OPAL_DECLSPEC int | opal_graph_get_size (opal_graph_t *graph) |
This Graph API returns the size of the graph (number of edges) More... | |
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. More... | |
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. More... | |
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 the vertex. More... | |
OPAL_DECLSPEC void | opal_graph_duplicate (opal_graph_t **dest, opal_graph_t *src) |
This graph API duplicates a graph. More... | |
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. More... | |
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 graph using the Dijkstra algorithm. More... | |
OPAL_DECLSPEC void | opal_graph_print (opal_graph_t *graph) |
This graph API prints a graph - mostly for debug uses. More... | |
The opal_graph interface is used to provide a generic graph infrastructure to Open-MPI.
The graph is represented as an adjacentcy 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.
typedef int(* opal_graph_compare_vertex_data)(void *vertex_data1, void *vertex_data2) |
Compare two vertices data.
vertex_data1 | |
vertex_data2 |
typedef void(* opal_graph_copy_vertex_data)(void **dst, void *src) |
Function pointer for coping a vertex data from one vertex to another.
dst | The destination pointer of vertex_data |
src | The source pointer of the vertex_data |
typedef void(* opal_graph_free_vertex_data)(void *vertex_data) |
free vertex data.
vertex_data | The vertex data can point to the structure that this vertex belongs to. |
typedef char*(* opal_graph_print_vertex)(void *vertex_data) |
print a vertex data.
vertex_data |
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.
The most common use for this API is while building a graph.
graph | The graph that this edge will be added to. |
edge | The edge that we want to add. |
find the vertices that this edge should connect.
if one of the vertices either the start or the end is not found - return an error.
References opal_list_append, opal_list_get_end(), opal_list_get_first(), and opal_list_get_next.
Referenced by opal_carto_base_connect_nodes_fn(), and opal_graph_duplicate().
OPAL_DECLSPEC void opal_graph_add_vertex | ( | opal_graph_t * | graph, |
opal_graph_vertex_t * | vertex | ||
) |
This graph API adds a vertex to graph.
The most common use for this API is while building a graph.
graph | The graph that the vertex will be added to. |
vertex | The vertex we want to add. |
Find if this vertex already exists in the graph.
References opal_list_append, opal_list_get_end(), opal_list_get_first(), and opal_list_get_next.
Referenced by opal_carto_base_graph_add_node_fn(), and opal_graph_duplicate().
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.
graph | The graph that the vertices belongs to. |
vertex1 | first vertex. |
vertex2 | second vertex. |
Verify that the first vertex belongs to the graph.
Verify that the second vertex belongs to the graph.
If the first vertex and the second vertex are the same vertex, the distance between the is 0.
find the second vertex in the adjacency list of the first vertex.
References opal_list_get_end(), opal_list_get_first(), opal_list_get_next, and OPAL_OUTPUT.
Referenced by opal_graph_dijkstra().
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 graph using the Dijkstra algorithm.
graph | |
vertex | The reference vertex. |
distance_array | An array of vertices and their distance from the reference vertex. |
Verify that the reference vertex belongs to the graph.
assign an infinity distance to all the vertices in the queue except the reference vertex which its distance should be 0.
if the distance from the first vertex in the queue to the I vertex in the queue plus the distance of the first vertex in the queue from the referenced vertex is smaller than the distance of the I vertex from the referenced vertex, assign the lower distance to the I vertex.
References opal_graph_adjacent(), opal_graph_get_order(), opal_list_get_end(), opal_list_get_first(), opal_list_get_next, and OPAL_OUTPUT.
Referenced by opal_carto_base_get_nodes_distance_fn(), and opal_graph_spf().
OPAL_DECLSPEC void opal_graph_duplicate | ( | opal_graph_t ** | dest, |
opal_graph_t * | src | ||
) |
This graph API duplicates a graph.
Note that this API does not copy the graph but builds a new graph while coping just the vertices data.
dest | The new created graph. |
src | The graph we want to duplicate. |
Note that this API does not copy the graph but builds a new graph while coping just the vertex data.
dest | The new created graph. |
src | The graph we want to duplicate. |
Now, copy all the edges from the source graph
References opal_graph_add_edge(), opal_graph_add_vertex(), opal_list_get_end(), opal_list_get_first(), and opal_list_get_next.
Referenced by opal_carto_base_duplicate_graph_fn().
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.
graph | the graph we searching in. |
vertex_data | the vertex data we are searching according to. |
Run on all the vertices of the graph
References opal_list_get_end(), opal_list_get_first(), and opal_list_get_next.
Referenced by opal_carto_base_graph_find_node_fn().
OPAL_DECLSPEC int opal_graph_get_adjacent_vertices | ( | opal_graph_t * | graph, |
opal_graph_vertex_t * | vertex, | ||
opal_value_array_t * | adjacents | ||
) |
This graph API returns all the adjacent of a vertex and the distance (weight) of those adjacent and the vertex.
graph | |
vertex | The reference vertex |
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 |
This graph API returns all the adjacent of a vertex and the distance (weight) of those adjacent and the vertex.
graph | |
vertex | The reference vertex |
adjacents | 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 |
Verify that the vertex belongs to the graph.
find the adjacency list that this vertex belongs to
References opal_list_get_end(), opal_list_get_first(), opal_list_get_next, opal_list_get_size(), and OPAL_OUTPUT.
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.
graph | |
vertices_list | an array of pointers of all the vertices in the graph vertices. |
If the graph order is 0, return NULL.
References opal_list_get_end(), opal_list_get_first(), opal_list_get_next, and opal_pointer_array_add().
Referenced by opal_carto_base_duplicate_graph_fn(), and opal_carto_base_free_graph_fn().
OPAL_DECLSPEC int opal_graph_get_order | ( | opal_graph_t * | graph | ) |
This Graph API returns the order of the graph (number of vertices)
graph |
Referenced by opal_graph_dijkstra().
OPAL_DECLSPEC int opal_graph_get_size | ( | opal_graph_t * | graph | ) |
This Graph API returns the size of the graph (number of edges)
graph |
OPAL_DECLSPEC void opal_graph_print | ( | opal_graph_t * | graph | ) |
This graph API prints a graph - mostly for debug uses.
graph |
References opal_list_get_end(), opal_list_get_first(), opal_list_get_next, and opal_output().
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.
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.
graph | The graph that this edge will be remove from. |
edge | the edge that we want to remove. |
References opal_list_remove_item().
OPAL_DECLSPEC void opal_graph_remove_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.
graph | The graph that the vertex will be remove from. |
vertex | The vertex we want to remove. |
remove all the edges of this vertex and destruct them.
remove the adjscency list of this vertex from the graph and destruct it.
delete all the edges that connected to the vertex.
References OBJ_RELEASE, opal_list_is_empty(), opal_list_remove_first(), and opal_list_remove_item().
Referenced by opal_carto_base_duplicate_graph_fn().
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.
graph | |
vertex1 | The start vertex. |
vertex2 | The end vertex. |
Verify that the first vertex belongs to the graph.
Verify that the second vertex belongs to the graph.
Run Dijkstra algorithm on the graph from the start vertex.
find the end vertex in the distance array that Dijkstra algorithm returned.
References OBJ_RELEASE, opal_graph_dijkstra(), and OPAL_OUTPUT.
Referenced by opal_carto_base_graph_spf_fn().