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