src/xbt/graph.c

   1 /* a generic graph library.                                                 */
   2
   3 /* Copyright (c) 2006-2017. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "xbt/sysdep.h"
  10 #include "xbt/log.h"
  11 #include "xbt/graph.h"
  12 #include "graph_private.h"
  13 #include "xbt/dict.h"
  14
  15 #include <errno.h>
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18
  19 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph");
  20
  21 /** @brief Constructor
  22  *  @return a new graph
  23  */
  24 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
  25 {
  26   xbt_graph_t graph = xbt_new0(struct xbt_graph, 1);
  27   graph->directed = directed;
  28   graph->data = data;
  29   graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  30   graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  31
  32   return graph;
  33 }
  34
  35 /** @brief add a node to the given graph */
  36 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
  37 {
  38   xbt_node_t node= xbt_new0(struct xbt_node, 1);
  39   node->data = data;
  40   if (g->directed)
  41     /* only the "out" field is used */
  42     node->in = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  43
  44   node->out = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  45   node->position_x = -1.0;
  46   node->position_y = -1.0;
  47
  48   xbt_dynar_push(g->nodes, &node);
  49
  50   return node;
  51 }
  52
  53 /** @brief add an edge to the given graph */
  54 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data)
  55 {
  56   xbt_edge_t edge = xbt_new0(struct xbt_edge, 1);
  57   xbt_dynar_push(src->out, &edge);
  58   if (g->directed)
  59     xbt_dynar_push(dst->in, &edge);
  60   else                          /* only the "out" field is used */
  61     xbt_dynar_push(dst->out, &edge);
  62
  63   edge->data = data;
  64   edge->src = src;
  65   edge->dst = dst;
  66
  67   xbt_dynar_push(g->edges, &edge);
  68
  69   return edge;
  70 }
  71
  72 /** @brief Get the edge connecting src and dst */
  73 xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst)
  74 {
  75   xbt_edge_t edge;
  76   unsigned int cursor;
  77
  78   xbt_dynar_foreach(src->out, cursor, edge) {
  79     XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
  80     if ((edge->src == src) && (edge->dst == dst))
  81       return edge;
  82   }
  83   if (!g->directed) {
  84     xbt_dynar_foreach(src->out, cursor, edge) {
  85       XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
  86       if ((edge->dst == src) && (edge->src == dst))
  87         return edge;
  88     }
  89   }
  90   return NULL;
  91 }
  92
  93 /** @brief Get the user data associated to a node */
  94 void *xbt_graph_node_get_data(xbt_node_t node)
  95 {
  96   return node->data;
  97 }
  98
  99 /** @brief Set the user data associated to a node */
 100 void xbt_graph_node_set_data(xbt_node_t node, void *data)
 101 {
 102   node->data = data;
 103 }
 104
 105 /** @brief Get the user data associated to a edge */
 106 void *xbt_graph_edge_get_data(xbt_edge_t edge)
 107 {
 108   return edge->data;
 109 }
 110
 111 /** @brief Set the user data associated to a edge */
 112 void xbt_graph_edge_set_data(xbt_edge_t edge, void *data)
 113 {
 114   edge->data = data;
 115 }
 116
 117 /** @brief Destructor
 118  *  @param g: poor victim
 119  *  @param node_free_function: function to use to free data associated to each node
 120  *  @param edge_free_function: function to use to free data associated to each edge
 121  *  @param graph_free_function: function to use to free data associated to g
 122  *
 123  * Free the graph structure.
 124  */
 125 void xbt_graph_free_graph(xbt_graph_t g, void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function,
 126                           void_f_pvoid_t graph_free_function)
 127 {
 128   unsigned int cursor;
 129   xbt_node_t node;
 130   xbt_edge_t edge;
 131
 132   xbt_dynar_foreach(g->edges, cursor, edge) {
 133     if (edge_free_function)
 134       edge_free_function(edge->data);
 135     free(edge);
 136   }
 137   xbt_dynar_free(&(g->edges));
 138
 139   xbt_dynar_foreach(g->nodes, cursor, node) {
 140     xbt_dynar_free(&(node->out));
 141     xbt_dynar_free(&(node->in));
 142     if (node_free_function)
 143       node_free_function(node->data);
 144     free(node);
 145   }
 146   xbt_dynar_free(&(g->nodes));
 147
 148   if (graph_free_function)
 149     graph_free_function(g->data);
 150   free(g);
 151 }
 152
 153 /** @brief Retrieve the graph's nodes as a dynar */
 154 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
 155 {
 156   return g->nodes;
 157 }
 158
 159 /** @brief Retrieve the graph's edges as a dynar */
 160 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
 161 {
 162   return g->edges;
 163 }
 164
 165 /** @brief Retrieve the node at the source of the given edge */
 166 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
 167 {
 168   return e->src;
 169 }
 170
 171 /** @brief Retrieve the node being the target of the given edge */
 172 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
 173 {
 174   return e->dst;
 175 }
 176
 177 /** @brief Retrieve the outgoing edges of the given node */
 178 xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n)
 179 {
 180   return n->out;
 181 }
 182
 183 /** @brief Set the weight of the given edge */
 184 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
 185 {
 186   e->length = length;
 187
 188 }
 189
 190 /** @brief Get the length of a edge */
 191 double xbt_graph_edge_get_length(xbt_edge_t edge)
 192 {
 193   return edge->length;
 194 }
 195
 196 /** @brief Floyd-Warshall algorithm for shortest path finding
 197  *
 198  * From wikipedia:
 199  *
 200  * The Floyd-Warshall algorithm takes as input an adjacency matrix representation of a weighted, directed graph (V, E).
 201  * The weight of a path between two vertices is the sum of the weights of the edges along that path. The edges E of the
 202  * graph may have negative weights, but the graph must not have any negative weight cycles. The algorithm computes, for
 203  * each pair of vertices, the minimum weight among all paths between the two vertices. The running time complexity is
 204  * Θ(|V|3).
 205  */
 206 void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d, xbt_node_t * p)
 207 {
 208   unsigned long i;
 209   unsigned long j;
 210   unsigned long k;
 211   unsigned long n = xbt_dynar_length(g->nodes);
 212
 213   for (i = 0; i < n * n; i++) {
 214     d[i] = adj[i];
 215   }
 216
 217   for (i = 0; i < n; i++) {
 218     for (j = 0; j < n; j++) {
 219       if (d[i*n+j] > -1) {
 220         p[i*n+j] = *((xbt_node_t *) xbt_dynar_get_ptr(g->nodes, i));
 221       }
 222     }
 223   }
 224
 225   for (k = 0; k < n; k++) {
 226     for (i = 0; i < n; i++) {
 227       for (j = 0; j < n; j++) {
 228         if (d[i * n + k] > -1 && d[k * n + j] > -1 &&
 229             (d[i * n + j] < 0 || d[i * n + j] > d[i * n + k] + d[k * n + j])) {
 230           d[i * n + j] = d[i * n + k] + d[k * n + j];
 231           p[i * n + j] = p[k * n + j];
 232         }
 233       }
 234     }
 235   }
 236 }
 237
 238 /** @brief Export the given graph in the GraphViz formatting for visualization */
 239 void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename, const char *(node_name) (xbt_node_t),
 240                                const char *(edge_name) (xbt_edge_t))
 241 {
 242   unsigned int cursor = 0;
 243   xbt_node_t node = NULL;
 244   xbt_edge_t edge = NULL;
 245   const char *name = NULL;
 246
 247   FILE *file = fopen(filename, "w");
 248   xbt_assert(file, "Failed to open %s \n", filename);
 249
 250   if (g->directed)
 251     fprintf(file, "digraph test {\n");
 252   else
 253     fprintf(file, "graph test {\n");
 254
 255   fprintf(file, "  graph [overlap=scale]\n");
 256
 257   fprintf(file, "  node [shape=box, style=filled]\n");
 258   fprintf(file, "  node [width=.3, height=.3, style=filled, color=skyblue]\n\n");
 259
 260   xbt_dynar_foreach(g->nodes, cursor, node) {
 261     if (node_name){
 262       fprintf(file, "  \"%s\";\n", node_name(node));
 263     }else{
 264       fprintf(file, "  \"%p\";\n", node);
 265     }
 266   }
 267   xbt_dynar_foreach(g->edges, cursor, edge) {
 268     const char *c;
 269     const char *c_dir = "->";
 270     const char *c_ndir = "--";
 271     if (g->directed){
 272       c = c_dir;
 273     }else{
 274       c = c_ndir;
 275     }
 276     if (node_name){
 277       const char *src_name = node_name(edge->src);
 278       const char *dst_name = node_name(edge->dst);
 279       fprintf(file, "  \"%s\" %s \"%s\"", src_name, c, dst_name);
 280     }else{
 281       fprintf(file, "  \"%p\" %s \"%p\"", edge->src, c, edge->dst);
 282     }
 283
 284     if (edge_name){
 285       name = edge_name(edge);
 286       if (name)
 287         fprintf(file, "[label=\"%s\"]", name);
 288     }
 289     fprintf(file, ";\n");
 290   }
 291   fprintf(file, "}\n");
 292   fclose(file);
 293 }