src/graph/graph_dfs.c File Reference

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

Go to the source code of this file.

Functions

static vertex_t * find_an_end_vertex (vertex_t *v, st_table *visit_list)
static int dfs_recurr (vertex_t *v, st_table *dfs_list, array_t *dfs_array)
static array_t * g_dfs_int (graph_t *g)
array_t * g_dfs (graph_t *g)
int g_is_acyclic (graph_t *g)
static int reachable_recurr (vertex_t *v, st_table *dfs_list)
st_table * g_reachable (graph_t *g, st_table *init)
static int EF_recurr (vertex_t *v, st_table *EF_list)
st_table * g_EF (graph_t *g, st_table *goal)
static void searchSCC (vertex_t *v, st_table *scc, st_table *old, lsList stack, st_table *onstack, int *countr)
st_table * g_SCC (graph_t *g, st_table *init)

Function Documentation

static int dfs_recurr ( vertex_t *  v,
st_table *  dfs_list,
array_t *  dfs_array 
) [static]

Definition at line 31 of file graph_dfs.c.

00032 {
00033     edge_t *e;
00034     lsGen gen;
00035     int val;
00036 
00037     if (st_lookup_int(dfs_list,(char *) v, &val)) {
00038         return(val == 0);
00039     }
00040     (void) st_insert(dfs_list,(char *) v,(char *) 1);
00041 
00042     foreach_in_edge (v,gen,e) {
00043         if (!dfs_recurr(g_e_source(e),dfs_list,dfs_array)) {
00044             return(0);
00045         }
00046     }
00047     (void) st_insert(dfs_list,(char *) v,(char *) 0);
00048     array_insert_last(vertex_t *,dfs_array,v);
00049     return(1);
00050 }

static int EF_recurr ( vertex_t *  v,
st_table *  EF_list 
) [static]

Definition at line 151 of file graph_dfs.c.

00152 {
00153     edge_t *e;
00154     lsGen gen;
00155     int val;
00156 
00157     if (st_lookup_int(EF_list,(char *) v, &val)) {
00158         return(val == 0);
00159     }
00160     (void) st_insert(EF_list,(char *) v,(char *) 1);
00161 
00162     foreach_in_edge (v,gen,e) {
00163         EF_recurr(g_e_source(e),EF_list);
00164     }
00165     (void) st_insert(EF_list,(char *) v,(char *) 0);
00166 
00167     return(1);
00168 }

static vertex_t* find_an_end_vertex ( vertex_t *  v,
st_table *  visit_list 
) [static]

Definition at line 8 of file graph_dfs.c.

00009 {
00010     edge_t *e;
00011     vertex_t *dest;
00012     lsGen gen;
00013 
00014     if (lsLength(g_get_out_edges(v)) == 0) {
00015         return(v);
00016     }
00017     foreach_out_edge (v,gen,e) {
00018         (void) lsFinish(gen);
00019         dest = g_e_dest(e);
00020         if (st_insert(visit_list,(char *) dest,(char *) 0) == 1) {
00021             return(NIL(vertex_t));
00022         }
00023         return(find_an_end_vertex(dest,visit_list));
00024         /* NOTREACHED */
00025     }
00026     /* no free out_edges */
00027     return(NIL(vertex_t));
00028 }

array_t* g_dfs ( graph_t *  g  ) 

Definition at line 87 of file graph_dfs.c.

00088 {
00089     array_t *x;
00090 
00091     x = g_dfs_int(g);
00092     if (x == NIL(array_t)) {
00093         fail("g_dfs: Graph has cycle");
00094     }
00095     return(x);
00096 }

static array_t* g_dfs_int ( graph_t *  g  )  [static]

Definition at line 53 of file graph_dfs.c.

00054 {
00055     vertex_t *v;
00056     lsGen gen;
00057     array_t *dfs_array;
00058     st_table *visit_list,*dfs_list;
00059     int cycle = FALSE;
00060 
00061     dfs_array = array_alloc(vertex_t *,0);
00062     visit_list = st_init_table(st_ptrcmp,st_ptrhash);
00063     dfs_list = st_init_table(st_ptrcmp,st_ptrhash);
00064 
00065     foreach_vertex (g,gen,v) {
00066         if (!st_is_member(dfs_list,(char *) v)) {
00067             (void) st_insert(visit_list,(char *) v,(char *) 0);
00068             v = find_an_end_vertex(v,visit_list);
00069             if (v == NIL(vertex_t) || !dfs_recurr(v,dfs_list,dfs_array)) {
00070                 cycle = TRUE;
00071                 (void) lsFinish(gen);
00072                 break;
00073             }
00074         }
00075     }
00076 
00077     st_free_table(visit_list);
00078     st_free_table(dfs_list);
00079     if (cycle == TRUE) {
00080         array_free(dfs_array);
00081         return(NIL(array_t));
00082     }
00083     return(dfs_array);
00084 }

st_table* g_EF ( graph_t *  g,
st_table *  goal 
)

Definition at line 172 of file graph_dfs.c.

