Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Spell check, again O:-)
[simgrid.git] / src / xbt / graph.c
1 /* a generic graph library.                                                 */
2
3 /* Copyright (c) 2006-2014. 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 "xbt/sysdep.h"
10 #include "xbt/log.h"
11 #include "xbt/graph.h"
12 #include "graph_private.h"
13 #include "xbt/dict.h"
14 #include "xbt/heap.h"
15 #include "xbt/str.h"
16 #include "xbt/file.h"
17
18 #include <errno.h>
19 #include <stdlib.h>
20
21 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph");
22
23 /** @brief 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 /** @brief add a node to the given graph */
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   if (g->directed)
45     /* only the "out" field is used */
46     node->in = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
47
48   node->out = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
49   node->position_x = -1.0;
50   node->position_y = -1.0;
51
52   xbt_dynar_push(g->nodes, &node);
53
54   return node;
55 }
56
57 /** @brief add an edge to the given graph */
58 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data)
59 {
60   xbt_edge_t edge = NULL;
61
62   edge = xbt_new0(struct xbt_edge, 1);
63   xbt_dynar_push(src->out, &edge);
64   if (g->directed)
65     xbt_dynar_push(dst->in, &edge);
66   else                          /* only the "out" field is used */
67     xbt_dynar_push(dst->out, &edge);
68
69   edge->data = data;
70   edge->src = src;
71   edge->dst = dst;
72
73   xbt_dynar_push(g->edges, &edge);
74
75   return edge;
76 }
77
78 /** @brief Get the edge connecting src and dst */
79 xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst)
80 {
81   xbt_edge_t edge;
82   unsigned int cursor;
83
84   xbt_dynar_foreach(src->out, cursor, edge) {
85     XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
86     if ((edge->src == src) && (edge->dst == dst))
87       return edge;
88   }
89   if (!g->directed) {
90     xbt_dynar_foreach(src->out, cursor, edge) {
91       XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
92       if ((edge->dst == src) && (edge->src == dst))
93         return edge;
94     }
95   }
96   return NULL;
97 }
98
99 /** @brief Get the user data associated to a node */
100 void *xbt_graph_node_get_data(xbt_node_t node)
101 {
102   return node->data;
103 }
104
105 /** @brief Set the user data associated to a node */
106 void xbt_graph_node_set_data(xbt_node_t node, void *data)
107 {
108   node->data = data;
109 }
110
111 /** @brief Get the user data associated to a edge */
112 void *xbt_graph_edge_get_data(xbt_edge_t edge)
113 {
114   return edge->data;
115 }
116
117 /** @brief Set the user data associated to a edge */
118 void xbt_graph_edge_set_data(xbt_edge_t edge, void *data)
119 {
120   edge->data = data;
121 }
122
123 /** @brief Destructor
124  *  @param g: poor victim
125  *  @param node_free_function: function to use to free data associated to each node
126  *  @param edge_free_function: function to use to free data associated to each edge
127  *  @param graph_free_function: function to use to free data associated to g
128  *
129  * Free the graph structure.
130  */
131 void xbt_graph_free_graph(xbt_graph_t g, void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function,
132                           void_f_pvoid_t graph_free_function)
133 {
134   unsigned int cursor;
135   xbt_node_t node;
136   xbt_edge_t edge;
137
138   xbt_dynar_foreach(g->edges, cursor, edge) {
139     if (edge_free_function)
140       edge_free_function(edge->data);
141     free(edge);
142   }
143   xbt_dynar_free(&(g->edges));
144
145   xbt_dynar_foreach(g->nodes, cursor, node) {
146     xbt_dynar_free(&(node->out));
147     xbt_dynar_free(&(node->in));
148     if (node_free_function)
149       node_free_function(node->data);
150     free(node);
151   }
152   xbt_dynar_free(&(g->nodes));
153
154   if (graph_free_function)
155     graph_free_function(g->data);
156   free(g);
157 }
158
159 /** @brief Retrieve the graph's nodes as a dynar */
160 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
161 {
162   return g->nodes;
163 }
164
165 /** @brief Retrieve the graph's edges as a dynar */
166 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
167 {
168   return g->edges;
169 }
170
171 /** @brief Retrieve the node at the source of the given edge */
172 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
173 {
174   return e->src;
175 }
176
177 /** @brief Retrieve the node being the target of the given edge */
178 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
179 {
180   return e->dst;
181 }
182
183 /** @brief Retrieve the outgoing edges of the given node */
184 xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n)
185 {
186   return n->out;
187 }
188
189 /** @brief Set the weight of the given edge */
190 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
191 {
192   e->length = length;
193
194 }
195
196 /** @brief Get the length of a edge */
197 double xbt_graph_edge_get_length(xbt_edge_t edge)
198 {
199   return edge->length;
200 }
201
202 /** @brief Floyd-Warshall algorithm for shortest path finding
203  *
204  * From wikipedia:
205  *
206  * The Floyd-Warshall algorithm takes as input an adjacency matrix representation of a weighted, directed graph (V, E).
207  * The weight of a path between two vertices is the sum of the weights of the edges along that path. The edges E of the
208  * graph may have negative weights, but the graph must not have any negative weight cycles. The algorithm computes, for
209  * each pair of vertices, the minimum weight among all paths between the two vertices. The running time complexity is
210  * Θ(|V|3).
211  */
212 void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d, xbt_node_t * p)
213 {
214   unsigned long i, j, k;
215   unsigned long n;
216   n = xbt_dynar_length(g->nodes);
217
218 # define D(u,v) d[(u)*n+(v)]
219 # define P(u,v) p[(u)*n+(v)]
220
221   for (i = 0; i < n * n; i++) {
222     d[i] = adj[i];
223   }
224
225   for (i = 0; i < n; i++) {
226     for (j = 0; j < n; j++) {
227       if (D(i, j) != -1) {
228         P(i, j) = *((xbt_node_t *) xbt_dynar_get_ptr(g->nodes, i));
229       }
230     }
231   }
232
233   for (k = 0; k < n; k++) {
234     for (i = 0; i < n; i++) {
235       for (j = 0; j < n; j++) {
236         if ((D(i, k) != -1) && (D(k, j) != -1)) {
237           if ((D(i, j) == -1) || (D(i, j) > D(i, k) + D(k, j))) {
238             D(i, j) = D(i, k) + D(k, j);
239             P(i, j) = P(k, j);
240           }
241         }
242       }
243     }
244   }
245 # undef P
246 # undef D
247 }
248
249 /** @brief Export the given graph in the GraphViz formatting for visualization */
250 void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename, const char *(node_name) (xbt_node_t),
251                                const char *(edge_name) (xbt_edge_t))
252 {
253   unsigned int cursor = 0;
254   xbt_node_t node = NULL;
255   xbt_edge_t edge = NULL;
256   FILE *file = NULL;
257   const char *name = NULL;
258
259   file = fopen(filename, "w");
260   xbt_assert(file, "Failed to open %s \n", filename);
261
262   if (g->directed)
263     fprintf(file, "digraph test {\n");
264   else
265     fprintf(file, "graph test {\n");
266
267   fprintf(file, "  graph [overlap=scale]\n");
268
269   fprintf(file, "  node [shape=box, style=filled]\n");
270   fprintf(file, "  node [width=.3, height=.3, style=filled, color=skyblue]\n\n");
271
272   xbt_dynar_foreach(g->nodes, cursor, node) {
273     if (node_name){
274       fprintf(file, "  \"%s\";\n", node_name(node));
275     }else{
276       fprintf(file, "  \"%p\";\n", node);
277     }
278   }
279   xbt_dynar_foreach(g->edges, cursor, edge) {
280     const char *c;
281     const char *c_dir = "->";
282     const char *c_ndir = "--";
283     if (g->directed){
284       c = c_dir;
285     }else{
286       c = c_ndir;
287     }
288     const char *src_name, *dst_name;
289     if (node_name){
290       src_name = node_name(edge->src);
291       dst_name = node_name(edge->dst);
292       fprintf(file, "  \"%s\" %s \"%s\"", src_name, c, dst_name);
293     }else{
294       fprintf(file, "  \"%p\" %s \"%p\"", edge->src, c, edge->dst);
295     }
296
297     if ((edge_name) && ((name = edge_name(edge))))
298       fprintf(file, "[label=\"%s\"]", name);
299     fprintf(file, ";\n");
300   }
301   fprintf(file, "}\n");
302   fclose(file);
303 }