source: vis_dev/glu-2.3/src/graph/graph.c@ 103

Last change on this file since 103 was 13, checked in by cecile, 15 years ago

library glu 2.3
File size: 8.7 KB
Line 
1/*
2 * $Id: graph.c,v 1.6 2005/04/15 23:24:21 fabio Exp $
3 */
4
5#include "graph_int.h"
6
7int g_unique_id;
8
9graph_t *
10g_alloc(void)
11{
12 graph_t_int *graph = ALLOC(graph_t_int,1);
13
14 graph->user_data = (gGeneric) NULL;
15 graph->v_list = lsCreate();
16 graph->e_list = lsCreate();
17
18 return((graph_t *) graph);
19}
20
21void
22g_free(
23 graph_t *g,
24 void (*f_free_g)(gGeneric),
25 void (*f_free_v)(gGeneric),
26 void (*f_free_e)(gGeneric))
27{
28 lsGen gen;
29 vertex_t *v;
30 edge_t *e;
31
32 if (g == NIL(graph_t)) {
33 return;
34 }
35 if (f_free_g != (void (*)(gGeneric)) NULL) {
36 (*f_free_g)(g->user_data);
37 }
38 foreach_vertex (g,gen,v) {
39 if (f_free_v != (void (*)(gGeneric)) NULL) {
40 (*f_free_v)(v->user_data);
41 }
42 (void) lsDestroy(g_get_in_edges(v),(void (*)(lsGeneric)) NULL);
43 (void) lsDestroy(g_get_out_edges(v),(void (*)(lsGeneric)) NULL);
44 FREE(v);
45 }
46 foreach_edge (g,gen,e) {
47 if (f_free_e != (void (*)(gGeneric)) NULL) {
48 (*f_free_e)(e->user_data);
49 }
50 FREE(e);
51 }
52 (void) lsDestroy(g_get_vertices(g),(void (*)(lsGeneric)) NULL);
53 (void) lsDestroy(g_get_edges(g),(void (*)(lsGeneric)) NULL);
54 FREE(g);
55}
56
57void
58g_check(graph_t *g)
59{
60 vertex_t *v, *source, *dest;
61 edge_t *e, *test;
62 lsGen gen, gen2;
63 int found;
64
65 if (g == NIL(graph_t)) {
66 return;
67 }
68 foreach_edge (g,gen,e) {
69 source = g_e_source(e);
70 dest = g_e_dest(e);
71 if (source == NIL(vertex_t)) {
72 fail("g_check: Edge has no source");
73 }
74 if (dest == NIL(vertex_t)) {
75 fail("g_check: Edge has no destination");
76 }
77 if (g_vertex_graph(source) != g_vertex_graph(dest)) {
78 fail("g_check: Edge connects different graphs");
79 }
80 found = FALSE;
81 foreach_out_edge (source,gen2,test) {
82 if (test == e) {
83 found = TRUE;
84 (void) lsFinish(gen2);
85 break;
86 }
87 }
88 if (found == FALSE) {
89 fail("g_check: Vertex does not point back to edge");
90 }
91 found = FALSE;
92 foreach_in_edge (dest,gen2,test) {
93 if (test == e) {
94 found = TRUE;
95 (void) lsFinish(gen2);
96 break;
97 }
98 }
99 if (found == FALSE) {
100 fail("g_check: Vertex does not point back to edge");
101 }
102 }
103 foreach_vertex (g,gen,v) {
104 if (g_vertex_graph(v) != g) {
105 fail("g_check: Vertex not a member of graph");
106 }
107 if (lsLength(g_get_in_edges(v)) + lsLength(g_get_out_edges(v)) == 0) {
108 (void) fprintf(stderr,"Warning: g_check: Unconnected vertex\n");
109 continue;
110 }
111 foreach_in_edge(v,gen2,test) {
112 if (g_e_dest(test) != v) {
113 fail("g_check: Edge does not point back to vertex");
114 }
115 }
116 foreach_out_edge(v,gen2,test) {
117 if (g_e_source(test) != v) {
118 fail("g_check: Edge does not point back to vertex");
119 }
120 }
121 }
122}
123
124graph_t *
125g_dup(
126 graph_t *g,
127 gGeneric (*f_copy_g)(gGeneric),
128 gGeneric (*f_copy_v)(gGeneric),
129 gGeneric (*f_copy_e)(gGeneric))
130{
131 graph_t *newg;
132 vertex_t *v, *new_v, *from, *to;
133 edge_t *e, *new_e;
134 st_table *ptrtable = st_init_table(st_ptrcmp,st_ptrhash);
135 lsGen gen;
136
137 newg = g_alloc();
138 if (g == NIL(graph_t)) {
139 return(newg);
140 }
141
142 if (f_copy_g == (gGeneric (*)(gGeneric)) NULL) {
143 newg->user_data = g->user_data;
144 }
145 else {
146 newg->user_data = (*f_copy_g)(g->user_data);
147 }
148 foreach_vertex (g,gen,v) {
149 new_v = g_add_vertex(newg);
150 if (f_copy_v == (gGeneric (*)(gGeneric)) NULL) {
151 new_v->user_data = v->user_data;
152 }
153 else {
154 new_v->user_data = (*f_copy_v)(v->user_data);
155 }
156 (void) st_insert(ptrtable,(char *) v,(char *) new_v);
157 }
158 foreach_edge (g,gen,e) {
159 (void) st_lookup(ptrtable,g_e_source(e),&from);
160 (void) st_lookup(ptrtable,g_e_dest(e),&to);
161 new_e = g_add_edge(from,to);
162 if (f_copy_e == (gGeneric (*)(gGeneric)) NULL) {
163 new_e->user_data = e->user_data;
164 }
165 else {
166 new_e->user_data = (*f_copy_e)(e->user_data);
167 }
168 }
169 st_free_table(ptrtable);
170 return(newg);
171}
172
173array_t *
174g_graph_sort(graph_t *g, int (*cmp)(const void *, const void *))
175{
176 int i;
177 lsGen gen;
178 vertex_t *v;
179 array_t *v_array;
180
181 i = 0;
182 v_array = array_alloc(vertex_t *,0);
183
184 foreach_vertex (g,gen,v) {
185 array_insert(vertex_t *,v_array,i++,v);
186 }
187 array_sort(v_array,cmp);
188 return(v_array);
189}
190
191lsList
192g_get_edges(graph_t *g)
193{
194 if (g == NIL(graph_t)) {
195 fail("g_get_edges: Null graph");
196 }
197 return(((graph_t_int *) g)->e_list);
198}
199
200lsList
201g_get_in_edges(vertex_t *v)
202{
203 if (v == NIL(vertex_t)) {
204 fail("g_get_in_edges: Null vertex");
205 }
206 return(((vertex_t_int *) v)->in_list);
207}
208
209lsList
210g_get_out_edges(vertex_t *v)
211{
212 if (v == NIL(vertex_t)) {
213 fail("g_get_out_edges: Null vertex");
214 }
215 return(((vertex_t_int *) v)->out_list);
216}
217
218edge_t *
219g_add_edge(vertex_t *v1, vertex_t *v2)
220{
221 edge_t_int *edge;
222 lsHandle handle;
223 graph_t *g;
224
225 if (v1 == NIL(vertex_t) || v2 == NIL(vertex_t)) {
226 fail("g_add_edge: Null vertex");
227 }
228 g = g_vertex_graph(v1);
229 if (g != g_vertex_graph(v2)) {
230 fail("g_add_edge: Edge connects different graphs");
231 }
232 edge = ALLOC(edge_t_int,1);
233 (void) lsNewEnd(g_get_edges(g),(lsGeneric) edge,&handle);
234 edge->user_data = (gGeneric) NULL;
235 edge->from = (vertex_t_int *) v1;
236 edge->to = (vertex_t_int *) v2;
237 edge->id = g_unique_id++;
238 edge->handle = handle;
239 (void) lsNewEnd(g_get_out_edges(v1),(lsGeneric) edge,LS_NH);
240 (void) lsNewEnd(g_get_in_edges(v2),(lsGeneric) edge,LS_NH);
241
242 return((edge_t *) edge);
243}
244
245static void
246g_del_from_list(lsList list, lsGeneric item)
247{
248 lsGen gen;
249 lsGeneric looking,dummy;
250 lsHandle handle;
251
252 gen = lsStart(list);
253 while (lsNext(gen,&looking,&handle) != LS_NOMORE) {
254 if (item == looking) {
255 if (lsRemoveItem(handle,&dummy) != LS_OK) {
256 fail("g_del_from_list: Can't remove edge");
257 }
258 break;
259 }
260 }
261 (void) lsFinish(gen);
262}
263
264void
265g_delete_edge(edge_t *e, void (*f_free_e)(gGeneric))
266{
267 lsGeneric junk;
268
269 if (e == NIL(edge_t)) {
270 fail("g_delete_edge: Null edge");
271 }
272 g_del_from_list(g_get_out_edges(g_e_source(e)),(lsGeneric) e);
273 g_del_from_list(g_get_in_edges(g_e_dest(e)),(lsGeneric) e);
274
275 (void) lsRemoveItem(((edge_t_int *) e)->handle,&junk);
276 if (f_free_e != (void (*)(gGeneric)) NULL) {
277 (*f_free_e)(e->user_data);
278 }
279 FREE(e);
280}
281
282graph_t *
283g_edge_graph(edge_t *e)
284{
285 if (e == NIL(edge_t)) {
286 fail("g_edge_graph: Null edge");
287 }
288 return((graph_t *) (((edge_t_int *) e)->to->g));
289}
290
291vertex_t *
292g_e_source(edge_t *e)
293{
294 if (e == NIL(edge_t)) {
295 fail("g_e_source: Null edge");
296 }
297 return((vertex_t *) (((edge_t_int *) e)->from));
298}
299
300vertex_t *
301g_e_dest(edge_t *e)
302{
303 if (e == NIL(edge_t)) {
304 fail("g_e_dest: Null edge");
305 }
306 return((vertex_t *) (((edge_t_int *) e)->to));
307}
308
309
310lsList
311g_get_vertices(graph_t *g)
312{
313 if (g == NIL(graph_t)) {
314 fail("g_get_vertices: Null graph");
315 }
316 return(((graph_t_int *) g)->v_list);
317}
318
319vertex_t *
320g_add_vertex(graph_t *g)
321{
322 lsHandle handle;
323 vertex_t_int *vert;
324
325 if (g == NIL(graph_t)) {
326 fail("g_add_vertex: Null graph");
327 }
328 vert = ALLOC(vertex_t_int,1);
329 if (lsNewEnd(g_get_vertices(g),(lsGeneric) vert,&handle) != LS_OK) {
330 fail("g_add_vertex: Can't add vertex");
331 }
332 vert->user_data = (gGeneric) NULL;
333 vert->g = (graph_t_int *) g;
334 vert->in_list = lsCreate();
335 vert->out_list = lsCreate();
336 vert->id = g_unique_id++;
337 vert->handle = handle;
338 return((vertex_t *) vert);
339}
340
341void
342g_delete_vertex(
343 vertex_t *v,
344 void (*f_free_v)(gGeneric),
345 void (*f_free_e)(gGeneric))
346{
347 edge_t *e;
348 lsGeneric junk;
349 lsGen gen;
350
351 if (v == NIL(vertex_t)) {
352 fail("g_delete_vertex: Null vertex");
353 }
354 if (f_free_v != (void (*)(gGeneric)) NULL) {
355 (*f_free_v)(v->user_data);
356 }
357 foreach_in_edge (v,gen,e) {
358 g_del_from_list(g_get_out_edges(g_e_source(e)),(lsGeneric) e);
359 if (f_free_e != (void (*)(gGeneric)) NULL) {
360 (*f_free_e)(e->user_data);
361 }
362 if (lsRemoveItem(((edge_t_int *) e)->handle,&junk) != LS_OK) {
363 fail("g_delete_vertex: Can't remove edge from graph");
364 }
365 FREE(e);
366 }
367 foreach_out_edge (v,gen,e) {
368 g_del_from_list(g_get_in_edges(g_e_dest(e)),(lsGeneric) e);
369 if (f_free_e != (void (*)(gGeneric)) NULL) {
370 (*f_free_e)(e->user_data);
371 }
372 if (lsRemoveItem(((edge_t_int *) e)->handle,&junk) != LS_OK) {
373 fail("g_delete_vertex: Can't remove edge from graph");
374 }
375 FREE(e);
376 }
377 (void) lsDestroy(g_get_out_edges(v),(void (*)(lsGeneric)) NULL);
378 (void) lsDestroy(g_get_in_edges(v),(void (*)(lsGeneric)) NULL);
379 (void) lsRemoveItem(((vertex_t_int *) v)->handle,&junk);
380 FREE(v);
381}
382
383graph_t *
384g_vertex_graph(vertex_t *v)
385{
386 if (v == NIL(vertex_t)) {
387 fail("g_vertex_graph: Null vertex");
388 }
389 return((graph_t *) ((vertex_t_int *) v)->g);
390}
Note: See TracBrowser for help on using the repository browser.