src/xbt/graph.c

   1 /*      $Id$     */
   2
   3 /* a generic graph library.                                                 */
   4
   5 /* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand.                     */
   6 /* All rights reserved.                                                     */
   7
   8 /* This program is free software; you can redistribute it and/or modify it
   9  * under the terms of the license (GNU LGPL) which comes with this package. */
  10
  11 #include <stdlib.h>
  12 #include "xbt/sysdep.h"
  13 #include "xbt/log.h"
  14 #include "xbt/graph.h"
  15 #include "graph_private.h"
  16 #include "xbt/graphxml_parse.h"
  17 #include "xbt/dict.h"
  18 #include "xbt/heap.h"
  19
  20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph, xbt, "Graph");
  21
  22
  23
  24 /** Constructor
  25  * \return a new graph
  26  */
  27 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
  28 {
  29   xbt_graph_t graph = NULL;
  30   graph = xbt_new0(struct xbt_graph, 1);
  31   graph->directed = directed;
  32   graph->data = data;
  33   graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  34   graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  35
  36   return graph;
  37 }
  38
  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   node->in = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  45   node->out = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  46   xbt_dynar_push(g->nodes, &node);
  47
  48   return node;
  49 }
  50
  51
  52 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
  53                               xbt_node_t src, xbt_node_t dst, void *data)
  54 {
  55   xbt_edge_t edge = NULL;
  56
  57
  58   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
  75 /** Destructor
  76  * \param l poor victim
  77  *
  78  * Free the graph structure.
  79  */
  80 void xbt_graph_free_graph(xbt_graph_t g,
  81                           void node_free_function(void *ptr),
  82                           void edge_free_function(void *ptr),
  83                           void graph_free_function(void *ptr))
  84 {
  85   int cursor = 0;
  86   xbt_node_t node = NULL;
  87   xbt_edge_t edge = NULL;
  88
  89
  90   xbt_dynar_foreach(g->nodes, cursor, node)
  91     {
  92       xbt_dynar_free(&(node->out));
  93       xbt_dynar_free(&(node->in));
  94       if(node_free_function)
  95         node_free_function(node->data);
  96     }
  97
  98   xbt_dynar_foreach(g->edges, cursor, edge)
  99     {
 100       if(edge_free_function)
 101         edge_free_function(edge->data);
 102     }
 103
 104   xbt_dynar_foreach(g->nodes, cursor, node)
 105     free(node);
 106   xbt_dynar_free(&(g->nodes));
 107
 108   xbt_dynar_foreach(g->edges, cursor, edge)
 109     free(edge);
 110   xbt_dynar_free(&(g->edges));
 111
 112   free(g);
 113
 114   return;
 115 }
 116
 117
 118
 119 void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n,
 120                          void_f_pvoid_t * node_free_function,
 121                          void_f_pvoid_t * edge_free_function)
 122 {
 123   unsigned long nbr;
 124   int i;
 125   int cursor = 0;
 126   xbt_node_t node = NULL;
 127   xbt_edge_t edge = NULL;
 128
 129   nbr = xbt_dynar_length(g->edges);
 130   cursor=0;
 131   for (i = 0; i < nbr; i++)
 132     {
 133       xbt_dynar_cursor_get(g->edges, &cursor, &edge);
 134
 135       if ((edge->dst == n) || (edge->src == n))
 136         {
 137           xbt_graph_free_edge(g, edge, edge_free_function);
 138         }
 139       else xbt_dynar_cursor_step( g->edges, &cursor);
 140     }
 141
 142
 143  if ((node_free_function) && (n->data))
 144     node_free_function(n->data);
 145
 146   cursor = 0;
 147   xbt_dynar_foreach(g->nodes, cursor, node)
 148     {
 149       if (node == n)
 150         xbt_dynar_cursor_rm(g->nodes, &cursor);
 151
 152     }
 153
 154   return;
 155 }
 156
 157 void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e,
 158                          void free_function(void *ptr))
 159 {
 160   int idx;
 161   int cursor = 0;
 162   xbt_edge_t edge = NULL;
 163
 164   if ((free_function) && (e->data))
 165     free_function(e->data);
 166
 167   xbt_dynar_foreach(g->edges, cursor, edge)
 168     {
 169     if (edge == e)
 170       {
 171         if (g->directed) {
 172           idx = __xbt_find_in_dynar(edge->dst->in,edge);
 173           xbt_dynar_remove_at(edge->dst->in, idx,NULL);
 174         } else { /* only the out field is used */
 175           idx = __xbt_find_in_dynar(edge->dst->out,edge);
 176           xbt_dynar_remove_at(edge->dst->out, idx,NULL);
 177         }
 178
 179         idx = __xbt_find_in_dynar(edge->src->out,edge);
 180         xbt_dynar_remove_at(edge->src->out,idx,NULL);
 181
 182         xbt_dynar_cursor_rm(g->edges, &cursor);
 183         free(edge);
 184         break;
 185       }
 186     }
 187 }
 188
 189 int __xbt_find_in_dynar(xbt_dynar_t dynar, void *p)
 190 {
 191
 192   int cursor = 0;
 193   void *tmp=NULL;
 194
 195   xbt_dynar_foreach(dynar, cursor, tmp)
 196     {
 197       if (tmp == p)
 198         return cursor;
 199     }
 200   return -1;
 201 }
 202
 203 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
 204 {
 205   return g->nodes;
 206 }
 207
 208 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
 209 {
 210   return g->edges;
 211 }
 212
 213 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
 214 {
 215
 216   return e->src;
 217 }
 218
 219 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
 220 {
 221   return e->dst;
 222 }
 223
 224
 225 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
 226 {
 227   e->length = length;
 228
 229 }
 230
 231 double xbt_graph_edge_get_length(xbt_edge_t e)
 232 {
 233   return e->length;
 234 }
 235
 236
 237 /*construct the adjacency matrix corresponding to a graph,
 238   the weights are the distances between nodes
 239  */
 240 double *xbt_graph_get_length_matrix(xbt_graph_t g)
 241 {
 242   int cursor = 0;
 243   int in_cursor = 0;
 244   int  idx,i;
 245   unsigned long n;
 246   xbt_edge_t edge = NULL;
 247   xbt_node_t node=NULL;
 248   double *d = NULL;
 249
 250 # define D(u,v) d[(u)*n+(v)]
 251   n = xbt_dynar_length(g->nodes);
 252
 253   d = (double *) xbt_new0(double, n*n);
 254
 255   for (i = 0; i < n * n; i++)
 256     {
 257       d[i] = -1.0;
 258     }
 259
 260   xbt_dynar_foreach(g->nodes, cursor, node)
 261     {
 262       in_cursor = 0;
 263       D(cursor, cursor) = 0;
 264
 265       xbt_dynar_foreach(node->out, in_cursor, edge)
 266         {
 267           if (edge->dst==node)
 268             idx= __xbt_find_in_dynar(g->nodes, edge->src);
 269           else /*case of  undirected graphs*/
 270              idx = __xbt_find_in_dynar(g->nodes, edge->dst);
 271           D( cursor,idx) = edge->length;
 272         }
 273     }
 274
 275 # undef D
 276
 277   return d;
 278 }
 279
 280
 281 void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d,
 282                          xbt_node_t * p)
 283 {
 284   int i, j, k;
 285   unsigned long n;
 286   n = xbt_dynar_length(g->nodes);
 287
 288 # define D(u,v) d[(u)*n+(v)]
 289 # define P(u,v) p[(u)*n+(v)]
 290
 291   for (i = 0; i < n * n; i++)
 292     {
 293       d[i] = adj[i];
 294     }
 295
 296
 297   for (i = 0; i < n; i++)
 298     {
 299       for (j = 0; j < n; j++)
 300         {
 301           if (D(i, j) != -1)
 302             {
 303               P(i,j) =*((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, i));
 304             }
 305         }
 306     }
 307
 308   for (k = 0; k < n; k++)
 309     {
 310       for (i = 0; i < n; i++)
 311         {
 312           for (j = 0; j < n; j++)
 313             {
 314               if ((D(i, k) != -1) && (D(k, j) != -1))
 315                 {
 316                   if ((D(i, j) == -1) || (D(i, j) > D(i, k) + D(k, j)))
 317                     {
 318                       D(i, j) = D(i, k) + D(k, j);
 319                       P(i, j) = P(k, j);
 320                     }
 321                 }
 322             }
 323         }
 324     }
 325
 326
 327
 328 # undef P
 329 # undef D
 330 }
 331
 332 /*computes all-pairs shortest paths*/
 333 xbt_node_t *xbt_graph_shortest_paths(xbt_graph_t g)
 334 {
 335   xbt_node_t *p;
 336   xbt_node_t *r;
 337   int i, j, k;
 338   unsigned long n;
 339
 340   double *adj = NULL;
 341   double *d = NULL;
 342
 343 # define P(u,v) p[(u)*n+(v)]
 344 # define R(u,v) r[(u)*n+(v)]
 345
 346   n = xbt_dynar_length(g->nodes);
 347   adj = xbt_graph_get_length_matrix(g);
 348   d = xbt_new0(double,n*n);
 349   p = xbt_new0(xbt_node_t,n*n);
 350   r = xbt_new0(xbt_node_t,n*n);
 351
 352   xbt_floyd_algorithm(g, adj, d, p);
 353
 354   for (i = 0; i < n; i++)
 355     {
 356       for (j = 0; j < n; j++)
 357         {
 358           k = j;
 359
 360           while ((P(i, k)) && (__xbt_find_in_dynar(g->nodes, P(i, k)) != i))
 361             {
 362               k = __xbt_find_in_dynar(g->nodes, P(i, k));
 363             }
 364
 365           if (P(i, j))
 366             {
 367               R(i, j) = *((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, k));
 368             }
 369         }
 370     }
 371 # undef R
 372 # undef P
 373
 374   free(d);
 375   free(p);
 376   free(adj);
 377   return r;
 378 }
 379
 380
 381 xbt_edge_t* xbt_graph_spanning_tree_prim(xbt_graph_t g)
 382 {
 383   int tree_size=0;
 384   int tree_size_max=xbt_dynar_length(g->nodes)-1;
 385   xbt_edge_t *tree = xbt_new0(xbt_edge_t,tree_size_max);
 386   xbt_edge_t e,edge;
 387   xbt_node_t node = NULL;
 388   xbt_dynar_t edge_list = NULL;
 389   xbt_heap_t heap = xbt_heap_new(10,NULL);
 390   int cursor;
 391
 392   xbt_assert0(!(g->directed),
 393               "Spanning trees do not make sense on directed graphs");
 394
 395   node = xbt_dynar_getfirst_as(g->nodes,xbt_node_t);
 396   node->xbtdata = (void*) 1;
 397   edge_list = node->out;
 398   xbt_dynar_foreach(edge_list, cursor, e)
 399     xbt_heap_push(heap,e, -(e->length));
 400
 401   while((edge=xbt_heap_pop(heap))) {
 402     if((edge->src->xbtdata) && (edge->dst->xbtdata)) continue;
 403     tree[tree_size++]=edge;
 404     if(!(edge->src->xbtdata)) {
 405       edge->src->xbtdata = (void*) 1;
 406       edge_list = edge->src->out;
 407       xbt_dynar_foreach(edge_list, cursor, e) {
 408         xbt_heap_push(heap,e, -(e->length));
 409       }
 410     } else {
 411       edge->dst->xbtdata = (void*) 1;
 412       edge_list = edge->dst->out;
 413       xbt_dynar_foreach(edge_list, cursor, e) {
 414         xbt_heap_push(heap,e, -(e->length));
 415       }
 416     }
 417     if(tree_size==tree_size_max) break;
 418   }
 419
 420   xbt_heap_free(heap);
 421
 422   xbt_dynar_foreach(g->nodes, cursor, node) {
 423     node->xbtdata = NULL;
 424   }
 425   return tree;
 426 }
 427
 428 /********************* Import and Export ******************/
 429 static xbt_graph_t parsed_graph = NULL;
 430 static xbt_dict_t parsed_nodes = NULL;
 431
 432 static void __parse_graph_begin(void)
 433 {
 434   DEBUG0("<graph>");
 435 }
 436 static void __parse_graph_end(void)
 437 {
 438   DEBUG0("</graph>");
 439 }
 440
 441 static void __parse_node(void)
 442 {
 443   xbt_node_t node =
 444       xbt_graph_new_node(parsed_graph, NULL);
 445
 446   xbt_dict_set(parsed_nodes, A_graphxml_node_name, (void *) node, NULL);
 447
 448   DEBUG1("<node label=\"%s\"/>", (char *) (node->data));
 449 }
 450 static void __parse_edge(void)
 451 {
 452   xbt_edge_t edge =
 453     xbt_graph_new_edge(parsed_graph,
 454                        xbt_dict_get(parsed_nodes,A_graphxml_edge_source),
 455                        xbt_dict_get(parsed_nodes,A_graphxml_edge_target),
 456                        NULL);
 457
 458   xbt_graph_edge_set_length(edge, atof(A_graphxml_edge_length));
 459
 460   DEBUG4("<edge name=\"%s\"  source=\"%s\" target=\"%s\" length=\"%f\"/>",
 461          (char *) edge->data,
 462          (char *) (edge->src)->data,
 463          (char *) (edge->dst)->data,
 464          xbt_graph_edge_get_length(edge));
 465 }
 466
 467 xbt_graph_t xbt_graph_read(const char *filename)
 468 {
 469   xbt_graph_t graph = xbt_graph_new_graph(1, NULL);
 470
 471   parsed_graph = graph;
 472   parsed_nodes = xbt_dict_new();
 473
 474
 475   xbt_graph_parse_reset_parser();
 476
 477   STag_graphxml_graph_fun = __parse_graph_begin;
 478   ETag_graphxml_graph_fun = __parse_graph_end;
 479   ETag_graphxml_node_fun = __parse_node;
 480   ETag_graphxml_edge_fun = __parse_edge;
 481
 482
 483   xbt_graph_parse_open(filename);
 484   xbt_assert1((!xbt_graph_parse()), "Parse error in %s", filename);
 485   xbt_graph_parse_close();
 486
 487   xbt_dict_free(&parsed_nodes);
 488
 489   parsed_graph = NULL;
 490   return graph;
 491 }
 492
 493 void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename,
 494                                const char *(node_name) (xbt_node_t),
 495                                const char *(edge_name) (xbt_edge_t))
 496 {
 497   int cursor = 0;
 498   xbt_node_t node = NULL;
 499   xbt_edge_t edge = NULL;
 500   FILE *file = NULL;
 501   const char *name=NULL;
 502
 503   file=fopen(filename,"w");
 504   xbt_assert1(file, "Failed to open %s \n",filename);
 505
 506   if(g->directed) fprintf(file,"digraph test {\n");
 507   else fprintf(file,"graph test {\n");
 508
 509   fprintf(file,"  graph [overlap=scale]\n");
 510
 511   fprintf(file,"  node [shape=box, style=filled]\n");
 512   fprintf(file,"  node [width=.3, height=.3, style=filled, color=skyblue]\n\n");
 513
 514   xbt_dynar_foreach(g->nodes, cursor, node) {
 515     fprintf(file,"  \"%p\" ", node);
 516     if((node_name)&&((name=node_name(node)))) fprintf(file,"[label=\"%s\"]",name);
 517     fprintf(file,";\n");
 518   }
 519   xbt_dynar_foreach(g->edges, cursor, edge) {
 520     if(g->directed)
 521       fprintf(file,"  \"%p\" -> \"%p\"",edge->src, edge->dst);
 522     else
 523       fprintf(file,"  \"%p\" -- \"%p\"",edge->src, edge->dst);
 524     if((edge_name)&&((name=edge_name(edge)))) fprintf(file,"[label=\"%s\"]",name);
 525     fprintf(file,";\n");
 526   }
 527   fprintf(file,"}\n");
 528   fclose(file);
 529 }
 530
 531 void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
 532                                const char *(node_name)(xbt_node_t),
 533                                const char *(edge_name)(xbt_edge_t))
 534 {
 535   int cursor = 0;
 536   xbt_node_t node = NULL;
 537   xbt_edge_t edge = NULL;
 538   FILE *file = NULL;
 539   const char *name = NULL;
 540
 541   file=fopen(filename,"w");
 542   xbt_assert1(file, "Failed to open %s \n",filename);
 543
 544   fprintf(file,"<?xml version='1.0'?>\n");
 545   fprintf(file,"<!DOCTYPE graph SYSTEM \"graphxml.dtd\">\n");
 546   fprintf(file,"<graph>\n");
 547   xbt_dynar_foreach(g->nodes, cursor, node) {
 548     fprintf(file,"  <node name=\"%p\" ", node);
 549     if((node_name)&&((name=node_name(node)))) fprintf(file,"label=\"%s\" ",name);
 550     fprintf(file,">\n");
 551   }
 552   xbt_dynar_foreach(g->edges, cursor, edge) {
 553     fprintf(file,"  <edge source=\"%p\" target =\"%p\" ",
 554             edge->src, edge->dst );
 555     if((edge_name)&&((name=edge_name(edge)))) fprintf(file,"label=\"%s\" ",name);
 556     fprintf(file,">\n");
 557   }
 558   fprintf(file,"</graph>\n");
 559   fclose(file);
 560 }
 561