Logo AND Algorithmique Numérique Distribuée

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