Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
using pointer to scalar is a strange way to return a value...
[simgrid.git] / src / xbt / graph.c
1 /* a generic graph library.                                                 */
2
3 /* Copyright (c) 2006, 2007, 2008, 2009, 2010. The SimGrid Team.
4  * All rights reserved.                                                     */
5
6 /* This program is free software; you can redistribute it and/or modify it
7  * under the terms of the license (GNU LGPL) which comes with this package. */
8
9 #include "simgrid_config.h" /* getline */
10 #include <errno.h>
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 #include "xbt/str.h"
20
21
22
23
24 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph");
25
26
27
28 /** @brief Constructor
29  *  @return a new graph
30  */
31 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
32 {
33   xbt_graph_t graph = NULL;
34   graph = xbt_new0(struct xbt_graph, 1);
35   graph->directed = directed;
36   graph->data = data;
37   graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL);
38   graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
39
40   return graph;
41 }
42
43 /** @brief add a node to the given graph */
44 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
45 {
46   xbt_node_t node = NULL;
47   node = xbt_new0(struct xbt_node, 1);
48   node->data = data;
49   if (g->directed)
50     /* only the "out" field is used */
51     node->in = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
52
53   node->out = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
54   node->position_x = -1.0;
55   node->position_y = -1.0;
56
57   xbt_dynar_push(g->nodes, &node);
58
59   return node;
60 }
61
62 /** @brief add an edge to the given graph */
63 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
64                               xbt_node_t src, xbt_node_t dst, void *data)
65 {
66   xbt_edge_t edge = NULL;
67
68   edge = xbt_new0(struct xbt_edge, 1);
69   xbt_dynar_push(src->out, &edge);
70   if (g->directed)
71     xbt_dynar_push(dst->in, &edge);
72   else                          /* only the "out" field is used */
73     xbt_dynar_push(dst->out, &edge);
74
75   edge->data = data;
76   edge->src = src;
77   edge->dst = dst;
78
79   xbt_dynar_push(g->edges, &edge);
80
81   return edge;
82 }
83
84 xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src,
85                               xbt_node_t dst)
86 {
87   xbt_edge_t edge;
88   unsigned int cursor;
89
90   xbt_dynar_foreach(src->out, cursor, edge) {
91     XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
92     if ((edge->src == src) && (edge->dst == dst))
93       return edge;
94   }
95   if (!g->directed) {
96     xbt_dynar_foreach(src->out, cursor, edge) {
97       XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
98       if ((edge->dst == src) && (edge->src == dst))
99         return edge;
100     }
101   }
102   return NULL;
103 }
104
105 void *xbt_graph_node_get_data(xbt_node_t node)
106 {
107   return node->data;
108 }
109
110 void xbt_graph_node_set_data(xbt_node_t node, void *data)
111 {
112   node->data = data;
113 }
114
115 void *xbt_graph_edge_get_data(xbt_edge_t edge)
116 {
117   return edge->data;
118 }
119
120 void xbt_graph_edge_set_data(xbt_edge_t edge, void *data)
121 {
122   edge->data = data;
123 }
124
125 /** @brief Destructor
126  *  @param g: poor victim
127  *  @param node_free_function: function to use to free data associated to each node
128  *  @param edge_free_function: function to use to free data associated to each edge
129  *  @param graph_free_function: function to use to free data associated to g
130  *
131  * Free the graph structure.
132  */
133 void xbt_graph_free_graph(xbt_graph_t g,
134                           void_f_pvoid_t node_free_function,
135                           void_f_pvoid_t edge_free_function,
136                           void_f_pvoid_t graph_free_function)
137 {
138   unsigned int cursor = 0;
139   xbt_node_t node = NULL;
140   xbt_edge_t edge = NULL;
141
142
143   xbt_dynar_foreach(g->nodes, cursor, node) {
144     xbt_dynar_free(&(node->out));
145     xbt_dynar_free(&(node->in));
146     if (node_free_function)
147       (*node_free_function) (node->data);
148   }
149
150   xbt_dynar_foreach(g->edges, cursor, edge) {
151     if (edge_free_function)
152       (*edge_free_function) (edge->data);
153   }
154
155   xbt_dynar_foreach(g->nodes, cursor, node)
156       free(node);
157   xbt_dynar_free(&(g->nodes));
158
159   xbt_dynar_foreach(g->edges, cursor, edge)
160       free(edge);
161   xbt_dynar_free(&(g->edges));
162   if (graph_free_function)
163     (*graph_free_function) (g->data);
164   free(g);
165   xbt_graph_parse_lex_destroy();
166   return;
167 }
168
169
170 /** @brief remove the given node from the given graph */
171 void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n,
172                          void_f_pvoid_t node_free_function,
173                          void_f_pvoid_t edge_free_function)
174 {
175   unsigned long nbr;
176   unsigned long i;
177   unsigned int cursor = 0;
178   xbt_node_t node = NULL;
179   xbt_edge_t edge = NULL;
180
181   nbr = xbt_dynar_length(g->edges);
182   cursor = 0;
183   for (i = 0; i < nbr; i++) {
184     xbt_dynar_get_cpy(g->edges, cursor, &edge);
185
186     if ((edge->dst == n) || (edge->src == n)) {
187       xbt_graph_free_edge(g, edge, edge_free_function);
188     } else
189       cursor++;
190   }
191
192   if ((node_free_function) && (n->data))
193     (*node_free_function) (n->data);
194
195   cursor = 0;
196   xbt_dynar_foreach(g->nodes, cursor, node)
197       if (node == n)
198     xbt_dynar_cursor_rm(g->nodes, &cursor);
199
200   xbt_dynar_free(&(n->in));
201   xbt_dynar_free(&(n->out));
202
203   free(n);
204
205   return;
206 }
207
208 /** @brief remove the given edge from the given graph */
209 void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e,
210                          void_f_pvoid_t free_function)
211 {
212   int idx;
213   unsigned int cursor = 0;
214   xbt_edge_t edge = NULL;
215
216   if ((free_function) && (e->data))
217     (*free_function) (e->data);
218
219   xbt_dynar_foreach(g->edges, cursor, edge) {
220     if (edge == e) {
221       if (g->directed) {
222         idx = __xbt_find_in_dynar(edge->dst->in, edge);
223         xbt_dynar_remove_at(edge->dst->in, idx, NULL);
224       } else {                  /* only the out field is used */
225         idx = __xbt_find_in_dynar(edge->dst->out, edge);
226         xbt_dynar_remove_at(edge->dst->out, idx, NULL);
227       }
228
229       idx = __xbt_find_in_dynar(edge->src->out, edge);
230       xbt_dynar_remove_at(edge->src->out, idx, NULL);
231
232       xbt_dynar_cursor_rm(g->edges, &cursor);
233       free(edge);
234       break;
235     }
236   }
237 }
238
239 int __xbt_find_in_dynar(xbt_dynar_t dynar, void *p)
240 {
241
242   unsigned int cursor = 0;
243   void *tmp = NULL;
244
245   xbt_dynar_foreach(dynar, cursor, tmp) {
246     if (tmp == p)
247       return cursor;
248   }
249   return -1;
250 }
251
252 /** @brief Retrieve the graph's nodes as a dynar */
253 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
254 {
255   return g->nodes;
256 }
257
258 /** @brief Retrieve the graph's edges as a dynar */
259 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
260 {
261   return g->edges;
262 }
263
264 /** @brief Retrieve the node at the source of the given edge */
265 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
266 {
267   return e->src;
268 }
269
270 /** @brief Retrieve the node being the target of the given edge */
271 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
272 {
273   return e->dst;
274 }
275
276 /** @brief Retrieve the outgoing edges of the given node */
277 xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n)
278 {
279   return n->out;
280 }
281
282 /** @brief Set the weight of the given edge */
283 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
284 {
285   e->length = length;
286
287 }
288
289 double xbt_graph_edge_get_length(xbt_edge_t e)
290 {
291   return e->length;
292 }
293
294
295 /** @brief construct the adjacency matrix corresponding to the given graph
296  *
297  * The weights are the distances between nodes
298  */
299 double *xbt_graph_get_length_matrix(xbt_graph_t g)
300 {
301   unsigned int cursor = 0;
302   unsigned int in_cursor = 0;
303   unsigned long idx, i;
304   unsigned long n;
305   xbt_edge_t edge = NULL;
306   xbt_node_t node = NULL;
307   double *d = NULL;
308
309 # define D(u,v) d[(u)*n+(v)]
310   n = xbt_dynar_length(g->nodes);
311
312   d = (double *) xbt_new0(double, n * n);
313
314   for (i = 0; i < n * n; i++) {
315     d[i] = -1.0;
316   }
317
318   xbt_dynar_foreach(g->nodes, cursor, node) {
319     in_cursor = 0;
320     D(cursor, cursor) = 0;
321
322     xbt_dynar_foreach(node->out, in_cursor, edge) {
323       if (edge->dst == node)
324         idx = __xbt_find_in_dynar(g->nodes, edge->src);
325       else                      /*case of  undirected graphs */
326         idx = __xbt_find_in_dynar(g->nodes, edge->dst);
327       D(cursor, idx) = edge->length;
328     }
329   }
330
331 # undef D
332
333   return d;
334 }
335
336 /** @brief Floyd-Warshall algorithm for shortest path finding
337  *
338  * From wikipedia:
339  *
340  * The Floyd–Warshall algorithm takes as input an adjacency matrix
341  * representation of a weighted, directed graph (V, E). The weight of a
342  * path between two vertices is the sum of the weights of the edges along
343  * that path. The edges E of the graph may have negative weights, but the
344  * graph must not have any negative weight cycles. The algorithm computes,
345  * for each pair of vertices, the minimum weight among all paths between
346  * the two vertices. The running time complexity is Θ(|V|3).
347  */
348 void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d,
349                          xbt_node_t * p)
350 {
351   unsigned long i, j, k;
352   unsigned long n;
353   n = xbt_dynar_length(g->nodes);
354
355 # define D(u,v) d[(u)*n+(v)]
356 # define P(u,v) p[(u)*n+(v)]
357
358   for (i = 0; i < n * n; i++) {
359     d[i] = adj[i];
360   }
361
362
363   for (i = 0; i < n; i++) {
364     for (j = 0; j < n; j++) {
365       if (D(i, j) != -1) {
366         P(i, j) = *((xbt_node_t *) xbt_dynar_get_ptr(g->nodes, i));
367       }
368     }
369   }
370
371   for (k = 0; k < n; k++) {
372     for (i = 0; i < n; i++) {
373       for (j = 0; j < n; j++) {
374         if ((D(i, k) != -1) && (D(k, j) != -1)) {
375           if ((D(i, j) == -1) || (D(i, j) > D(i, k) + D(k, j))) {
376             D(i, j) = D(i, k) + D(k, j);
377             P(i, j) = P(k, j);
378           }
379         }
380       }
381     }
382   }
383
384
385
386 # undef P
387 # undef D
388 }
389
390 /** @brief computes all-pairs shortest paths */
391 xbt_node_t *xbt_graph_shortest_paths(xbt_graph_t g)
392 {
393   xbt_node_t *p;
394   xbt_node_t *r;
395   unsigned long i, j, k;
396   unsigned long n;
397
398   double *adj = NULL;
399   double *d = NULL;
400
401 # define P(u,v) p[(u)*n+(v)]
402 # define R(u,v) r[(u)*n+(v)]
403
404   n = xbt_dynar_length(g->nodes);
405   adj = xbt_graph_get_length_matrix(g);
406   d = xbt_new0(double, n * n);
407   p = xbt_new0(xbt_node_t, n * n);
408   r = xbt_new0(xbt_node_t, n * n);
409
410   xbt_floyd_algorithm(g, adj, d, p);
411
412   for (i = 0; i < n; i++) {
413     for (j = 0; j < n; j++) {
414       k = j;
415
416       while ((P(i, k)) && (__xbt_find_in_dynar(g->nodes, P(i, k)) != i)) {
417         k = __xbt_find_in_dynar(g->nodes, P(i, k));
418       }
419
420       if (P(i, j)) {
421         R(i, j) = *((xbt_node_t *) xbt_dynar_get_ptr(g->nodes, k));
422       }
423     }
424   }
425 # undef R
426 # undef P
427
428   free(d);
429   free(p);
430   free(adj);
431   return r;
432 }
433
434 /** @brief Extract a spanning tree of the given graph */
435 xbt_edge_t *xbt_graph_spanning_tree_prim(xbt_graph_t g)
436 {
437   int tree_size = 0;
438   int tree_size_max = xbt_dynar_length(g->nodes) - 1;
439   xbt_edge_t *tree = xbt_new0(xbt_edge_t, tree_size_max);
440   xbt_edge_t e, edge;
441   xbt_node_t node = NULL;
442   xbt_dynar_t edge_list = NULL;
443   xbt_heap_t heap = xbt_heap_new(10, NULL);
444   unsigned int cursor;
445
446   xbt_assert(!(g->directed),
447               "Spanning trees do not make sense on directed graphs");
448
449   xbt_dynar_foreach(g->nodes, cursor, node) {
450     node->xbtdata = NULL;
451   }
452
453   node = xbt_dynar_getfirst_as(g->nodes, xbt_node_t);
454   node->xbtdata = (void *) 1;
455   edge_list = node->out;
456   xbt_dynar_foreach(edge_list, cursor, e)
457       xbt_heap_push(heap, e, -(e->length));
458
459   while ((edge = xbt_heap_pop(heap))) {
460     if ((edge->src->xbtdata) && (edge->dst->xbtdata))
461       continue;
462     tree[tree_size++] = edge;
463     if (!(edge->src->xbtdata)) {
464       edge->src->xbtdata = (void *) 1;
465       edge_list = edge->src->out;
466       xbt_dynar_foreach(edge_list, cursor, e) {
467         xbt_heap_push(heap, e, -(e->length));
468       }
469     } else {
470       edge->dst->xbtdata = (void *) 1;
471       edge_list = edge->dst->out;
472       xbt_dynar_foreach(edge_list, cursor, e) {
473         xbt_heap_push(heap, e, -(e->length));
474       }
475     }
476     if (tree_size == tree_size_max)
477       break;
478   }
479
480   xbt_heap_free(heap);
481
482   return tree;
483 }
484
485 /** @brief Topological sort on the given graph
486  *
487  *  From wikipedia:
488  *
489  * In graph theory, a topological sort of a directed acyclic graph (DAG) is
490  * a linear ordering of its nodes which is compatible with the partial
491  * order R induced on the nodes where x comes before y (xRy) if there's a
492  * directed path from x to y in the DAG. An equivalent definition is that
493  * each node comes before all nodes to which it has edges. Every DAG has at
494  * least one topological sort, and may have many.
495  */
496 xbt_node_t *xbt_graph_topo_sort(xbt_graph_t g)
497 {
498
499   xbt_node_t *sorted;
500   unsigned int cursor;
501   int idx;
502   xbt_node_t node;
503   unsigned long n;
504
505   n = xbt_dynar_length(g->nodes);
506   idx = n - 1;
507
508   sorted = xbt_malloc(n * sizeof(xbt_node_t));
509
510   xbt_dynar_foreach(g->nodes, cursor, node)
511       node->xbtdata = xbt_new0(int, 1);
512
513   xbt_dynar_foreach(g->nodes, cursor, node)
514       xbt_graph_depth_visit(g, node, sorted, &idx);
515
516   xbt_dynar_foreach(g->nodes, cursor, node) {
517     free(node->xbtdata);
518     node->xbtdata = NULL;
519   }
520
521   return sorted;
522 }
523
524 /** @brief First-depth graph traversal */
525 void xbt_graph_depth_visit(xbt_graph_t g, xbt_node_t n,
526                            xbt_node_t * sorted, int *idx)
527 {
528   unsigned int cursor;
529   xbt_edge_t edge;
530
531   if (*((int *) (n->xbtdata)) == ALREADY_EXPLORED)
532     return;
533   else if (*((int *) (n->xbtdata)) == CURRENTLY_EXPLORING)
534     THROWF(0, 0, "There is a cycle");
535   else {
536     *((int *) (n->xbtdata)) = CURRENTLY_EXPLORING;
537
538     xbt_dynar_foreach(n->out, cursor, edge) {
539       xbt_graph_depth_visit(g, edge->dst, sorted, idx);
540     }
541
542     *((int *) (n->xbtdata)) = ALREADY_EXPLORED;
543     sorted[(*idx)--] = n;
544   }
545 }
546
547 /********************* Import and Export ******************/
548 static xbt_graph_t parsed_graph = NULL;
549 static xbt_dict_t parsed_nodes = NULL;
550
551 static void *(*__parse_node_label_and_data) (xbt_node_t, const char *,
552                                              const char *) = NULL;
553 static void *(*__parse_edge_label_and_data) (xbt_edge_t, const char *,
554                                              const char *) = NULL;
555
556 static void __parse_graph_begin(void)
557 {
558   XBT_DEBUG("<graph>");
559   if (A_graphxml_graph_isDirected == A_graphxml_graph_isDirected_true)
560     parsed_graph = xbt_graph_new_graph(1, NULL);
561   else
562     parsed_graph = xbt_graph_new_graph(0, NULL);
563
564   parsed_nodes = xbt_dict_new();
565 }
566
567 static void __parse_graph_end(void)
568 {
569   xbt_dict_free(&parsed_nodes);
570   XBT_DEBUG("</graph>");
571 }
572
573 static void __parse_node(void)
574 {
575   xbt_node_t node = xbt_graph_new_node(parsed_graph, NULL);
576
577   XBT_DEBUG("<node name=\"%s\"/>", A_graphxml_node_name);
578   if (__parse_node_label_and_data)
579     node->data = __parse_node_label_and_data(node, A_graphxml_node_label,
580                                              A_graphxml_node_data);
581   node->position_x = xbt_graph_parse_get_double(A_graphxml_node_position_x);
582   node->position_y = xbt_graph_parse_get_double(A_graphxml_node_position_y);
583
584   xbt_dict_set(parsed_nodes, A_graphxml_node_name, (void *) node, NULL);
585 }
586
587 static void __parse_edge(void)
588 {
589   xbt_edge_t edge = xbt_graph_new_edge(parsed_graph,
590                                        xbt_dict_get(parsed_nodes,
591                                                     A_graphxml_edge_source),
592                                        xbt_dict_get(parsed_nodes,
593                                                     A_graphxml_edge_target),
594                                        NULL);
595
596   if (__parse_edge_label_and_data)
597     edge->data = __parse_edge_label_and_data(edge, A_graphxml_edge_label,
598                                              A_graphxml_edge_data);
599
600   edge->length = xbt_graph_parse_get_double(A_graphxml_edge_length);
601
602   XBT_DEBUG("<edge  source=\"%s\" target=\"%s\" length=\"%f\"/>",
603          (char *) (edge->src)->data,
604          (char *) (edge->dst)->data, xbt_graph_edge_get_length(edge));
605 }
606
607 /** @brief Import a graph from a file following the GraphXML format */
608 xbt_graph_t xbt_graph_read(const char *filename,
609                            void *(*node_label_and_data) (xbt_node_t,
610                                                          const char *,
611                                                          const char *),
612                            void *(*edge_label_and_data) (xbt_edge_t,
613                                                          const char *,
614                                                          const char *))
615 {
616
617   xbt_graph_t graph = NULL;
618
619   __parse_node_label_and_data = node_label_and_data;
620   __parse_edge_label_and_data = edge_label_and_data;
621
622   xbt_graph_parse_reset_parser();
623
624   STag_graphxml_graph_fun = __parse_graph_begin;
625   ETag_graphxml_graph_fun = __parse_graph_end;
626   ETag_graphxml_node_fun = __parse_node;
627   ETag_graphxml_edge_fun = __parse_edge;
628
629   xbt_graph_parse_open(filename);
630   int res;
631   res = (*xbt_graph_parse) ();
632   xbt_assert(!res, "Parse error in %s", filename);
633   xbt_graph_parse_close();
634
635   graph = parsed_graph;
636   parsed_graph = NULL;
637
638   return graph;
639 }
640
641 /** @brief Export the given graph in the GraphViz formatting for visualization */
642 void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename,
643                                const char *(node_name) (xbt_node_t),
644                                const char *(edge_name) (xbt_edge_t))
645 {
646   unsigned int cursor = 0;
647   xbt_node_t node = NULL;
648   xbt_edge_t edge = NULL;
649   FILE *file = NULL;
650   const char *name = NULL;
651
652   file = fopen(filename, "w");
653   xbt_assert(file, "Failed to open %s \n", filename);
654
655   if (g->directed)
656     fprintf(file, "digraph test {\n");
657   else
658     fprintf(file, "graph test {\n");
659
660   fprintf(file, "  graph [overlap=scale]\n");
661
662   fprintf(file, "  node [shape=box, style=filled]\n");
663   fprintf(file,
664           "  node [width=.3, height=.3, style=filled, color=skyblue]\n\n");
665
666   xbt_dynar_foreach(g->nodes, cursor, node) {
667     fprintf(file, "  \"%p\" ", node);
668     if ((node_name) && ((name = node_name(node))))
669       fprintf(file, "[label=\"%s\"]", name);
670     fprintf(file, ";\n");
671   }
672   xbt_dynar_foreach(g->edges, cursor, edge) {
673     if (g->directed)
674       fprintf(file, "  \"%p\" -> \"%p\"", edge->src, edge->dst);
675     else
676       fprintf(file, "  \"%p\" -- \"%p\"", edge->src, edge->dst);
677     if ((edge_name) && ((name = edge_name(edge))))
678       fprintf(file, "[label=\"%s\"]", name);
679     fprintf(file, ";\n");
680   }
681   fprintf(file, "}\n");
682   fclose(file);
683 }
684
685 /** @brief Export the given graph in the GraphXML format */
686 void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
687                                const char *(node_name) (xbt_node_t),
688                                const char *(edge_name) (xbt_edge_t),
689                                const char *(node_data_print) (void *),
690                                const char *(edge_data_print) (void *))
691 {
692   unsigned int cursor = 0;
693   xbt_node_t node = NULL;
694   xbt_edge_t edge = NULL;
695   FILE *file = NULL;
696   const char *name = NULL;
697
698   file = fopen(filename, "w");
699   xbt_assert(file, "Failed to open %s \n", filename);
700
701   fprintf(file, "<?xml version='1.0'?>\n");
702   fprintf(file, "<!DOCTYPE graph SYSTEM \"graphxml.dtd\">\n");
703   if (g->directed)
704     fprintf(file, "<graph isDirected=\"true\">\n");
705   else
706     fprintf(file, "<graph isDirected=\"false\">\n");
707   xbt_dynar_foreach(g->nodes, cursor, node) {
708     fprintf(file, "  <node name=\"%p\" ", node);
709     if ((node_name) && ((name = node_name(node))))
710       fprintf(file, "label=\"%s\" ", name);
711     if ((node_data_print) && ((name = node_data_print(node->data))))
712       fprintf(file, "data=\"%s\" ", name);
713     fprintf(file, ">\n");
714   }
715   xbt_dynar_foreach(g->edges, cursor, edge) {
716     fprintf(file, "  <edge source=\"%p\" target =\"%p\" ",
717             edge->src, edge->dst);
718     if ((edge_name) && ((name = edge_name(edge))))
719       fprintf(file, "label=\"%s\" ", name);
720     if (edge->length >= 0.0)
721       fprintf(file, "length=\"%g\" ", edge->length);
722     if ((edge_data_print) && ((name = edge_data_print(edge->data))))
723       fprintf(file, "data=\"%s\" ", name);
724     fprintf(file, ">\n");
725   }
726   fprintf(file, "</graph>\n");
727   fclose(file);
728 }
729
730 /** @brief Load a graph from a file (in the SimGrid Graph format) */
731 xbt_graph_t xbt_graph_load (const char *filename)
732 {
733   FILE *file = NULL;
734   ssize_t read;
735   file = fopen (filename, "r");
736   xbt_assert(file, "Failed to open %s \n", filename);
737
738   xbt_dict_t nodes_dict = xbt_dict_new ();
739   xbt_graph_t ret = xbt_graph_new_graph (0, NULL);
740
741   //read the number of nodes
742   size_t size;
743   char *nnodes_str = NULL;
744   read = getline (&nnodes_str, &size, file);
745   if (read == -1)
746     THROWF(system_error, 0, "getline failed to read the number of nodes (errno = %d)", errno);
747   int i, nnodes = atoi (nnodes_str);
748   free (nnodes_str);
749
750   //read all nodes
751   for (i = 0; i < nnodes; i++){
752     char *node_str = NULL;
753     read = getline (&node_str, &size, file);
754     if (read == -1)
755       THROWF(system_error, 0, "getline failed to read all nodes (errno = %d)", errno);
756     xbt_node_t n;
757     char *name = xbt_strdup (node_str);
758     xbt_str_subst (name, '\n', '\0', 0);
759     n = xbt_graph_new_node (ret, name);
760     xbt_dict_set (nodes_dict, name, n, NULL);
761     free (node_str);
762   }
763
764   //read the number of edges
765   char *nedges_str = NULL;
766   read = getline (&nedges_str, &size, file);
767   if (read == -1)
768     THROWF(system_error, 0, "getline failed to read the number of edges (errno = %d)", errno);
769   int nedges = atoi (nedges_str);
770   free (nedges_str);
771
772   //read all edges
773   for (i = 0; i < nedges; i++){
774     char *edge_str = NULL, edge_id[200], node_source[200], node_target[200];
775     read = getline (&edge_str, &size, file);
776     if (read == -1)
777       THROWF(system_error, 0, "getline failed to read all edges (errno = %d)", errno);
778     sscanf (edge_str, "%s %s %s", edge_id, node_source, node_target);
779     free (edge_str);
780     xbt_str_subst (edge_id, '\n', '\0', 0);
781     xbt_str_subst (node_source, '\n', '\0', 0);
782     xbt_str_subst (node_target, '\n', '\0', 0);
783
784     xbt_node_t source = xbt_dict_get (nodes_dict, node_source);
785     xbt_node_t target = xbt_dict_get (nodes_dict, node_target);
786     xbt_graph_new_edge (ret, source, target, xbt_strdup(edge_id));
787   }
788   xbt_dict_free (&nodes_dict);
789   return ret;
790 }
791
792 /** @brief Save a graph from a file (in the SimGrid Graph format) */
793 void xbt_graph_save (xbt_graph_t span,
794                      const char *filename,
795                      const char *(nname) (xbt_node_t),
796                      const char *(ename) (xbt_edge_t))
797 {
798   FILE *file = NULL;
799   file = fopen(filename, "w");
800   xbt_assert(file, "Failed to open %s \n", filename);
801
802   xbt_dynar_t nodes = xbt_graph_get_nodes (span);
803   xbt_dynar_t edges = xbt_graph_get_edges (span);
804   unsigned int cpt;
805   xbt_node_t node;
806   fprintf (file, "%ld\n", xbt_dynar_length (nodes));
807   xbt_dynar_foreach (nodes, cpt, node) {
808     if (nname){
809       fprintf (file, "%s\n", nname(node));
810     }else{
811       fprintf (file, "%p\n", node);
812     }
813   }
814   fprintf (file, "%ld\n", xbt_dynar_length (edges));
815   xbt_edge_t edge;
816   xbt_dynar_foreach (edges, cpt, edge) {
817     xbt_node_t source = xbt_graph_edge_get_source (edge);
818     xbt_node_t target = xbt_graph_edge_get_target (edge);
819     if (ename){
820       if (nname){
821         fprintf (file, "%s %s %s\n", ename(edge), nname(source), nname(target));
822       }else{
823         fprintf (file, "%s %p %p\n", ename(edge), source, target);
824       }
825     }else{
826       if (nname){
827         fprintf (file, "%p %s %s\n", edge, nname(source), nname(target));
828       }else{
829         fprintf (file, "%p %p %p\n", edge, source, target);
830       }
831     }
832   }
833   fclose (file);
834 }