1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * ccgraph.c
5 *
6 * This file contains the functions that create the coarse graph
7 *
8 * Started 8/11/97
9 * George
10 *
11 * $Id: ccgraph.c,v 1.1 1998/11/27 17:59:12 karypis Exp $
12 *
13 */
14
15 #include "metis.h"
16
17
18
19 /*************************************************************************
20 * This function creates the coarser graph
21 **************************************************************************/
CreateCoarseGraph(CtrlType * ctrl,GraphType * graph,int cnvtxs,idxtype * match,idxtype * perm)22 void CreateCoarseGraph(CtrlType *ctrl, GraphType *graph, int cnvtxs, idxtype *match, idxtype *perm)
23 {
24 int i, j, jj, k, kk, l, m, istart, iend, nvtxs, nedges, ncon, cnedges, v, u, mask, dovsize;
25 idxtype *xadj, *vwgt, *vsize, *adjncy, *adjwgt, *adjwgtsum, *auxadj;
26 idxtype *cmap, *htable;
27 idxtype *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt, *cadjwgtsum;
28 float *nvwgt, *cnvwgt;
29 GraphType *cgraph;
30
31 dovsize = (ctrl->optype == OP_KVMETIS ? 1 : 0);
32
33 mask = HTLENGTH;
34 if (cnvtxs < 8*mask || graph->nedges/graph->nvtxs > 15) {
35 CreateCoarseGraphNoMask(ctrl, graph, cnvtxs, match, perm);
36 return;
37 }
38
39 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
40
41 nvtxs = graph->nvtxs;
42 ncon = graph->ncon;
43 xadj = graph->xadj;
44 vwgt = graph->vwgt;
45 vsize = graph->vsize;
46 nvwgt = graph->nvwgt;
47 adjncy = graph->adjncy;
48 adjwgt = graph->adjwgt;
49 adjwgtsum = graph->adjwgtsum;
50 cmap = graph->cmap;
51
52 /* Initialize the coarser graph */
53 cgraph = SetUpCoarseGraph(graph, cnvtxs, dovsize);
54 cxadj = cgraph->xadj;
55 cvwgt = cgraph->vwgt;
56 cvsize = cgraph->vsize;
57 cnvwgt = cgraph->nvwgt;
58 cadjwgtsum = cgraph->adjwgtsum;
59 cadjncy = cgraph->adjncy;
60 cadjwgt = cgraph->adjwgt;
61
62
63 iend = xadj[nvtxs];
64 auxadj = ctrl->wspace.auxcore;
65 memcpy(auxadj, adjncy, iend*sizeof(idxtype));
66 for (i=0; i<iend; i++)
67 auxadj[i] = cmap[auxadj[i]];
68
69 htable = idxset(mask+1, -1, idxwspacemalloc(ctrl, mask+1));
70
71 cxadj[0] = cnvtxs = cnedges = 0;
72 for (i=0; i<nvtxs; i++) {
73 v = perm[i];
74 if (cmap[v] != cnvtxs)
75 continue;
76
77 u = match[v];
78 if (ncon == 1)
79 cvwgt[cnvtxs] = vwgt[v];
80 else
81 scopy(ncon, nvwgt+v*ncon, cnvwgt+cnvtxs*ncon);
82
83 if (dovsize)
84 cvsize[cnvtxs] = vsize[v];
85
86 cadjwgtsum[cnvtxs] = adjwgtsum[v];
87 nedges = 0;
88
89 istart = xadj[v];
90 iend = xadj[v+1];
91 for (j=istart; j<iend; j++) {
92 k = auxadj[j];
93 kk = k&mask;
94 if ((m = htable[kk]) == -1) {
95 cadjncy[nedges] = k;
96 cadjwgt[nedges] = adjwgt[j];
97 htable[kk] = nedges++;
98 }
99 else if (cadjncy[m] == k) {
100 cadjwgt[m] += adjwgt[j];
101 }
102 else {
103 for (jj=0; jj<nedges; jj++) {
104 if (cadjncy[jj] == k) {
105 cadjwgt[jj] += adjwgt[j];
106 break;
107 }
108 }
109 if (jj == nedges) {
110 cadjncy[nedges] = k;
111 cadjwgt[nedges++] = adjwgt[j];
112 }
113 }
114 }
115
116 if (v != u) {
117 if (ncon == 1)
118 cvwgt[cnvtxs] += vwgt[u];
119 else
120 saxpy(ncon, 1.0, nvwgt+u*ncon, 1, cnvwgt+cnvtxs*ncon, 1);
121
122 if (dovsize)
123 cvsize[cnvtxs] += vsize[u];
124
125 cadjwgtsum[cnvtxs] += adjwgtsum[u];
126
127 istart = xadj[u];
128 iend = xadj[u+1];
129 for (j=istart; j<iend; j++) {
130 k = auxadj[j];
131 kk = k&mask;
132 if ((m = htable[kk]) == -1) {
133 cadjncy[nedges] = k;
134 cadjwgt[nedges] = adjwgt[j];
135 htable[kk] = nedges++;
136 }
137 else if (cadjncy[m] == k) {
138 cadjwgt[m] += adjwgt[j];
139 }
140 else {
141 for (jj=0; jj<nedges; jj++) {
142 if (cadjncy[jj] == k) {
143 cadjwgt[jj] += adjwgt[j];
144 break;
145 }
146 }
147 if (jj == nedges) {
148 cadjncy[nedges] = k;
149 cadjwgt[nedges++] = adjwgt[j];
150 }
151 }
152 }
153
154 /* Remove the contracted adjacency weight */
155 jj = htable[cnvtxs&mask];
156 if (jj >= 0 && cadjncy[jj] != cnvtxs) {
157 for (jj=0; jj<nedges; jj++) {
158 if (cadjncy[jj] == cnvtxs)
159 break;
160 }
161 }
162 if (jj >= 0 && cadjncy[jj] == cnvtxs) { /* This 2nd check is needed for non-adjacent matchings */
163 cadjwgtsum[cnvtxs] -= cadjwgt[jj];
164 cadjncy[jj] = cadjncy[--nedges];
165 cadjwgt[jj] = cadjwgt[nedges];
166 }
167 }
168
169 ASSERTP(cadjwgtsum[cnvtxs] == idxsum(nedges, cadjwgt), ("%d %d %d %d %d\n", cnvtxs, cadjwgtsum[cnvtxs], idxsum(nedges, cadjwgt), adjwgtsum[u], adjwgtsum[v]));
170
171 for (j=0; j<nedges; j++)
172 htable[cadjncy[j]&mask] = -1; /* Zero out the htable */
173 htable[cnvtxs&mask] = -1;
174
175 cnedges += nedges;
176 cxadj[++cnvtxs] = cnedges;
177 cadjncy += nedges;
178 cadjwgt += nedges;
179 }
180
181 cgraph->nedges = cnedges;
182
183 ReAdjustMemory(graph, cgraph, dovsize);
184
185 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
186
187 idxwspacefree(ctrl, mask+1);
188
189 }
190
191
192 /*************************************************************************
193 * This function creates the coarser graph
194 **************************************************************************/
CreateCoarseGraphNoMask(CtrlType * ctrl,GraphType * graph,int cnvtxs,idxtype * match,idxtype * perm)195 void CreateCoarseGraphNoMask(CtrlType *ctrl, GraphType *graph, int cnvtxs, idxtype *match, idxtype *perm)
196 {
197 int i, j, k, m, istart, iend, nvtxs, nedges, ncon, cnedges, v, u, dovsize;
198 idxtype *xadj, *vwgt, *vsize, *adjncy, *adjwgt, *adjwgtsum, *auxadj;
199 idxtype *cmap, *htable;
200 idxtype *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt, *cadjwgtsum;
201 float *nvwgt, *cnvwgt;
202 GraphType *cgraph;
203
204 dovsize = (ctrl->optype == OP_KVMETIS ? 1 : 0);
205
206 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
207
208 nvtxs = graph->nvtxs;
209 ncon = graph->ncon;
210 xadj = graph->xadj;
211 vwgt = graph->vwgt;
212 vsize = graph->vsize;
213 nvwgt = graph->nvwgt;
214 adjncy = graph->adjncy;
215 adjwgt = graph->adjwgt;
216 adjwgtsum = graph->adjwgtsum;
217 cmap = graph->cmap;
218
219
220 /* Initialize the coarser graph */
221 cgraph = SetUpCoarseGraph(graph, cnvtxs, dovsize);
222 cxadj = cgraph->xadj;
223 cvwgt = cgraph->vwgt;
224 cvsize = cgraph->vsize;
225 cnvwgt = cgraph->nvwgt;
226 cadjwgtsum = cgraph->adjwgtsum;
227 cadjncy = cgraph->adjncy;
228 cadjwgt = cgraph->adjwgt;
229
230
231 htable = idxset(cnvtxs, -1, idxwspacemalloc(ctrl, cnvtxs));
232
233 iend = xadj[nvtxs];
234 auxadj = ctrl->wspace.auxcore;
235 memcpy(auxadj, adjncy, iend*sizeof(idxtype));
236 for (i=0; i<iend; i++)
237 auxadj[i] = cmap[auxadj[i]];
238
239 cxadj[0] = cnvtxs = cnedges = 0;
240 for (i=0; i<nvtxs; i++) {
241 v = perm[i];
242 if (cmap[v] != cnvtxs)
243 continue;
244
245 u = match[v];
246 if (ncon == 1)
247 cvwgt[cnvtxs] = vwgt[v];
248 else
249 scopy(ncon, nvwgt+v*ncon, cnvwgt+cnvtxs*ncon);
250
251 if (dovsize)
252 cvsize[cnvtxs] = vsize[v];
253
254 cadjwgtsum[cnvtxs] = adjwgtsum[v];
255 nedges = 0;
256
257 istart = xadj[v];
258 iend = xadj[v+1];
259 for (j=istart; j<iend; j++) {
260 k = auxadj[j];
261 if ((m = htable[k]) == -1) {
262 cadjncy[nedges] = k;
263 cadjwgt[nedges] = adjwgt[j];
264 htable[k] = nedges++;
265 }
266 else {
267 cadjwgt[m] += adjwgt[j];
268 }
269 }
270
271 if (v != u) {
272 if (ncon == 1)
273 cvwgt[cnvtxs] += vwgt[u];
274 else
275 saxpy(ncon, 1.0, nvwgt+u*ncon, 1, cnvwgt+cnvtxs*ncon, 1);
276
277 if (dovsize)
278 cvsize[cnvtxs] += vsize[u];
279
280 cadjwgtsum[cnvtxs] += adjwgtsum[u];
281
282 istart = xadj[u];
283 iend = xadj[u+1];
284 for (j=istart; j<iend; j++) {
285 k = auxadj[j];
286 if ((m = htable[k]) == -1) {
287 cadjncy[nedges] = k;
288 cadjwgt[nedges] = adjwgt[j];
289 htable[k] = nedges++;
290 }
291 else {
292 cadjwgt[m] += adjwgt[j];
293 }
294 }
295
296 /* Remove the contracted adjacency weight */
297 if ((j = htable[cnvtxs]) != -1) {
298 ASSERT(cadjncy[j] == cnvtxs);
299 cadjwgtsum[cnvtxs] -= cadjwgt[j];
300 cadjncy[j] = cadjncy[--nedges];
301 cadjwgt[j] = cadjwgt[nedges];
302 htable[cnvtxs] = -1;
303 }
304 }
305
306 ASSERTP(cadjwgtsum[cnvtxs] == idxsum(nedges, cadjwgt), ("%d %d\n", cadjwgtsum[cnvtxs], idxsum(nedges, cadjwgt)));
307
308 for (j=0; j<nedges; j++)
309 htable[cadjncy[j]] = -1; /* Zero out the htable */
310
311 cnedges += nedges;
312 cxadj[++cnvtxs] = cnedges;
313 cadjncy += nedges;
314 cadjwgt += nedges;
315 }
316
317 cgraph->nedges = cnedges;
318
319 ReAdjustMemory(graph, cgraph, dovsize);
320
321 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
322
323 idxwspacefree(ctrl, cnvtxs);
324 }
325
326
327 /*************************************************************************
328 * This function creates the coarser graph
329 **************************************************************************/
CreateCoarseGraph_NVW(CtrlType * ctrl,GraphType * graph,int cnvtxs,idxtype * match,idxtype * perm)330 void CreateCoarseGraph_NVW(CtrlType *ctrl, GraphType *graph, int cnvtxs, idxtype *match, idxtype *perm)
331 {
332 int i, j, jj, k, kk, l, m, istart, iend, nvtxs, nedges, ncon, cnedges, v, u, mask;
333 idxtype *xadj, *adjncy, *adjwgtsum, *auxadj;
334 idxtype *cmap, *htable;
335 idxtype *cxadj, *cvwgt, *cadjncy, *cadjwgt, *cadjwgtsum;
336 float *nvwgt, *cnvwgt;
337 GraphType *cgraph;
338
339
340 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
341
342 nvtxs = graph->nvtxs;
343 ncon = graph->ncon;
344 xadj = graph->xadj;
345 nvwgt = graph->nvwgt;
346 adjncy = graph->adjncy;
347 adjwgtsum = graph->adjwgtsum;
348 cmap = graph->cmap;
349
350 /* Initialize the coarser graph */
351 cgraph = SetUpCoarseGraph(graph, cnvtxs, 0);
352 cxadj = cgraph->xadj;
353 cvwgt = cgraph->vwgt;
354 cnvwgt = cgraph->nvwgt;
355 cadjwgtsum = cgraph->adjwgtsum;
356 cadjncy = cgraph->adjncy;
357 cadjwgt = cgraph->adjwgt;
358
359
360 iend = xadj[nvtxs];
361 auxadj = ctrl->wspace.auxcore;
362 memcpy(auxadj, adjncy, iend*sizeof(idxtype));
363 for (i=0; i<iend; i++)
364 auxadj[i] = cmap[auxadj[i]];
365
366 mask = HTLENGTH;
367 htable = idxset(mask+1, -1, idxwspacemalloc(ctrl, mask+1));
368
369 cxadj[0] = cnvtxs = cnedges = 0;
370 for (i=0; i<nvtxs; i++) {
371 v = perm[i];
372 if (cmap[v] != cnvtxs)
373 continue;
374
375 u = match[v];
376 cvwgt[cnvtxs] = 1;
377 cadjwgtsum[cnvtxs] = adjwgtsum[v];
378 nedges = 0;
379
380 istart = xadj[v];
381 iend = xadj[v+1];
382 for (j=istart; j<iend; j++) {
383 k = auxadj[j];
384 kk = k&mask;
385 if ((m = htable[kk]) == -1) {
386 cadjncy[nedges] = k;
387 cadjwgt[nedges] = 1;
388 htable[kk] = nedges++;
389 }
390 else if (cadjncy[m] == k) {
391 cadjwgt[m]++;
392 }
393 else {
394 for (jj=0; jj<nedges; jj++) {
395 if (cadjncy[jj] == k) {
396 cadjwgt[jj]++;
397 break;
398 }
399 }
400 if (jj == nedges) {
401 cadjncy[nedges] = k;
402 cadjwgt[nedges++] = 1;
403 }
404 }
405 }
406
407 if (v != u) {
408 cvwgt[cnvtxs]++;
409 cadjwgtsum[cnvtxs] += adjwgtsum[u];
410
411 istart = xadj[u];
412 iend = xadj[u+1];
413 for (j=istart; j<iend; j++) {
414 k = auxadj[j];
415 kk = k&mask;
416 if ((m = htable[kk]) == -1) {
417 cadjncy[nedges] = k;
418 cadjwgt[nedges] = 1;
419 htable[kk] = nedges++;
420 }
421 else if (cadjncy[m] == k) {
422 cadjwgt[m]++;
423 }
424 else {
425 for (jj=0; jj<nedges; jj++) {
426 if (cadjncy[jj] == k) {
427 cadjwgt[jj]++;
428 break;
429 }
430 }
431 if (jj == nedges) {
432 cadjncy[nedges] = k;
433 cadjwgt[nedges++] = 1;
434 }
435 }
436 }
437
438 /* Remove the contracted adjacency weight */
439 jj = htable[cnvtxs&mask];
440 if (jj >= 0 && cadjncy[jj] != cnvtxs) {
441 for (jj=0; jj<nedges; jj++) {
442 if (cadjncy[jj] == cnvtxs)
443 break;
444 }
445 }
446 if (jj >= 0 && cadjncy[jj] == cnvtxs) { /* This 2nd check is needed for non-adjacent matchings */
447 cadjwgtsum[cnvtxs] -= cadjwgt[jj];
448 cadjncy[jj] = cadjncy[--nedges];
449 cadjwgt[jj] = cadjwgt[nedges];
450 }
451 }
452
453 ASSERTP(cadjwgtsum[cnvtxs] == idxsum(nedges, cadjwgt), ("%d %d %d %d %d\n", cnvtxs, cadjwgtsum[cnvtxs], idxsum(nedges, cadjwgt), adjwgtsum[u], adjwgtsum[v]));
454
455 for (j=0; j<nedges; j++)
456 htable[cadjncy[j]&mask] = -1; /* Zero out the htable */
457 htable[cnvtxs&mask] = -1;
458
459 cnedges += nedges;
460 cxadj[++cnvtxs] = cnedges;
461 cadjncy += nedges;
462 cadjwgt += nedges;
463 }
464
465 cgraph->nedges = cnedges;
466
467 ReAdjustMemory(graph, cgraph, 0);
468
469 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
470
471 idxwspacefree(ctrl, mask+1);
472
473 }
474
475
476 /*************************************************************************
477 * Setup the various arrays for the coarse graph
478 **************************************************************************/
SetUpCoarseGraph(GraphType * graph,int cnvtxs,int dovsize)479 GraphType *SetUpCoarseGraph(GraphType *graph, int cnvtxs, int dovsize)
480 {
481 GraphType *cgraph;
482
483 cgraph = CreateGraph();
484 cgraph->nvtxs = cnvtxs;
485 cgraph->ncon = graph->ncon;
486
487 cgraph->finer = graph;
488 graph->coarser = cgraph;
489
490
491 /* Allocate memory for the coarser graph */
492 if (graph->ncon == 1) {
493 if (dovsize) {
494 cgraph->gdata = idxmalloc(5*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
495 cgraph->xadj = cgraph->gdata;
496 cgraph->vwgt = cgraph->gdata + cnvtxs+1;
497 cgraph->vsize = cgraph->gdata + 2*cnvtxs+1;
498 cgraph->adjwgtsum = cgraph->gdata + 3*cnvtxs+1;
499 cgraph->cmap = cgraph->gdata + 4*cnvtxs+1;
500 cgraph->adjncy = cgraph->gdata + 5*cnvtxs+1;
501 cgraph->adjwgt = cgraph->gdata + 5*cnvtxs+1 + graph->nedges;
502 }
503 else {
504 cgraph->gdata = idxmalloc(4*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
505 cgraph->xadj = cgraph->gdata;
506 cgraph->vwgt = cgraph->gdata + cnvtxs+1;
507 cgraph->adjwgtsum = cgraph->gdata + 2*cnvtxs+1;
508 cgraph->cmap = cgraph->gdata + 3*cnvtxs+1;
509 cgraph->adjncy = cgraph->gdata + 4*cnvtxs+1;
510 cgraph->adjwgt = cgraph->gdata + 4*cnvtxs+1 + graph->nedges;
511 }
512 }
513 else {
514 if (dovsize) {
515 cgraph->gdata = idxmalloc(4*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
516 cgraph->xadj = cgraph->gdata;
517 cgraph->vsize = cgraph->gdata + cnvtxs+1;
518 cgraph->adjwgtsum = cgraph->gdata + 2*cnvtxs+1;
519 cgraph->cmap = cgraph->gdata + 3*cnvtxs+1;
520 cgraph->adjncy = cgraph->gdata + 4*cnvtxs+1;
521 cgraph->adjwgt = cgraph->gdata + 4*cnvtxs+1 + graph->nedges;
522 }
523 else {
524 cgraph->gdata = idxmalloc(3*cnvtxs+1 + 2*graph->nedges, "SetUpCoarseGraph: gdata");
525 cgraph->xadj = cgraph->gdata;
526 cgraph->adjwgtsum = cgraph->gdata + cnvtxs+1;
527 cgraph->cmap = cgraph->gdata + 2*cnvtxs+1;
528 cgraph->adjncy = cgraph->gdata + 3*cnvtxs+1;
529 cgraph->adjwgt = cgraph->gdata + 3*cnvtxs+1 + graph->nedges;
530 }
531
532 cgraph->nvwgt = fmalloc(graph->ncon*cnvtxs, "SetUpCoarseGraph: nvwgt");
533 }
534
535 return cgraph;
536 }
537
538
539 /*************************************************************************
540 * This function re-adjusts the amount of memory that was allocated if
541 * it will lead to significant savings
542 **************************************************************************/
ReAdjustMemory(GraphType * graph,GraphType * cgraph,int dovsize)543 void ReAdjustMemory(GraphType *graph, GraphType *cgraph, int dovsize)
544 {
545
546 if (cgraph->nedges > 100000 && graph->nedges < 0.7*graph->nedges) {
547 idxcopy(cgraph->nedges, cgraph->adjwgt, cgraph->adjncy+cgraph->nedges);
548
549 if (graph->ncon == 1) {
550 if (dovsize) {
551 cgraph->gdata = (idxtype*) realloc(cgraph->gdata, (5*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
552
553 /* Do this, in case everything was copied into new space */
554 cgraph->xadj = cgraph->gdata;
555 cgraph->vwgt = cgraph->gdata + cgraph->nvtxs+1;
556 cgraph->vsize = cgraph->gdata + 2*cgraph->nvtxs+1;
557 cgraph->adjwgtsum = cgraph->gdata + 3*cgraph->nvtxs+1;
558 cgraph->cmap = cgraph->gdata + 4*cgraph->nvtxs+1;
559 cgraph->adjncy = cgraph->gdata + 5*cgraph->nvtxs+1;
560 cgraph->adjwgt = cgraph->gdata + 5*cgraph->nvtxs+1 + cgraph->nedges;
561 }
562 else {
563 cgraph->gdata = (idxtype*) realloc(cgraph->gdata, (4*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
564
565 /* Do this, in case everything was copied into new space */
566 cgraph->xadj = cgraph->gdata;
567 cgraph->vwgt = cgraph->gdata + cgraph->nvtxs+1;
568 cgraph->adjwgtsum = cgraph->gdata + 2*cgraph->nvtxs+1;
569 cgraph->cmap = cgraph->gdata + 3*cgraph->nvtxs+1;
570 cgraph->adjncy = cgraph->gdata + 4*cgraph->nvtxs+1;
571 cgraph->adjwgt = cgraph->gdata + 4*cgraph->nvtxs+1 + cgraph->nedges;
572 }
573 }
574 else {
575 if (dovsize) {
576 cgraph->gdata = (idxtype*) realloc(cgraph->gdata, (4*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
577
578 /* Do this, in case everything was copied into new space */
579 cgraph->xadj = cgraph->gdata;
580 cgraph->vsize = cgraph->gdata + cgraph->nvtxs+1;
581 cgraph->adjwgtsum = cgraph->gdata + 2*cgraph->nvtxs+1;
582 cgraph->cmap = cgraph->gdata + 3*cgraph->nvtxs+1;
583 cgraph->adjncy = cgraph->gdata + 4*cgraph->nvtxs+1;
584 cgraph->adjwgt = cgraph->gdata + 4*cgraph->nvtxs+1 + cgraph->nedges;
585 }
586 else {
587 cgraph->gdata = (idxtype*) realloc(cgraph->gdata, (3*cgraph->nvtxs+1 + 2*cgraph->nedges)*sizeof(idxtype));
588
589 /* Do this, in case everything was copied into new space */
590 cgraph->xadj = cgraph->gdata;
591 cgraph->adjwgtsum = cgraph->gdata + cgraph->nvtxs+1;
592 cgraph->cmap = cgraph->gdata + 2*cgraph->nvtxs+1;
593 cgraph->adjncy = cgraph->gdata + 3*cgraph->nvtxs+1;
594 cgraph->adjwgt = cgraph->gdata + 3*cgraph->nvtxs+1 + cgraph->nedges;
595 }
596 }
597 }
598
599 }
600