X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/bc5f945db724984312da4c8d3905c1db7d168889..1d2f05c1a2fbdc662e0eb9ad8e2dd7f7e6f7986c:/src/xbt/graph.c?ds=sidebyside diff --git a/src/xbt/graph.c b/src/xbt/graph.c index b946ef8511..71ee5b5963 100644 --- a/src/xbt/graph.c +++ b/src/xbt/graph.c @@ -1,5 +1,8 @@ + + /* $Id$ */ + /* a generic graph library. */ /* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand. @@ -8,11 +11,13 @@ /* 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"); @@ -38,7 +43,7 @@ xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data) 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); + xbt_dynar_push(g->nodes,&node); return node; } @@ -50,17 +55,18 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_edge_t edge=NULL; edge=xbt_new0(struct xbt_edge,1); - xbt_dynar_push(src->out,edge); - xbt_dynar_push(dst->in,edge); + 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); + xbt_dynar_push(src->in,&edge); + xbt_dynar_push(dst->out,&edge); } - xbt_dynar_push(g->edges,edge); + + xbt_dynar_push(g->edges,&edge); return edge; } @@ -75,37 +81,34 @@ 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_edge_t edge=NULL; + xbt_node_t node=NULL; xbt_dynar_foreach(g->nodes,cursor,node) - xbt_graph_remove_node(g,node,node_free_function); + xbt_graph_free_node(g,node,node_free_function); xbt_assert0(!xbt_dynar_length(g->edges), "Damnit, there are some remaining edges!"); - xbt_dynar_foreach(g->edges,cursor,edge) - xbt_graph_remove_edge(g,edge,edge_free_function); - xbt_dynar_free(&(g->nodes)); xbt_dynar_free(&(g->edges)); - -/* void xbt_dynar_free(g->edges); */ + fprintf(stderr,"%s","after free containers\n"); return; } -void xbt_graph_remove_node(xbt_graph_t g, xbt_node_t n, void free_function(void * ptr)) -{ +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); + free_function(n->data); + xbt_dynar_free_container(&(n->in)); + xbt_dynar_free_container(&(n->out)); xbt_dynar_foreach(g->nodes,cursor,node) { @@ -116,7 +119,7 @@ void xbt_graph_remove_node(xbt_graph_t g, xbt_node_t n, void free_function(void return; } -void xbt_graph_remove_edge(xbt_graph_t g, xbt_edge_t e, void free_function(void * ptr)) +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; @@ -153,27 +156,230 @@ void xbt_graph_remove_edge(xbt_graph_t g, xbt_edge_t e, void free_function(void } +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) +{ + return g->edges; +} + +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) +{ + + int cursor=0; + xbt_node_t tmp; + xbt_dynar_foreach(g->nodes,cursor,tmp) + { + if (tmp==n) + break; + } + return (cursor-1); +} + +void xbt_graph_edge_set_length(xbt_edge_t e, double length) +{ + e->length=length; + +} +double xbt_graph_edge_get_length(xbt_edge_t e) +{ + return e->length; +} + + +/*construct the adjacency matrix corresponding to a graph, + the weights are the distances between nodes + */ +double* xbt_graph_get_length_matrix(xbt_graph_t g) +{ + 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; + 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;inodes,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 + +return d; +} + + /* 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) +{ + 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 +} + +/*computes all-pairs shortest paths*/ +xbt_node_t* xbt_graph_shortest_paths(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; +} + 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) { +static void __parse_graph_begin(void) +{ DEBUG0(""); } -static void __parse_graph_end(void) { +static void __parse_graph_end(void) +{ DEBUG0(""); } -static void __parse_node(void) { - DEBUG1("",A_graphxml_node_name); + +static void __parse_node(void) +{ + 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) { - DEBUG2("",A_graphxml_edge_source, - A_graphxml_edge_target); +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)); } 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(); @@ -182,11 +388,21 @@ xbt_graph_t xbt_graph_read(const char *filename) 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) + ) +{ + +} + +/* ./xbt/graphxml_usage xbt/graph.xml --xbt-log=graph.thres=debug */