Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Adding basic parsing functions to the graph library
[simgrid.git] / src / xbt / graph.c
1 /*      $Id$     */
2
3 /* a generic graph library.                                                 */
4
5 /* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand. 
6    All rights reserved.                  */
7
8 /* This program is free software; you can redistribute it and/or modify it
9  * under the terms of the license (GNU LGPL) which comes with this package. */
10
11 #include "xbt/sysdep.h"
12 #include "xbt/log.h"
13 #include "xbt/graph.h"
14 #include "graph_private.h"
15 #include "xbt/graphxml_parse.h"
16
17 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph,xbt,"Graph");
18
19 /** Constructor
20  * \return a new graph
21  */
22 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
23 {
24   xbt_graph_t graph=NULL;
25   graph=xbt_new0(struct xbt_graph,1);
26   graph->directed=directed;
27   graph->data=data;
28   graph->nodes= xbt_dynar_new(sizeof(xbt_node_t), free);
29   graph->edges= xbt_dynar_new(sizeof(xbt_edge_t), free);
30
31   return graph;
32 }
33
34 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
35 {
36   xbt_node_t node=NULL;
37   node=xbt_new0(struct xbt_node,1);
38   node->data=data;
39   node->in=xbt_dynar_new(sizeof(xbt_node_t), free);
40   node->out=xbt_dynar_new(sizeof(xbt_node_t), free);
41   xbt_dynar_push(g->nodes,node);  
42
43   return node;
44 }
45
46
47 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
48                              xbt_node_t src, xbt_node_t dst, void *data)
49 {
50   xbt_edge_t edge=NULL;
51
52   edge=xbt_new0(struct xbt_edge,1);
53   xbt_dynar_push(src->out,edge); 
54   xbt_dynar_push(dst->in,edge); 
55   edge->data=data;
56   edge->src=src;
57   edge->dst=dst;
58   if(!g->directed) 
59    {
60      xbt_dynar_push(src->in,edge); 
61      xbt_dynar_push(dst->out,edge); 
62    }
63  xbt_dynar_push(g->edges,edge);
64
65  return edge; 
66 }
67
68
69 /** Destructor
70  * \param l poor victim
71  *
72  * Free the graph structure. 
73  */
74 void xbt_graph_free_graph(xbt_graph_t g,
75                           void node_free_function(void * ptr),
76                           void edge_free_function(void * ptr),
77                           void graph_free_function(void * ptr))
78 {
79   int cursor; 
80   xbt_node_t node=NULL;
81   xbt_edge_t edge=NULL; 
82
83   xbt_dynar_foreach(g->nodes,cursor,node)
84     xbt_graph_remove_node(g,node,node_free_function);
85
86   xbt_assert0(!xbt_dynar_length(g->edges),
87               "Damnit, there are some remaining edges!");
88
89   xbt_dynar_foreach(g->edges,cursor,edge)
90       xbt_graph_remove_edge(g,edge,edge_free_function); 
91
92   xbt_dynar_free(&(g->nodes));
93   xbt_dynar_free(&(g->edges));
94       
95 /*  void xbt_dynar_free(g->edges); */
96
97
98   return;
99 }
100
101 void xbt_graph_remove_node(xbt_graph_t g, xbt_node_t n, void free_function(void * ptr))
102 {
103   int cursor; 
104   xbt_node_t node=NULL;
105
106   if ((free_function)&&(n->data))
107    free_function(n->data);
108   xbt_dynar_free_container(&(n->in));
109   xbt_dynar_free_container(&(n->out));
110   xbt_dynar_foreach(g->nodes,cursor,node)
111     {
112       if (node==n)
113         xbt_dynar_cursor_rm(g->nodes,&cursor);   
114       
115     }
116   return;
117    
118 }
119 void xbt_graph_remove_edge(xbt_graph_t g, xbt_edge_t e, void free_function(void * ptr))
120 {
121    int cursor=0; 
122    xbt_edge_t edge=NULL;
123    xbt_node_t node=NULL;
124    xbt_node_t temp=NULL;
125    
126    if ((free_function)&&(e->data))
127      free_function(e->data);
128    xbt_dynar_foreach(g->nodes,cursor,node)
129      {
130        if (node==e->src)
131          xbt_dynar_pop(node->out,temp);
132        if (g->directed)
133          xbt_dynar_pop(node->in,temp);
134         
135      }
136    node=NULL;
137    cursor=0;
138    xbt_dynar_foreach(g->nodes,cursor,node)
139      {
140         if (node==e->dst)
141           xbt_dynar_pop(node->in,temp);
142         if (g->directed)
143           xbt_dynar_pop(node->out,temp);
144         
145      }
146    cursor=0;
147    xbt_dynar_foreach(g->edges,cursor,edge)
148      if (edge==e) 
149        {
150          xbt_dynar_cursor_rm(g->edges,&cursor);
151          break;
152        }
153    
154 }
155
156 static xbt_graph_t parsed_graph=NULL;
157
158 static void  __parse_graph_begin(void) {
159   DEBUG0("<graph>");
160 }
161 static void  __parse_graph_end(void) {
162   DEBUG0("</graph>");
163 }
164 static void __parse_node(void) {
165   DEBUG1("<node label=\"%s\"/>",A_node_name);
166 }
167 static void __parse_edge(void) {
168   DEBUG2("<edge source=\"%s\" target=\"%s\"/>",A_edge_source,A_edge_target);
169 }
170
171 xbt_graph_t xbt_graph_read(const char *filename)
172 {
173   xbt_graph_t graph = xbt_graph_new_graph(1,NULL);
174
175   parsed_graph = graph;
176
177   xbt_graph_parse_reset_parser();
178   
179   STag_graph_fun = __parse_graph_begin;
180   ETag_graph_fun = __parse_graph_end;
181   ETag_node_fun = __parse_node;
182   ETag_edge_fun = __parse_edge;
183
184   xbt_graph_parse_open(filename);
185   xbt_assert1((!xbt_graph_parse()),"Parse error in %s",filename);
186   xbt_graph_parse_close();
187
188   parsed_graph = NULL;
189   
190   return graph;
191 }