1 /* mkAdjGraph.c.c */
2
3 #include "../EGraph.h"
4
5 /*--------------------------------------------------------------------*/
6 /*
7 ----------------------------------------------------
8 create a Graph object that holds the adjacency graph
9 of the assembled elements.
10
11 created -- 95nov03, cca
12 ----------------------------------------------------
13 */
14 Graph *
EGraph_mkAdjGraph(EGraph * egraph)15 EGraph_mkAdjGraph (
16 EGraph *egraph
17 ) {
18 int elem, esize, i, nelem, nvtx, v, vsize, w ;
19 int *eind, *head, *link, *marker, *offsets, *vind ;
20 IVL *eadjIVL, *gadjIVL ;
21 Graph *graph ;
22 /*
23 ---------------
24 check the input
25 ---------------
26 */
27 if ( egraph == NULL || (eadjIVL = egraph->adjIVL) == NULL ) {
28 fprintf(stderr, "\n fatal error in EGraph_mkAdjGraph(%p)"
29 "\n bad input\n", egraph) ;
30 exit(-1) ;
31 }
32 nelem = egraph->nelem ;
33 nvtx = egraph->nvtx ;
34 /*
35 --------------------------------
36 set up the linked list structure
37 --------------------------------
38 */
39 head = IVinit(nvtx, -1) ;
40 link = IVinit(nelem, -1) ;
41 offsets = IVinit(nelem, 0) ;
42 /*
43 -----------------------------------------------------------
44 sort the vertices in each element list into ascending order
45 and link them into their first vertex
46 -----------------------------------------------------------
47 */
48 for ( elem = 0 ; elem < nelem ; elem++ ) {
49 IVL_listAndSize(eadjIVL, elem, &esize, &eind) ;
50 if ( esize > 0 ) {
51 IVqsortUp(esize, eind) ;
52 v = eind[0] ;
53 link[elem] = head[v] ;
54 head[v] = elem ;
55 }
56 }
57 /*
58 ---------------------------
59 create the new Graph object
60 ---------------------------
61 */
62 graph = Graph_new() ;
63 Graph_init1(graph, egraph->type, nvtx, 0, 0, IVL_CHUNKED, IVL_CHUNKED) ;
64 gadjIVL = graph->adjIVL ;
65 /*
66 ----------------------
67 loop over the vertices
68 ----------------------
69 */
70 vind = IVinit(nvtx, -1) ;
71 marker = IVinit(nvtx, -1) ;
72 for ( v = 0 ; v < nvtx ; v++ ) {
73 /*
74 ---------------------------------
75 loop over the supporting elements
76 ---------------------------------
77 */
78 vsize = 0 ;
79 vind[vsize++] = v ;
80 marker[v] = v ;
81 while ( (elem = head[v]) != -1 ) {
82 /*
83 fprintf(stdout, "\n checking out element %d :", jelem) ;
84 */
85 head[v] = link[elem] ;
86 IVL_listAndSize(eadjIVL, elem, &esize, &eind) ;
87 for ( i = 0 ; i < esize ; i++ ) {
88 w = eind[i] ;
89 if ( marker[w] != v ) {
90 marker[w] = v ;
91 vind[vsize++] = w ;
92 }
93 }
94 if ( (i = ++offsets[elem]) < esize ) {
95 w = eind[i] ;
96 link[elem] = head[w] ;
97 head[w] = elem ;
98 }
99 }
100 IVqsortUp(vsize, vind) ;
101 IVL_setList(gadjIVL, v, vsize, vind) ;
102 }
103 graph->nedges = gadjIVL->tsize ;
104 if ( egraph->type == 0 ) {
105 graph->totvwght = nvtx ;
106 } else if ( egraph->type == 1 ) {
107 /*
108 ------------------------------
109 fill the vertex weights vector
110 ------------------------------
111 */
112 IVcopy(nvtx, graph->vwghts, egraph->vwghts) ;
113 graph->totvwght = IVsum(nvtx, graph->vwghts) ;
114 }
115 graph->totewght = graph->nedges ;
116 /*
117 ------------------------
118 free the working storage
119 ------------------------
120 */
121 IVfree(head) ;
122 IVfree(link) ;
123 IVfree(marker) ;
124 IVfree(vind) ;
125 IVfree(offsets) ;
126
127 return(graph) ; }
128
129 /*--------------------------------------------------------------------*/
130