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
  19 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph, xbt, "Graph");
  20
  21
  22
  23 /** 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 = NULL;
  29   graph = xbt_new0(struct xbt_graph, 1);
  30   graph->directed = directed;
  31   graph->data = data;
  32   graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  33   graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  34
  35   return graph;
  36 }
  37
  38 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
  39 {
  40   xbt_node_t node = NULL;
  41   node = xbt_new0(struct xbt_node, 1);
  42   node->data = data;
  43   node->in = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  44   node->out = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  45   xbt_dynar_push(g->nodes, &node);
  46
  47   return node;
  48 }
  49
  50
  51 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
  52                               xbt_node_t src, xbt_node_t dst, void *data)
  53 {
  54   xbt_edge_t edge = NULL;
  55
  56
  57   edge = xbt_new0(struct xbt_edge, 1);
  58   xbt_dynar_push(src->out, &edge);
  59   xbt_dynar_push(dst->in, &edge);
  60
  61   edge->data = data;
  62   edge->src = src;
  63   edge->dst = dst;
  64   if (!g->directed)
  65     {
  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 cursor = 0;
 127   xbt_node_t node = NULL;
 128   xbt_edge_t edge = NULL;
 129
 130   nbr = xbt_dynar_length(g->edges);
 131   cursor=0;
 132   for (i = 0; i < nbr; i++)
 133     {
 134       xbt_dynar_cursor_get(g->edges, &cursor, &edge);
 135
 136       if ((edge->dst == n) || (edge->src == n))
 137         {
 138           xbt_graph_free_edge(g, edge, edge_free_function);
 139         }
 140       else xbt_dynar_cursor_step( g->edges, &cursor);
 141     }
 142
 143
 144  if ((node_free_function) && (n->data))
 145     node_free_function(n->data);
 146
 147   cursor = 0;
 148   xbt_dynar_foreach(g->nodes, cursor, node)
 149     {
 150       if (node == n)
 151         xbt_dynar_cursor_rm(g->nodes, &cursor);
 152
 153     }
 154
 155   return;
 156 }
 157
 158 void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e,
 159                          void free_function(void *ptr))
 160 {
 161   int idx;
 162   int cursor = 0;
 163   xbt_edge_t edge = NULL;
 164
 165   if ((free_function) && (e->data))
 166     free_function(e->data);
 167
 168   xbt_dynar_foreach(g->edges, cursor, edge)
 169     {
 170     if (edge == e)
 171       {
 172         idx = __xbt_find_in_dynar(edge->dst->in,edge);
 173         xbt_dynar_remove_at(edge->dst->in, idx,NULL);
 174         idx = __xbt_find_in_dynar(edge->src->out,edge);
 175         xbt_dynar_remove_at(edge->src->out,idx,NULL);
 176         if (!g->directed)
 177           {
 178             idx = __xbt_find_in_dynar(edge->src->in,edge);
 179             xbt_dynar_remove_at(edge->src->in,idx,NULL);
 180             idx = __xbt_find_in_dynar(edge->dst->out,edge);
 181             xbt_dynar_remove_at(edge->dst->out,idx,NULL);
 182           }
 183         xbt_dynar_cursor_rm(g->edges, &cursor);
 184         free(edge);
 185         break;
 186       }
 187     }
 188 }
 189
 190 int __xbt_find_in_dynar(xbt_dynar_t dynar, void *p)
 191 {
 192
 193   int cursor = 0;
 194   void *tmp=NULL;
 195
 196   xbt_dynar_foreach(dynar, cursor, tmp)
 197     {
 198       if (tmp == p)
 199         return cursor;
 200     }
 201   return -1;
 202 }
 203
 204 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
 205 {
 206   return g->nodes;
 207 }
 208
 209 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
 210 {
 211   return g->edges;
 212 }
 213
 214 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
 215 {
 216
 217   return e->src;
 218 }
 219
 220 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
 221 {
 222   return e->dst;
 223 }
 224
 225
 226 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
 227 {
 228   e->length = length;
 229
 230 }
 231
 232 double xbt_graph_edge_get_length(xbt_edge_t e)
 233 {
 234   return e->length;
 235 }
 236
 237
 238 /*construct the adjacency matrix corresponding to a graph,
 239   the weights are the distances between nodes
 240  */
 241 double *xbt_graph_get_length_matrix(xbt_graph_t g)
 242 {
 243   int cursor = 0;
 244   int in_cursor = 0;
 245   int  idx,i;
 246   unsigned long n;
 247   xbt_edge_t edge = NULL;
 248   xbt_node_t node=NULL;
 249   double *d = NULL;
 250
 251 # define D(u,v) d[(u)*n+(v)]
 252   n = xbt_dynar_length(g->nodes);
 253
 254   d = (double *) xbt_new0(double, n*n);
 255
 256   for (i = 0; i < n * n; i++)
 257     {
 258       d[i] = -1.0;
 259     }
 260
 261   xbt_dynar_foreach(g->nodes, cursor, node)
 262     {
 263       in_cursor = 0;
 264       D(cursor, cursor) = 0;
 265
 266       xbt_dynar_foreach(node->out, in_cursor, edge)
 267         {
 268           if (edge->dst==node)
 269             idx= __xbt_find_in_dynar(g->nodes, edge->src);
 270           else /*case of  undirected graphs*/
 271              idx = __xbt_find_in_dynar(g->nodes, edge->dst);
 272           D( cursor,idx) = edge->length;
 273         }
 274     }
 275
 276 # undef D
 277
 278   return d;
 279 }
 280
 281
 282 void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d,
 283                          xbt_node_t * p)
 284 {
 285   int i, j, k;
 286   unsigned long n;
 287   n = xbt_dynar_length(g->nodes);
 288
 289 # define D(u,v) d[(u)*n+(v)]
 290 # define P(u,v) p[(u)*n+(v)]
 291
 292   for (i = 0; i < n * n; i++)
 293     {
 294       d[i] = adj[i];
 295     }
 296
 297
 298   for (i = 0; i < n; i++)
 299     {
 300       for (j = 0; j < n; j++)
 301         {
 302           if (D(i, j) != -1)
 303             {
 304               P(i,j) =*((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, i));
 305             }
 306         }
 307     }
 308
 309   for (k = 0; k < n; k++)
 310     {
 311       for (i = 0; i < n; i++)
 312         {
 313           for (j = 0; j < n; j++)
 314             {
 315               if ((D(i, k) != -1) && (D(k, j) != -1))
 316                 {
 317                   if ((D(i, j) == -1) || (D(i, j) > D(i, k) + D(k, j)))
 318                     {
 319                       D(i, j) = D(i, k) + D(k, j);
 320                       P(i, j) = P(k, j);
 321                     }
 322                 }
 323             }
 324         }
 325     }
 326
 327
 328
 329 # undef P
 330 # undef D
 331 }
 332
 333 /*computes all-pairs shortest paths*/
 334 xbt_node_t *xbt_graph_shortest_paths(xbt_graph_t g)
 335 {
 336   xbt_node_t *p;
 337   xbt_node_t *r;
 338   int i, j, k;
 339   unsigned long n;
 340
 341   double *adj = NULL;
 342   double *d = NULL;
 343
 344 # define P(u,v) p[(u)*n+(v)]
 345 # define R(u,v) r[(u)*n+(v)]
 346
 347   n = xbt_dynar_length(g->nodes);
 348   adj = xbt_graph_get_length_matrix(g);
 349   d = xbt_new0(double,n*n);
 350   p = xbt_new0(xbt_node_t,n*n);
 351   r = xbt_new0(xbt_node_t,n*n);
 352
 353   xbt_floyd_algorithm(g, adj, d, p);
 354
 355   for (i = 0; i < n; i++)
 356     {
 357       for (j = 0; j < n; j++)
 358         {
 359           k = j;
 360
 361           while ((P(i, k)) && (__xbt_find_in_dynar(g->nodes, P(i, k)) != i))
 362             {
 363               k = __xbt_find_in_dynar(g->nodes, P(i, k));
 364             }
 365
 366           if (P(i, j))
 367             {
 368               R(i, j) = *((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, k));
 369             }
 370         }
 371     }
 372 # undef R
 373 # undef P
 374
 375   free(d);
 376   free(p);
 377   free(adj);
 378   return r;
 379 }
 380
 381 static xbt_graph_t parsed_graph = NULL;
 382 static xbt_dict_t parsed_nodes = NULL;
 383
 384
 385 static void __parse_graph_begin(void)
 386 {
 387   DEBUG0("<graph>");
 388 }
 389 static void __parse_graph_end(void)
 390 {
 391   DEBUG0("</graph>");
 392 }
 393
 394 static void __parse_node(void)
 395 {
 396   xbt_node_t node =
 397       xbt_graph_new_node(parsed_graph, NULL);
 398
 399   xbt_dict_set(parsed_nodes, A_graphxml_node_name, (void *) node, NULL);
 400
 401   DEBUG1("<node label=\"%s\"/>", (char *) (node->data));
 402 }
 403 static void __parse_edge(void)
 404 {
 405   xbt_edge_t edge =
 406     xbt_graph_new_edge(parsed_graph,
 407                        xbt_dict_get(parsed_nodes,A_graphxml_edge_source),
 408                        xbt_dict_get(parsed_nodes,A_graphxml_edge_target),
 409                        NULL);
 410
 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,
 417          xbt_graph_edge_get_length(edge));
 418 }
 419
 420 xbt_graph_t xbt_graph_read(const char *filename)
 421 {
 422   xbt_graph_t graph = xbt_graph_new_graph(1, NULL);
 423
 424   parsed_graph = graph;
 425   parsed_nodes = 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
 442   parsed_graph = NULL;
 443   return graph;
 444 }
 445
 446 void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename,
 447                                const char *(node_name) (xbt_node_t),
 448                                const char *(edge_name) (xbt_edge_t))
 449 {
 450   int cursor = 0;
 451   xbt_node_t node = NULL;
 452   xbt_edge_t edge = NULL;
 453   FILE *file = NULL;
 454   const char *name=NULL;
 455
 456   file=fopen(filename,"w");
 457   xbt_assert1(file, "Failed to open %s \n",filename);
 458
 459   if(g->directed) fprintf(file,"digraph test {\n");
 460   else fprintf(file,"graph test {\n");
 461
 462   fprintf(file,"  graph [overlap=scale]\n");
 463
 464   fprintf(file,"  node [shape=box, style=filled]\n");
 465   fprintf(file,"  node [width=.3, height=.3, style=filled, color=skyblue]\n\n");
 466
 467   xbt_dynar_foreach(g->nodes, cursor, node) {
 468     fprintf(file,"  \"%p\" ", node);
 469     if((node_name)&&((name=node_name(node)))) fprintf(file,"[label=\"%s\"]",name);
 470     fprintf(file,";\n");
 471   }
 472   xbt_dynar_foreach(g->edges, cursor, edge) {
 473     if(g->directed)
 474       fprintf(file,"  \"%p\" -> \"%p\"",edge->src, edge->dst);
 475     else
 476       fprintf(file,"  \"%p\" -- \"%p\"",edge->src, edge->dst);
 477     if((edge_name)&&((name=edge_name(edge)))) fprintf(file,"[label=\"%s\"]",name);
 478     fprintf(file,";\n");
 479   }
 480   fprintf(file,"}\n");
 481   fclose(file);
 482 }
 483
 484 void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
 485                                const char *(node_name)(xbt_node_t),
 486                                const char *(edge_name)(xbt_edge_t))
 487 {
 488   int cursor = 0;
 489   xbt_node_t node = NULL;
 490   xbt_edge_t edge = NULL;
 491   FILE *file = NULL;
 492   const char *name = NULL;
 493
 494   file=fopen(filename,"w");
 495   xbt_assert1(file, "Failed to open %s \n",filename);
 496
 497   fprintf(file,"<?xml version='1.0'?>\n");
 498   fprintf(file,"<!DOCTYPE graph SYSTEM \"graphxml.dtd\">\n");
 499   fprintf(file,"<graph>\n");
 500   xbt_dynar_foreach(g->nodes, cursor, node) {
 501     fprintf(file,"  <node name=\"%p\" ", node);
 502     if((node_name)&&((name=node_name(node)))) fprintf(file,"label=\"%s\" ",name);
 503     fprintf(file,">\n");
 504   }
 505   xbt_dynar_foreach(g->edges, cursor, edge) {
 506     fprintf(file,"  <edge source=\"%p\" target =\"%p\" ",
 507             edge->src, edge->dst );
 508     if((edge_name)&&((name=edge_name(edge)))) fprintf(file,"label=\"%s\" ",name);
 509     fprintf(file,">\n");
 510   }
 511   fprintf(file,"</graph>\n");
 512   fclose(file);
 513 }
 514