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