src/xbt/graph.c

   1
   2
   3
   4 /*      $Id$     */
   5
   6
   7 /* a generic graph library.                                                 */
   8
   9 /* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand.
  10    All rights reserved.                  */
  11
  12 /* This program is free software; you can redistribute it and/or modify it
  13  * under the terms of the license (GNU LGPL) which comes with this package. */
  14
  15 #include <stdlib.h>
  16 #include "xbt/sysdep.h"
  17 #include "xbt/log.h"
  18 #include "xbt/graph.h"
  19 #include "graph_private.h"
  20 #include "xbt/graphxml_parse.h"
  21 #include "xbt/dict.h"
  22
  23 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph, xbt, "Graph");
  24
  25
  26
  27 /** Constructor
  28  * \return a new graph
  29  */
  30 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
  31 {
  32   xbt_graph_t graph = NULL;
  33   graph = xbt_new0(struct xbt_graph, 1);
  34   graph->directed = directed;
  35   graph->data = data;
  36   graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  37   graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  38
  39   return graph;
  40 }
  41
  42 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
  43 {
  44   xbt_node_t node = NULL;
  45   node = xbt_new0(struct xbt_node, 1);
  46   node->data = data;
  47   node->in = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  48   node->out = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  49   xbt_dynar_push(g->nodes, &node);
  50
  51   return node;
  52 }
  53
  54
  55 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
  56                               xbt_node_t src, xbt_node_t dst, void *data)
  57 {
  58   xbt_edge_t edge = NULL;
  59
  60
  61   edge = xbt_new0(struct xbt_edge, 1);
  62   xbt_dynar_push(src->out, &edge);
  63   xbt_dynar_push(dst->in, &edge);
  64
  65   edge->data = data;
  66   edge->src = src;
  67   edge->dst = dst;
  68   if (!g->directed)
  69     {
  70     xbt_dynar_push(src->in, &edge);
  71     xbt_dynar_push(dst->out, &edge);
  72   }
  73
  74   xbt_dynar_push(g->edges, &edge);
  75
  76   return edge;
  77 }
  78
  79
  80 /** Destructor
  81  * \param l poor victim
  82  *
  83  * Free the graph structure.
  84  */
  85 void xbt_graph_free_graph(xbt_graph_t g,
  86                           void node_free_function(void *ptr),
  87                           void edge_free_function(void *ptr),
  88                           void graph_free_function(void *ptr))
  89 {
  90   int cursor = 0;
  91   xbt_node_t node = NULL;
  92   xbt_edge_t edge = NULL;
  93
  94
  95   xbt_dynar_foreach(g->nodes, cursor, node)
  96     {
  97       xbt_dynar_free(&(node->out));
  98       xbt_dynar_free(&(node->in));
  99       if(node_free_function)
 100         node_free_function(node->data);
 101     }
 102
 103   xbt_dynar_foreach(g->edges, cursor, edge)
 104     {
 105       if(edge_free_function)
 106         edge_free_function(edge->data);
 107     }
 108
 109   xbt_dynar_foreach(g->nodes, cursor, node)
 110     free(node);
 111   xbt_dynar_free(&(g->nodes));
 112
 113   xbt_dynar_foreach(g->edges, cursor, edge)
 114     free(edge);
 115   xbt_dynar_free(&(g->edges));
 116
 117   free(g);
 118
 119   return;
 120 }
 121
 122
 123
 124 void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n,
 125                          void_f_pvoid_t * node_free_function,
 126                          void_f_pvoid_t * edge_free_function)
 127 {
 128   unsigned long nbr;
 129   int i;
 130   int cursor = 0;
 131   xbt_node_t node = NULL;
 132   xbt_edge_t edge = NULL;
 133
 134   nbr = xbt_dynar_length(g->edges);
 135   cursor=0;
 136   for (i = 0; i < nbr; i++)
 137     {
 138       xbt_dynar_cursor_get(g->edges, &cursor, &edge);
 139
 140       if ((edge->dst == n) || (edge->src == n))
 141         {
 142           xbt_graph_free_edge(g, edge, edge_free_function);
 143         }
 144       else xbt_dynar_cursor_step( g->edges, &cursor);
 145     }
 146
 147
 148  if ((node_free_function) && (n->data))
 149     node_free_function(n->data);
 150
 151   cursor = 0;
 152   xbt_dynar_foreach(g->nodes, cursor, node)
 153     {
 154       if (node == n)
 155         xbt_dynar_cursor_rm(g->nodes, &cursor);
 156
 157     }
 158   return;
 159 }
 160
 161 void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e,
 162                          void free_function(void *ptr))
 163 {
 164   int idx;
 165   int cursor = 0;
 166   xbt_edge_t edge = NULL;
 167
 168   if ((free_function) && (e->data))
 169     free_function(e->data);
 170
 171   xbt_dynar_foreach(g->edges, cursor, edge)
 172     {
 173     if (edge == e)
 174       {
 175         idx = __xbt_find_in_dynar(edge->dst->in,edge);
 176         xbt_dynar_remove_at(edge->dst->in, idx,NULL);
 177         idx = __xbt_find_in_dynar(edge->src->out,edge);
 178         xbt_dynar_remove_at(edge->src->out,idx,NULL);
 179         if (!g->directed)
 180           {
 181             idx = __xbt_find_in_dynar(edge->src->in,edge);
 182             xbt_dynar_remove_at(edge->src->in,idx,NULL);
 183             idx = __xbt_find_in_dynar(edge->dst->out,edge);
 184             xbt_dynar_remove_at(edge->dst->out,idx,NULL);
 185           }
 186         xbt_dynar_cursor_rm(g->edges, &cursor);
 187         break;
 188       }
 189     }
 190 }
 191
 192 int __xbt_find_in_dynar(xbt_dynar_t dynar, void *p)
 193 {
 194
 195   int cursor = 0;
 196   void *tmp=NULL;
 197
 198   xbt_dynar_foreach(dynar, cursor, tmp)
 199     {
 200       if (tmp == p)
 201         return cursor;
 202     }
 203   return -1;
 204 }
 205
 206 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
 207 {
 208   return g->nodes;
 209 }
 210
 211 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
 212 {
 213   return g->edges;
 214 }
 215
 216 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
 217 {
 218
 219   return e->src;
 220 }
 221
 222 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
 223 {
 224   return e->dst;
 225 }
 226
 227
 228 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
 229 {
 230   e->length = length;
 231
 232 }
 233
 234 double xbt_graph_edge_get_length(xbt_edge_t e)
 235 {
 236   return e->length;
 237 }
 238
 239
 240 /*construct the adjacency matrix corresponding to a graph,
 241   the weights are the distances between nodes
 242  */
 243 double *xbt_graph_get_length_matrix(xbt_graph_t g)
 244 {
 245   int cursor = 0;
 246   int in_cursor = 0;
 247   int  idx,i;
 248   unsigned long n;
 249   xbt_edge_t edge = NULL;
 250   xbt_node_t node=NULL;
 251   double *d = NULL;
 252
 253 # define D(u,v) d[(u)*n+(v)]
 254   n = xbt_dynar_length(g->nodes);
 255
 256   d = (double *) xbt_malloc(n * n * (sizeof(double)));
 257
 258   for (i = 0; i < n * n; i++)
 259     {
 260       d[i] = -1.0;
 261     }
 262
 263   xbt_dynar_foreach(g->nodes, cursor, node)
 264     {
 265       in_cursor = 0;
 266       D(cursor, cursor) = 0;
 267
 268       xbt_dynar_foreach(node->out, in_cursor, edge)
 269         {
 270           if (edge->dst==node)
 271             idx= __xbt_find_in_dynar(g->nodes, edge->src);
 272           else /*case of  undirected graphs*/
 273              idx = __xbt_find_in_dynar(g->nodes, edge->dst);
 274           D( cursor,idx) = edge->length;
 275         }
 276     }
 277
 278 # undef D
 279
 280   return d;
 281 }
 282
 283
 284 void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d,
 285                          xbt_node_t * p)
 286 {
 287   int i, j, k;
 288   unsigned long n;
 289   n = xbt_dynar_length(g->nodes);
 290
 291 # define D(u,v) d[(u)*n+(v)]
 292 # define P(u,v) p[(u)*n+(v)]
 293
 294   for (i = 0; i < n * n; i++)
 295     {
 296       d[i] = adj[i];
 297     }
 298
 299
 300   for (i = 0; i < n; i++)
 301     {
 302       for (j = 0; j < n; j++)
 303         {
 304           if (D(i, j) != -1)
 305             {
 306               P(i,j) =*((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, i));
 307             }
 308         }
 309     }
 310
 311   for (k = 0; k < n; k++)
 312     {
 313       for (i = 0; i < n; i++)
 314         {
 315           for (j = 0; j < n; j++)
 316             {
 317               if ((D(i, k) != -1) && (D(k, j) != -1))
 318                 {
 319                   if ((D(i, j) == -1) || (D(i, j) > D(i, k) + D(k, j)))
 320                     {
 321                       D(i, j) = D(i, k) + D(k, j);
 322                       P(i, j) = P(k, j);
 323                     }
 324                 }
 325             }
 326         }
 327     }
 328
 329
 330
 331 # undef P
 332 # undef D
 333 }
 334
 335 /*computes all-pairs shortest paths*/
 336 xbt_node_t *xbt_graph_shortest_paths(xbt_graph_t g)
 337 {
 338   xbt_node_t *p;
 339   xbt_node_t *r;
 340   int i, j, k;
 341   unsigned long n;
 342
 343   double *adj = NULL;
 344   double *d = NULL;
 345
 346 # define P(u,v) p[(u)*n+(v)]
 347 # define R(u,v) r[(u)*n+(v)]
 348
 349   n = xbt_dynar_length(g->nodes);
 350   adj = xbt_graph_get_length_matrix(g);
 351   d = xbt_malloc(n*n*sizeof(double));
 352   p = xbt_malloc(n*n*sizeof(xbt_node_t));
 353   r = xbt_malloc(n*n*sizeof(xbt_node_t));
 354
 355   xbt_floyd_algorithm(g, adj, d, p);
 356
 357   for (i = 0; i < n; i++)
 358     {
 359       for (j = 0; j < n; j++)
 360         {
 361           k = j;
 362
 363           while ((P(i, k)) && (__xbt_find_in_dynar(g->nodes, P(i, k)) != i))
 364             {
 365               k = __xbt_find_in_dynar(g->nodes, P(i, k));
 366             }
 367
 368           if (P(i, j))
 369             {
 370               R(i, j) = *((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, k));
 371             }
 372         }
 373     }
 374 # undef R
 375 # undef P
 376
 377   xbt_free(d);
 378   xbt_free(p);
 379   return r;
 380 }
 381
 382
 383 static xbt_graph_t parsed_graph = NULL;
 384 static xbt_dict_t parsed_nodes = NULL;
 385
 386
 387 static void __parse_graph_begin(void)
 388 {
 389   DEBUG0("<graph>");
 390 }
 391 static void __parse_graph_end(void)
 392 {
 393   DEBUG0("</graph>");
 394 }
 395
 396 static void __parse_node(void)
 397 {
 398   xbt_node_t node =
 399       xbt_graph_new_node(parsed_graph, (void *) A_graphxml_node_name);
 400
 401   xbt_dict_set(parsed_nodes, A_graphxml_node_name, (void *) node, NULL);
 402
 403   DEBUG1("<node label=\"%s\"/>", (char *) (node->data));
 404 }
 405 static void __parse_edge(void)
 406 {
 407   xbt_edge_t edge = xbt_graph_new_edge(parsed_graph,
 408                                        xbt_dict_get(parsed_nodes,
 409                                                     A_graphxml_edge_source),
 410                                        xbt_dict_get(parsed_nodes,
 411                                                     A_graphxml_edge_target),
 412                                        (void *) A_graphxml_edge_name);
 413
 414   xbt_graph_edge_set_length(edge, atof(A_graphxml_edge_length));
 415
 416   DEBUG4("<edge name=\"%s\"  source=\"%s\" target=\"%s\" length=\"%f\"/>",
 417          (char *) edge->data,
 418          (char *) (edge->src)->data,
 419          (char *) (edge->dst)->data,
 420          xbt_graph_edge_get_length(edge));
 421 }
 422
 423 xbt_graph_t xbt_graph_read(const char *filename)
 424 {
 425   xbt_graph_t graph = xbt_graph_new_graph(1, NULL);
 426
 427   parsed_graph = graph;
 428   parsed_nodes = xbt_dict_new();
 429
 430
 431   xbt_graph_parse_reset_parser();
 432
 433   STag_graphxml_graph_fun = __parse_graph_begin;
 434   ETag_graphxml_graph_fun = __parse_graph_end;
 435   ETag_graphxml_node_fun = __parse_node;
 436   ETag_graphxml_edge_fun = __parse_edge;
 437
 438
 439   xbt_graph_parse_open(filename);
 440   xbt_assert1((!xbt_graph_parse()), "Parse error in %s", filename);
 441   xbt_graph_parse_close();
 442
 443   xbt_dict_free(&parsed_nodes);
 444
 445   parsed_graph = NULL;
 446   return graph;
 447 }
 448 void xbt_graph_export_surfxml(xbt_graph_t g,
 449                               const char *filename,
 450                               const char *(node_name) (xbt_node_t),
 451                               const char *(edge_name) (xbt_edge_t)
 452     )
 453 {
 454
 455 }
 456