Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
ccgraph.c
Go to the documentation of this file.
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 = 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 = 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 = 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 = 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 }
#define idxwspacefree
Definition: rename.h:165
#define HTLENGTH
Definition: defs.h:26
#define CreateCoarseGraph_NVW
Definition: rename.h:28
#define saxpy
Definition: rename.h:409
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
int optype
Definition: struct.h:222
#define scopy(n, a, b)
Definition: macros.h:43
#define fmalloc
Definition: rename.h:384
#define idxwspacemalloc
Definition: rename.h:164
timer ContractTmr
Definition: struct.h:230
struct graphdef * coarser
Definition: struct.h:198
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
struct graphdef * finer
Definition: struct.h:198
#define ReAdjustMemory
Definition: rename.h:30
HitTile_Vector graph
#define CreateCoarseGraphNoMask
Definition: rename.h:27
int idxtype
Definition: struct.h:19
#define u(a, b, c)
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define OP_KVMETIS
Definition: defs.h:94
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxcopy(n, a, b)
Definition: macros.h:44
#define SetUpCoarseGraph
Definition: rename.h:29
#define ASSERTP(expr, msg)
Definition: macros.h:142
int ncon
Definition: struct.h:194
#define CreateGraph
Definition: rename.h:167
idxtype * auxcore
Definition: struct.h:106
#define m(a, b, c)
idxtype * vwgt
Definition: struct.h:163
#define DBG_TIME
Definition: defs.h:154
int nedges
Definition: struct.h:161
#define idxmalloc
Definition: rename.h:383
#define v(a, b, c)
idxtype * gdata
Definition: struct.h:157
int nvtxs
Definition: struct.h:161
WorkSpaceType wspace
Definition: struct.h:227
#define ASSERT(expr)
Definition: macros.h:130
float * nvwgt
Definition: struct.h:195
idxtype * vsize
Definition: struct.h:164
#define CreateCoarseGraph
Definition: rename.h:26
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53