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