src/graph/graph.c File Reference

#include "graph_int.h"
Include dependency graph for graph.c:

Go to the source code of this file.

Functions

graph_t * g_alloc (void)
void g_free (graph_t *g, void(*f_free_g)(gGeneric), void(*f_free_v)(gGeneric), void(*f_free_e)(gGeneric))
void g_check (graph_t *g)
graph_t * g_dup (graph_t *g, gGeneric(*f_copy_g)(gGeneric), gGeneric(*f_copy_v)(gGeneric), gGeneric(*f_copy_e)(gGeneric))
array_t * g_graph_sort (graph_t *g, int(*cmp)(const void *, const void *))
lsList g_get_edges (graph_t *g)
lsList g_get_in_edges (vertex_t *v)
lsList g_get_out_edges (vertex_t *v)
edge_t * g_add_edge (vertex_t *v1, vertex_t *v2)
static void g_del_from_list (lsList list, lsGeneric item)
void g_delete_edge (edge_t *e, void(*f_free_e)(gGeneric))
graph_t * g_edge_graph (edge_t *e)
vertex_t * g_e_source (edge_t *e)
vertex_t * g_e_dest (edge_t *e)
lsList g_get_vertices (graph_t *g)
vertex_t * g_add_vertex (graph_t *g)
void g_delete_vertex (vertex_t *v, void(*f_free_v)(gGeneric), void(*f_free_e)(gGeneric))
graph_t * g_vertex_graph (vertex_t *v)

Variables

int g_unique_id

Function Documentation

edge_t* g_add_edge ( vertex_t *  v1,
vertex_t *  v2 
)

Definition at line 219 of file graph.c.

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 }

vertex_t* g_add_vertex ( graph_t *  g  ) 

Definition at line 320 of file graph.c.

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 }

graph_t* g_alloc ( void   ) 

Definition at line 10 of file graph.c.

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 }

void g_check ( graph_t *  g  ) 

Definition at line 58 of file graph.c.

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 }

static void g_del_from_list ( lsList  list,
lsGeneric  item 
) [static]

Definition at line 246 of file graph.c.

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 }

void g_delete_edge ( edge_t *  e,
void(*)(gGeneric)  f_free_e 
)

Definition at line 265 of file graph.c.

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 }

void g_delete_vertex ( vertex_t *  v,
void(*)(gGeneric)  f_free_v,
void(*)(gGeneric)  f_free_e 
)

Definition at line 342 of file graph.c.

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 }

graph_t* g_dup ( graph_t *  g,
gGeneric(*)(gGeneric)  f_copy_g,
gGeneric(*)(gGeneric)  f_copy_v,
gGeneric(*)(gGeneric)  f_copy_e 
)

Definition at line 125 of file graph.c.

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 }

vertex_t* g_e_dest ( edge_t *  e  ) 

Definition at line 301 of file graph.c.

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 }

vertex_t* g_e_source ( edge_t *  e  ) 

Definition at line 292 of file graph.c.

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 }

graph_t* g_edge_graph ( edge_t *  e  ) 

Definition at line 283 of file graph.c.

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 }

void g_free ( graph_t *  g,
void(*)(gGeneric)  f_free_g,
void(*)(gGeneric)  f_free_v,
void(*)(gGeneric)  f_free_e 
)

Definition at line 22 of file graph.c.

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 }

lsList g_get_edges ( graph_t *  g  ) 

Definition at line 192 of file graph.c.

00193 {
00194     if (g == NIL(graph_t)) {
00195         fail("g_get_edges: Null graph");
00196     }
00197     return(((graph_t_int *) g)->e_list);
00198 }

lsList g_get_in_edges ( vertex_t *  v  ) 

Definition at line 201 of file graph.c.

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 }

lsList g_get_out_edges ( vertex_t *  v  ) 

Definition at line 210 of file graph.c.

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 }

lsList g_get_vertices ( graph_t *  g  ) 

Definition at line 311 of file graph.c.

00312 {
00313     if (g == NIL(graph_t)) {
00314         fail("g_get_vertices: Null graph");
00315     }
00316     return(((graph_t_int *) g)->v_list);
00317 }

array_t* g_graph_sort ( graph_t *  g,
int(*)(const void *, const void *)  cmp 
)

Definition at line 174 of file graph.c.

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 }

graph_t* g_vertex_graph ( vertex_t *  v  ) 

Definition at line 384 of file graph.c.

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 }

Variable Documentation

int g_unique_id

Definition at line 7 of file graph.c.

Generated on Tue Jan 12 13:57:24 2010 for glu-2.2 by  doxygen 1.6.1