1 #include "graph.h"
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <limits.h>
6 #include <assert.h>
7 #include <string.h>
8 #include "vstack.h"
9 #include "bitbool.h"
10
11 //#define DEBUG
12 #include "debug.h"
13
14 /* static const cmph_uint8 bitmask[8] = { 1, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7 }; */
15 /* #define GETBIT(array, i) (array[(i) / 8] & bitmask[(i) % 8]) */
16 /* #define SETBIT(array, i) (array[(i) / 8] |= bitmask[(i) % 8]) */
17 /* #define UNSETBIT(array, i) (array[(i) / 8] &= (~(bitmask[(i) % 8]))) */
18
19 #define abs_edge(e, i) (e % g->nedges + i * g->nedges)
20
21 struct __graph_t
22 {
23 cmph_uint32 nnodes;
24 cmph_uint32 nedges;
25 cmph_uint32 *edges;
26 cmph_uint32 *first;
27 cmph_uint32 *next;
28 cmph_uint8 *critical_nodes; /* included -- Fabiano*/
29 cmph_uint32 ncritical_nodes; /* included -- Fabiano*/
30 cmph_uint32 cedges;
31 int shrinking;
32 };
33
34 static cmph_uint32 EMPTY = UINT_MAX;
35
36 graph_t *graph_new(cmph_uint32 nnodes, cmph_uint32 nedges)
37 {
38 graph_t *graph = (graph_t *)malloc(sizeof(graph_t));
39 if (!graph) return NULL;
40
41 graph->edges = (cmph_uint32 *)malloc(sizeof(cmph_uint32) * 2 * nedges);
42 graph->next = (cmph_uint32 *)malloc(sizeof(cmph_uint32) * 2 * nedges);
43 graph->first = (cmph_uint32 *)malloc(sizeof(cmph_uint32) * nnodes);
44 graph->critical_nodes = NULL; /* included -- Fabiano*/
45 graph->ncritical_nodes = 0; /* included -- Fabiano*/
46 graph->nnodes = nnodes;
47 graph->nedges = nedges;
48
49 graph_clear_edges(graph);
50 return graph;
51 }
52
53
54 void graph_destroy(graph_t *graph)
55 {
56 DEBUGP("Destroying graph\n");
57 free(graph->edges);
58 free(graph->first);
59 free(graph->next);
60 free(graph->critical_nodes); /* included -- Fabiano*/
61 free(graph);
62 return;
63 }
64
65 void graph_print(graph_t *g)
66 {
67 cmph_uint32 i, e;
68 for (i = 0; i < g->nnodes; ++i)
69 {
70 DEBUGP("Printing edges connected to %u\n", i);
71 e = g->first[i];
72 if (e != EMPTY)
73 {
74 printf("%u -> %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
75 while ((e = g->next[e]) != EMPTY)
76 {
77 printf("%u -> %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
78 }
79 }
80
81 }
82 return;
83 }
84
85 void graph_add_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
86 {
87 cmph_uint32 e = g->cedges;
88
89 assert(v1 < g->nnodes);
90 assert(v2 < g->nnodes);
91 assert(e < g->nedges);
92 assert(!g->shrinking);
93
94 g->next[e] = g->first[v1];
95 g->first[v1] = e;
96 g->edges[e] = v2;
97
98 g->next[e + g->nedges] = g->first[v2];
99 g->first[v2] = e + g->nedges;
100 g->edges[e + g->nedges] = v1;
101
102 ++(g->cedges);
103 }
104
105 static int check_edge(graph_t *g, cmph_uint32 e, cmph_uint32 v1, cmph_uint32 v2)
106 {
107 DEBUGP("Checking edge %u %u looking for %u %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)], v1, v2);
108 if (g->edges[abs_edge(e, 0)] == v1 && g->edges[abs_edge(e, 1)] == v2) return 1;
109 if (g->edges[abs_edge(e, 0)] == v2 && g->edges[abs_edge(e, 1)] == v1) return 1;
110 return 0;
111 }
112
113 cmph_uint32 graph_edge_id(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
114 {
115 cmph_uint32 e;
116 e = g->first[v1];
117 assert(e != EMPTY);
118 if (check_edge(g, e, v1, v2)) return abs_edge(e, 0);
119 do
120 {
121 e = g->next[e];
122 assert(e != EMPTY);
123 }
124 while (!check_edge(g, e, v1, v2));
125 return abs_edge(e, 0);
126 }
127 static void del_edge_point(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
128 {
129 cmph_uint32 e, prev;
130
131 DEBUGP("Deleting edge point %u %u\n", v1, v2);
132 e = g->first[v1];
133 if (check_edge(g, e, v1, v2))
134 {
135 g->first[v1] = g->next[e];
136 //g->edges[e] = EMPTY;
137 DEBUGP("Deleted\n");
138 return;
139 }
140 DEBUGP("Checking linked list\n");
141 do
142 {
143 prev = e;
144 e = g->next[e];
145 assert(e != EMPTY);
146 }
147 while (!check_edge(g, e, v1, v2));
148
149 g->next[prev] = g->next[e];
150 //g->edges[e] = EMPTY;
151 DEBUGP("Deleted\n");
152 }
153
154
155 void graph_del_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
156 {
157 g->shrinking = 1;
158 del_edge_point(g, v1, v2);
159 del_edge_point(g, v2, v1);
160 }
161
162 void graph_clear_edges(graph_t *g)
163 {
164 cmph_uint32 i;
165 for (i = 0; i < g->nnodes; ++i) g->first[i] = EMPTY;
166 for (i = 0; i < g->nedges*2; ++i)
167 {
168 g->edges[i] = EMPTY;
169 g->next[i] = EMPTY;
170 }
171 g->cedges = 0;
172 g->shrinking = 0;
173 }
174
175 static cmph_uint8 find_degree1_edge(graph_t *g, cmph_uint32 v, cmph_uint8 *deleted, cmph_uint32 *e)
176 {
177 cmph_uint32 edge = g->first[v];
178 cmph_uint8 found = 0;
179 DEBUGP("Checking degree of vertex %u\n", v);
180 if (edge == EMPTY) return 0;
181 else if (!(GETBIT(deleted, abs_edge(edge, 0))))
182 {
183 found = 1;
184 *e = edge;
185 }
186 while(1)
187 {
188 edge = g->next[edge];
189 if (edge == EMPTY) break;
190 if (GETBIT(deleted, abs_edge(edge, 0))) continue;
191 if (found) return 0;
192 DEBUGP("Found first edge\n");
193 *e = edge;
194 found = 1;
195 }
196 return found;
197 }
198
199 static void cyclic_del_edge(graph_t *g, cmph_uint32 v, cmph_uint8 *deleted)
200 {
201
202 cmph_uint32 e = 0;
203 cmph_uint8 degree1;
204 cmph_uint32 v1 = v;
205 cmph_uint32 v2 = 0;
206
207 degree1 = find_degree1_edge(g, v1, deleted, &e);
208 if (!degree1) return;
209 while(1)
210 {
211 DEBUGP("Deleting edge %u (%u->%u)\n", e, g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
212 SETBIT(deleted, abs_edge(e, 0));
213
214 v2 = g->edges[abs_edge(e, 0)];
215 if (v2 == v1) v2 = g->edges[abs_edge(e, 1)];
216
217 DEBUGP("Checking if second endpoint %u has degree 1\n", v2);
218 degree1 = find_degree1_edge(g, v2, deleted, &e);
219 if (degree1)
220 {
221 DEBUGP("Inspecting vertex %u\n", v2);
222 v1 = v2;
223 }
224 else break;
225 }
226 }
227
228 int graph_is_cyclic(graph_t *g)
229 {
230 cmph_uint32 i;
231 cmph_uint32 v;
232 cmph_uint8 *deleted = (cmph_uint8 *)malloc((g->nedges*sizeof(cmph_uint8))/8 + 1);
233 size_t deleted_len = g->nedges/8 + 1;
234 memset(deleted, 0, deleted_len);
235
236 DEBUGP("Looking for cycles in graph with %u vertices and %u edges\n", g->nnodes, g->nedges);
237 for (v = 0; v < g->nnodes; ++v)
238 {
239 cyclic_del_edge(g, v, deleted);
240 }
241 for (i = 0; i < g->nedges; ++i)
242 {
243 if (!(GETBIT(deleted, i)))
244 {
245 DEBUGP("Edge %u %u->%u was not deleted\n", i, g->edges[i], g->edges[i + g->nedges]);
246 free(deleted);
247 return 1;
248 }
249 }
250 free(deleted);
251 return 0;
252 }
253
254 cmph_uint8 graph_node_is_critical(graph_t * g, cmph_uint32 v) /* included -- Fabiano */
255 {
256 return (cmph_uint8)GETBIT(g->critical_nodes,v);
257 }
258
259 void graph_obtain_critical_nodes(graph_t *g) /* included -- Fabiano*/
260 {
261 cmph_uint32 i;
262 cmph_uint32 v;
263 cmph_uint8 *deleted = (cmph_uint8 *)malloc((g->nedges*sizeof(cmph_uint8))/8+1);
264 size_t deleted_len = g->nedges/8 + 1;
265 memset(deleted, 0, deleted_len);
266 free(g->critical_nodes);
267 g->critical_nodes = (cmph_uint8 *)malloc((g->nnodes*sizeof(cmph_uint8))/8 + 1);
268 g->ncritical_nodes = 0;
269 memset(g->critical_nodes, 0, (g->nnodes*sizeof(cmph_uint8))/8 + 1);
270 DEBUGP("Looking for the 2-core in graph with %u vertices and %u edges\n", g->nnodes, g->nedges);
271 for (v = 0; v < g->nnodes; ++v)
272 {
273 cyclic_del_edge(g, v, deleted);
274 }
275
276 for (i = 0; i < g->nedges; ++i)
277 {
278 if (!(GETBIT(deleted,i)))
279 {
280 DEBUGP("Edge %u %u->%u belongs to the 2-core\n", i, g->edges[i], g->edges[i + g->nedges]);
281 if(!(GETBIT(g->critical_nodes,g->edges[i])))
282 {
283 g->ncritical_nodes ++;
284 SETBIT(g->critical_nodes,g->edges[i]);
285 }
286 if(!(GETBIT(g->critical_nodes,g->edges[i + g->nedges])))
287 {
288 g->ncritical_nodes ++;
289 SETBIT(g->critical_nodes,g->edges[i + g->nedges]);
290 }
291 }
292 }
293 free(deleted);
294 }
295
296 cmph_uint8 graph_contains_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2) /* included -- Fabiano*/
297 {
298 cmph_uint32 e;
299 e = g->first[v1];
300 if(e == EMPTY) return 0;
301 if (check_edge(g, e, v1, v2)) return 1;
302 do
303 {
304 e = g->next[e];
305 if(e == EMPTY) return 0;
306 }
307 while (!check_edge(g, e, v1, v2));
308 return 1;
309 }
310
311 cmph_uint32 graph_vertex_id(graph_t *g, cmph_uint32 e, cmph_uint32 id) /* included -- Fabiano*/
312 {
313 return (g->edges[e + id*g->nedges]);
314 }
315
316 cmph_uint32 graph_ncritical_nodes(graph_t *g) /* included -- Fabiano*/
317 {
318 return g->ncritical_nodes;
319 }
320
321 graph_iterator_t graph_neighbors_it(graph_t *g, cmph_uint32 v)
322 {
323 graph_iterator_t it;
324 it.vertex = v;
325 it.edge = g->first[v];
326 return it;
327 }
328 cmph_uint32 graph_next_neighbor(graph_t *g, graph_iterator_t* it)
329 {
330 cmph_uint32 ret;
331 if(it->edge == EMPTY) return GRAPH_NO_NEIGHBOR;
332 if (g->edges[it->edge] == it->vertex) ret = g->edges[it->edge + g->nedges];
333 else ret = g->edges[it->edge];
334 it->edge = g->next[it->edge];
335 return ret;
336 }
337
338