glu-2.2: src/graph/graph.c Source File

00001 /*
00002  * $Id: graph.c,v 1.6 2005/04/15 23:24:21 fabio Exp $
00003  */
00004 
00005 #include "graph_int.h"
00006 
00007 int g_unique_id;
00008 
00009 graph_t *
00010 g_alloc(void)
00011 {
00012     graph_t_int *graph = ALLOC(graph_t_int,1);
00013     
00014     graph->user_data = (gGeneric) NULL;
00015     graph->v_list = lsCreate();
00016     graph->e_list = lsCreate();
00017 
00018     return((graph_t *) graph);
00019 }
00020 
00021 void
00022 g_free(
00023   graph_t *g,
00024   void (*f_free_g)(gGeneric),
00025   void (*f_free_v)(gGeneric),
00026   void (*f_free_e)(gGeneric))
00027 {
00028     lsGen gen;
00029     vertex_t *v;
00030     edge_t *e;
00031 
00032     if (g == NIL(graph_t)) {
00033         return;
00034     }
00035     if (f_free_g != (void (*)(gGeneric)) NULL) {
00036         (*f_free_g)(g->user_data);
00037     }
00038     foreach_vertex (g,gen,v) {
00039         if (f_free_v != (void (*)(gGeneric)) NULL) {
00040             (*f_free_v)(v->user_data);
00041         }
00042         (void) lsDestroy(g_get_in_edges(v),(void (*)(lsGeneric)) NULL);
00043         (void) lsDestroy(g_get_out_edges(v),(void (*)(lsGeneric)) NULL);
00044         FREE(v);
00045     }
00046     foreach_edge (g,gen,e) {
00047         if (f_free_e != (void (*)(gGeneric)) NULL) {
00048             (*f_free_e)(e->user_data);
00049         }
00050         FREE(e);
00051     }
00052     (void) lsDestroy(g_get_vertices(g),(void (*)(lsGeneric)) NULL);
00053     (void) lsDestroy(g_get_edges(g),(void (*)(lsGeneric)) NULL);
00054     FREE(g);
00055 }
00056 
00057 void
00058 g_check(graph_t *g)
00059 {
00060     vertex_t *v, *source, *dest;
00061     edge_t *e, *test;
00062     lsGen gen, gen2;
00063     int found;
00064 
00065     if (g == NIL(graph_t)) {
00066         return;
00067     }
00068     foreach_edge (g,gen,e) {
00069         source = g_e_source(e);
00070         dest = g_e_dest(e);
00071         if (source == NIL(vertex_t)) {
00072             fail("g_check: Edge has no source");
00073         }
00074         if (dest == NIL(vertex_t)) {
00075             fail("g_check: Edge has no destination");
00076         }
00077         if (g_vertex_graph(source) != g_vertex_graph(dest)) {
00078             fail("g_check: Edge connects different graphs");
00079         }
00080         found = FALSE;
00081         foreach_out_edge (source,gen2,test) {
00082             if (test == e) {
00083                 found = TRUE;
00084                 (void) lsFinish(gen2);
00085                 break;
00086             }
00087         }
00088         if (found == FALSE) {
00089             fail("g_check: Vertex does not point back to edge");
00090         }
00091         found = FALSE;
00092         foreach_in_edge (dest,gen2,test) {
00093             if (test == e) {
00094                 found = TRUE;
00095                 (void) lsFinish(gen2);
00096                 break;
00097             }
00098         }
00099         if (found == FALSE) {
00100             fail("g_check: Vertex does not point back to edge");
00101         }
00102     }
00103     foreach_vertex (g,gen,v) {
00104         if (g_vertex_graph(v) != g) {
00105             fail("g_check: Vertex not a member of graph");
00106         }
00107         if (lsLength(g_get_in_edges(v)) + lsLength(g_get_out_edges(v)) == 0) {
00108             (void) fprintf(stderr,"Warning: g_check: Unconnected vertex\n");
00109             continue;
00110         }
00111         foreach_in_edge(v,gen2,test) {
00112             if (g_e_dest(test) != v) {
00113                 fail("g_check: Edge does not point back to vertex");
00114             }
00115         }
00116         foreach_out_edge(v,gen2,test) {
00117             if (g_e_source(test) != v) {
00118                 fail("g_check: Edge does not point back to vertex");
00119             }
00120         }
00121     }
00122 }
00123 
00124 graph_t *
00125 g_dup(
00126   graph_t *g,
00127   gGeneric (*f_copy_g)(gGeneric),
00128   gGeneric (*f_copy_v)(gGeneric),
00129   gGeneric (*f_copy_e)(gGeneric))
00130 {
00131     graph_t *newg;
00132     vertex_t *v, *new_v, *from, *to;
00133     edge_t *e, *new_e;
00134     st_table *ptrtable = st_init_table(st_ptrcmp,st_ptrhash);
00135     lsGen gen;
00136 
00137     newg = g_alloc();
00138     if (g == NIL(graph_t)) {
00139         return(newg);
00140     }
00141 
00142     if (f_copy_g == (gGeneric (*)(gGeneric)) NULL) {
00143         newg->user_data = g->user_data;
00144     }
00145     else {
00146         newg->user_data = (*f_copy_g)(g->user_data);
00147     }
00148     foreach_vertex (g,gen,v) {
00149         new_v = g_add_vertex(newg);
00150         if (f_copy_v == (gGeneric (*)(gGeneric)) NULL) {
00151             new_v->user_data = v->user_data;
00152         }
00153         else {
00154             new_v->user_data = (*f_copy_v)(v->user_data);
00155         }
00156         (void) st_insert(ptrtable,(char *) v,(char *) new_v);
00157     }
00158     foreach_edge (g,gen,e) {
00159         (void) st_lookup(ptrtable,g_e_source(e),&from);
00160         (void) st_lookup(ptrtable,g_e_dest(e),&to);
00161         new_e = g_add_edge(from,to);
00162         if (f_copy_e == (gGeneric (*)(gGeneric)) NULL) {
00163             new_e->user_data = e->user_data;
00164         }
00165         else {
00166             new_e->user_data = (*f_copy_e)(e->user_data);
00167         }
00168     }
00169     st_free_table(ptrtable);
00170     return(newg);
00171 }
00172 
00173 array_t *
00174 g_graph_sort(graph_t *g, int (*cmp)(const void *, const void *))
00175 {
00176     int i;
00177     lsGen gen;
00178     vertex_t *v;
00179     array_t *v_array;
00180 
00181     i = 0;
00182     v_array = array_alloc(vertex_t *,0);
00183 
00184     foreach_vertex (g,gen,v) {
00185         array_insert(vertex_t *,v_array,i++,v);
00186     }
00187     array_sort(v_array,cmp);
00188     return(v_array);
00189 }
00190 
00191 lsList
00192 g_get_edges(graph_t *g)
00193 {
00194     if (g == NIL(graph_t)) {
00195         fail("g_get_edges: Null graph");
00196     }
00197     return(((graph_t_int *) g)->e_list);
00198 }
00199 
00200 lsList
00201 g_get_in_edges(vertex_t *v)
00202 {
00203     if (v == NIL(vertex_t)) {
00204         fail("g_get_in_edges: Null vertex");
00205     }
00206     return(((vertex_t_int *) v)->in_list);
00207 }
00208 
00209 lsList
00210 g_get_out_edges(vertex_t *v)
00211 {
00212     if (v == NIL(vertex_t)) {
00213         fail("g_get_out_edges: Null vertex");
00214     }
00215     return(((vertex_t_int *) v)->out_list);
00216 }
00217 
00218 edge_t *
00219 g_add_edge(vertex_t *v1, vertex_t *v2)
00220 {
00221     edge_t_int *edge;
00222     lsHandle handle;
00223     graph_t *g;
00224 
00225     if (v1 == NIL(vertex_t) || v2 == NIL(vertex_t)) {
00226         fail("g_add_edge: Null vertex");
00227     }
00228     g = g_vertex_graph(v1);
00229     if (g != g_vertex_graph(v2)) {
00230         fail("g_add_edge: Edge connects different graphs");
00231     }
00232     edge = ALLOC(edge_t_int,1);
00233     (void) lsNewEnd(g_get_edges(g),(lsGeneric) edge,&handle);
00234     edge->user_data = (gGeneric) NULL;
00235     edge->from = (vertex_t_int *) v1;
00236     edge->to = (vertex_t_int *) v2;
00237     edge->id = g_unique_id++;
00238     edge->handle = handle;
00239     (void) lsNewEnd(g_get_out_edges(v1),(lsGeneric) edge,LS_NH);
00240     (void) lsNewEnd(g_get_in_edges(v2),(lsGeneric) edge,LS_NH);
00241 
00242     return((edge_t *) edge);
00243 }
00244 
00245 static void
00246 g_del_from_list(lsList list, lsGeneric item)
00247 {
00248     lsGen gen;
00249     lsGeneric looking,dummy;
00250     lsHandle handle;
00251 
00252     gen = lsStart(list);
00253     while (lsNext(gen,&looking,&handle) != LS_NOMORE) {
00254         if (item == looking) {
00255             if (lsRemoveItem(handle,&dummy) != LS_OK) {
00256                 fail("g_del_from_list: Can't remove edge");
00257             }
00258             break;
00259         }
00260     }
00261     (void) lsFinish(gen);
00262 }
00263 
00264 void
00265 g_delete_edge(edge_t *e, void (*f_free_e)(gGeneric))
00266 {
00267     lsGeneric junk;
00268 
00269     if (e == NIL(edge_t)) {
00270         fail("g_delete_edge: Null edge");
00271     }
00272     g_del_from_list(g_get_out_edges(g_e_source(e)),(lsGeneric) e);
00273     g_del_from_list(g_get_in_edges(g_e_dest(e)),(lsGeneric) e);
00274 
00275     (void) lsRemoveItem(((edge_t_int *) e)->handle,&junk);
00276     if (f_free_e != (void (*)(gGeneric)) NULL) {
00277         (*f_free_e)(e->user_data);
00278     }
00279     FREE(e);
00280 }
00281 
00282 graph_t *
00283 g_edge_graph(edge_t *e)
00284 {
00285     if (e == NIL(edge_t)) {
00286         fail("g_edge_graph: Null edge");
00287     }
00288     return((graph_t *) (((edge_t_int *) e)->to->g));
00289 }
00290 
00291 vertex_t *
00292 g_e_source(edge_t *e)
00293 {
00294     if (e == NIL(edge_t)) {
00295         fail("g_e_source: Null edge");
00296     }
00297     return((vertex_t *) (((edge_t_int *) e)->from));
00298 }
00299 
00300 vertex_t *
00301 g_e_dest(edge_t *e)
00302 {
00303     if (e == NIL(edge_t)) {
00304         fail("g_e_dest: Null edge");
00305     }
00306     return((vertex_t *) (((edge_t_int *) e)->to));
00307 }
00308 
00309 
00310 lsList
00311 g_get_vertices(graph_t *g)
00312 {
00313     if (g == NIL(graph_t)) {
00314         fail("g_get_vertices: Null graph");
00315     }
00316     return(((graph_t_int *) g)->v_list);
00317 }
00318 
00319 vertex_t *
00320 g_add_vertex(graph_t *g)
00321 {
00322     lsHandle handle;
00323     vertex_t_int *vert;
00324 
00325     if (g == NIL(graph_t)) {
00326         fail("g_add_vertex: Null graph");
00327     }
00328     vert = ALLOC(vertex_t_int,1);
00329     if (lsNewEnd(g_get_vertices(g),(lsGeneric) vert,&handle) != LS_OK) {
00330         fail("g_add_vertex: Can't add vertex");
00331     }    
00332     vert->user_data = (gGeneric) NULL;
00333     vert->g = (graph_t_int *) g;
00334     vert->in_list = lsCreate();
00335     vert->out_list = lsCreate();
00336     vert->id = g_unique_id++;
00337     vert->handle = handle;
00338     return((vertex_t *) vert);
00339 }
00340 
00341 void
00342 g_delete_vertex(
00343   vertex_t *v,
00344   void (*f_free_v)(gGeneric),
00345   void (*f_free_e)(gGeneric))
00346 {
00347     edge_t *e;
00348     lsGeneric junk;
00349     lsGen gen;
00350 
00351     if (v == NIL(vertex_t)) {
00352         fail("g_delete_vertex: Null vertex");
00353     }
00354     if (f_free_v != (void (*)(gGeneric)) NULL) {
00355         (*f_free_v)(v->user_data);
00356     }
00357     foreach_in_edge (v,gen,e) {
00358         g_del_from_list(g_get_out_edges(g_e_source(e)),(lsGeneric) e);
00359         if (f_free_e != (void (*)(gGeneric)) NULL) {
00360             (*f_free_e)(e->user_data);
00361         }
00362         if (lsRemoveItem(((edge_t_int *) e)->handle,&junk) != LS_OK) {
00363             fail("g_delete_vertex: Can't remove edge from graph");
00364         }
00365         FREE(e);
00366     }
00367     foreach_out_edge (v,gen,e) {
00368         g_del_from_list(g_get_in_edges(g_e_dest(e)),(lsGeneric) e);
00369         if (f_free_e != (void (*)(gGeneric)) NULL) {
00370             (*f_free_e)(e->user_data);
00371         }
00372         if (lsRemoveItem(((edge_t_int *) e)->handle,&junk) != LS_OK) {
00373             fail("g_delete_vertex: Can't remove edge from graph");
00374         }
00375         FREE(e);
00376     }
00377     (void) lsDestroy(g_get_out_edges(v),(void (*)(lsGeneric)) NULL);
00378     (void) lsDestroy(g_get_in_edges(v),(void (*)(lsGeneric)) NULL);
00379     (void) lsRemoveItem(((vertex_t_int *) v)->handle,&junk);
00380     FREE(v);
00381 }
00382 
00383 graph_t *
00384 g_vertex_graph(vertex_t *v)
00385 {
00386     if (v == NIL(vertex_t)) {
00387         fail("g_vertex_graph: Null vertex");
00388     }
00389     return((graph_t *) ((vertex_t_int *) v)->g);
00390 }