Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
plug memleak, fix uninitialized values, export functions
[simgrid.git] / 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
159   return;
160 }
161
162 void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e,
163                          void free_function(void *ptr))
164 {
165   int idx;
166   int cursor = 0;
167   xbt_edge_t edge = NULL; 
168
169   if ((free_function) && (e->data))
170     free_function(e->data);
171
172   xbt_dynar_foreach(g->edges, cursor, edge) 
173     {
174     if (edge == e)
175       {
176         idx = __xbt_find_in_dynar(edge->dst->in,edge); 
177         xbt_dynar_remove_at(edge->dst->in, idx,NULL);
178         idx = __xbt_find_in_dynar(edge->src->out,edge);
179         xbt_dynar_remove_at(edge->src->out,idx,NULL);   
180         if (!g->directed)
181           {
182             idx = __xbt_find_in_dynar(edge->src->in,edge); 
183             xbt_dynar_remove_at(edge->src->in,idx,NULL);
184             idx = __xbt_find_in_dynar(edge->dst->out,edge);
185             xbt_dynar_remove_at(edge->dst->out,idx,NULL);          
186           }
187         xbt_dynar_cursor_rm(g->edges, &cursor); 
188         free(edge);
189         break;
190       }
191     }
192 }
193
194 int __xbt_find_in_dynar(xbt_dynar_t dynar, void *p)
195 {
196
197   int cursor = 0;
198   void *tmp=NULL;
199
200   xbt_dynar_foreach(dynar, cursor, tmp)
201     {
202       if (tmp == p)
203         return cursor;
204     }
205   return -1;
206 }
207
208 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
209 {
210   return g->nodes;
211 }
212
213 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
214 {
215   return g->edges;
216 }
217
218 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
219 {
220
221   return e->src;
222 }
223
224 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
225 {
226   return e->dst;
227 }
228
229
230 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
231 {
232   e->length = length;
233
234 }
235
236 double xbt_graph_edge_get_length(xbt_edge_t e)
237 {
238   return e->length;
239 }
240
241
242 /*construct the adjacency matrix corresponding to a graph,
243   the weights are the distances between nodes
244  */
245 double *xbt_graph_get_length_matrix(xbt_graph_t g)
246 {
247   int cursor = 0;
248   int in_cursor = 0;
249   int  idx,i;
250   unsigned long n;
251   xbt_edge_t edge = NULL;
252   xbt_node_t node=NULL;
253   double *d = NULL;
254
255 # define D(u,v) d[(u)*n+(v)]
256   n = xbt_dynar_length(g->nodes);
257
258   d = (double *) xbt_new0(double, n*n);
259
260   for (i = 0; i < n * n; i++)
261     {
262       d[i] = -1.0;
263     }
264  
265   xbt_dynar_foreach(g->nodes, cursor, node) 
266     {
267       in_cursor = 0;
268       D(cursor, cursor) = 0;
269     
270       xbt_dynar_foreach(node->out, in_cursor, edge)
271         {
272           if (edge->dst==node) 
273             idx= __xbt_find_in_dynar(g->nodes, edge->src);
274           else /*case of  undirected graphs*/ 
275              idx = __xbt_find_in_dynar(g->nodes, edge->dst);
276           D( cursor,idx) = edge->length;
277         }
278     }
279
280 # undef D
281
282   return d;
283 }
284
285
286 void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d,
287                          xbt_node_t * p)
288 {
289   int i, j, k;
290   unsigned long n;
291   n = xbt_dynar_length(g->nodes);
292
293 # define D(u,v) d[(u)*n+(v)]
294 # define P(u,v) p[(u)*n+(v)]
295
296   for (i = 0; i < n * n; i++)
297     {
298       d[i] = adj[i];
299     }
300
301
302   for (i = 0; i < n; i++)
303     {
304       for (j = 0; j < n; j++)
305         {
306           if (D(i, j) != -1)
307             {
308               P(i,j) =*((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, i));       
309             }
310         }
311     }
312  
313   for (k = 0; k < n; k++)
314     {
315       for (i = 0; i < n; i++)
316         {
317           for (j = 0; j < n; j++)
318             {
319               if ((D(i, k) != -1) && (D(k, j) != -1))
320                 {
321                   if ((D(i, j) == -1) || (D(i, j) > D(i, k) + D(k, j)))
322                     {
323                       D(i, j) = D(i, k) + D(k, j);
324                       P(i, j) = P(k, j);
325                     }
326                 }
327             }
328         }
329     }
330
331
332
333 # undef P
334 # undef D
335 }
336
337 /*computes all-pairs shortest paths*/
338 xbt_node_t *xbt_graph_shortest_paths(xbt_graph_t g)
339 {
340   xbt_node_t *p;
341   xbt_node_t *r;
342   int i, j, k;
343   unsigned long n;
344
345   double *adj = NULL;
346   double *d = NULL;
347
348 # define P(u,v) p[(u)*n+(v)]
349 # define R(u,v) r[(u)*n+(v)]
350
351   n = xbt_dynar_length(g->nodes);
352   adj = xbt_graph_get_length_matrix(g);
353   d = xbt_new0(double,n*n);
354   p = xbt_new0(xbt_node_t,n*n);
355   r = xbt_new0(xbt_node_t,n*n);
356  
357   xbt_floyd_algorithm(g, adj, d, p);
358  
359   for (i = 0; i < n; i++)
360     {
361       for (j = 0; j < n; j++)
362         {
363           k = j;
364
365           while ((P(i, k)) && (__xbt_find_in_dynar(g->nodes, P(i, k)) != i))
366             {
367               k = __xbt_find_in_dynar(g->nodes, P(i, k));
368             }
369
370           if (P(i, j))
371             {
372               R(i, j) = *((xbt_node_t*) xbt_dynar_get_ptr(g->nodes, k));
373             }
374         }
375     }
376 # undef R
377 # undef P
378
379   free(d);
380   free(p);
381   free(adj);
382   return r;
383 }
384
385
386 static xbt_graph_t parsed_graph = NULL;
387 static xbt_dict_t parsed_nodes = NULL;
388
389
390 static void __parse_graph_begin(void)
391 {
392   DEBUG0("<graph>");
393 }
394 static void __parse_graph_end(void)
395 {
396   DEBUG0("</graph>");
397 }
398
399 static void __parse_node(void)
400 {
401   xbt_node_t node =
402       xbt_graph_new_node(parsed_graph, (void *) A_graphxml_node_name);
403
404   xbt_dict_set(parsed_nodes, A_graphxml_node_name, (void *) node, NULL);
405
406   DEBUG1("<node label=\"%s\"/>", (char *) (node->data));
407 }
408 static void __parse_edge(void)
409 {
410   xbt_edge_t edge = xbt_graph_new_edge(parsed_graph,
411                                        xbt_dict_get(parsed_nodes,
412                                                     A_graphxml_edge_source),
413                                        xbt_dict_get(parsed_nodes,
414                                                     A_graphxml_edge_target),
415                                        (void *) A_graphxml_edge_name);
416
417   xbt_graph_edge_set_length(edge, atof(A_graphxml_edge_length));
418
419   DEBUG4("<edge name=\"%s\"  source=\"%s\" target=\"%s\" length=\"%f\"/>",
420          (char *) edge->data,
421          (char *) (edge->src)->data,
422          (char *) (edge->dst)->data,
423          xbt_graph_edge_get_length(edge));
424 }
425
426 xbt_graph_t xbt_graph_read(const char *filename)
427 {
428   xbt_graph_t graph = xbt_graph_new_graph(1, NULL);
429
430   parsed_graph = graph;
431   parsed_nodes = xbt_dict_new();
432
433
434   xbt_graph_parse_reset_parser();
435
436   STag_graphxml_graph_fun = __parse_graph_begin;
437   ETag_graphxml_graph_fun = __parse_graph_end;
438   ETag_graphxml_node_fun = __parse_node;
439   ETag_graphxml_edge_fun = __parse_edge;
440
441
442   xbt_graph_parse_open(filename);
443   xbt_assert1((!xbt_graph_parse()), "Parse error in %s", filename);
444   xbt_graph_parse_close();
445
446   xbt_dict_free(&parsed_nodes);
447
448   parsed_graph = NULL;
449   return graph;
450 }
451
452 void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
453                                const char *(node_name) (xbt_node_t),
454                                const char *(edge_name) (xbt_edge_t))
455 {
456   int cursor = 0;
457   xbt_node_t node = NULL;
458   xbt_edge_t edge = NULL;
459   FILE *file = NULL;
460   const char *name=NULL;
461
462   file=fopen(filename,"w");
463   xbt_assert1(file, "Failed to open %s \n",filename);
464
465   fprintf(file,"graph test {\n");
466   fprintf(file,"  graph [overlap=scale]\n");
467
468   fprintf(file,"  node [shape=box, style=filled]\n");
469   fprintf(file,"  node [width=.3, height=.3, style=filled, color=skyblue]\n\n");
470   
471   xbt_dynar_foreach(g->nodes, cursor, node) {
472     fprintf(file,"  %p ", node);
473     if((node_name)&&((name=node_name(node)))) fprintf(file,"[label=\"%s\"]",name);
474     fprintf(file,";\n");
475   }
476   xbt_dynar_foreach(g->edges, cursor, edge) {
477     fprintf(file,"  %p -- %p",edge->src, edge->dst);
478     if((edge_name)&&((name=edge_name(edge)))) fprintf(file,"[label=\"%s\"]",name);
479     fprintf(file,";\n");
480   }
481   fprintf(file,"}\n");
482   fclose(file);
483 }
484
485 void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename,
486                                const char *(node_name)(xbt_node_t),
487                                const char *(edge_name)(xbt_edge_t))
488 {
489   int cursor = 0;
490   xbt_node_t node = NULL;
491   xbt_edge_t edge = NULL;
492   FILE *file = NULL;
493   const char *name = NULL;
494
495   file=fopen(filename,"w");
496   xbt_assert1(file, "Failed to open %s \n",filename);
497
498   fprintf(file,"<?xml version='1.0'?>\n");
499   fprintf(file,"<!DOCTYPE graph SYSTEM \"graphxml.dtd\">\n");
500   fprintf(file,"<graph>\n");
501   xbt_dynar_foreach(g->nodes, cursor, node) {
502     fprintf(file,"  <node name=\"%p\" ", node);
503     if((node_name)&&((name=node_name(node)))) fprintf(file,"label=\"%s\" ",name);
504     fprintf(file,">\n");
505   }
506   xbt_dynar_foreach(g->edges, cursor, edge) {
507     fprintf(file,"  <edge source=\"%p\" target =\"%p\" ",
508             edge->src, edge->dst );
509     if((edge_name)&&((name=edge_name(edge)))) fprintf(file,"label=\"%s\" ",name);
510     fprintf(file,">\n");
511   }
512   fprintf(file,"</graph>\n");
513   fclose(file);
514 }
515