Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
shortest path algorithm already working
[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   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 static xbt_dict_t parsed_edges = NULL;
386
387
388 static void __parse_graph_begin(void)
389 {
390   DEBUG0("<graph>");
391 }
392 static void __parse_graph_end(void)
393 {
394   DEBUG0("</graph>");
395 }
396
397 static void __parse_node(void)
398 {
399   xbt_node_t node =
400       xbt_graph_new_node(parsed_graph, (void *) A_graphxml_node_name);
401
402   xbt_dict_set(parsed_nodes, A_graphxml_node_name, (void *) node, NULL);
403
404   DEBUG1("<node label=\"%s\"/>", (char *) (node->data));
405 }
406 static void __parse_edge(void)
407 {
408   xbt_edge_t edge = xbt_graph_new_edge(parsed_graph,
409                                        xbt_dict_get(parsed_nodes,
410                                                     A_graphxml_edge_source),
411                                        xbt_dict_get(parsed_nodes,
412                                                     A_graphxml_edge_target),
413                                        (void *) A_graphxml_edge_name);
414
415   xbt_dict_set(parsed_edges, A_graphxml_edge_name, (void *) edge, NULL);
416   xbt_graph_edge_set_length(edge, atof(A_graphxml_edge_length));
417
418   DEBUG4("<edge name=\"%s\"  source=\"%s\" target=\"%s\" length=\"%f\"/>",
419          (char *) edge->data,
420          (char *) (edge->src)->data,
421          (char *) (edge->dst)->data,
422          xbt_graph_edge_get_length(edge));
423 }
424
425 xbt_graph_t xbt_graph_read(const char *filename)
426 {
427   xbt_graph_t graph = xbt_graph_new_graph(1, NULL);
428
429   parsed_graph = graph;
430   parsed_nodes = xbt_dict_new();
431   parsed_edges = 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   xbt_dict_free(&parsed_edges);
448
449   parsed_graph = NULL;
450   return graph;
451 }
452 void xbt_graph_export_surfxml(xbt_graph_t g,
453                               const char *filename,
454                               const char *(node_name) (xbt_node_t),
455                               const char *(edge_name) (xbt_edge_t)
456     )
457 {
458
459 }
460