X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/eb3be59d63b0d199fa3f32b5a22553e44cfb917a..c941a6b513a71ef786c4c749f8c01f5d018d976c:/src/xbt/graph.c?ds=sidebyside diff --git a/src/xbt/graph.c b/src/xbt/graph.c index 160a41f004..aef75bfac7 100644 --- a/src/xbt/graph.c +++ b/src/xbt/graph.c @@ -1,24 +1,22 @@ /* a generic graph library. */ -/* Copyright (c) 2006, 2007, 2008, 2009, 2010. The SimGrid Team. +/* Copyright (c) 2006-2014. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ -#include "simgrid_config.h" /* getline */ -#include -#include #include "xbt/sysdep.h" #include "xbt/log.h" #include "xbt/graph.h" #include "graph_private.h" -#include "xbt/graphxml_parse.h" #include "xbt/dict.h" #include "xbt/heap.h" #include "xbt/str.h" +#include "xbt/file.h" - +#include +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph"); @@ -81,6 +79,7 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, return edge; } +/** @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) { @@ -102,21 +101,25 @@ xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, return NULL; } +/** @brief Get the user data associated to a node */ void *xbt_graph_node_get_data(xbt_node_t node) { return node->data; } +/** @brief Set the user data associated to a node */ 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) { return edge->data; } +/** @brief Set the user data associated to a edge */ void xbt_graph_edge_set_data(xbt_edge_t edge, void *data) { edge->data = data; @@ -135,39 +138,33 @@ void xbt_graph_free_graph(xbt_graph_t g, void_f_pvoid_t edge_free_function, void_f_pvoid_t graph_free_function) { - unsigned int cursor = 0; - xbt_node_t node = NULL; - xbt_edge_t edge = NULL; + unsigned int cursor; + xbt_node_t node; + xbt_edge_t edge; + xbt_dynar_foreach(g->edges, cursor, edge) { + if (edge_free_function) + edge_free_function(edge->data); + free(edge); + } + xbt_dynar_free(&(g->edges)); xbt_dynar_foreach(g->nodes, cursor, node) { xbt_dynar_free(&(node->out)); xbt_dynar_free(&(node->in)); if (node_free_function) node_free_function(node->data); + free(node); } - - xbt_dynar_foreach(g->edges, cursor, edge) { - if (edge_free_function) - edge_free_function(edge->data); - } - - xbt_dynar_foreach(g->nodes, cursor, node) - free(node); xbt_dynar_free(&(g->nodes)); - xbt_dynar_foreach(g->edges, cursor, edge) - free(edge); - xbt_dynar_free(&(g->edges)); if (graph_free_function) graph_free_function(g->data); free(g); - xbt_graph_parse_lex_destroy(); - return; } -/** @brief remove the given node from the given graph */ +/** @brief remove the given node from the given graph */ void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n, void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function) @@ -205,7 +202,7 @@ void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n, return; } -/** @brief remove the given edge from the given graph */ +/** @brief remove the given edge from the given graph */ void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e, void_f_pvoid_t free_function) { @@ -286,9 +283,10 @@ void xbt_graph_edge_set_length(xbt_edge_t e, double length) } -double xbt_graph_edge_get_length(xbt_edge_t e) +/** @brief Get the length of a edge */ +double xbt_graph_edge_get_length(xbt_edge_t edge) { - return e->length; + return edge->length; } @@ -316,7 +314,6 @@ double *xbt_graph_get_length_matrix(xbt_graph_t g) } xbt_dynar_foreach(g->nodes, cursor, node) { - in_cursor = 0; D(cursor, cursor) = 0; xbt_dynar_foreach(node->out, in_cursor, edge) { @@ -544,100 +541,6 @@ void xbt_graph_depth_visit(xbt_graph_t g, xbt_node_t n, } } -/********************* Import and Export ******************/ -static xbt_graph_t parsed_graph = NULL; -static xbt_dict_t parsed_nodes = NULL; - -static void *(*__parse_node_label_and_data) (xbt_node_t, const char *, - const char *) = NULL; -static void *(*__parse_edge_label_and_data) (xbt_edge_t, const char *, - const char *) = NULL; - -static void __parse_graph_begin(void) -{ - XBT_DEBUG(""); - if (A_graphxml_graph_isDirected == A_graphxml_graph_isDirected_true) - parsed_graph = xbt_graph_new_graph(1, NULL); - else - parsed_graph = xbt_graph_new_graph(0, NULL); - - parsed_nodes = xbt_dict_new_homogeneous(NULL); -} - -static void __parse_graph_end(void) -{ - xbt_dict_free(&parsed_nodes); - XBT_DEBUG(""); -} - -static void __parse_node(void) -{ - xbt_node_t node = xbt_graph_new_node(parsed_graph, NULL); - - XBT_DEBUG("", A_graphxml_node_name); - if (__parse_node_label_and_data) - node->data = __parse_node_label_and_data(node, A_graphxml_node_label, - A_graphxml_node_data); - node->position_x = xbt_graph_parse_get_double(A_graphxml_node_position_x); - node->position_y = xbt_graph_parse_get_double(A_graphxml_node_position_y); - - xbt_dict_set(parsed_nodes, A_graphxml_node_name, (void *) node, NULL); -} - -static void __parse_edge(void) -{ - xbt_edge_t edge = xbt_graph_new_edge(parsed_graph, - xbt_dict_get(parsed_nodes, - A_graphxml_edge_source), - xbt_dict_get(parsed_nodes, - A_graphxml_edge_target), - NULL); - - if (__parse_edge_label_and_data) - edge->data = __parse_edge_label_and_data(edge, A_graphxml_edge_label, - A_graphxml_edge_data); - - edge->length = xbt_graph_parse_get_double(A_graphxml_edge_length); - - XBT_DEBUG("", - (char *) (edge->src)->data, - (char *) (edge->dst)->data, xbt_graph_edge_get_length(edge)); -} - -/** @brief Import a graph from a file following the GraphXML format */ -xbt_graph_t xbt_graph_read(const char *filename, - void *(*node_label_and_data) (xbt_node_t, - const char *, - const char *), - void *(*edge_label_and_data) (xbt_edge_t, - const char *, - const char *)) -{ - - xbt_graph_t graph = NULL; - - __parse_node_label_and_data = node_label_and_data; - __parse_edge_label_and_data = edge_label_and_data; - - xbt_graph_parse_reset_parser(); - - STag_graphxml_graph_fun = __parse_graph_begin; - ETag_graphxml_graph_fun = __parse_graph_end; - ETag_graphxml_node_fun = __parse_node; - ETag_graphxml_edge_fun = __parse_edge; - - xbt_graph_parse_open(filename); - _XBT_GNUC_UNUSED int res; - res = xbt_graph_parse(); - xbt_assert(!res, "Parse error in %s", filename); - xbt_graph_parse_close(); - - graph = parsed_graph; - parsed_graph = NULL; - - return graph; -} - /** @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), @@ -664,16 +567,30 @@ void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename, " node [width=.3, height=.3, style=filled, color=skyblue]\n\n"); xbt_dynar_foreach(g->nodes, cursor, node) { - fprintf(file, " \"%p\" ", node); - if ((node_name) && ((name = node_name(node)))) - fprintf(file, "[label=\"%s\"]", name); - fprintf(file, ";\n"); + if (node_name){ + fprintf(file, " \"%s\";\n", node_name(node)); + }else{ + fprintf(file, " \"%p\";\n", node); + } } xbt_dynar_foreach(g->edges, cursor, edge) { - if (g->directed) - fprintf(file, " \"%p\" -> \"%p\"", edge->src, edge->dst); - else - fprintf(file, " \"%p\" -- \"%p\"", edge->src, edge->dst); + 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"); @@ -710,7 +627,7 @@ void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename, fprintf(file, "label=\"%s\" ", name); if ((node_data_print) && ((name = node_data_print(node->data)))) fprintf(file, "data=\"%s\" ", name); - fprintf(file, ">\n"); + fprintf(file, "/>\n"); } xbt_dynar_foreach(g->edges, cursor, edge) { fprintf(file, " length); if ((edge_data_print) && ((name = edge_data_print(edge->data)))) fprintf(file, "data=\"%s\" ", name); - fprintf(file, ">\n"); + fprintf(file, "/>\n"); } fprintf(file, "\n"); fclose(file); @@ -741,18 +658,18 @@ xbt_graph_t xbt_graph_load (const char *filename) //read the number of nodes size_t size; char *nnodes_str = NULL; - read = getline (&nnodes_str, &size, file); + read = xbt_getline (&nnodes_str, &size, file); if (read == -1) - THROWF(system_error, 0, "getline failed to read the number of nodes (errno = %d)", errno); + THROWF(system_error, 0, "xbt_getline failed to read the number of nodes (errno = %d)", errno); int i, nnodes = atoi (nnodes_str); free (nnodes_str); //read all nodes for (i = 0; i < nnodes; i++){ char *node_str = NULL; - read = getline (&node_str, &size, file); + read = xbt_getline (&node_str, &size, file); if (read == -1) - THROWF(system_error, 0, "getline failed to read all nodes (errno = %d)", errno); + THROWF(system_error, 0, "xbt_getline failed to read all nodes (errno = %d)", errno); xbt_node_t n; char *name = xbt_strdup (node_str); xbt_str_subst (name, '\n', '\0', 0); @@ -763,18 +680,18 @@ xbt_graph_t xbt_graph_load (const char *filename) //read the number of edges char *nedges_str = NULL; - read = getline (&nedges_str, &size, file); + read = xbt_getline (&nedges_str, &size, file); if (read == -1) - THROWF(system_error, 0, "getline failed to read the number of edges (errno = %d)", errno); + THROWF(system_error, 0, "xbt_getline failed to read the number of edges (errno = %d)", errno); int nedges = atoi (nedges_str); free (nedges_str); //read all edges for (i = 0; i < nedges; i++){ char *edge_str = NULL, edge_id[200], node_source[200], node_target[200]; - read = getline (&edge_str, &size, file); + read = xbt_getline (&edge_str, &size, file); if (read == -1) - THROWF(system_error, 0, "getline failed to read all edges (errno = %d)", errno); + THROWF(system_error, 0, "xbt_getline failed to read all edges (errno = %d)", errno); sscanf (edge_str, "%s %s %s", edge_id, node_source, node_target); free (edge_str); xbt_str_subst (edge_id, '\n', '\0', 0);