Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
please sonar there
[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   for (i = 0; i < n * n; i++) {
216     d[i] = adj[i];
217   }
218
219   for (i = 0; i < n; i++) {
220     for (j = 0; j < n; j++) {
221       if (d[i*n+j] > -1) {
222         p[i*n+j] = *((xbt_node_t *) xbt_dynar_get_ptr(g->nodes, i));
223       }
224     }
225   }
226
227   for (k = 0; k < n; k++) {
228     for (i = 0; i < n; i++) {
229       for (j = 0; j < n; j++) {
230         if ((d[i*n+k] > -1) && (d[k*n+j] > -1)) {
231           if ((d[i*n+j] < 0) || (d[i*n+j] > d[i*n+k] + d[k*n+j])) {
232             d[i*n+j] = d[i*n+k] + d[k*n+j];
233             p[i*n+j] = p[k*n+j];
234           }
235         }
236       }
237     }
238   }
239 }
240
241 /** @brief Export the given graph in the GraphViz formatting for visualization */
242 void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename, const char *(node_name) (xbt_node_t),
243                                const char *(edge_name) (xbt_edge_t))
244 {
245   unsigned int cursor = 0;
246   xbt_node_t node = NULL;
247   xbt_edge_t edge = NULL;
248   const char *name = NULL;
249
250   FILE *file = fopen(filename, "w");
251   xbt_assert(file, "Failed to open %s \n", filename);
252
253   if (g->directed)
254     fprintf(file, "digraph test {\n");
255   else
256     fprintf(file, "graph test {\n");
257
258   fprintf(file, "  graph [overlap=scale]\n");
259
260   fprintf(file, "  node [shape=box, style=filled]\n");
261   fprintf(file, "  node [width=.3, height=.3, style=filled, color=skyblue]\n\n");
262
263   xbt_dynar_foreach(g->nodes, cursor, node) {
264     if (node_name){
265       fprintf(file, "  \"%s\";\n", node_name(node));
266     }else{
267       fprintf(file, "  \"%p\";\n", node);
268     }
269   }
270   xbt_dynar_foreach(g->edges, cursor, edge) {
271     const char *c;
272     const char *c_dir = "->";
273     const char *c_ndir = "--";
274     if (g->directed){
275       c = c_dir;
276     }else{
277       c = c_ndir;
278     }
279     if (node_name){
280       const char *src_name = node_name(edge->src);
281       const char *dst_name = node_name(edge->dst);
282       fprintf(file, "  \"%s\" %s \"%s\"", src_name, c, dst_name);
283     }else{
284       fprintf(file, "  \"%p\" %s \"%p\"", edge->src, c, edge->dst);
285     }
286
287     if (edge_name){
288       name = edge_name(edge);
289       if (name)
290         fprintf(file, "[label=\"%s\"]", name);
291     }
292     fprintf(file, ";\n");
293   }
294   fprintf(file, "}\n");
295   fclose(file);
296 }