X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/7410b72db09489e8b9d3ee3cb087f35882397d93..ab5814bd4ea6117ecf9ac2df328333e89eb45f5f:/src/xbt/graph.c diff --git a/src/xbt/graph.c b/src/xbt/graph.c index 0c8325a789..efacd0c2dc 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-2023. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it @@ -9,13 +9,10 @@ #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"); @@ -25,8 +22,7 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "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); @@ -36,10 +32,9 @@ 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 xbt_graph_new_node(const s_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 */ @@ -55,11 +50,9 @@ 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 xbt_graph_new_edge(const s_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); @@ -76,7 +69,7 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, voi } /** @brief Get the edge connecting src and dst */ -xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst) +xbt_edge_t xbt_graph_get_edge(const s_xbt_graph_t* g, const s_xbt_node_t* src, const s_xbt_node_t* dst) { xbt_edge_t edge; unsigned int cursor; @@ -97,7 +90,7 @@ xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst) } /** @brief Get the user data associated to a node */ -void *xbt_graph_node_get_data(xbt_node_t node) +void* xbt_graph_node_get_data(const s_xbt_node_t* node) { return node->data; } @@ -108,13 +101,13 @@ void xbt_graph_node_set_data(xbt_node_t node, void *data) node->data = data; } -/** @brief Get the user data associated to a edge */ -void *xbt_graph_edge_get_data(xbt_edge_t edge) +/** @brief Get the user data associated to an edge */ +void* xbt_graph_edge_get_data(const s_xbt_edge_t* edge) { return edge->data; } -/** @brief Set the user data associated to a edge */ +/** @brief Set the user data associated to an edge */ void xbt_graph_edge_set_data(xbt_edge_t edge, void *data) { edge->data = data; @@ -157,147 +150,31 @@ void xbt_graph_free_graph(xbt_graph_t g, void_f_pvoid_t node_free_function, void } /** @brief Retrieve the graph's nodes as a dynar */ -xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g) +xbt_dynar_t xbt_graph_get_nodes(const s_xbt_graph_t* g) { return g->nodes; } /** @brief Retrieve the graph's edges as a dynar */ -xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g) +xbt_dynar_t xbt_graph_get_edges(const s_xbt_graph_t* g) { return g->edges; } /** @brief Retrieve the node at the source of the given edge */ -xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e) +xbt_node_t xbt_graph_edge_get_source(const s_xbt_edge_t* e) { return e->src; } /** @brief Retrieve the node being the target of the given edge */ -xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e) +xbt_node_t xbt_graph_edge_get_target(const s_xbt_edge_t* e) { return e->dst; } /** @brief Retrieve the outgoing edges of the given node */ -xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n) +xbt_dynar_t xbt_graph_node_get_outedges(const s_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); -}