00173 {
00174     vertex_t *v;
00175     st_table *EF_list;
00176     st_generator *stgen;
00177 
00178     EF_list = st_init_table(st_ptrcmp, st_ptrhash);
00179 
00180     st_foreach_item(goal, stgen, &v, NIL(char *)) {
00181         EF_recurr(v,EF_list);
00182     }
00183 
00184     return (EF_list);
00185 }

int g_is_acyclic ( graph_t *  g  ) 

Definition at line 99 of file graph_dfs.c.

00100 {
00101     array_t *x;
00102 
00103     x = g_dfs_int(g);
00104     if (x) {
00105         array_free(x);
00106         return(TRUE);
00107     }
00108     return(FALSE);
00109 }

st_table* g_reachable ( graph_t *  g,
st_table *  init 
)

Definition at line 134 of file graph_dfs.c.

00135 {
00136     vertex_t *v;
00137     st_table *dfs_list;
00138     st_generator *stgen;
00139 
00140     dfs_list = st_init_table(st_ptrcmp, st_ptrhash);
00141 
00142     st_foreach_item(init, stgen, &v, NIL(char *)) {
00143         reachable_recurr(v,dfs_list);
00144     }
00145 
00146     return (dfs_list);
00147 }

st_table* g_SCC ( graph_t *  g,
st_table *  init 
)

Definition at line 242 of file graph_dfs.c.

00243 {
00244     vertex_t *v;
00245     lsList stack;
00246     st_table *old, *onstack, *scc;
00247     st_generator *stgen;
00248     int countr = 0;
00249 
00250     scc = st_init_table(st_ptrcmp, st_ptrhash);
00251     
00252     stack = lsCreate();
00253     old = st_init_table(st_ptrcmp, st_ptrhash);
00254     onstack = st_init_table(st_ptrcmp, st_ptrhash);
00255     st_foreach_item(init, stgen, &v, NIL(char *)) {
00256         if (!st_is_member(old, (char *)v))
00257             searchSCC(v,scc,old,stack,onstack,&countr);
00258     }
00259     lsDestroy(stack, (void (*)(lsGeneric))0 );
00260     st_free_table(old);
00261     st_free_table(onstack);
00262 
00263     return scc;
00264 }

static int reachable_recurr ( vertex_t *  v,
st_table *  dfs_list 
) [static]

Definition at line 113 of file graph_dfs.c.

00114 {
00115     edge_t *e;
00116     lsGen gen;
00117     int val;
00118 
00119     if (st_lookup_int(dfs_list,(char *) v, &val)) {
00120         return(val == 0);
00121     }
00122     (void) st_insert(dfs_list,(char *) v,(char *) 1);
00123 
00124     foreach_out_edge (v,gen,e) {
00125         reachable_recurr(g_e_dest(e),dfs_list);
00126     }
00127     (void) st_insert(dfs_list,(char *) v,(char *) 0);
00128 
00129     return(1);
00130 }

static void searchSCC ( vertex_t *  v,
st_table *  scc,
st_table *  old,
lsList  stack,
st_table *  onstack,
int *  countr 
) [static]

Definition at line 188 of file graph_dfs.c.

00195 {
00196     int lowlink_v, dfnumber_v, lowlink_w, dfnumber_w;
00197     vertex_t *x, *w;
00198     st_table *component;
00199     lsGen gen;
00200     edge_t *e;
00201 
00202     lowlink_v = dfnumber_v = *countr;
00203     (*countr)++;
00204     st_insert(old, (char *)v, (char *)(long)dfnumber_v);
00205     st_insert(onstack, (char *)v, (char *)(long)lowlink_v);
00206     lsNewBegin(stack, (lsGeneric)v, NIL(lsHandle));
00207 
00208     foreach_out_edge (v,gen,e) {
00209         w = g_e_dest(e);
00210         if (!st_is_member(old, (char *)w)) {
00211             searchSCC(w,scc,old,stack,onstack,countr);
00212             if(st_lookup_int(onstack, (char *)w, &lowlink_w) &&
00213                lowlink_w < lowlink_v) {
00214                 lowlink_v = lowlink_w;
00215                 st_insert(onstack, (char *)v, (char *)(long)lowlink_v);
00216             }
00217         }else {
00218             st_lookup_int(old, (char *)w, &dfnumber_w);
00219             if (dfnumber_w < dfnumber_v && st_is_member(onstack, (char *)w)) {
00220                 if (dfnumber_w < lowlink_v) {
00221                     lowlink_v = dfnumber_w;
00222                     st_insert(onstack, (char *)v, (char *)(long)lowlink_v);
00223                 }
00224             }
00225         }
00226     }
00227 
00228     /* put current SCC into st_table, and then insert into 'scc' */
00229     if (dfnumber_v == lowlink_v) {
00230         component = st_init_table(st_ptrcmp, st_ptrhash);
00231         while (lsDelBegin(stack, &x) != LS_NOMORE) {
00232             st_insert(component, (char *)x, NIL(char)); 
00233             st_delete(onstack, &x, NIL(char *));
00234             if (v == x) break;
00235         }
00236         st_insert(scc, (char *)component, NIL(char)); /* is component fair? */
00237     }
00238 }

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