[13] | 1 | #include "util.h" |
---|
| 2 | #include "list.h" |
---|
| 3 | #include "array.h" |
---|
| 4 | #include "graph.h" |
---|
| 5 | #include "graph_static.h" |
---|
| 6 | |
---|
| 7 | |
---|
| 8 | static char *month[] = {"Jan", "Feb", "March", "april", "may", "June", |
---|
| 9 | "july", "Aug", "Sept", "Oct", "nov", "Dec" |
---|
| 10 | }; |
---|
| 11 | |
---|
| 12 | #define voidNULL (void (*)()) NULL |
---|
| 13 | #define gGenericNULL (gGeneric (*)()) NULL |
---|
| 14 | |
---|
| 15 | static void |
---|
| 16 | strfree(thing) |
---|
| 17 | gGeneric thing; |
---|
| 18 | { |
---|
| 19 | FREE(thing); |
---|
| 20 | } |
---|
| 21 | |
---|
| 22 | static int |
---|
| 23 | graph_test() |
---|
| 24 | { |
---|
| 25 | graph_t *g1, *g2; |
---|
| 26 | int i, j; |
---|
| 27 | vertex_t *v[10]; |
---|
| 28 | lsGen gen, gen2; |
---|
| 29 | vertex_t *vert; |
---|
| 30 | edge_t *edge; |
---|
| 31 | |
---|
| 32 | g1 = g_alloc(); |
---|
| 33 | |
---|
| 34 | for (i = 0; i < 10; i++) { |
---|
| 35 | v[i] = g_add_vertex(g1); |
---|
| 36 | v[i]->user_data = (gGeneric) i; |
---|
| 37 | } |
---|
| 38 | for (i = 0; i < 9; i++) { |
---|
| 39 | for (j = i + 1; j < 10; j++) { |
---|
| 40 | (void) g_add_edge(v[i],v[j]); |
---|
| 41 | } |
---|
| 42 | } |
---|
| 43 | (void) g_add_edge(v[5],v[5]); /* self loop */ |
---|
| 44 | |
---|
| 45 | (void) lsFirstItem(g_get_out_edges(v[4]),(lsGeneric *) &edge,LS_NH); |
---|
| 46 | g_delete_edge(edge,voidNULL); |
---|
| 47 | |
---|
| 48 | g_delete_vertex(v[8],voidNULL,voidNULL); |
---|
| 49 | |
---|
| 50 | g_add_vertex(g1)->user_data = (gGeneric) 10; /* unconnected vertex */ |
---|
| 51 | |
---|
| 52 | g2 = g_dup(g1,gGenericNULL,gGenericNULL,gGenericNULL); |
---|
| 53 | foreach_vertex (g2,gen,vert) { |
---|
| 54 | (void) fprintf(stdout,"\nCopy of %d\ngoes to: ",vert->user_data); |
---|
| 55 | foreach_out_edge (vert,gen2,edge) { |
---|
| 56 | (void) fprintf(stdout,"%d ",g_e_dest(edge)->user_data); |
---|
| 57 | } |
---|
| 58 | (void) fprintf(stdout,"\ncomes from: "); |
---|
| 59 | foreach_in_edge (vert,gen2,edge) { |
---|
| 60 | (void) fprintf(stdout,"%d ",g_e_source(edge)->user_data); |
---|
| 61 | } |
---|
| 62 | } |
---|
| 63 | (void) fputc('\n',stdout); |
---|
| 64 | g_check(g1); |
---|
| 65 | g_check(g2); |
---|
| 66 | g_free(g1,voidNULL,voidNULL,voidNULL); |
---|
| 67 | g_free(g2,voidNULL,voidNULL,voidNULL); |
---|
| 68 | |
---|
| 69 | g1 = g_alloc(); |
---|
| 70 | for (i = 0; i < 12; i++) { |
---|
| 71 | g_add_vertex(g1)->user_data = (gGeneric) month[i]; |
---|
| 72 | } |
---|
| 73 | g2 = g_dup(g1,gGenericNULL,(gGeneric (*)()) util_strsav,gGenericNULL); |
---|
| 74 | foreach_vertex (g1,gen,vert) { |
---|
| 75 | ((char *) vert->user_data)[0] = '\0'; |
---|
| 76 | } |
---|
| 77 | foreach_vertex (g2,gen,vert) { /* strings copied by strsav */ |
---|
| 78 | (void) fprintf(stdout, "%s\n", (char *) vert->user_data); |
---|
| 79 | } |
---|
| 80 | g_free(g1, voidNULL, voidNULL, voidNULL); /* don't free static strings */ |
---|
| 81 | g_free(g2, voidNULL, strfree, voidNULL); /* free copies */ |
---|
| 82 | return(0); |
---|
| 83 | } |
---|
| 84 | |
---|
| 85 | static void |
---|
| 86 | edge_free(thing) |
---|
| 87 | gGeneric thing; |
---|
| 88 | { |
---|
| 89 | FREE(((gGeneric *) thing)[2]); |
---|
| 90 | } |
---|
| 91 | |
---|
| 92 | static gGeneric |
---|
| 93 | edge_copy(thing) |
---|
| 94 | gGeneric thing; |
---|
| 95 | { |
---|
| 96 | gGeneric *new = ALLOC(gGeneric,4); |
---|
| 97 | gGeneric *old = (gGeneric *) thing; |
---|
| 98 | |
---|
| 99 | new[0] = old[0]; |
---|
| 100 | new[1] = old[1]; |
---|
| 101 | new[2] = (gGeneric) util_strsav((char *) old[2]); |
---|
| 102 | new[3] = old[3]; |
---|
| 103 | return((gGeneric) new); |
---|
| 104 | } |
---|
| 105 | |
---|
| 106 | |
---|
| 107 | static int |
---|
| 108 | graph_static_test() |
---|
| 109 | { |
---|
| 110 | graph_t *g1, *g2; |
---|
| 111 | int i,j,x; |
---|
| 112 | vertex_t *v[10], *v1, *v2; |
---|
| 113 | edge_t *e, *edge; |
---|
| 114 | lsGen gen; |
---|
| 115 | |
---|
| 116 | g1 = g_alloc_static(3,2,4); |
---|
| 117 | |
---|
| 118 | for (i = 0; i < 10; i++) { |
---|
| 119 | v[i] = g_add_vertex_static(g1); |
---|
| 120 | g_set_v_slot_static(v[i],0,(gGeneric) i); |
---|
| 121 | g_set_v_slot_static(v[i],1,(gGeneric) (2 * i)); |
---|
| 122 | } |
---|
| 123 | x = 0; |
---|
| 124 | for (i = 0; i < 9; i++) { |
---|
| 125 | for (j = i + 1; j < 10; j++) { |
---|
| 126 | e = g_add_edge_static(v[i],v[j]); |
---|
| 127 | g_set_e_slot_static(e,2,(gGeneric) util_strsav(month[i])); |
---|
| 128 | g_set_e_slot_static(e,1,(gGeneric) x++); |
---|
| 129 | } |
---|
| 130 | } |
---|
| 131 | g_delete_vertex_static(v[3],voidNULL,edge_free); /* kill v[3] */ |
---|
| 132 | (void) lsLastItem(g_get_out_edges(v[6]),(lsGeneric *) &edge,LS_NH); |
---|
| 133 | g_delete_edge_static(edge,edge_free); /* kill last edge of v[6] */ |
---|
| 134 | |
---|
| 135 | g_set_g_slot_static(g1,1,(gGeneric) 'f'); |
---|
| 136 | g2 = g_dup_static(g1,gGenericNULL,gGenericNULL,edge_copy); |
---|
| 137 | |
---|
| 138 | v1 = g_add_vertex_static(g2); |
---|
| 139 | g_copy_v_slots_static(v[2],v1,gGenericNULL); |
---|
| 140 | |
---|
| 141 | foreach_edge (g2,gen,edge) { |
---|
| 142 | v1 = g_e_source(edge); |
---|
| 143 | v2 = g_e_dest(edge); |
---|
| 144 | (void) fprintf(stdout, |
---|
| 145 | "%d (%s) connects %d & %d\n",g_get_e_slot_static(edge,1), |
---|
| 146 | g_get_e_slot_static(edge,2),g_get_v_slot_static(v1,0), |
---|
| 147 | g_get_v_slot_static(v2,0)); |
---|
| 148 | } |
---|
| 149 | g_free_static(g1,voidNULL,voidNULL,edge_free); |
---|
| 150 | g_free_static(g2,voidNULL,voidNULL,edge_free); |
---|
| 151 | return(0); |
---|
| 152 | } |
---|
| 153 | |
---|
| 154 | static int |
---|
| 155 | reverso(a,b) |
---|
| 156 | char *a,*b; |
---|
| 157 | { |
---|
| 158 | return((int) ((vertex_t *) b)->user_data - (int) ((vertex_t *) a)->user_data); |
---|
| 159 | } |
---|
| 160 | |
---|
| 161 | static int |
---|
| 162 | graph_dfs_test() |
---|
| 163 | { |
---|
| 164 | int i; |
---|
| 165 | vertex_t *v[10]; |
---|
| 166 | array_t *arr; |
---|
| 167 | graph_t *g; |
---|
| 168 | vertex_t *x; |
---|
| 169 | |
---|
| 170 | g = g_alloc(); |
---|
| 171 | for (i = 0; i < 10; i++) { |
---|
| 172 | v[i] = g_add_vertex(g); |
---|
| 173 | v[i]->user_data = (gGeneric) i; |
---|
| 174 | } |
---|
| 175 | (void) g_add_edge(v[3],v[4]); |
---|
| 176 | (void) g_add_edge(v[0],v[3]); |
---|
| 177 | (void) g_add_edge(v[0],v[6]); |
---|
| 178 | (void) g_add_edge(v[0],v[2]); |
---|
| 179 | (void) g_add_edge(v[1],v[3]); |
---|
| 180 | (void) g_add_edge(v[6],v[3]); |
---|
| 181 | (void) g_add_edge(v[2],v[5]); |
---|
| 182 | (void) g_add_edge(v[2],v[3]); |
---|
| 183 | (void) g_add_edge(v[3],v[5]); |
---|
| 184 | (void) g_add_edge(v[6],v[2]); |
---|
| 185 | |
---|
| 186 | (void) g_add_edge(v[7],v[8]); |
---|
| 187 | (void) g_add_edge(v[9],v[7]); |
---|
| 188 | (void) g_add_edge(v[9],v[8]); |
---|
| 189 | arr = g_dfs(g); |
---|
| 190 | (void) fprintf(stdout,"Depth first sort\n"); |
---|
| 191 | for (i = 0; i < 10; i++) { |
---|
| 192 | x = array_fetch(vertex_t *,arr,i); |
---|
| 193 | (void) fprintf(stdout,"%d\n",x->user_data); |
---|
| 194 | } |
---|
| 195 | array_free(arr); |
---|
| 196 | (void) fprintf(stdout,"\nReverse sort\n"); |
---|
| 197 | arr = g_graph_sort(g,reverso); |
---|
| 198 | for (i = 0; i < 10; i++) { |
---|
| 199 | x = array_fetch(vertex_t *,arr,i); |
---|
| 200 | (void) fprintf(stdout,"%d\n",x->user_data); |
---|
| 201 | } |
---|
| 202 | array_free(arr); |
---|
| 203 | g_free(g,voidNULL,voidNULL,voidNULL); |
---|
| 204 | return(0); |
---|
| 205 | } |
---|
| 206 | |
---|
| 207 | init_graph() |
---|
| 208 | { |
---|
| 209 | extern int g_unique_id; |
---|
| 210 | |
---|
| 211 | g_unique_id = 0; |
---|
| 212 | com_add_command("_graph_test",graph_test,0); |
---|
| 213 | com_add_command("_graph_static_test",graph_static_test,0); |
---|
| 214 | com_add_command("_graph_dfs_test",graph_dfs_test,0); |
---|
| 215 | } |
---|
| 216 | |
---|
| 217 | end_graph() |
---|
| 218 | { |
---|
| 219 | } |
---|
| 220 | |
---|
| 221 | /* |
---|
| 222 | |
---|
| 223 | ______ 1 |
---|
| 224 | / \ / |
---|
| 225 | / v v |
---|
| 226 | | 0 ---> 3 ----> 4 9 --> 8 |
---|
| 227 | | | \ ^\ | ^ |
---|
| 228 | | | \ | \ | / |
---|
| 229 | | | \ | \ | / |
---|
| 230 | \ | \ | \ | / |
---|
| 231 | \v v| v v/ |
---|
| 232 | 6 ---> 2 --> 5 7 |
---|
| 233 | |
---|
| 234 | This is the graph represented in test_graph_dfs |
---|
| 235 | */ |
---|
| 236 | |
---|