src/xbt/graph.c

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