1 | /* |
---|
2 | * mmd.c |
---|
3 | * |
---|
4 | * ************************************************************** |
---|
5 | * The following C function was developed from a FORTRAN subroutine |
---|
6 | * in SPARSPAK written by Eleanor Chu, Alan George, Joseph Liu |
---|
7 | * and Esmond Ng. |
---|
8 | * |
---|
9 | * The FORTRAN-to-C transformation and modifications such as dynamic |
---|
10 | * memory allocation and deallocation were performed by Chunguang |
---|
11 | * Sun. |
---|
12 | * ************************************************************** |
---|
13 | * |
---|
14 | * Taken from SMMS, George 12/13/94 |
---|
15 | * |
---|
16 | * The meaning of invperm, and perm vectors is different from that |
---|
17 | * in genqmd_ of SparsPak |
---|
18 | * |
---|
19 | * $Id: mmd.c,v 1.1 1998/11/27 17:59:25 karypis Exp $ |
---|
20 | */ |
---|
21 | |
---|
22 | #include <metis.h> |
---|
23 | |
---|
24 | |
---|
25 | /************************************************************************* |
---|
26 | * genmmd -- multiple minimum external degree |
---|
27 | * purpose -- this routine implements the minimum degree |
---|
28 | * algorithm. it makes use of the implicit representation |
---|
29 | * of elimination graphs by quotient graphs, and the notion |
---|
30 | * of indistinguishable nodes. It also implements the modifications |
---|
31 | * by multiple elimination and minimum external degree. |
---|
32 | * Caution -- the adjacency vector adjncy will be destroyed. |
---|
33 | * Input parameters -- |
---|
34 | * neqns -- number of equations. |
---|
35 | * (xadj, adjncy) -- the adjacency structure. |
---|
36 | * delta -- tolerance value for multiple elimination. |
---|
37 | * maxint -- maximum machine representable (short) integer |
---|
38 | * (any smaller estimate will do) for marking nodes. |
---|
39 | * Output parameters -- |
---|
40 | * perm -- the minimum degree ordering. |
---|
41 | * invp -- the inverse of perm. |
---|
42 | * *ncsub -- an upper bound on the number of nonzero subscripts |
---|
43 | * for the compressed storage scheme. |
---|
44 | * Working parameters -- |
---|
45 | * head -- vector for head of degree lists. |
---|
46 | * invp -- used temporarily for degree forward link. |
---|
47 | * perm -- used temporarily for degree backward link. |
---|
48 | * qsize -- vector for size of supernodes. |
---|
49 | * list -- vector for temporary linked lists. |
---|
50 | * marker -- a temporary marker vector. |
---|
51 | * Subroutines used -- mmdelm, mmdint, mmdnum, mmdupd. |
---|
52 | **************************************************************************/ |
---|
53 | void genmmd(int neqns, idxtype *xadj, idxtype *adjncy, idxtype *invp, idxtype *perm, |
---|
54 | int delta, idxtype *head, idxtype *qsize, idxtype *list, idxtype *marker, |
---|
55 | int maxint, int *ncsub) |
---|
56 | { |
---|
57 | int ehead, i, mdeg, mdlmt, mdeg_node, nextmd, num, tag; |
---|
58 | |
---|
59 | if (neqns <= 0) |
---|
60 | return; |
---|
61 | |
---|
62 | /* Adjust from C to Fortran */ |
---|
63 | xadj--; adjncy--; invp--; perm--; head--; qsize--; list--; marker--; |
---|
64 | |
---|
65 | /* initialization for the minimum degree algorithm. */ |
---|
66 | *ncsub = 0; |
---|
67 | mmdint(neqns, xadj, adjncy, head, invp, perm, qsize, list, marker); |
---|
68 | |
---|
69 | /* 'num' counts the number of ordered nodes plus 1. */ |
---|
70 | num = 1; |
---|
71 | |
---|
72 | /* eliminate all isolated nodes. */ |
---|
73 | nextmd = head[1]; |
---|
74 | while (nextmd > 0) { |
---|
75 | mdeg_node = nextmd; |
---|
76 | nextmd = invp[mdeg_node]; |
---|
77 | marker[mdeg_node] = maxint; |
---|
78 | invp[mdeg_node] = -num; |
---|
79 | num = num + 1; |
---|
80 | } |
---|
81 | |
---|
82 | /* search for node of the minimum degree. 'mdeg' is the current */ |
---|
83 | /* minimum degree; 'tag' is used to facilitate marking nodes. */ |
---|
84 | if (num > neqns) |
---|
85 | goto n1000; |
---|
86 | tag = 1; |
---|
87 | head[1] = 0; |
---|
88 | mdeg = 2; |
---|
89 | |
---|
90 | /* infinite loop here ! */ |
---|
91 | while (1) { |
---|
92 | while (head[mdeg] <= 0) |
---|
93 | mdeg++; |
---|
94 | |
---|
95 | /* use value of 'delta' to set up 'mdlmt', which governs */ |
---|
96 | /* when a degree update is to be performed. */ |
---|
97 | mdlmt = mdeg + delta; |
---|
98 | ehead = 0; |
---|
99 | |
---|
100 | n500: |
---|
101 | mdeg_node = head[mdeg]; |
---|
102 | while (mdeg_node <= 0) { |
---|
103 | mdeg++; |
---|
104 | |
---|
105 | if (mdeg > mdlmt) |
---|
106 | goto n900; |
---|
107 | mdeg_node = head[mdeg]; |
---|
108 | }; |
---|
109 | |
---|
110 | /* remove 'mdeg_node' from the degree structure. */ |
---|
111 | nextmd = invp[mdeg_node]; |
---|
112 | head[mdeg] = nextmd; |
---|
113 | if (nextmd > 0) |
---|
114 | perm[nextmd] = -mdeg; |
---|
115 | invp[mdeg_node] = -num; |
---|
116 | *ncsub += mdeg + qsize[mdeg_node] - 2; |
---|
117 | if ((num+qsize[mdeg_node]) > neqns) |
---|
118 | goto n1000; |
---|
119 | |
---|
120 | /* eliminate 'mdeg_node' and perform quotient graph */ |
---|
121 | /* transformation. reset 'tag' value if necessary. */ |
---|
122 | tag++; |
---|
123 | if (tag >= maxint) { |
---|
124 | tag = 1; |
---|
125 | for (i = 1; i <= neqns; i++) |
---|
126 | if (marker[i] < maxint) |
---|
127 | marker[i] = 0; |
---|
128 | }; |
---|
129 | |
---|
130 | mmdelm(mdeg_node, xadj, adjncy, head, invp, perm, qsize, list, marker, maxint, tag); |
---|
131 | |
---|
132 | num += qsize[mdeg_node]; |
---|
133 | list[mdeg_node] = ehead; |
---|
134 | ehead = mdeg_node; |
---|
135 | if (delta >= 0) |
---|
136 | goto n500; |
---|
137 | |
---|
138 | n900: |
---|
139 | /* update degrees of the nodes involved in the */ |
---|
140 | /* minimum degree nodes elimination. */ |
---|
141 | if (num > neqns) |
---|
142 | goto n1000; |
---|
143 | mmdupd( ehead, neqns, xadj, adjncy, delta, &mdeg, head, invp, perm, qsize, list, marker, maxint, &tag); |
---|
144 | }; /* end of -- while ( 1 ) -- */ |
---|
145 | |
---|
146 | n1000: |
---|
147 | mmdnum( neqns, perm, invp, qsize ); |
---|
148 | |
---|
149 | /* Adjust from Fortran back to C*/ |
---|
150 | xadj++; adjncy++; invp++; perm++; head++; qsize++; list++; marker++; |
---|
151 | } |
---|
152 | |
---|
153 | |
---|
154 | /************************************************************************** |
---|
155 | * mmdelm ...... multiple minimum degree elimination |
---|
156 | * Purpose -- This routine eliminates the node mdeg_node of minimum degree |
---|
157 | * from the adjacency structure, which is stored in the quotient |
---|
158 | * graph format. It also transforms the quotient graph representation |
---|
159 | * of the elimination graph. |
---|
160 | * Input parameters -- |
---|
161 | * mdeg_node -- node of minimum degree. |
---|
162 | * maxint -- estimate of maximum representable (short) integer. |
---|
163 | * tag -- tag value. |
---|
164 | * Updated parameters -- |
---|
165 | * (xadj, adjncy) -- updated adjacency structure. |
---|
166 | * (head, forward, backward) -- degree doubly linked structure. |
---|
167 | * qsize -- size of supernode. |
---|
168 | * marker -- marker vector. |
---|
169 | * list -- temporary linked list of eliminated nabors. |
---|
170 | ***************************************************************************/ |
---|
171 | void mmdelm(int mdeg_node, idxtype *xadj, idxtype *adjncy, idxtype *head, idxtype *forward, |
---|
172 | idxtype *backward, idxtype *qsize, idxtype *list, idxtype *marker, int maxint,int tag) |
---|
173 | { |
---|
174 | int element, i, istop, istart, j, |
---|
175 | jstop, jstart, link, |
---|
176 | nabor, node, npv, nqnbrs, nxnode, |
---|
177 | pvnode, rlmt, rloc, rnode, xqnbr; |
---|
178 | |
---|
179 | /* find the reachable set of 'mdeg_node' and */ |
---|
180 | /* place it in the data structure. */ |
---|
181 | marker[mdeg_node] = tag; |
---|
182 | istart = xadj[mdeg_node]; |
---|
183 | istop = xadj[mdeg_node+1] - 1; |
---|
184 | |
---|
185 | /* 'element' points to the beginning of the list of */ |
---|
186 | /* eliminated nabors of 'mdeg_node', and 'rloc' gives the */ |
---|
187 | /* storage location for the next reachable node. */ |
---|
188 | element = 0; |
---|
189 | rloc = istart; |
---|
190 | rlmt = istop; |
---|
191 | for ( i = istart; i <= istop; i++ ) { |
---|
192 | nabor = adjncy[i]; |
---|
193 | if ( nabor == 0 ) break; |
---|
194 | if ( marker[nabor] < tag ) { |
---|
195 | marker[nabor] = tag; |
---|
196 | if ( forward[nabor] < 0 ) { |
---|
197 | list[nabor] = element; |
---|
198 | element = nabor; |
---|
199 | } else { |
---|
200 | adjncy[rloc] = nabor; |
---|
201 | rloc++; |
---|
202 | }; |
---|
203 | }; /* end of -- if -- */ |
---|
204 | }; /* end of -- for -- */ |
---|
205 | |
---|
206 | /* merge with reachable nodes from generalized elements. */ |
---|
207 | while ( element > 0 ) { |
---|
208 | adjncy[rlmt] = -element; |
---|
209 | link = element; |
---|
210 | |
---|
211 | n400: |
---|
212 | jstart = xadj[link]; |
---|
213 | jstop = xadj[link+1] - 1; |
---|
214 | for ( j = jstart; j <= jstop; j++ ) { |
---|
215 | node = adjncy[j]; |
---|
216 | link = -node; |
---|
217 | if ( node < 0 ) goto n400; |
---|
218 | if ( node == 0 ) break; |
---|
219 | if ((marker[node]<tag)&&(forward[node]>=0)) { |
---|
220 | marker[node] = tag; |
---|
221 | /*use storage from eliminated nodes if necessary.*/ |
---|
222 | while ( rloc >= rlmt ) { |
---|
223 | link = -adjncy[rlmt]; |
---|
224 | rloc = xadj[link]; |
---|
225 | rlmt = xadj[link+1] - 1; |
---|
226 | }; |
---|
227 | adjncy[rloc] = node; |
---|
228 | rloc++; |
---|
229 | }; |
---|
230 | }; /* end of -- for ( j = jstart; -- */ |
---|
231 | element = list[element]; |
---|
232 | }; /* end of -- while ( element > 0 ) -- */ |
---|
233 | if ( rloc <= rlmt ) adjncy[rloc] = 0; |
---|
234 | /* for each node in the reachable set, do the following. */ |
---|
235 | link = mdeg_node; |
---|
236 | |
---|
237 | n1100: |
---|
238 | istart = xadj[link]; |
---|
239 | istop = xadj[link+1] - 1; |
---|
240 | for ( i = istart; i <= istop; i++ ) { |
---|
241 | rnode = adjncy[i]; |
---|
242 | link = -rnode; |
---|
243 | if ( rnode < 0 ) goto n1100; |
---|
244 | if ( rnode == 0 ) return; |
---|
245 | |
---|
246 | /* 'rnode' is in the degree list structure. */ |
---|
247 | pvnode = backward[rnode]; |
---|
248 | if (( pvnode != 0 ) && ( pvnode != (-maxint) )) { |
---|
249 | /* then remove 'rnode' from the structure. */ |
---|
250 | nxnode = forward[rnode]; |
---|
251 | if ( nxnode > 0 ) backward[nxnode] = pvnode; |
---|
252 | if ( pvnode > 0 ) forward[pvnode] = nxnode; |
---|
253 | npv = -pvnode; |
---|
254 | if ( pvnode < 0 ) head[npv] = nxnode; |
---|
255 | }; |
---|
256 | |
---|
257 | /* purge inactive quotient nabors of 'rnode'. */ |
---|
258 | jstart = xadj[rnode]; |
---|
259 | jstop = xadj[rnode+1] - 1; |
---|
260 | xqnbr = jstart; |
---|
261 | for ( j = jstart; j <= jstop; j++ ) { |
---|
262 | nabor = adjncy[j]; |
---|
263 | if ( nabor == 0 ) break; |
---|
264 | if ( marker[nabor] < tag ) { |
---|
265 | adjncy[xqnbr] = nabor; |
---|
266 | xqnbr++; |
---|
267 | }; |
---|
268 | }; |
---|
269 | |
---|
270 | /* no active nabor after the purging. */ |
---|
271 | nqnbrs = xqnbr - jstart; |
---|
272 | if ( nqnbrs <= 0 ) { |
---|
273 | /* merge 'rnode' with 'mdeg_node'. */ |
---|
274 | qsize[mdeg_node] += qsize[rnode]; |
---|
275 | qsize[rnode] = 0; |
---|
276 | marker[rnode] = maxint; |
---|
277 | forward[rnode] = -mdeg_node; |
---|
278 | backward[rnode] = -maxint; |
---|
279 | } else { |
---|
280 | /* flag 'rnode' for degree update, and */ |
---|
281 | /* add 'mdeg_node' as a nabor of 'rnode'. */ |
---|
282 | forward[rnode] = nqnbrs + 1; |
---|
283 | backward[rnode] = 0; |
---|
284 | adjncy[xqnbr] = mdeg_node; |
---|
285 | xqnbr++; |
---|
286 | if ( xqnbr <= jstop ) adjncy[xqnbr] = 0; |
---|
287 | }; |
---|
288 | }; /* end of -- for ( i = istart; -- */ |
---|
289 | return; |
---|
290 | } |
---|
291 | |
---|
292 | /*************************************************************************** |
---|
293 | * mmdint ---- mult minimum degree initialization |
---|
294 | * purpose -- this routine performs initialization for the |
---|
295 | * multiple elimination version of the minimum degree algorithm. |
---|
296 | * input parameters -- |
---|
297 | * neqns -- number of equations. |
---|
298 | * (xadj, adjncy) -- adjacency structure. |
---|
299 | * output parameters -- |
---|
300 | * (head, dfrow, backward) -- degree doubly linked structure. |
---|
301 | * qsize -- size of supernode ( initialized to one). |
---|
302 | * list -- linked list. |
---|
303 | * marker -- marker vector. |
---|
304 | ****************************************************************************/ |
---|
305 | int mmdint(int neqns, idxtype *xadj, idxtype *adjncy, idxtype *head, idxtype *forward, |
---|
306 | idxtype *backward, idxtype *qsize, idxtype *list, idxtype *marker) |
---|
307 | { |
---|
308 | int fnode, ndeg, node; |
---|
309 | |
---|
310 | for ( node = 1; node <= neqns; node++ ) { |
---|
311 | head[node] = 0; |
---|
312 | qsize[node] = 1; |
---|
313 | marker[node] = 0; |
---|
314 | list[node] = 0; |
---|
315 | }; |
---|
316 | |
---|
317 | /* initialize the degree doubly linked lists. */ |
---|
318 | for ( node = 1; node <= neqns; node++ ) { |
---|
319 | ndeg = xadj[node+1] - xadj[node]/* + 1*/; /* george */ |
---|
320 | if (ndeg == 0) |
---|
321 | ndeg = 1; |
---|
322 | fnode = head[ndeg]; |
---|
323 | forward[node] = fnode; |
---|
324 | head[ndeg] = node; |
---|
325 | if ( fnode > 0 ) backward[fnode] = node; |
---|
326 | backward[node] = -ndeg; |
---|
327 | }; |
---|
328 | return 0; |
---|
329 | } |
---|
330 | |
---|
331 | /**************************************************************************** |
---|
332 | * mmdnum --- multi minimum degree numbering |
---|
333 | * purpose -- this routine performs the final step in producing |
---|
334 | * the permutation and inverse permutation vectors in the |
---|
335 | * multiple elimination version of the minimum degree |
---|
336 | * ordering algorithm. |
---|
337 | * input parameters -- |
---|
338 | * neqns -- number of equations. |
---|
339 | * qsize -- size of supernodes at elimination. |
---|
340 | * updated parameters -- |
---|
341 | * invp -- inverse permutation vector. on input, |
---|
342 | * if qsize[node] = 0, then node has been merged |
---|
343 | * into the node -invp[node]; otherwise, |
---|
344 | * -invp[node] is its inverse labelling. |
---|
345 | * output parameters -- |
---|
346 | * perm -- the permutation vector. |
---|
347 | ****************************************************************************/ |
---|
348 | void mmdnum(int neqns, idxtype *perm, idxtype *invp, idxtype *qsize) |
---|
349 | { |
---|
350 | int father, nextf, node, nqsize, num, root; |
---|
351 | |
---|
352 | for ( node = 1; node <= neqns; node++ ) { |
---|
353 | nqsize = qsize[node]; |
---|
354 | if ( nqsize <= 0 ) perm[node] = invp[node]; |
---|
355 | if ( nqsize > 0 ) perm[node] = -invp[node]; |
---|
356 | }; |
---|
357 | |
---|
358 | /* for each node which has been merged, do the following. */ |
---|
359 | for ( node = 1; node <= neqns; node++ ) { |
---|
360 | if ( perm[node] <= 0 ) { |
---|
361 | |
---|
362 | /* trace the merged tree until one which has not */ |
---|
363 | /* been merged, call it root. */ |
---|
364 | father = node; |
---|
365 | while ( perm[father] <= 0 ) |
---|
366 | father = - perm[father]; |
---|
367 | |
---|
368 | /* number node after root. */ |
---|
369 | root = father; |
---|
370 | num = perm[root] + 1; |
---|
371 | invp[node] = -num; |
---|
372 | perm[root] = num; |
---|
373 | |
---|
374 | /* shorten the merged tree. */ |
---|
375 | father = node; |
---|
376 | nextf = - perm[father]; |
---|
377 | while ( nextf > 0 ) { |
---|
378 | perm[father] = -root; |
---|
379 | father = nextf; |
---|
380 | nextf = -perm[father]; |
---|
381 | }; |
---|
382 | }; /* end of -- if ( perm[node] <= 0 ) -- */ |
---|
383 | }; /* end of -- for ( node = 1; -- */ |
---|
384 | |
---|
385 | /* ready to compute perm. */ |
---|
386 | for ( node = 1; node <= neqns; node++ ) { |
---|
387 | num = -invp[node]; |
---|
388 | invp[node] = num; |
---|
389 | perm[num] = node; |
---|
390 | }; |
---|
391 | return; |
---|
392 | } |
---|
393 | |
---|
394 | /**************************************************************************** |
---|
395 | * mmdupd ---- multiple minimum degree update |
---|
396 | * purpose -- this routine updates the degrees of nodes after a |
---|
397 | * multiple elimination step. |
---|
398 | * input parameters -- |
---|
399 | * ehead -- the beginning of the list of eliminated nodes |
---|
400 | * (i.e., newly formed elements). |
---|
401 | * neqns -- number of equations. |
---|
402 | * (xadj, adjncy) -- adjacency structure. |
---|
403 | * delta -- tolerance value for multiple elimination. |
---|
404 | * maxint -- maximum machine representable (short) integer. |
---|
405 | * updated parameters -- |
---|
406 | * mdeg -- new minimum degree after degree update. |
---|
407 | * (head, forward, backward) -- degree doubly linked structure. |
---|
408 | * qsize -- size of supernode. |
---|
409 | * list -- marker vector for degree update. |
---|
410 | * *tag -- tag value. |
---|
411 | ****************************************************************************/ |
---|
412 | void mmdupd(int ehead, int neqns, idxtype *xadj, idxtype *adjncy, int delta, int *mdeg, |
---|
413 | idxtype *head, idxtype *forward, idxtype *backward, idxtype *qsize, idxtype *list, |
---|
414 | idxtype *marker, int maxint,int *tag) |
---|
415 | { |
---|
416 | int deg, deg0, element, enode, fnode, i, iq2, istop, |
---|
417 | istart, j, jstop, jstart, link, mdeg0, mtag, nabor, |
---|
418 | node, q2head, qxhead; |
---|
419 | |
---|
420 | mdeg0 = *mdeg + delta; |
---|
421 | element = ehead; |
---|
422 | |
---|
423 | n100: |
---|
424 | if ( element <= 0 ) return; |
---|
425 | |
---|
426 | /* for each of the newly formed element, do the following. */ |
---|
427 | /* reset tag value if necessary. */ |
---|
428 | mtag = *tag + mdeg0; |
---|
429 | if ( mtag >= maxint ) { |
---|
430 | *tag = 1; |
---|
431 | for ( i = 1; i <= neqns; i++ ) |
---|
432 | if ( marker[i] < maxint ) marker[i] = 0; |
---|
433 | mtag = *tag + mdeg0; |
---|
434 | }; |
---|
435 | |
---|
436 | /* create two linked lists from nodes associated with 'element': */ |
---|
437 | /* one with two nabors (q2head) in the adjacency structure, and the*/ |
---|
438 | /* other with more than two nabors (qxhead). also compute 'deg0',*/ |
---|
439 | /* number of nodes in this element. */ |
---|
440 | q2head = 0; |
---|
441 | qxhead = 0; |
---|
442 | deg0 = 0; |
---|
443 | link =element; |
---|
444 | |
---|
445 | n400: |
---|
446 | istart = xadj[link]; |
---|
447 | istop = xadj[link+1] - 1; |
---|
448 | for ( i = istart; i <= istop; i++ ) { |
---|
449 | enode = adjncy[i]; |
---|
450 | link = -enode; |
---|
451 | if ( enode < 0 ) goto n400; |
---|
452 | if ( enode == 0 ) break; |
---|
453 | if ( qsize[enode] != 0 ) { |
---|
454 | deg0 += qsize[enode]; |
---|
455 | marker[enode] = mtag; |
---|
456 | |
---|
457 | /*'enode' requires a degree update*/ |
---|
458 | if ( backward[enode] == 0 ) { |
---|
459 | /* place either in qxhead or q2head list. */ |
---|
460 | if ( forward[enode] != 2 ) { |
---|
461 | list[enode] = qxhead; |
---|
462 | qxhead = enode; |
---|
463 | } else { |
---|
464 | list[enode] = q2head; |
---|
465 | q2head = enode; |
---|
466 | }; |
---|
467 | }; |
---|
468 | }; /* enf of -- if ( qsize[enode] != 0 ) -- */ |
---|
469 | }; /* end of -- for ( i = istart; -- */ |
---|
470 | |
---|
471 | /* for each node in q2 list, do the following. */ |
---|
472 | enode = q2head; |
---|
473 | iq2 = 1; |
---|
474 | |
---|
475 | n900: |
---|
476 | if ( enode <= 0 ) goto n1500; |
---|
477 | if ( backward[enode] != 0 ) goto n2200; |
---|
478 | (*tag)++; |
---|
479 | deg = deg0; |
---|
480 | |
---|
481 | /* identify the other adjacent element nabor. */ |
---|
482 | istart = xadj[enode]; |
---|
483 | nabor = adjncy[istart]; |
---|
484 | if ( nabor == element ) nabor = adjncy[istart+1]; |
---|
485 | link = nabor; |
---|
486 | if ( forward[nabor] >= 0 ) { |
---|
487 | /* nabor is uneliminated, increase degree count. */ |
---|
488 | deg += qsize[nabor]; |
---|
489 | goto n2100; |
---|
490 | }; |
---|
491 | |
---|
492 | /* the nabor is eliminated. for each node in the 2nd element */ |
---|
493 | /* do the following. */ |
---|
494 | n1000: |
---|
495 | istart = xadj[link]; |
---|
496 | istop = xadj[link+1] - 1; |
---|
497 | for ( i = istart; i <= istop; i++ ) { |
---|
498 | node = adjncy[i]; |
---|
499 | link = -node; |
---|
500 | if ( node != enode ) { |
---|
501 | if ( node < 0 ) goto n1000; |
---|
502 | if ( node == 0 ) goto n2100; |
---|
503 | if ( qsize[node] != 0 ) { |
---|
504 | if ( marker[node] < *tag ) { |
---|
505 | /* 'node' is not yet considered. */ |
---|
506 | marker[node] = *tag; |
---|
507 | deg += qsize[node]; |
---|
508 | } else { |
---|
509 | if ( backward[node] == 0 ) { |
---|
510 | if ( forward[node] == 2 ) { |
---|
511 | /* 'node' is indistinguishable from 'enode'.*/ |
---|
512 | /* merge them into a new supernode. */ |
---|
513 | qsize[enode] += qsize[node]; |
---|
514 | qsize[node] = 0; |
---|
515 | marker[node] = maxint; |
---|
516 | forward[node] = -enode; |
---|
517 | backward[node] = -maxint; |
---|
518 | } else { |
---|
519 | /* 'node' is outmacthed by 'enode' */ |
---|
520 | if (backward[node]==0) backward[node] = -maxint; |
---|
521 | }; |
---|
522 | }; /* end of -- if ( backward[node] == 0 ) -- */ |
---|
523 | }; /* end of -- if ( marker[node] < *tag ) -- */ |
---|
524 | }; /* end of -- if ( qsize[node] != 0 ) -- */ |
---|
525 | }; /* end of -- if ( node != enode ) -- */ |
---|
526 | }; /* end of -- for ( i = istart; -- */ |
---|
527 | goto n2100; |
---|
528 | |
---|
529 | n1500: |
---|
530 | /* for each 'enode' in the 'qx' list, do the following. */ |
---|
531 | enode = qxhead; |
---|
532 | iq2 = 0; |
---|
533 | |
---|
534 | n1600: if ( enode <= 0 ) goto n2300; |
---|
535 | if ( backward[enode] != 0 ) goto n2200; |
---|
536 | (*tag)++; |
---|
537 | deg = deg0; |
---|
538 | |
---|
539 | /*for each unmarked nabor of 'enode', do the following.*/ |
---|
540 | istart = xadj[enode]; |
---|
541 | istop = xadj[enode+1] - 1; |
---|
542 | for ( i = istart; i <= istop; i++ ) { |
---|
543 | nabor = adjncy[i]; |
---|
544 | if ( nabor == 0 ) break; |
---|
545 | if ( marker[nabor] < *tag ) { |
---|
546 | marker[nabor] = *tag; |
---|
547 | link = nabor; |
---|
548 | if ( forward[nabor] >= 0 ) |
---|
549 | /*if uneliminated, include it in deg count.*/ |
---|
550 | deg += qsize[nabor]; |
---|
551 | else { |
---|
552 | n1700: |
---|
553 | /* if eliminated, include unmarked nodes in this*/ |
---|
554 | /* element into the degree count. */ |
---|
555 | jstart = xadj[link]; |
---|
556 | jstop = xadj[link+1] - 1; |
---|
557 | for ( j = jstart; j <= jstop; j++ ) { |
---|
558 | node = adjncy[j]; |
---|
559 | link = -node; |
---|
560 | if ( node < 0 ) goto n1700; |
---|
561 | if ( node == 0 ) break; |
---|
562 | if ( marker[node] < *tag ) { |
---|
563 | marker[node] = *tag; |
---|
564 | deg += qsize[node]; |
---|
565 | }; |
---|
566 | }; /* end of -- for ( j = jstart; -- */ |
---|
567 | }; /* end of -- if ( forward[nabor] >= 0 ) -- */ |
---|
568 | }; /* end of -- if ( marker[nabor] < *tag ) -- */ |
---|
569 | }; /* end of -- for ( i = istart; -- */ |
---|
570 | |
---|
571 | n2100: |
---|
572 | /* update external degree of 'enode' in degree structure, */ |
---|
573 | /* and '*mdeg' if necessary. */ |
---|
574 | deg = deg - qsize[enode] + 1; |
---|
575 | fnode = head[deg]; |
---|
576 | forward[enode] = fnode; |
---|
577 | backward[enode] = -deg; |
---|
578 | if ( fnode > 0 ) backward[fnode] = enode; |
---|
579 | head[deg] = enode; |
---|
580 | if ( deg < *mdeg ) *mdeg = deg; |
---|
581 | |
---|
582 | n2200: |
---|
583 | /* get next enode in current element. */ |
---|
584 | enode = list[enode]; |
---|
585 | if ( iq2 == 1 ) goto n900; |
---|
586 | goto n1600; |
---|
587 | |
---|
588 | n2300: |
---|
589 | /* get next element in the list. */ |
---|
590 | *tag = mtag; |
---|
591 | element = list[element]; |
---|
592 | goto n100; |
---|
593 | } |
---|