OpenRadioss 2025.1.11
OpenRadioss project
Loading...
Searching...
No Matches
graph.c
Go to the documentation of this file.
1/*****************************************************************************
2/
3/ SPACE (SPArse Cholesky Elimination) Library: graph.c
4/
5/ author J"urgen Schulze, University of Paderborn
6/ created 99sep14
7/
8/ This file contains functions dealing with the graph object.
9/
10******************************************************************************
11
12Data type: struct graph
13 int nvtx; number of vertices
14 int nedges; number of edges
15 int type; vertices can be UNWEIGTHED or WEIGTHED
16 int totvwght; total vertex weight
17 int *xadj; xadj[u] points to start of u's adjacency list
18 int *adjncy; holds the adjacency lists
19 int *vwght; holds the vertex weights
20Comments:
21 o no edge weights are stored. In our application weighted graphs re-
22 present compressed unweighted graphs and, therefore, ewght[(u,v)] =
23 vwght[u] * vwght[v].
24Methods in lib/graph.c:
25- G = newGraph(int nvtx, int nedges);
26 o Initial: we assume that G is unweighted, therefore:
27 type = UNWEIGTHED, totvwght = nvtx, and vwght[u] = 1
28- void freeGraph(graph_t *G);
29- void printGraph(graph_t *G);
30- void randomizeGraph(graph_t *G);
31- Gsub = setupSubgraph(graph_t *G, int *intvertex, int nvint, int *vtxmap);
32 o extracts the subgraph induced by the vertices in array intvertex from G.
33 vtxmap maps the vertices in intvertex to the vertices of the subgraph.
34- G = setupGraphFromMtx(inputMtx_t *A);
35- G = setupGridGraph(int dimX, int dimY, int type);
36 o type e {GRID, MESH, TORUS}
37- int connectedComponents(graph_t *G);
38- cG = compressGraph(graph_t *G, int *vtxmap)
39 o cG = NULL, if there are not enough ind. vertices (see COMPRESS_FRACTION)
40 o for u in G vtxmap[u] points to representative of u in cG
41
42******************************************************************************/
43
44#include <space.h>
45
46
47/*****************************************************************************
48******************************************************************************/
49graph_t*
50newGraph(PORD_INT nvtx, PORD_INT nedges)
51{ graph_t *G;
52 PORD_INT i;
53
54 mymalloc(G, 1, graph_t);
55 mymalloc(G->xadj, (nvtx+1), PORD_INT);
56 mymalloc(G->adjncy, nedges, PORD_INT);
57 mymalloc(G->vwght, nvtx, PORD_INT);
58
59 G->nvtx = nvtx;
60 G->nedges = nedges;
61 G->type = UNWEIGHTED;
62 G->totvwght = nvtx;
63 for (i = 0; i < nvtx; i++)
64 G->vwght[i] = 1;
65
66 return(G);
67}
68
69
70/*****************************************************************************
71******************************************************************************/
72void
73freeGraph(graph_t *G)
74{
75 free(G->xadj);
76 free(G->adjncy);
77 free(G->vwght);
78 free(G);
79}
80
81
82/*****************************************************************************
83******************************************************************************/
84void
85printGraph(graph_t *G)
86{ PORD_INT count, u, i, istart, istop;
87
88 printf("\n#vertices %d, #edges %d, type %d, totvwght %d\n", G->nvtx,
89 G->nedges >> 1, G->type, G->totvwght);
90 for (u = 0; u < G->nvtx; u++)
91 { count = 0;
92 printf("--- adjacency list of vertex %d (weight %d):\n", u, G->vwght[u]);
93 istart = G->xadj[u];
94 istop = G->xadj[u+1];
95 for (i = istart; i < istop; i++)
96 { printf("%5d", G->adjncy[i]);
97 if ((++count % 16) == 0)
98 printf("\n");
99 }
100 if ((count % 16) != 0)
101 printf("\n");
102 }
103}
104
105
106/*****************************************************************************
107******************************************************************************/
108void
109randomizeGraph(graph_t *G)
110{ PORD_INT *xadj, *adjncy, nvtx, u, v, len, j, i, istart, istop;
111
112 nvtx = G->nvtx;
113 xadj = G->xadj;
114 adjncy = G->adjncy;
115
116 for (u = 0; u < nvtx; u++)
117 { istart = xadj[u];
118 istop = xadj[u+1];
119 if ((len = istop - istart) > 1)
120 for (i = istart; i < istop; i++)
121 { j = myrandom(len);
122 swap(adjncy[i], adjncy[i+j], v);
123 len--;
124 }
125 }
126}
127
128
129/*****************************************************************************
130******************************************************************************/
131graph_t*
132setupSubgraph(graph_t *G, PORD_INT *intvertex, PORD_INT nvint, PORD_INT *vtxmap)
133{ graph_t *Gsub;
134 PORD_INT *xadj, *adjncy, *vwght, *xadjGsub, *adjncyGsub, *vwghtGsub;
135 PORD_INT nvtx, nedgesGsub, totvwght, u, v, i, j, jstart, jstop, ptr;
136
137 nvtx = G->nvtx;
138 xadj = G->xadj;
139 adjncy = G->adjncy;
140 vwght = G->vwght;
141
142 /* -------------------------------------------------------------
143 compute number of edges and local indices of vertices in Gsub
144 ------------------------------------------------------------- */
145 nedgesGsub = 0;
146 for (i = 0; i < nvint; i++)
147 { u = intvertex[i];
148 if ((u < 0) || (u >= nvtx))
149 { fprintf(stderr, "\nError in function setupSubgraph\n"
150 " node %d does not belong to graph\n", u);
151 quit();
152 }
153 jstart = xadj[u];
154 jstop = xadj[u+1];
155 for (j = jstart; j < jstop; j++)
156 vtxmap[adjncy[j]] = -1;
157 nedgesGsub += (jstop - jstart);
158 }
159 for (i = 0; i < nvint; i++)
160 { u = intvertex[i];
161 vtxmap[u] = i;
162 }
163
164 Gsub = newGraph(nvint, nedgesGsub);
165 xadjGsub = Gsub->xadj;
166 adjncyGsub = Gsub->adjncy;
167 vwghtGsub = Gsub->vwght;
168
169 /* --------------------------
170 build the induced subgraph
171 -------------------------- */
172 totvwght = 0; ptr = 0;
173 for (i = 0; i < nvint; i++)
174 { u = intvertex[i];
175 xadjGsub[i] = ptr;
176 vwghtGsub[i] = vwght[u];
177 totvwght += vwght[u];
178 jstart = xadj[u];
179 jstop = xadj[u+1];
180 for (j = jstart; j < jstop; j++)
181 { v = adjncy[j];
182 if (vtxmap[v] >= 0)
183 adjncyGsub[ptr++] = vtxmap[v];
184 }
185 }
186 xadjGsub[nvint] = ptr;
187 Gsub->type = G->type;
188 Gsub->totvwght = totvwght;
189 return(Gsub);
190}
191
192/*****************************************************************************
193******************************************************************************/
194graph_t*
195setupGraphFromMtx(inputMtx_t *A)
196{ graph_t *G;
197 PORD_INT *xnza, *nzasub, *xadj, *adjncy;
198 PORD_INT neqs, nelem, nvtx, k, h1, h2, j, i, istart, istop;
199
200 neqs = A->neqs;
201 nelem = A->nelem;
202 xnza = A->xnza;
203 nzasub = A->nzasub;
204
205 /* ------------------------------------
206 allocate memory for unweighted graph
207 ------------------------------------ */
208 G = newGraph(neqs, 2*nelem);
209 nvtx = G->nvtx;
210 xadj = G->xadj;
211 adjncy = G->adjncy;
212
213 /* -----------------------------------------
214 determine the size of each adjacency list
215 ----------------------------------------- */
216 for (k = 0; k < neqs; k++)
217 xadj[k] = xnza[k+1] - xnza[k];
218 for (k = 0; k < nelem; k++)
219 xadj[nzasub[k]]++;
220
221 /* -------------------------------------------------------------
222 determine for each vertex where its adjacency list will start
223 ------------------------------------------------------------- */
224 h1 = xadj[0];
225 xadj[0] = 0;
226 for (k = 1; k <= nvtx; k++)
227 { h2 = xadj[k];
228 xadj[k] = xadj[k-1] + h1;
229 h1 = h2;
230 }
231
232 /* ------------------------
233 fill the adjacency lists
234 ------------------------ */
235 for (k = 0; k < neqs; k++)
236 { istart = xnza[k];
237 istop = xnza[k+1];
238 for (i = istart; i < istop; i++)
239 { j = nzasub[i];
240 adjncy[xadj[k]++] = j; /* store {k,j} in adjacency list of k */
241 adjncy[xadj[j]++] = k; /* store {j,k} in adjacency list of j */
242 }
243 }
244
245 /* --------------------------------------------
246 restore startpoint of each vertex and return
247 -------------------------------------------- */
248 for (k = nvtx-1; k > 0; k--)
249 xadj[k] = xadj[k-1];
250 xadj[0] = 0;
251 return(G);
252}
253
254
255/*****************************************************************************
256******************************************************************************/
257graph_t*
258setupGridGraph(PORD_INT dimX, PORD_INT dimY, PORD_INT type)
259{ graph_t *G;
260 PORD_INT *xadj, *adjncy, nvtx, nedges, knz, k;
261
262 /* ---------------
263 initializations
264 --------------- */
265 G = NULL;
266 knz = 0;
267 nvtx = dimX * dimY;
268
269 /* ---------------------------------
270 create unweighted grid/mesh graph
271 --------------------------------- */
272 if ((type == GRID) || (type == MESH))
273 { nedges = 8 /* for edge vertices */
274 + 6 * (dimX-2 + dimY-2) /* for border vertices */
275 + 4 * (dimX-2) * (dimY-2); /* for interior vertices */
276 if (type == MESH)
277 nedges += 4 * (dimX-1) * (dimY-1); /* diagonals */
278
279 G = newGraph(nvtx, nedges);
280 xadj = G->xadj;
281 adjncy = G->adjncy;
282
283 for (k = 0; k < nvtx; k++)
284 { xadj[k] = knz;
285 if ((k+1) % dimX > 0) /* / k+1-dimX (MESH) */
286 { adjncy[knz++] = k+1; /* k - k+1 (GRID) */
287 if (type == MESH) /* \ k+1+dimX (MESH) */
288 { if (k+1+dimX < nvtx)
289 adjncy[knz++] = k+1+dimX;
290 if (k+1-dimX >= 0)
291 adjncy[knz++] = k+1-dimX;
292 }
293 }
294 if (k % dimX > 0) /* k-1-dimX \ (MESH) */
295 { adjncy[knz++] = k-1; /* k-1 - k (GRID) */
296 if (type == MESH) /* k-1+dimX / (MESH) */
297 { if (k-1+dimX < nvtx)
298 adjncy[knz++] = k-1+dimX;
299 if (k-1-dimX >= 0)
300 adjncy[knz++] = k-1-dimX;
301 }
302 }
303 if (k+dimX < nvtx) /* k-dimX (GRID) */
304 adjncy[knz++] = k+dimX; /* | */
305 if (k-dimX >= 0) /* k */
306 adjncy[knz++] = k-dimX; /* | */
307 } /* k+dimX (GRID) */
308 xadj[nvtx] = knz;
309 }
310
311 /* -----------------------------
312 create unweighted torus graph
313 ----------------------------- */
314 if (type == TORUS)
315 { nedges = 4 * dimX * dimY;
316
317 G = newGraph(nvtx, nedges);
318 xadj = G->xadj;
319 adjncy = G->adjncy;
320
321 for (k = 0; k < nvtx; k++)
322 { xadj[k] = knz;
323 if (((k+1) % dimX) == 0) /* k -- k+1 */
324 adjncy[knz++] = k+1-dimX;
325 else
326 adjncy[knz++] = k+1;
327 if ((k % dimX) == 0) /* k-1 -- k */
328 adjncy[knz++] = k-1+dimX;
329 else
330 adjncy[knz++] = k-1;
331 adjncy[knz++] = (k+dimX) % nvtx; /* k-dimX */
332 adjncy[knz++] = (k+dimX*(dimY-1)) % nvtx; /* | */
333 } /* k */
334 xadj[nvtx] = knz; /* | */
335 } /* k+dimX */
336
337 return(G);
338}
339
340
341/*****************************************************************************
342******************************************************************************/
343PORD_INT
344connectedComponents(graph_t *G)
345{ PORD_INT *xadj, *adjncy, *marker, *queue;
346 PORD_INT nvtx, u, v, w, qhead, qtail, comp, i, istart, istop;
347
348 nvtx = G->nvtx;
349 xadj = G->xadj;
350 adjncy = G->adjncy;
351
352 /* ------------------------
353 allocate working storage
354 ------------------------ */
355 mymalloc(marker, nvtx, PORD_INT);
356 mymalloc(queue, nvtx, PORD_INT);
357
358 /* ---------------
359 initializations
360 --------------- */
361 comp = 0;
362 for (u = 0; u < nvtx; u++)
363 marker[u] = -1;
364
365 /* --------------------------------------
366 get the number of connected components
367 -------------------------------------- */
368 for (u = 0; u < nvtx; u++)
369 if (marker[u] == -1)
370 { comp++;
371 qhead = 0; qtail = 1;
372 queue[0] = u; marker[u] = 0;
373
374 while (qhead != qtail) /* breadth first search in each comp. */
375 { v = queue[qhead++];
376 istart = xadj[v];
377 istop = xadj[v+1];
378 for (i = istart; i < istop; i++)
379 { w = adjncy[i];
380 if (marker[w] == -1)
381 { queue[qtail++] = w;
382 marker[w] = 0;
383 }
384 }
385 }
386 }
387
388 /* -------------------------------
389 free working storage and return
390 ------------------------------- */
391 free(marker); free(queue);
392 return(comp);
393}
394
395
396/*****************************************************************************
397private function of compressGraph
398******************************************************************************/
399static PORD_INT
400indNodes(graph_t *G, PORD_INT *vtxmap)
401{ PORD_INT *xadj, *adjncy, *deg, *checksum, *tmp;
402 PORD_INT nvtx, cnvtx, u, v, i, istart, istop, j, jstart, jstop;
403
404 nvtx = G->nvtx;
405 xadj = G->xadj;
406 adjncy = G->adjncy;
407
408 /* -------------------------
409 set up the working arrays
410 ------------------------- */
411 mymalloc(deg, nvtx, PORD_INT);
412 mymalloc(checksum, nvtx, PORD_INT);
413 mymalloc(tmp, nvtx, PORD_INT);
414
415 /* -------------------------------------------------
416 compute for each vertex u its degree and checksum
417 ------------------------------------------------- */
418 for (u = 0; u < nvtx; u++)
419 { istart = xadj[u];
420 istop = xadj[u+1];
421 deg[u] = istop - istart;
422 checksum[u] = u;
423 tmp[u] = -1;
424 vtxmap[u] = u;
425 for (i = istart; i < istop; i++)
426 checksum[u] += adjncy[i];
427 }
428
429 /* -------------------------------------
430 search for indistinguishable vertices
431 ------------------------------------- */
432 cnvtx = nvtx;
433 for (u = 0; u < nvtx; u++)
434 if (vtxmap[u] == u)
435 { tmp[u] = u;
436 istart = xadj[u];
437 istop = xadj[u+1];
438 for (i = istart; i < istop; i++)
439 tmp[adjncy[i]] = u;
440
441 /* scan adjacency list of vertex u for indistinguishable vertices */
442 for (i = istart; i < istop; i++)
443 { v = adjncy[i];
444 if ((v > u) && (checksum[v] == checksum[u]) && (deg[v] == deg[u])
445 && (vtxmap[v] == v))
446 { jstart = xadj[v];
447 jstop = xadj[v+1];
448 for (j = jstart; j < jstop; j++)
449 if (tmp[adjncy[j]] != u) goto FAILURE;
450
451 /* found it!!! map v onto u */
452 vtxmap[v] = u;
453 cnvtx--;
454FAILURE: ;
455 }
456 }
457 }
458
459 /* ----------------------
460 free memory and return
461 ---------------------- */
462 free(deg); free(checksum); free(tmp);
463 return(cnvtx);
464}
465
466
467/*****************************************************************************
468******************************************************************************/
469graph_t*
470compressGraph(graph_t* G, PORD_INT* vtxmap)
471{ graph_t *Gc;
472 PORD_INT *xadj, *adjncy, *vwght, *xadjGc, *adjncyGc, *vwghtGc, *perm;
473 PORD_INT nvtx, nvtxGc, nedgesGc, u, v, i, istart, istop;
474
475 nvtx = G->nvtx;
476 xadj = G->xadj;
477 adjncy = G->adjncy;
478 vwght = G->vwght;
479
480 /* --------------------------------------------------------------
481 compressed graph small enough? if so, allocate working storage
482 -------------------------------------------------------------- */
483 /* avoid print statement
484 * printf("indNodes(G, vtxmap) = %d",indNodes(G, vtxmap)); */
485 if ((nvtxGc = indNodes(G, vtxmap)) > COMPRESS_FRACTION * nvtx)
486 return(NULL);
487 mymalloc(perm, nvtx, PORD_INT);
488
489 /* -----------------------------------
490 count edges of the compressed graph
491 ----------------------------------- */
492 nedgesGc = 0;
493 for (u = 0; u < nvtx; u++)
494 if (vtxmap[u] == u)
495 { istart = xadj[u];
496 istop = xadj[u+1];
497 for (i = istart; i < istop; i++)
498 { v = adjncy[i];
499 if (vtxmap[v] == v) nedgesGc++;
500 }
501 }
502
503 /* ---------------------------------------------------------
504 allocate memory for the compressed graph and construct it
505 --------------------------------------------------------- */
506 Gc = newGraph(nvtxGc, nedgesGc);
507 xadjGc = Gc->xadj;
508 adjncyGc = Gc->adjncy;
509 vwghtGc = Gc->vwght;
510
511 nvtxGc = nedgesGc = 0;
512 for (u = 0; u < nvtx; u++)
513 if (vtxmap[u] == u)
514 { istart = xadj[u];
515 istop = xadj[u+1];
516 xadjGc[nvtxGc] = nedgesGc;
517 vwghtGc[nvtxGc] = 0;
518 perm[u] = nvtxGc++;
519 for (i = istart; i < istop; i++)
520 { v = adjncy[i];
521 if (vtxmap[v] == v) adjncyGc[nedgesGc++] = v;
522 }
523 }
524 xadjGc[nvtxGc] = nedgesGc;
525
526 for (i = 0; i < nedgesGc; i++)
527 adjncyGc[i] = perm[adjncyGc[i]];
528 for (u = 0; u < nvtx; u++)
529 { vtxmap[u] = perm[vtxmap[u]];
530 vwghtGc[vtxmap[u]] += vwght[u];
531 }
532 Gc->type = WEIGHTED;
533 Gc->totvwght = G->totvwght;
534
535 /* ----------------------
536 free memory and return
537 ---------------------- */
538 free(perm);
539 return(Gc);
540}
541
MESH
#define MESH
Definition const.h:14
TORUS
#define TORUS
Definition const.h:15
WEIGHTED
#define WEIGHTED
Definition const.h:20
GRID
#define GRID
Definition const.h:13
UNWEIGHTED
#define UNWEIGHTED
Definition const.h:19
indNodes
static PORD_INT indNodes(graph_t *G, PORD_INT *vtxmap)
Definition graph.c:400
setupSubgraph
graph_t * setupSubgraph(graph_t *G, PORD_INT *intvertex, PORD_INT nvint, PORD_INT *vtxmap)
Definition graph.c:132
setupGraphFromMtx
graph_t * setupGraphFromMtx(inputMtx_t *A)
Definition graph.c:195
setupGridGraph
graph_t * setupGridGraph(PORD_INT dimX, PORD_INT dimY, PORD_INT type)
Definition graph.c:258
connectedComponents
PORD_INT connectedComponents(graph_t *G)
Definition graph.c:344
freeGraph
void freeGraph(graph_t *G)
Definition graph.c:73
compressGraph
graph_t * compressGraph(graph_t *G, PORD_INT *vtxmap)
Definition graph.c:470
randomizeGraph
void randomizeGraph(graph_t *G)
Definition graph.c:109
newGraph
graph_t * newGraph(PORD_INT nvtx, PORD_INT nedges)
Definition graph.c:50
printGraph
void printGraph(graph_t *G)
Definition graph.c:85
myrandom
#define myrandom(range)
Definition macros.h:37
swap
#define swap(a, b, tmp)
Definition macros.h:40
quit
#define quit()
Definition macros.h:64
mymalloc
#define mymalloc(ptr, nr, type)
Definition macros.h:23
COMPRESS_FRACTION
#define COMPRESS_FRACTION
Definition params.h:14
comp
int comp(int a, int b)
Definition set_surface_lines.cpp:102
_graph::totvwght
PORD_INT totvwght
Definition types.h:34
_graph::xadj
PORD_INT * xadj
Definition types.h:35
_graph::type
PORD_INT type
Definition types.h:33
_graph::nedges
PORD_INT nedges
Definition types.h:32
_graph::nvtx
PORD_INT nvtx
Definition types.h:31
_graph::vwght
PORD_INT * vwght
Definition types.h:37
_graph::adjncy
PORD_INT * adjncy
Definition types.h:36
_inputMtx::xnza
PORD_INT * xnza
Definition types.h:170
_inputMtx::nelem
PORD_INT nelem
Definition types.h:167
_inputMtx::neqs
PORD_INT neqs
Definition types.h:166
_inputMtx::nzasub
PORD_INT * nzasub
Definition types.h:171
PORD_INT
#define PORD_INT
Definition types.h:20
inputMtx_t
struct _inputMtx inputMtx_t
graph_t
struct _graph graph_t