Logo AND Algorithmique Numérique Distribuée

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