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

Last change on this file since 77 was 13, checked in by cecile, 13 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.