X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/e39d3a7637657a34fe154348228c07842430828d..08a29a4221dc5cec95b766cd9b25c95dcc361df9:/src/xbt/graph.c diff --git a/src/xbt/graph.c b/src/xbt/graph.c index ef852803cc..004c9fbe37 100644 --- a/src/xbt/graph.c +++ b/src/xbt/graph.c @@ -1,6 +1,6 @@ /* a generic graph library. */ -/* Copyright (c) 2006-2014. The SimGrid Team. +/* Copyright (c) 2006-2019. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it @@ -9,27 +9,20 @@ #include "xbt/sysdep.h" #include "xbt/log.h" #include "xbt/graph.h" -#include "graph_private.h" #include "xbt/dict.h" -#include "xbt/heap.h" -#include "xbt/str.h" -#include "xbt/file.h" #include +#include #include - XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph"); - - /** @brief Constructor * @return a new graph */ xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data) { - xbt_graph_t graph = NULL; - graph = xbt_new0(struct xbt_graph, 1); + xbt_graph_t graph = xbt_new0(struct xbt_graph, 1); graph->directed = directed; graph->data = data; graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL); @@ -41,8 +34,7 @@ xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data) /** @brief add a node to the given graph */ xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data) { - xbt_node_t node = NULL; - node = xbt_new0(struct xbt_node, 1); + xbt_node_t node= xbt_new0(struct xbt_node, 1); node->data = data; if (g->directed) /* only the "out" field is used */ @@ -60,9 +52,7 @@ xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data) /** @brief add an edge to the given graph */ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data) { - xbt_edge_t edge = NULL; - - edge = xbt_new0(struct xbt_edge, 1); + xbt_edge_t edge = xbt_new0(struct xbt_edge, 1); xbt_dynar_push(src->out, &edge); if (g->directed) xbt_dynar_push(dst->in, &edge); @@ -131,9 +121,7 @@ void xbt_graph_edge_set_data(xbt_edge_t edge, void *data) * * Free the graph structure. */ -void xbt_graph_free_graph(xbt_graph_t g, - void_f_pvoid_t node_free_function, - void_f_pvoid_t edge_free_function, +void xbt_graph_free_graph(xbt_graph_t g, void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function, void_f_pvoid_t graph_free_function) { unsigned int cursor; @@ -161,7 +149,6 @@ void xbt_graph_free_graph(xbt_graph_t g, free(g); } - /** @brief Retrieve the graph's nodes as a dynar */ xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g) { @@ -191,125 +178,3 @@ xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n) { return n->out; } - -/** @brief Set the weight of the given edge */ -void xbt_graph_edge_set_length(xbt_edge_t e, double length) -{ - e->length = length; - -} - -/** @brief Get the length of a edge */ -double xbt_graph_edge_get_length(xbt_edge_t edge) -{ - return edge->length; -} - -/** @brief Floyd-Warshall algorithm for shortest path finding - * - * From wikipedia: - * - * The Floyd–Warshall algorithm takes as input an adjacency matrix - * representation of a weighted, directed graph (V, E). 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 graph may have negative weights, but the - * graph must not have any negative weight cycles. The algorithm computes, - * for each pair of vertices, the minimum weight among all paths between - * the two vertices. The running time complexity is Θ(|V|3). - */ -void xbt_floyd_algorithm(xbt_graph_t g, double *adj, double *d, - xbt_node_t * p) -{ - unsigned long i, j, k; - unsigned long n; - n = xbt_dynar_length(g->nodes); - -# define D(u,v) d[(u)*n+(v)] -# define P(u,v) p[(u)*n+(v)] - - for (i = 0; i < n * n; i++) { - d[i] = adj[i]; - } - - - for (i = 0; i < n; i++) { - for (j = 0; j < n; j++) { - if (D(i, j) != -1) { - P(i, j) = *((xbt_node_t *) xbt_dynar_get_ptr(g->nodes, i)); - } - } - } - - for (k = 0; k < n; k++) { - for (i = 0; i < n; i++) { - for (j = 0; j < n; j++) { - if ((D(i, k) != -1) && (D(k, j) != -1)) { - if ((D(i, j) == -1) || (D(i, j) > D(i, k) + D(k, j))) { - D(i, j) = D(i, k) + D(k, j); - P(i, j) = P(k, j); - } - } - } - } - } -# undef P -# undef D -} - -/** @brief Export the given graph in the GraphViz formatting for visualization */ -void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename, - const char *(node_name) (xbt_node_t), - const char *(edge_name) (xbt_edge_t)) -{ - unsigned int cursor = 0; - xbt_node_t node = NULL; - xbt_edge_t edge = NULL; - FILE *file = NULL; - const char *name = NULL; - - file = fopen(filename, "w"); - xbt_assert(file, "Failed to open %s \n", filename); - - if (g->directed) - fprintf(file, "digraph test {\n"); - else - fprintf(file, "graph test {\n"); - - fprintf(file, " graph [overlap=scale]\n"); - - fprintf(file, " node [shape=box, style=filled]\n"); - fprintf(file, - " node [width=.3, height=.3, style=filled, color=skyblue]\n\n"); - - xbt_dynar_foreach(g->nodes, cursor, node) { - if (node_name){ - fprintf(file, " \"%s\";\n", node_name(node)); - }else{ - fprintf(file, " \"%p\";\n", node); - } - } - xbt_dynar_foreach(g->edges, cursor, edge) { - const char *c; - const char *c_dir = "->"; - const char *c_ndir = "--"; - if (g->directed){ - c = c_dir; - }else{ - c = c_ndir; - } - const char *src_name, *dst_name; - if (node_name){ - src_name = node_name(edge->src); - dst_name = node_name(edge->dst); - fprintf(file, " \"%s\" %s \"%s\"", src_name, c, dst_name); - }else{ - fprintf(file, " \"%p\" %s \"%p\"", edge->src, c, edge->dst); - } - - if ((edge_name) && ((name = edge_name(edge)))) - fprintf(file, "[label=\"%s\"]", name); - fprintf(file, ";\n"); - } - fprintf(file, "}\n"); - fclose(file); -}