From 1d2f05c1a2fbdc662e0eb9ad8e2dd7f7e6f7986c Mon Sep 17 00:00:00 2001 From: dimitrov Date: Wed, 22 Mar 2006 14:34:28 +0000 Subject: [PATCH 1/1] some test code and bugs fixed + add of some accessors to members of private data structures edge and graph git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@1972 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- include/xbt/graph.h | 17 ++- src/xbt/graph.c | 272 +++++++++++++++++++++++++++++++++++----- src/xbt/graph_private.h | 5 + 3 files changed, 261 insertions(+), 33 deletions(-) diff --git a/include/xbt/graph.h b/include/xbt/graph.h index df4a32259c..310d7a2d2c 100644 --- a/include/xbt/graph.h +++ b/include/xbt/graph.h @@ -9,7 +9,7 @@ #ifndef _XBT_GRAPH_H #define _XBT_GRAPH_H #include "xbt/misc.h" /* SG_BEGIN_DECL */ - +#include "xbt/dynar.h" SG_BEGIN_DECL() typedef struct xbt_node *xbt_node_t; @@ -21,16 +21,23 @@ xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data); xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data); xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data); +void xbt_graph_edge_set_length(xbt_edge_t e, double length); +double xbt_graph_edge_get_length(xbt_edge_t e); +double* xbt_graph_get_length_matrix(xbt_graph_t g); -void xbt_graph_remove_node(xbt_graph_t g, xbt_node_t n, +void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n, void_f_pvoid_t *free_function); -void xbt_graph_remove_edge(xbt_graph_t g, xbt_edge_t e, +void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e, void_f_pvoid_t *free_function); 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); +xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g); +xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g); +xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e); +xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e); xbt_graph_t xbt_graph_read(const char *filename); /* Not implemented yet ! */ @@ -45,8 +52,8 @@ void xbt_graph_export_surfxml(xbt_graph_t g, const char *(edge_name)(xbt_edge_t) ); -void *xbt_graph_to_array(xbt_graph_t g); -void xbt_graph_shortest_paths(xbt_graph_t g); +/* void *xbt_graph_to_array(xbt_graph_t g); */ +xbt_node_t* xbt_graph_shortest_paths(xbt_graph_t g); void xbt_graph_topological_sort(xbt_graph_t g); 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 */ diff --git a/src/xbt/graph_private.h b/src/xbt/graph_private.h index 922f164a61..f08f3c77e4 100644 --- a/src/xbt/graph_private.h +++ b/src/xbt/graph_private.h @@ -16,6 +16,7 @@ typedef struct xbt_node { xbt_dynar_t out; xbt_dynar_t in; +/* int index; */ void *data; } s_xbt_node_t; @@ -26,6 +27,7 @@ typedef struct xbt_edge xbt_node_t src; xbt_node_t dst; void *data; + double length; } s_xbt_edge_t; /* Graph structure */ @@ -37,5 +39,8 @@ typedef struct xbt_graph unsigned short int directed; void *data; } s_xbt_graph_t; +void xbt_floyd_algorithm(xbt_graph_t g, double* adj,double* d, xbt_node_t* p); + +int xbt_get_node_index(xbt_graph_t g, xbt_node_t n); #endif /* _XBT_GRAPH_PRIVATE_H */ -- 2.20.1