OpenMPI  0.1.1
opal_graph.h File Reference

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_topal_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...
 

Detailed Description

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 Documentation

typedef int(* opal_graph_compare_vertex_data)(void *vertex_data1, void *vertex_data2)

Compare two vertices data.

Parameters
vertex_data1
vertex_data2
Returns
int The comparition 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 void(* opal_graph_copy_vertex_data)(void **dst, void *src)

Function pointer for coping a vertex data from one vertex to another.

Parameters
dstThe destination pointer of vertex_data
srcThe source pointer of the vertex_data
typedef void(* opal_graph_free_vertex_data)(void *vertex_data)

free vertex data.

Parameters
vertex_dataThe 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.

Parameters
vertex_data

Function Documentation

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.

Parameters
graphThe graph that this edge will be added to.
edgeThe edge that we want to add.
Returns
int Success or error. this API can return an error if one of the vertices is not in the graph.

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.

Parameters
graphThe graph that the vertex will be added to.
vertexThe 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.

Parameters
graphThe graph that the vertices belongs to.
vertex1first vertex.
vertex2second vertex.
Returns
uint32_t the weight of the connection between the two vertices or infinity if the vertices are not connected.

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.

Parameters
graph
vertexThe reference vertex.
distance_arrayAn array of vertices and their distance from the reference vertex.
Returns
uint32_t the size of the distance array

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.

Parameters
destThe new created graph.
srcThe 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.

Parameters
destThe new created graph.
srcThe 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.

Parameters
graphthe graph we searching in.
vertex_datathe vertex data we are searching according to.
Returns
opal_graph_vertex_t* The vertex founded or NULL.

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.

Parameters
graph
vertexThe reference vertex
adjacentAn allocated pointer array of vertices and their distance from the reference vertex. Note that this pointer should be free after usage by the user
Returns
int the number of adjacent in the list.

This graph API returns all the adjacent of a vertex and the distance (weight) of those adjacent and the vertex.

Parameters
graph
vertexThe reference vertex
adjacentsAn allocated pointer array of vertices and their distance from the reference vertex. Note that this pointer should be free after usage by the user
Returns
int the number of adjacents in the list.

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.

Parameters
graph
vertices_listan array of pointers of all the vertices in the graph vertices.
Returns
int returning the graph order (the number of vertices in the returned array)

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)

Parameters
graph
Returns
int

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)

Parameters
graph
Returns
int
OPAL_DECLSPEC void opal_graph_print ( opal_graph_t graph)

This graph API prints a graph - mostly for debug uses.

Parameters
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.

Parameters
graphThe graph that this edge will be remove from.
edgethe 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.

Parameters
graphThe graph that the vertex will be remove from.
vertexThe 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.

Parameters
graph
vertex1The start vertex.
vertex2The end vertex.
Returns
uint32_t the distance between the two vertices.

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().