src/xbt/graph.c

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