X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/1d2f05c1a2fbdc662e0eb9ad8e2dd7f7e6f7986c..7d28d93b90eedd2a49da8b9b990296669e46d05c:/src/xbt/graph.c diff --git a/src/xbt/graph.c b/src/xbt/graph.c index 71ee5b5963..9801b9b66e 100644 --- a/src/xbt/graph.c +++ b/src/xbt/graph.c @@ -1,408 +1,180 @@ - - -/* $Id$ */ - - /* a generic graph library. */ -/* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand. - All rights reserved. */ +/* Copyright (c) 2006-2020. 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 #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" -XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph,xbt,"Graph"); +#include +#include +#include + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph"); -/** Constructor - * \return a new 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); - graph->directed=directed; - graph->data=data; - graph->nodes= xbt_dynar_new(sizeof(xbt_node_t), free); - graph->edges= xbt_dynar_new(sizeof(xbt_edge_t), free); + 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); + graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL); return 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); - node->data=data; - node->in=xbt_dynar_new(sizeof(xbt_node_t), free); - node->out=xbt_dynar_new(sizeof(xbt_node_t), free); - xbt_dynar_push(g->nodes,&node); - - return node; -} - - -xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, - xbt_node_t src, xbt_node_t dst, void *data) +/** @brief add a node to the given graph */ +xbt_node_t xbt_graph_new_node(const s_xbt_graph_t* g, void* data) { - xbt_edge_t edge=NULL; + xbt_node_t node= xbt_new0(struct xbt_node, 1); + node->data = data; + if (g->directed) + /* only the "out" field is used */ + node->in = xbt_dynar_new(sizeof(xbt_edge_t), NULL); - edge=xbt_new0(struct xbt_edge,1); - xbt_dynar_push(src->out,&edge); - xbt_dynar_push(dst->in,&edge); - edge->data=data; - edge->src=src; - edge->dst=dst; - if(!g->directed) - { - xbt_dynar_push(src->in,&edge); - xbt_dynar_push(dst->out,&edge); - } + node->out = xbt_dynar_new(sizeof(xbt_edge_t), NULL); + node->position_x = -1.0; + node->position_y = -1.0; - xbt_dynar_push(g->edges,&edge); + xbt_dynar_push(g->nodes, &node); - return edge; + return node; } +/** @brief add an edge to the given graph */ +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 = xbt_new0(struct xbt_edge, 1); + xbt_dynar_push(src->out, &edge); + if (g->directed) + xbt_dynar_push(dst->in, &edge); + else /* only the "out" field is used */ + xbt_dynar_push(dst->out, &edge); -/** Destructor - * \param l poor victim - * - * Free the graph structure. - */ -void xbt_graph_free_graph(xbt_graph_t g, - void node_free_function(void * ptr), - void edge_free_function(void * ptr), - void graph_free_function(void * ptr)) -{ - int cursor; - xbt_node_t node=NULL; - - xbt_dynar_foreach(g->nodes,cursor,node) - xbt_graph_free_node(g,node,node_free_function); - - xbt_assert0(!xbt_dynar_length(g->edges), - "Damnit, there are some remaining edges!"); - - xbt_dynar_free(&(g->nodes)); - xbt_dynar_free(&(g->edges)); - fprintf(stderr,"%s","after free containers\n"); + edge->data = data; + edge->src = src; + edge->dst = dst; + xbt_dynar_push(g->edges, &edge); - return; + return edge; } -void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n, void free_function(void * ptr)) -{ - int cursor; - xbt_node_t node=NULL; - - if ((free_function)&&(n->data)) - free_function(n->data); - - xbt_dynar_free_container(&(n->in)); +/** @brief Get the edge connecting src and 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; - xbt_dynar_free_container(&(n->out)); - xbt_dynar_foreach(g->nodes,cursor,node) - { - if (node==n) - xbt_dynar_cursor_rm(g->nodes,&cursor); - + xbt_dynar_foreach(src->out, cursor, edge) { + XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst); + if ((edge->src == src) && (edge->dst == dst)) + return edge; + } + if (!g->directed) { + xbt_dynar_foreach(src->out, cursor, edge) { + XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst); + if ((edge->dst == src) && (edge->src == dst)) + return edge; } - return; - -} -void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e, void free_function(void * ptr)) -{ - int cursor=0; - xbt_edge_t edge=NULL; - xbt_node_t node=NULL; - xbt_node_t temp=NULL; - - if ((free_function)&&(e->data)) - free_function(e->data); - xbt_dynar_foreach(g->nodes,cursor,node) - { - if (node==e->src) - xbt_dynar_pop(node->out,temp); - if (g->directed) - xbt_dynar_pop(node->in,temp); - - } - node=NULL; - cursor=0; - xbt_dynar_foreach(g->nodes,cursor,node) - { - if (node==e->dst) - xbt_dynar_pop(node->in,temp); - if (g->directed) - xbt_dynar_pop(node->out,temp); - - } - cursor=0; - xbt_dynar_foreach(g->edges,cursor,edge) - if (edge==e) - { - xbt_dynar_cursor_rm(g->edges,&cursor); - break; - } - + } + return NULL; } -xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g) -{ - return g->nodes; -} -xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g) +/** @brief Get the user data associated to a node */ +void* xbt_graph_node_get_data(const s_xbt_node_t* node) { - return g->edges; + return node->data; } -xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e) -{ - - return e->src; -} -xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e) -{ - return e->dst; -} -int xbt_get_node_index(xbt_graph_t g, xbt_node_t n) +/** @brief Set the user data associated to a node */ +void xbt_graph_node_set_data(xbt_node_t node, void *data) { - - int cursor=0; - xbt_node_t tmp; - xbt_dynar_foreach(g->nodes,cursor,tmp) - { - if (tmp==n) - break; - } - return (cursor-1); + node->data = data; } -void xbt_graph_edge_set_length(xbt_edge_t e, double length) +/** @brief Get the user data associated to an edge */ +void* xbt_graph_edge_get_data(const s_xbt_edge_t* edge) { - e->length=length; - + return edge->data; } -double xbt_graph_edge_get_length(xbt_edge_t e) + +/** @brief Set the user data associated to an edge */ +void xbt_graph_edge_set_data(xbt_edge_t edge, void *data) { - return e->length; + edge->data = data; } - -/*construct the adjacency matrix corresponding to a graph, - the weights are the distances between nodes +/** @brief Destructor + * @param g: poor victim + * @param node_free_function: function to use to free data associated to each node + * @param edge_free_function: function to use to free data associated to each edge + * @param graph_free_function: function to use to free data associated to g + * + * Free the graph structure. */ -double* xbt_graph_get_length_matrix(xbt_graph_t g) +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) { - fprintf(stderr,"%s","START GET LENGTHS\n" ); - int cursor = 0; - int in_cursor = 0; - int idx,i; - unsigned long n; - xbt_edge_t edge = NULL; + unsigned int cursor; xbt_node_t node; - double* d=NULL; - - # define D(u,v) d[(u)*n+(v)] - n = xbt_dynar_length(g->nodes); - - d = (double*)xbt_malloc(n*n*(sizeof(double))); - - for (i=0;iedges, 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) - {fprintf(stderr,"CURSOR: %d\n",cursor ); - in_cursor=0; - D(cursor-1,cursor-1)=0; - xbt_dynar_foreach(node->in,in_cursor,edge) - {fprintf(stderr,"EDGE IN: %s\n",(char*)edge->data ); -fprintf(stderr,"EDGE DST: %s\n",(char*)edge->dst->data ); - idx = xbt_get_node_index(g,edge->dst); - fprintf(stderr,"IDX: %d\n",idx ); -fprintf(stderr,"EDGE ADR: %x\n",(int)edge ); -fprintf(stderr,"EDGE LENGTH: %le\n", edge->length ); - D(cursor-1,idx) = edge->length; - } - } - fprintf(stderr,"BEFORE RETURN\n" ); - -# undef D + 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_free(&(g->nodes)); -return d; + if (graph_free_function) + graph_free_function(g->data); + free(g); } - /* calculate all-pairs shortest paths */ -/* the shortest distance between node i and j are stocked in distances[i][j] */ -void xbt_floyd_algorithm(xbt_graph_t g, double* adj,double* d, xbt_node_t* p) +/** @brief Retrieve the graph's nodes as a dynar */ +xbt_dynar_t xbt_graph_get_nodes(const s_xbt_graph_t* g) { - int 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;inodes,i) ; - } - } - - for(k=0;k 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 + return g->nodes; } -/*computes all-pairs shortest paths*/ -xbt_node_t* xbt_graph_shortest_paths(xbt_graph_t g) +/** @brief Retrieve the graph's edges as a dynar */ +xbt_dynar_t xbt_graph_get_edges(const s_xbt_graph_t* g) { - xbt_node_t* p; - xbt_node_t* r; - int i,j,k; - unsigned long n; - - double* adj=NULL; - double* d=NULL; - -# define P(u,v) p[(u)*n+(v)] -# define R(u,v) r[(u)*n+(v)] - - n = xbt_dynar_length(g->nodes); - adj= xbt_graph_get_length_matrix(g); - xbt_floyd_algorithm(g,adj,d,p); - - for(i=0;inodes,k); - } - } - } -# undef R -# undef P - - xbt_free(d); - xbt_free(p); - return r; + return g->edges; } -static xbt_graph_t parsed_graph=NULL; -static xbt_dict_t parsed_nodes=NULL; -static xbt_dict_t parsed_edges=NULL; - - -static void __parse_graph_begin(void) +/** @brief Retrieve the node at the source of the given edge */ +xbt_node_t xbt_graph_edge_get_source(const s_xbt_edge_t* e) { - DEBUG0(""); -} -static void __parse_graph_end(void) -{ - DEBUG0(""); + return e->src; } -static void __parse_node(void) +/** @brief Retrieve the node being the target of the given edge */ +xbt_node_t xbt_graph_edge_get_target(const s_xbt_edge_t* e) { - xbt_node_t node= xbt_graph_new_node(parsed_graph,(void*)A_graphxml_node_name); - - xbt_dict_set( parsed_nodes,A_graphxml_node_name, (void *)node, free); - - DEBUG1("",(char*)(node->data)); -} -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), - (void*) A_graphxml_edge_name); - - xbt_dict_set( parsed_edges,A_graphxml_edge_name, (void *)edge, free); - xbt_graph_edge_set_length(edge,atof(A_graphxml_edge_length)); - - DEBUG4("", - (char*)edge->data, - (char*)(edge->src)->data, - (char*)(edge->dst)->data, - xbt_graph_edge_get_length(edge)); + return e->dst; } -xbt_graph_t xbt_graph_read(const char *filename) -{ - xbt_graph_t graph = xbt_graph_new_graph(1,NULL); - - parsed_graph = graph; - parsed_nodes= xbt_dict_new(); - parsed_edges= xbt_dict_new(); - - - 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_assert1((!xbt_graph_parse()),"Parse error in %s",filename); - xbt_graph_parse_close(); - - parsed_graph = NULL; - return graph; -} -void xbt_graph_export_surfxml(xbt_graph_t g, - const char *filename, - const char *(node_name)(xbt_node_t), - const char *(edge_name)(xbt_edge_t) - ) +/** @brief Retrieve the outgoing edges of the given node */ +xbt_dynar_t xbt_graph_node_get_outedges(const s_xbt_node_t* n) { - + return n->out; } - -/* ./xbt/graphxml_usage xbt/graph.xml --xbt-log=graph.thres=debug */