root/opal/class/opal_graph.h

/* [<][>][^][v][top][bottom][index][help] */

INCLUDED FROM


   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"
  35 #include "opal/class/opal_pointer_array.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 */
  44 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_vertex_t);
  45 
  46     /* A class for an edge (a connection between two verices) */
  47 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_graph_edge_t);
  48 
  49     /* A class for an adjacency list  */
  50 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_adjacency_list_t);
  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  */
 104 struct opal_graph_vertex_t {
 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  */
 123 typedef struct opal_graph_vertex_t opal_graph_vertex_t;
 124 
 125 /**
 126  * An opal_adjacency_list_t class
 127  */
 128 struct opal_adjacency_list_t {
 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  */
 137 typedef struct opal_adjacency_list_t opal_adjacency_list_t;
 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  */
 146 struct opal_graph_edge_t {
 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  */
 159 typedef struct opal_graph_edge_t opal_graph_edge_t;
 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  */
 181 struct vertex_distance_from_t {
 182     opal_graph_vertex_t *vertex;
 183     uint32_t            weight;
 184 };
 185 
 186 /**
 187  * A type for vertex distance.
 188  */
 189 typedef struct vertex_distance_from_t vertex_distance_from_t;
 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 

/* [<][>][^][v][top][bottom][index][help] */