X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/4725d7a4bc5ac1fdae3e86222cdc23eaaf6fb226..ef57f86ce57e5fc8e0a9fb0da96f32da4516ce5d:/src/xbt/graph.c diff --git a/src/xbt/graph.c b/src/xbt/graph.c index 53341c83a6..61b83645f5 100644 --- a/src/xbt/graph.c +++ b/src/xbt/graph.c @@ -1,13 +1,13 @@ -/* $Id$ */ - /* a generic graph library. */ -/* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand. */ -/* All rights reserved. */ +/* Copyright (c) 2006, 2007, 2008, 2009, 2010. 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" @@ -16,6 +16,7 @@ #include "xbt/graphxml_parse.h" #include "xbt/dict.h" #include "xbt/heap.h" +#include "xbt/str.h" @@ -68,7 +69,7 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_dynar_push(src->out, &edge); if (g->directed) xbt_dynar_push(dst->in, &edge); - else /* only the "out" field is used */ + else /* only the "out" field is used */ xbt_dynar_push(dst->out, &edge); edge->data = data; @@ -80,39 +81,47 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, return edge; } -xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst) +/** @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 edge; unsigned int cursor; xbt_dynar_foreach(src->out, cursor, edge) { - DEBUG3("%p = %p--%p",edge,edge->src,edge->dst); - if((edge->src==src) && (edge->dst==dst)) return edge; + XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst); + if ((edge->src == src) && (edge->dst == dst)) + return edge; } - if(!g->directed) { + if (!g->directed) { xbt_dynar_foreach(src->out, cursor, edge) { - DEBUG3("%p = %p--%p",edge,edge->src,edge->dst); - if((edge->dst==src) && (edge->src==dst)) return edge; + XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst); + if ((edge->dst == src) && (edge->src == dst)) + return edge; } } 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; @@ -131,39 +140,34 @@ 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); - } - - xbt_dynar_foreach(g->edges, cursor, edge) { - if (edge_free_function) - (*edge_free_function)(edge->data); + node_free_function(node->data); + free(node); } - - 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); + if (graph_free_function) + graph_free_function(g->data); free(g); - - return; + xbt_graph_parse_lex_destroy(); } -/** @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) @@ -182,15 +186,15 @@ void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n, if ((edge->dst == n) || (edge->src == n)) { xbt_graph_free_edge(g, edge, edge_free_function); } else - cursor ++; + cursor++; } if ((node_free_function) && (n->data)) - (*node_free_function)(n->data); + node_free_function(n->data); cursor = 0; xbt_dynar_foreach(g->nodes, cursor, node) - if (node == n) + if (node == n) xbt_dynar_cursor_rm(g->nodes, &cursor); xbt_dynar_free(&(n->in)); @@ -201,7 +205,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) { @@ -210,14 +214,14 @@ void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e, xbt_edge_t edge = NULL; if ((free_function) && (e->data)) - (*free_function)(e->data); + free_function(e->data); xbt_dynar_foreach(g->edges, cursor, edge) { if (edge == e) { if (g->directed) { idx = __xbt_find_in_dynar(edge->dst->in, edge); xbt_dynar_remove_at(edge->dst->in, idx, NULL); - } else { /* only the out field is used */ + } else { /* only the out field is used */ idx = __xbt_find_in_dynar(edge->dst->out, edge); xbt_dynar_remove_at(edge->dst->out, idx, NULL); } @@ -260,7 +264,6 @@ xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g) /** @brief Retrieve the node at the source of the given edge */ xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e) { - return e->src; } @@ -270,6 +273,11 @@ xbt_node_t xbt_graph_edge_get_target(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) +{ + return n->out; +} /** @brief Set the weight of the given edge */ void xbt_graph_edge_set_length(xbt_edge_t e, double length) @@ -278,9 +286,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; } @@ -314,7 +323,7 @@ double *xbt_graph_get_length_matrix(xbt_graph_t g) xbt_dynar_foreach(node->out, in_cursor, edge) { if (edge->dst == node) idx = __xbt_find_in_dynar(g->nodes, edge->src); - else /*case of undirected graphs */ + else /*case of undirected graphs */ idx = __xbt_find_in_dynar(g->nodes, edge->dst); D(cursor, idx) = edge->length; } @@ -435,7 +444,7 @@ xbt_edge_t *xbt_graph_spanning_tree_prim(xbt_graph_t g) xbt_heap_t heap = xbt_heap_new(10, NULL); unsigned int cursor; - xbt_assert0(!(g->directed), + xbt_assert(!(g->directed), "Spanning trees do not make sense on directed graphs"); xbt_dynar_foreach(g->nodes, cursor, node) { @@ -446,7 +455,7 @@ xbt_edge_t *xbt_graph_spanning_tree_prim(xbt_graph_t g) node->xbtdata = (void *) 1; edge_list = node->out; xbt_dynar_foreach(edge_list, cursor, e) - xbt_heap_push(heap, e, -(e->length)); + xbt_heap_push(heap, e, -(e->length)); while ((edge = xbt_heap_pop(heap))) { if ((edge->src->xbtdata) && (edge->dst->xbtdata)) @@ -500,10 +509,10 @@ xbt_node_t *xbt_graph_topo_sort(xbt_graph_t g) sorted = xbt_malloc(n * sizeof(xbt_node_t)); xbt_dynar_foreach(g->nodes, cursor, node) - node->xbtdata = xbt_new0(int, 1); + node->xbtdata = xbt_new0(int, 1); xbt_dynar_foreach(g->nodes, cursor, node) - xbt_graph_depth_visit(g, node, sorted, &idx); + xbt_graph_depth_visit(g, node, sorted, &idx); xbt_dynar_foreach(g->nodes, cursor, node) { free(node->xbtdata); @@ -523,7 +532,7 @@ void xbt_graph_depth_visit(xbt_graph_t g, xbt_node_t n, if (*((int *) (n->xbtdata)) == ALREADY_EXPLORED) return; else if (*((int *) (n->xbtdata)) == CURRENTLY_EXPLORING) - THROW0(0, 0, "There is a cycle"); + THROWF(0, 0, "There is a cycle"); else { *((int *) (n->xbtdata)) = CURRENTLY_EXPLORING; @@ -541,39 +550,37 @@ 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; + const char *) = NULL; static void *(*__parse_edge_label_and_data) (xbt_edge_t, const char *, - const char *) = NULL; + const char *) = NULL; static void __parse_graph_begin(void) { - DEBUG0(""); + 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(); + parsed_nodes = xbt_dict_new_homogeneous(NULL); } static void __parse_graph_end(void) { xbt_dict_free(&parsed_nodes); - DEBUG0(""); + XBT_DEBUG(""); } static void __parse_node(void) { xbt_node_t node = xbt_graph_new_node(parsed_graph, NULL); - DEBUG1("", A_graphxml_node_name); + 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); - xbt_graph_parse_get_double(&(node->position_x), - A_graphxml_node_position_x); - xbt_graph_parse_get_double(&(node->position_y), - A_graphxml_node_position_y); + 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); } @@ -583,17 +590,17 @@ 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); + 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); - xbt_graph_parse_get_double(&(edge->length), A_graphxml_edge_length); + edge->length = xbt_graph_parse_get_double(A_graphxml_edge_length); - DEBUG3("", + XBT_DEBUG("", (char *) (edge->src)->data, (char *) (edge->dst)->data, xbt_graph_edge_get_length(edge)); } @@ -601,11 +608,11 @@ static void __parse_edge(void) /** @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 *)) + const char *, + const char *), + void *(*edge_label_and_data) (xbt_edge_t, + const char *, + const char *)) { xbt_graph_t graph = NULL; @@ -621,7 +628,9 @@ xbt_graph_t xbt_graph_read(const char *filename, ETag_graphxml_edge_fun = __parse_edge; xbt_graph_parse_open(filename); - xbt_assert1((!(*xbt_graph_parse)()), "Parse error in %s", 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; @@ -642,7 +651,7 @@ void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename, const char *name = NULL; file = fopen(filename, "w"); - xbt_assert1(file, "Failed to open %s \n", filename); + xbt_assert(file, "Failed to open %s \n", filename); if (g->directed) fprintf(file, "digraph test {\n"); @@ -656,16 +665,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"); @@ -688,7 +711,7 @@ void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename, const char *name = NULL; file = fopen(filename, "w"); - xbt_assert1(file, "Failed to open %s \n", filename); + xbt_assert(file, "Failed to open %s \n", filename); fprintf(file, "\n"); fprintf(file, "\n"); @@ -718,3 +741,109 @@ void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename, fprintf(file, "\n"); fclose(file); } + +/** @brief Load a graph from a file (in the SimGrid Graph format) */ +xbt_graph_t xbt_graph_load (const char *filename) +{ + FILE *file = NULL; + ssize_t read; + file = fopen (filename, "r"); + xbt_assert(file, "Failed to open %s \n", filename); + + xbt_dict_t nodes_dict = xbt_dict_new_homogeneous(NULL); + xbt_graph_t ret = xbt_graph_new_graph (0, NULL); + + //read the number of nodes + size_t size; + char *nnodes_str = NULL; + read = getline (&nnodes_str, &size, file); + if (read == -1) + THROWF(system_error, 0, "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); + if (read == -1) + THROWF(system_error, 0, "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); + n = xbt_graph_new_node (ret, name); + xbt_dict_set (nodes_dict, name, n, NULL); + free (node_str); + } + + //read the number of edges + char *nedges_str = NULL; + read = getline (&nedges_str, &size, file); + if (read == -1) + THROWF(system_error, 0, "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); + if (read == -1) + THROWF(system_error, 0, "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); + xbt_str_subst (node_source, '\n', '\0', 0); + xbt_str_subst (node_target, '\n', '\0', 0); + + xbt_node_t source = xbt_dict_get (nodes_dict, node_source); + xbt_node_t target = xbt_dict_get (nodes_dict, node_target); + xbt_graph_new_edge (ret, source, target, xbt_strdup(edge_id)); + } + xbt_dict_free (&nodes_dict); + return ret; +} + +/** @brief Save a graph from a file (in the SimGrid Graph format) */ +void xbt_graph_save (xbt_graph_t span, + const char *filename, + const char *(nname) (xbt_node_t), + const char *(ename) (xbt_edge_t)) +{ + FILE *file = NULL; + file = fopen(filename, "w"); + xbt_assert(file, "Failed to open %s \n", filename); + + xbt_dynar_t nodes = xbt_graph_get_nodes (span); + xbt_dynar_t edges = xbt_graph_get_edges (span); + unsigned int cpt; + xbt_node_t node; + fprintf (file, "%lu\n", xbt_dynar_length (nodes)); + xbt_dynar_foreach (nodes, cpt, node) { + if (nname){ + fprintf (file, "%s\n", nname(node)); + }else{ + fprintf (file, "%p\n", node); + } + } + fprintf (file, "%lu\n", xbt_dynar_length (edges)); + xbt_edge_t edge; + xbt_dynar_foreach (edges, cpt, edge) { + xbt_node_t source = xbt_graph_edge_get_source (edge); + xbt_node_t target = xbt_graph_edge_get_target (edge); + if (ename){ + if (nname){ + fprintf (file, "%s %s %s\n", ename(edge), nname(source), nname(target)); + }else{ + fprintf (file, "%s %p %p\n", ename(edge), source, target); + } + }else{ + if (nname){ + fprintf (file, "%p %s %s\n", edge, nname(source), nname(target)); + }else{ + fprintf (file, "%p %p %p\n", edge, source, target); + } + } + } + fclose (file); +}