OpenMPI 0.1.1

- Main Page
- Related Pages
- Modules
- Data Structures
- Files

- File List
- Globals

Data Structures | Macros | Typedefs | Functions
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_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...

## 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

  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.

Parameters

  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.

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

  graph | The graph that this edge will be added to.
  edge | The 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

  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.

Parameters

  graph | The graph that the vertices belongs to.
  vertex1 | first vertex.
  vertex2 | second 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 |
  vertex | The reference vertex.
  distance_array | An 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

  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.

Parameters

  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.

Parameters

  graph | the graph we searching in.
  vertex_data | the 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 |
  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

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

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_list | an 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

  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.

Parameters

  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.

Parameters

  graph |
  vertex1 | The start vertex.
  vertex2 | The 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().