1 /* makeSchurComplement.c */
2
3 #include "../MSMD.h"
4
5 #define MYDEBUG 0
6
7 /*--------------------------------------------------------------------*/
8 /*
9 ----------------------------------------------------------------
10 purpose --
11
12 if the elimination has halted before all the stages have been
13 eliminated, then create the schur complement graph and the map
14 from the original vertices those in the schur complement graph.
15
16 schurGraph -- Graph object to contain the schur complement graph
17 VtoPhi -- IV object to contain the map from vertices in V
18 to schur complement vertices in Phi
19
20 created -- 97feb01, cca
21 ----------------------------------------------------------------
22 */
23 void
MSMD_makeSchurComplement(MSMD * msmd,Graph * schurGraph,IV * VtoPhiIV)24 MSMD_makeSchurComplement (
25 MSMD *msmd,
26 Graph *schurGraph,
27 IV *VtoPhiIV
28 ) {
29 int nedge, nPhi, nvtx, totewght, totvwght ;
30 int *mark, *rep, *VtoPhi, *vwghts ;
31 int count, *list ;
32 int ierr, ii, size, *adj ;
33 int phi, psi, tag ;
34 IP *ip ;
35 IVL *adjIVL ;
36 MSMDvtx *u, *v, *vertices, *vfirst, *vlast, *w ;
37 /*
38 ---------------
39 check the input
40 ---------------
41 */
42 if ( msmd == NULL || schurGraph == NULL || VtoPhiIV == NULL ) {
43 fprintf(stderr,
44 "\n\n fatal error in MSMD_makeSchurComplement(%p,%p,%p)"
45 "\n bad input\n", msmd, schurGraph, VtoPhiIV) ;
46 exit(-1) ;
47 }
48 vertices = msmd->vertices ;
49 nvtx = msmd->nvtx ;
50 /*
51 -------------------------------------
52 initialize the V-to-Phi map IV object
53 -------------------------------------
54 */
55 IV_clearData(VtoPhiIV) ;
56 IV_setSize(VtoPhiIV, nvtx) ;
57 IV_fill(VtoPhiIV, -2) ;
58 VtoPhi = IV_entries(VtoPhiIV) ;
59 /*
60 ---------------------------------------------
61 count the number of Schur complement vertices
62 ---------------------------------------------
63 */
64 vfirst = vertices ;
65 vlast = vfirst + nvtx - 1 ;
66 nPhi = 0 ;
67 for ( v = vfirst ; v <= vlast ; v++ ) {
68 #if MYDEBUG > 0
69 fprintf(stdout, "\n v->id = %d, v->status = %c", v->id, v->status) ;
70 fflush(stdout) ;
71 #endif
72 switch ( v->status ) {
73 case 'L' :
74 case 'E' :
75 case 'I' :
76 break ;
77 case 'B' :
78 VtoPhi[v->id] = nPhi++ ;
79 #if MYDEBUG > 0
80 fprintf(stdout, ", VtoPhi[%d] = %d", v->id, VtoPhi[v->id]) ;
81 fflush(stdout) ;
82 #endif
83 break ;
84 default :
85 break ;
86 }
87 }
88 #if MYDEBUG > 0
89 fprintf(stdout, "\n\n nPhi = %d", nPhi) ;
90 fflush(stdout) ;
91 #endif
92 /*
93 ----------------------------------------------------
94 get the representative vertex id for each Phi vertex
95 ----------------------------------------------------
96 */
97 rep = IVinit(nPhi, -1) ;
98 for ( v = vfirst ; v <= vlast ; v++ ) {
99 if ( (phi = VtoPhi[v->id]) >= 0 ) {
100 #if MYDEBUG > 0
101 fprintf(stdout, "\n rep[%d] = %d", phi, v->id) ;
102 fflush(stdout) ;
103 #endif
104 rep[phi] = v->id ;
105 }
106 }
107 /*
108 ------------------------------------------
109 set the map for indistinguishable vertices
110 ------------------------------------------
111 */
112 for ( v = vfirst ; v <= vlast ; v++ ) {
113 if ( v->status == 'I' ) {
114 w = v ;
115 while ( w->status == 'I' ) {
116 w = w->par ;
117 }
118 #if MYDEBUG > 0
119 fprintf(stdout, "\n v = %d, status = %c, w = %d, status = %c",
120 v->id, v->status, w->id, w->status) ;
121 fflush(stdout) ;
122 #endif
123 VtoPhi[v->id] = VtoPhi[w->id] ;
124 }
125 }
126 #if MYDEBUG > 0
127 fprintf(stdout, "\n\n VtoPhi") ;
128 IV_writeForHumanEye(VtoPhiIV, stdout) ;
129 fflush(stdout) ;
130 #endif
131 /*
132 ---------------------------
133 initialize the Graph object
134 ---------------------------
135 */
136 Graph_clearData(schurGraph) ;
137 Graph_init1(schurGraph, 1, nPhi, 0, 0, IVL_CHUNKED, IVL_CHUNKED) ;
138 adjIVL = schurGraph->adjIVL ;
139 vwghts = schurGraph->vwghts ;
140 #if MYDEBUG > 0
141 fprintf(stdout, "\n\n schurGraph initialized, nvtx = %d",
142 schurGraph->nvtx) ;
143 fflush(stdout) ;
144 #endif
145 /*
146 -------------------------------
147 fill the vertex adjacency lists
148 -------------------------------
149 */
150 mark = IVinit(nPhi, -1) ;
151 list = IVinit(nPhi, -1) ;
152 nedge = totvwght = totewght = 0 ;
153 for ( phi = 0 ; phi < nPhi ; phi++ ) {
154 /*
155 -----------------------------
156 get the representative vertex
157 -----------------------------
158 */
159 v = vfirst + rep[phi] ;
160 #if MYDEBUG > 0
161 fprintf(stdout, "\n phi = %d, v = %d", phi, v->id) ;
162 fflush(stdout) ;
163 MSMDvtx_print(v, stdout) ;
164 fflush(stdout) ;
165 #endif
166 count = 0 ;
167 tag = v->id ;
168 /*
169 ---------------------------
170 load self in adjacency list
171 ---------------------------
172 */
173 mark[phi] = tag ;
174 totewght += v->wght * v->wght ;
175 #if MYDEBUG > 0
176 fprintf(stdout, "\n mark[%d] = %d", phi, mark[phi]) ;
177 fflush(stdout) ;
178 #endif
179 list[count++] = phi ;
180 /*
181 ----------------------------------------
182 load boundary lists of adjacent subtrees
183 ----------------------------------------
184 */
185 for ( ip = v->subtrees ; ip != NULL ; ip = ip->next ) {
186 u = vertices + ip->val ;
187 size = u->nadj ;
188 adj = u->adj ;
189 #if MYDEBUG > 0
190 fprintf(stdout, "\n subtree %d :", u->id) ;
191 IVfp80(stdout, size, adj, 15, &ierr) ;
192 fflush(stdout) ;
193 #endif
194 for ( ii = 0 ; ii < size ; ii++ ) {
195 w = vertices + adj[ii] ;
196 #if MYDEBUG > 0
197 fprintf(stdout, "\n w %d, status %c, psi %d",
198 w->id, w->status, VtoPhi[w->id]) ;
199 fflush(stdout) ;
200 #endif
201 if ( (psi = VtoPhi[w->id]) != -2 && mark[psi] != tag ) {
202 mark[psi] = tag ;
203 #if MYDEBUG > 0
204 fprintf(stdout, ", mark[%d] = %d", psi, mark[psi]) ;
205 fflush(stdout) ;
206 #endif
207 list[count++] = psi ;
208 totewght += v->wght * w->wght ;
209 }
210 }
211 }
212 /*
213 ----------------------
214 load adjacent vertices
215 ----------------------
216 */
217 size = v->nadj ;
218 adj = v->adj ;
219 for ( ii = 0 ; ii < size ; ii++ ) {
220 w = vertices + adj[ii] ;
221 if ( (psi = VtoPhi[w->id]) != -2 && mark[psi] != tag ) {
222 mark[psi] = tag ;
223 list[count++] = psi ;
224 totewght += v->wght * w->wght ;
225 }
226 }
227 /*
228 ---------------------------------------------
229 sort the list and inform adjacency IVL object
230 ---------------------------------------------
231 */
232 IVqsortUp(count, list) ;
233 IVL_setList(adjIVL, phi, count, list) ;
234 /*
235 --------------------------------------
236 set the vertex weight and increment
237 the total vertex weight and edge count
238 --------------------------------------
239 */
240 vwghts[phi] = v->wght ;
241 totvwght += v->wght ;
242 nedge += count ;
243 }
244 schurGraph->totvwght = totvwght ;
245 schurGraph->nedges = nedge ;
246 schurGraph->totewght = totewght ;
247 /*
248 ------------------------
249 free the working storage
250 ------------------------
251 */
252 IVfree(list) ;
253 IVfree(mark) ;
254 IVfree(rep) ;
255
256 return ; }
257
258 /*--------------------------------------------------------------------*/
259