6 /* a generic graph library. */
8 /* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand.
9 All rights reserved. */
11 /* This program is free software; you can redistribute it and/or modify it
12 * under the terms of the license (GNU LGPL) which comes with this package. */
15 #include "xbt/sysdep.h"
17 #include "xbt/graph.h"
18 #include "graph_private.h"
19 #include "xbt/graphxml_parse.h"
22 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph,xbt,"Graph");
27 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
29 xbt_graph_t graph=NULL;
30 graph=xbt_new0(struct xbt_graph,1);
31 graph->directed=directed;
33 graph->nodes= xbt_dynar_new(sizeof(xbt_node_t), free);
34 graph->edges= xbt_dynar_new(sizeof(xbt_edge_t), free);
39 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
42 node=xbt_new0(struct xbt_node,1);
44 node->in=xbt_dynar_new(sizeof(xbt_node_t), free);
45 node->out=xbt_dynar_new(sizeof(xbt_node_t), free);
46 xbt_dynar_push(g->nodes,&node);
52 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
53 xbt_node_t src, xbt_node_t dst, void *data)
57 edge=xbt_new0(struct xbt_edge,1);
58 xbt_dynar_push(src->out,&edge);
59 xbt_dynar_push(dst->in,&edge);
65 xbt_dynar_push(src->in,&edge);
66 xbt_dynar_push(dst->out,&edge);
69 xbt_dynar_push(g->edges,&edge);
76 * \param l poor victim
78 * Free the graph structure.
80 void xbt_graph_free_graph(xbt_graph_t g,
81 void node_free_function(void * ptr),
82 void edge_free_function(void * ptr),
83 void graph_free_function(void * ptr))
88 xbt_dynar_foreach(g->nodes,cursor,node)
89 xbt_graph_free_node(g,node,node_free_function);
91 xbt_assert0(!xbt_dynar_length(g->edges),
92 "Damnit, there are some remaining edges!");
94 xbt_dynar_free(&(g->nodes));
95 xbt_dynar_free(&(g->edges));
96 fprintf(stderr,"%s","after free containers\n");
102 void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n, void free_function(void * ptr))
105 xbt_node_t node=NULL;
107 if ((free_function)&&(n->data))
108 free_function(n->data);
110 xbt_dynar_free_container(&(n->in));
112 xbt_dynar_free_container(&(n->out));
113 xbt_dynar_foreach(g->nodes,cursor,node)
116 xbt_dynar_cursor_rm(g->nodes,&cursor);
122 void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e, void free_function(void * ptr))
125 xbt_edge_t edge=NULL;
126 xbt_node_t node=NULL;
127 xbt_node_t temp=NULL;
129 if ((free_function)&&(e->data))
130 free_function(e->data);
131 xbt_dynar_foreach(g->nodes,cursor,node)
134 xbt_dynar_pop(node->out,temp);
136 xbt_dynar_pop(node->in,temp);
141 xbt_dynar_foreach(g->nodes,cursor,node)
144 xbt_dynar_pop(node->in,temp);
146 xbt_dynar_pop(node->out,temp);
150 xbt_dynar_foreach(g->edges,cursor,edge)
153 xbt_dynar_cursor_rm(g->edges,&cursor);
159 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
163 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
168 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
173 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
177 int xbt_get_node_index(xbt_graph_t g, xbt_node_t n)
182 xbt_dynar_foreach(g->nodes,cursor,tmp)
190 void xbt_graph_edge_set_length(xbt_edge_t e, double length)
195 double xbt_graph_edge_get_length(xbt_edge_t e)
201 /*construct the adjacency matrix corresponding to a graph,
202 the weights are the distances between nodes
204 double* xbt_graph_get_length_matrix(xbt_graph_t g)
206 fprintf(stderr,"%s","START GET LENGTHS\n" );
211 xbt_edge_t edge = NULL;
215 # define D(u,v) d[(u)*n+(v)]
216 n = xbt_dynar_length(g->nodes);
218 d = (double*)xbt_malloc(n*n*(sizeof(double)));
226 xbt_dynar_foreach(g->nodes,cursor,node)
227 {fprintf(stderr,"CURSOR: %d\n",cursor );
229 D(cursor-1,cursor-1)=0;
230 xbt_dynar_foreach(node->in,in_cursor,edge)
231 {fprintf(stderr,"EDGE IN: %s\n",(char*)edge->data );
232 fprintf(stderr,"EDGE DST: %s\n",(char*)edge->dst->data );
233 idx = xbt_get_node_index(g,edge->dst);
234 fprintf(stderr,"IDX: %d\n",idx );
235 fprintf(stderr,"EDGE ADR: %x\n",(int)edge );
236 fprintf(stderr,"EDGE LENGTH: %le\n", edge->length );
237 D(cursor-1,idx) = edge->length;
240 fprintf(stderr,"BEFORE RETURN\n" );
247 /* calculate all-pairs shortest paths */
248 /* the shortest distance between node i and j are stocked in distances[i][j] */
249 void xbt_floyd_algorithm(xbt_graph_t g, double* adj,double* d, xbt_node_t* p)
253 n = xbt_dynar_length(g->nodes);
255 # define D(u,v) d[(u)*n+(v)]
256 # define P(u,v) p[(u)*n+(v)]
268 if(D(i,j)!=-1) P(i,j)=xbt_dynar_get_ptr (g->nodes,i) ;
278 if((D(i,k)!=-1) && (D(k,j)!=-1))
280 if((D(i,j)==-1) || (D(i,j) > D(i,k)+D(k,j)))
282 D(i,j) = D(i,k)+D(k,j) ;
293 /*computes all-pairs shortest paths*/
294 xbt_node_t* xbt_graph_shortest_paths(xbt_graph_t g)
304 # define P(u,v) p[(u)*n+(v)]
305 # define R(u,v) r[(u)*n+(v)]
307 n = xbt_dynar_length(g->nodes);
308 adj= xbt_graph_get_length_matrix(g);
309 xbt_floyd_algorithm(g,adj,d,p);
316 while((P(i,k))&&( xbt_get_node_index(g,P(i,k))!=i))
318 k = xbt_get_node_index(g,P(i,k));
322 R(i,j)=(xbt_node_t)xbt_dynar_get_ptr(g->nodes,k);
334 static xbt_graph_t parsed_graph=NULL;
335 static xbt_dict_t parsed_nodes=NULL;
336 static xbt_dict_t parsed_edges=NULL;
339 static void __parse_graph_begin(void)
343 static void __parse_graph_end(void)
348 static void __parse_node(void)
350 xbt_node_t node= xbt_graph_new_node(parsed_graph,(void*)A_graphxml_node_name);
352 xbt_dict_set( parsed_nodes,A_graphxml_node_name, (void *)node, free);
354 DEBUG1("<node label=\"%s\"/>",(char*)(node->data));
356 static void __parse_edge(void)
358 xbt_edge_t edge= xbt_graph_new_edge(parsed_graph,
359 xbt_dict_get(parsed_nodes,
360 A_graphxml_edge_source),
361 xbt_dict_get(parsed_nodes,
362 A_graphxml_edge_target),
363 (void*) A_graphxml_edge_name);
365 xbt_dict_set( parsed_edges,A_graphxml_edge_name, (void *)edge, free);
366 xbt_graph_edge_set_length(edge,atof(A_graphxml_edge_length));
368 DEBUG4("<edge name=\"%s\" source=\"%s\" target=\"%s\" length=\"%f\"/>",
370 (char*)(edge->src)->data,
371 (char*)(edge->dst)->data,
372 xbt_graph_edge_get_length(edge));
375 xbt_graph_t xbt_graph_read(const char *filename)
377 xbt_graph_t graph = xbt_graph_new_graph(1,NULL);
379 parsed_graph = graph;
380 parsed_nodes= xbt_dict_new();
381 parsed_edges= xbt_dict_new();
384 xbt_graph_parse_reset_parser();
386 STag_graphxml_graph_fun = __parse_graph_begin;
387 ETag_graphxml_graph_fun = __parse_graph_end;
388 ETag_graphxml_node_fun = __parse_node;
389 ETag_graphxml_edge_fun = __parse_edge;
392 xbt_graph_parse_open(filename);
393 xbt_assert1((!xbt_graph_parse()),"Parse error in %s",filename);
394 xbt_graph_parse_close();
399 void xbt_graph_export_surfxml(xbt_graph_t g,
400 const char *filename,
401 const char *(node_name)(xbt_node_t),
402 const char *(edge_name)(xbt_edge_t)
408 /* ./xbt/graphxml_usage xbt/graph.xml --xbt-log=graph.thres=debug */