1 /* fullAdj.c */
2
3 #include "../InpMtx.h"
4
5 #define MYDEBUG 0
6
7 /*--------------------------------------------------------------------*/
8 /*
9 -------------------------------------------------------------
10 purpose -- to return the full, symmetric adjacency IVL object
11 for the graph of A + A^T
12
13 created -- 98jan28, cca
14 -------------------------------------------------------------
15 */
16 IVL *
InpMtx_fullAdjacency(InpMtx * inpmtx)17 InpMtx_fullAdjacency (
18 InpMtx *inpmtx
19 ) {
20 int count, ii, jvtx, jsize, kvtx, nvtx ;
21 int *jind, *list, *mark ;
22 IP *baseIP, *freeIP, *ip ;
23 IP **head ;
24 IVL *adjIVL ;
25 /*
26 ---------------
27 check the input
28 ---------------
29 */
30 if ( inpmtx == NULL ) {
31 fprintf(stderr, "\n fatal error in InpMtx_fullAdjacency(%p)"
32 "\n NULL input\n", inpmtx) ;
33 exit(-1) ;
34 }
35 /*
36 ----------------------
37 check for empty matrix
38 ----------------------
39 */
40 if ( inpmtx->nent == 0 ) {
41 return(NULL) ;
42 }
43 /*
44 -------------------------------------------------
45 check for invalid coordinate type or storage mode
46 -------------------------------------------------
47 */
48 if ( ! (INPMTX_IS_BY_ROWS(inpmtx) || INPMTX_IS_BY_COLUMNS(inpmtx)) ) {
49 InpMtx_changeCoordType(inpmtx, INPMTX_BY_ROWS) ;
50 }
51 if ( ! INPMTX_IS_BY_VECTORS(inpmtx) ) {
52 InpMtx_changeStorageMode(inpmtx, INPMTX_BY_VECTORS) ;
53 }
54 nvtx = 1 + IV_max(&inpmtx->ivec1IV) ;
55 if ( nvtx < (count = 1 + IV_max(&inpmtx->ivec2IV)) ) {
56 nvtx = count ;
57 }
58 /*
59 -------------------------
60 initialize the IVL object
61 -------------------------
62 */
63 adjIVL = IVL_new() ;
64 IVL_init1(adjIVL, IVL_CHUNKED, nvtx) ;
65 list = IVinit(nvtx, -1) ;
66 mark = IVinit(nvtx, -1) ;
67 ALLOCATE(head, struct _IP *, nvtx) ;
68 baseIP = freeIP = NULL ;
69 /*
70 ---------------------------
71 initially link the vertices
72 ---------------------------
73 */
74 for ( jvtx = 0 ; jvtx < nvtx ; jvtx++ ) {
75 head[jvtx] = NULL ;
76 }
77 for ( jvtx = 0 ; jvtx < nvtx ; jvtx++ ) {
78 InpMtx_vector(inpmtx, jvtx, &jsize, &jind) ;
79 if ( jsize > 0 ) {
80 for ( ii = 0 ; ii < jsize ; ii++ ) {
81 if ( (kvtx = jind[ii]) < jvtx ) {
82 /*
83 -----------------
84 link jvtx to kvtx
85 -----------------
86 */
87 if ( (ip = freeIP) == NULL ) {
88 ip = IP_init(nvtx+1, IP_FORWARD) ;
89 ip->next = baseIP ; baseIP = ip ;
90 freeIP = baseIP + 1 ;
91 ip = freeIP ;
92 }
93 freeIP = ip->next ;
94 ip->val = jvtx ;
95 ip->next = head[kvtx] ;
96 head[kvtx] = ip ;
97 #if MYDEBUG > 0
98 fprintf(stdout, "\n linking %d to %d, %p to %p",
99 jvtx, kvtx, ip, ip->next) ;
100 fflush(stdout) ;
101 #endif
102 }
103 }
104 }
105 }
106 for ( jvtx = 0 ; jvtx < nvtx ; jvtx++ ) {
107 #if MYDEBUG > 0
108 fprintf(stdout, "\n\n working on vertex %d :", jvtx) ;
109 fflush(stdout) ;
110 #endif
111 list[0] = jvtx ;
112 #if MYDEBUG > 0
113 fprintf(stdout, "\n 0. adding %d", jvtx) ;
114 fflush(stdout) ;
115 #endif
116 mark[jvtx] = jvtx ;
117 count = 1 ;
118 /*
119 -------------------------------------
120 check previous rows that contain jvtx
121 -------------------------------------
122 */
123 while ( (ip = head[jvtx]) != NULL ) {
124 kvtx = ip->val ;
125 #if MYDEBUG > 0
126 fprintf(stdout, "\n 1. kvtx %d", kvtx) ;
127 fflush(stdout) ;
128 #endif
129 if ( mark[kvtx] != jvtx ) {
130 mark[kvtx] = jvtx ;
131 list[count++] = kvtx ;
132 #if MYDEBUG > 0
133 fprintf(stdout, ", adding") ;
134 fflush(stdout) ;
135 #endif
136 }
137 head[jvtx] = ip->next ;
138 ip->next = freeIP ;
139 freeIP = ip ;
140 }
141 /*
142 ----------------------------
143 get the indices for row jvtx
144 ----------------------------
145 */
146 InpMtx_vector(inpmtx, jvtx, &jsize, &jind) ;
147 if ( jsize > 0 ) {
148 /*
149 ----------------------------
150 add row indices for row jvtx
151 ----------------------------
152 */
153 #if MYDEBUG > 0
154 fprintf(stdout, "\n InpMtx row %d :", jvtx) ;
155 IVfprintf(stdout, jsize, jind) ;
156 fflush(stdout) ;
157 #endif
158 for ( ii = 0 ; ii < jsize ; ii++ ) {
159 kvtx = jind[ii] ;
160 if ( mark[kvtx] != jvtx ) {
161 mark[kvtx] = jvtx ;
162 list[count++] = kvtx ;
163 #if MYDEBUG > 0
164 fprintf(stdout, "\n 2. adding %d", kvtx) ;
165 fflush(stdout) ;
166 #endif
167 }
168 if ( kvtx > jvtx ) {
169 /*
170 -----------------
171 link jvtx to kvtx
172 -----------------
173 */
174 if ( (ip = freeIP) == NULL ) {
175 ip = IP_init(nvtx+1, IP_FORWARD) ;
176 ip->next = baseIP ; baseIP = ip ;
177 freeIP = baseIP + 1 ;
178 ip = freeIP ;
179 }
180 freeIP = ip->next ;
181 ip->val = jvtx ;
182 ip->next = head[kvtx] ;
183 head[kvtx] = ip ;
184 #if MYDEBUG > 0
185 fprintf(stdout, "\n linking %d to %d, %p to %p",
186 jvtx, kvtx, ip, ip->next) ;
187 fflush(stdout) ;
188 #endif
189 }
190 }
191 }
192 /*
193 ------------------------------------------------
194 list is complete, sort and insert into adjacency
195 ------------------------------------------------
196 */
197 IVqsortUp(count, list) ;
198 IVL_setList(adjIVL, jvtx, count, list) ;
199 }
200 /*
201 ------------------------
202 free the working storage
203 ------------------------
204 */
205 IVfree(list) ;
206 IVfree(mark) ;
207 FREE(head) ;
208 while ( (ip = baseIP) != NULL ) {
209 baseIP = baseIP->next ;
210 IP_free(ip) ;
211 }
212 return(adjIVL) ; }
213
214 /*--------------------------------------------------------------------*/
215 /*
216 -------------------------------------------------------------
217 purpose -- to return the full, symmetric adjacency IVL object
218 for the graph of (A + B) + (A + B)^T
219
220 created -- 97nov05, cca
221 -------------------------------------------------------------
222 */
223 IVL *
InpMtx_fullAdjacency2(InpMtx * inpmtxA,InpMtx * inpmtxB)224 InpMtx_fullAdjacency2 (
225 InpMtx *inpmtxA,
226 InpMtx *inpmtxB
227 ) {
228 int count, ierr, ii, jvtx, jsize, kvtx, nvtx ;
229 int *jind, *list, *mark ;
230 IP *baseIP, *freeIP, *ip ;
231 IP **head ;
232 IVL *adjIVL ;
233 /*
234 ---------------
235 check the input
236 ---------------
237 */
238 if ( inpmtxA == NULL && inpmtxB == NULL ) {
239 fprintf(stderr, "\n fatal error in InpMtx_fullAdjacency2(%p,%p)"
240 "\n both input matrices are NULL\n", inpmtxA, inpmtxB) ;
241 exit(-1) ;
242 }
243 /*
244 ------------------------------
245 cases where one matrix is NULL
246 ------------------------------
247 */
248 if ( inpmtxA == NULL ) {
249 adjIVL = InpMtx_fullAdjacency(inpmtxB) ;
250 return(adjIVL) ;
251 } else if ( inpmtxB == NULL ) {
252 adjIVL = InpMtx_fullAdjacency(inpmtxA) ;
253 return(adjIVL) ;
254 }
255 /*
256 -------------------------------------------------
257 check for invalid coordinate type or storage mode
258 -------------------------------------------------
259 */
260 if ( ! (INPMTX_IS_BY_ROWS(inpmtxA) || INPMTX_IS_BY_COLUMNS(inpmtxA)) ) {
261 InpMtx_changeCoordType(inpmtxA, INPMTX_BY_ROWS) ;
262 }
263 if ( ! INPMTX_IS_BY_VECTORS(inpmtxA) ) {
264 InpMtx_changeStorageMode(inpmtxA, INPMTX_BY_VECTORS) ;
265 }
266 if ( ! (INPMTX_IS_BY_ROWS(inpmtxB) || INPMTX_IS_BY_COLUMNS(inpmtxB)) ) {
267 InpMtx_changeCoordType(inpmtxB, INPMTX_BY_ROWS) ;
268 }
269 if ( ! INPMTX_IS_BY_VECTORS(inpmtxB) ) {
270 InpMtx_changeStorageMode(inpmtxB, INPMTX_BY_VECTORS) ;
271 }
272 nvtx = 1 + IV_max(&inpmtxA->ivec1IV) ;
273 if ( nvtx < (count = 1 + IV_max(&inpmtxA->ivec2IV)) ) {
274 nvtx = count ;
275 }
276 if ( nvtx < (count = 1 + IV_max(&inpmtxB->ivec1IV)) ) {
277 nvtx = count ;
278 }
279 if ( nvtx < (count = 1 + IV_max(&inpmtxB->ivec2IV)) ) {
280 nvtx = count ;
281 }
282 /*
283 -------------------------
284 initialize the IVL object
285 -------------------------
286 */
287 adjIVL = IVL_new() ;
288 IVL_init1(adjIVL, IVL_CHUNKED, nvtx) ;
289 /*
290 ------------------------------
291 initialize the working storage
292 ------------------------------
293 */
294 list = IVinit(nvtx, -1) ;
295 mark = IVinit(nvtx, -1) ;
296 ALLOCATE(head, struct _IP *, nvtx) ;
297 baseIP = freeIP = NULL ;
298 /*
299 ---------------------------
300 initially link the vertices
301 ---------------------------
302 */
303 for ( jvtx = 0 ; jvtx < nvtx ; jvtx++ ) {
304 head[jvtx] = NULL ;
305 }
306 for ( jvtx = 0 ; jvtx < nvtx ; jvtx++ ) {
307 InpMtx_vector(inpmtxA, jvtx, &jsize, &jind) ;
308 if ( jsize > 0 ) {
309 for ( ii = 0 ; ii < jsize ; ii++ ) {
310 if ( (kvtx = jind[ii]) < jvtx ) {
311 /*
312 -----------------
313 link jvtx to kvtx
314 -----------------
315 */
316 if ( (ip = freeIP) == NULL ) {
317 ip = IP_init(nvtx+1, IP_FORWARD) ;
318 ip->next = baseIP ; baseIP = ip ;
319 freeIP = baseIP + 1 ;
320 ip = freeIP ;
321 }
322 freeIP = ip->next ;
323 ip->val = jvtx ;
324 ip->next = head[kvtx] ;
325 head[kvtx] = ip ;
326 #if MYDEBUG > 0
327 fprintf(stdout, "\n linking %d to %d, %p to %p",
328 jvtx, kvtx, ip, ip->next) ;
329 fflush(stdout) ;
330 #endif
331 }
332 }
333 }
334 InpMtx_vector(inpmtxB, jvtx, &jsize, &jind) ;
335 if ( jsize > 0 ) {
336 for ( ii = 0 ; ii < jsize ; ii++ ) {
337 if ( (kvtx = jind[ii]) < jvtx ) {
338 /*
339 -----------------
340 link jvtx to kvtx
341 -----------------
342 */
343 if ( (ip = freeIP) == NULL ) {
344 ip = IP_init(nvtx+1, IP_FORWARD) ;
345 ip->next = baseIP ; baseIP = ip ;
346 freeIP = baseIP + 1 ;
347 ip = freeIP ;
348 }
349 freeIP = ip->next ;
350 ip->val = jvtx ;
351 ip->next = head[kvtx] ;
352 head[kvtx] = ip ;
353 #if MYDEBUG > 0
354 fprintf(stdout, "\n linking %d to %d, %p to %p",
355 jvtx, kvtx, ip, ip->next) ;
356 fflush(stdout) ;
357 #endif
358 }
359 }
360 }
361 }
362 for ( jvtx = 0 ; jvtx < nvtx ; jvtx++ ) {
363 #if MYDEBUG > 0
364 fprintf(stdout, "\n vertex %d :", jvtx) ;
365 fflush(stdout) ;
366 #endif
367 list[0] = jvtx ;
368 #if MYDEBUG > 0
369 fprintf(stdout, "\n 0. adding %d", jvtx) ;
370 fflush(stdout) ;
371 #endif
372 mark[jvtx] = jvtx ;
373 count = 1 ;
374 /*
375 -------------------------------------
376 check previous rows that contain jvtx
377 -------------------------------------
378 */
379 while ( (ip = head[jvtx]) != NULL ) {
380 kvtx = ip->val ;
381 #if MYDEBUG > 0
382 fprintf(stdout, "\n 1. kvtx %d", kvtx) ;
383 fflush(stdout) ;
384 #endif
385 if ( mark[kvtx] != jvtx ) {
386 mark[kvtx] = jvtx ;
387 list[count++] = kvtx ;
388 #if MYDEBUG > 0
389 fprintf(stdout, ", adding") ;
390 fflush(stdout) ;
391 #endif
392 }
393 head[jvtx] = ip->next ;
394 ip->next = freeIP ;
395 freeIP = ip ;
396 }
397 /*
398 ----------------------------
399 get the indices for row jvtx
400 ----------------------------
401 */
402 InpMtx_vector(inpmtxA, jvtx, &jsize, &jind) ;
403 if ( jsize > 0 ) {
404 /*
405 ----------------------------
406 add row indices for row jvtx
407 ----------------------------
408 */
409 #if MYDEBUG > 0
410 fprintf(stdout, "\n InpMtx row %d :", jvtx) ;
411 IVfprintf(stdout, jsize, jind) ;
412 fflush(stdout) ;
413 #endif
414 for ( ii = 0 ; ii < jsize ; ii++ ) {
415 kvtx = jind[ii] ;
416 if ( mark[kvtx] != jvtx ) {
417 mark[kvtx] = jvtx ;
418 list[count++] = kvtx ;
419 #if MYDEBUG > 0
420 fprintf(stdout, "\n 2. adding %d", kvtx) ;
421 fflush(stdout) ;
422 #endif
423 }
424 if ( kvtx > jvtx ) {
425 /*
426 -----------------
427 link jvtx to kvtx
428 -----------------
429 */
430 if ( (ip = freeIP) == NULL ) {
431 ip = IP_init(nvtx+1, IP_FORWARD) ;
432 ip->next = baseIP ; baseIP = ip ;
433 freeIP = baseIP + 1 ;
434 ip = freeIP ;
435 }
436 freeIP = ip->next ;
437 ip->val = jvtx ;
438 ip->next = head[kvtx] ;
439 head[kvtx] = ip ;
440 #if MYDEBUG > 0
441 fprintf(stdout, "\n linking %d to %d, %p to %p",
442 jvtx, kvtx, ip, ip->next) ;
443 fflush(stdout) ;
444 #endif
445 }
446 }
447 }
448 InpMtx_vector(inpmtxB, jvtx, &jsize, &jind) ;
449 if ( jsize > 0 ) {
450 /*
451 ----------------------------
452 add row indices for row jvtx
453 ----------------------------
454 */
455 #if MYDEBUG > 0
456 fprintf(stdout, "\n InpMtx row %d :", jvtx) ;
457 IVfprintf(stdout, jsize, jind) ;
458 fflush(stdout) ;
459 #endif
460 for ( ii = 0 ; ii < jsize ; ii++ ) {
461 kvtx = jind[ii] ;
462 if ( mark[kvtx] != jvtx ) {
463 mark[kvtx] = jvtx ;
464 list[count++] = kvtx ;
465 #if MYDEBUG > 0
466 fprintf(stdout, "\n 2. adding %d", kvtx) ;
467 fflush(stdout) ;
468 #endif
469 }
470 if ( kvtx > jvtx ) {
471 /*
472 -----------------
473 link jvtx to kvtx
474 -----------------
475 */
476 if ( (ip = freeIP) == NULL ) {
477 ip = IP_init(nvtx+1, IP_FORWARD) ;
478 ip->next = baseIP ; baseIP = ip ;
479 freeIP = baseIP + 1 ;
480 ip = freeIP ;
481 }
482 freeIP = ip->next ;
483 ip->val = jvtx ;
484 ip->next = head[kvtx] ;
485 head[kvtx] = ip ;
486 #if MYDEBUG > 0
487 fprintf(stdout, "\n linking %d to %d, %p to %p",
488 jvtx, kvtx, ip, ip->next) ;
489 fflush(stdout) ;
490 #endif
491 }
492 }
493 }
494 /*
495 ------------------------------------------------
496 list is complete, sort and insert into adjacency
497 ------------------------------------------------
498 */
499 IVqsortUp(count, list) ;
500 IVL_setList(adjIVL, jvtx, count, list) ;
501 }
502 /*
503 ------------------------
504 free the working storage
505 ------------------------
506 */
507 IVfree(list) ;
508 IVfree(mark) ;
509 FREE(head) ;
510 while ( (ip = baseIP) != NULL ) {
511 baseIP = baseIP->next ;
512 IP_free(ip) ;
513 }
514
515 return(adjIVL) ; }
516
517 /*--------------------------------------------------------------------*/
518