1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * estmem.c
5 *
6 * This file contains code for estimating the amount of memory required by
7 * the various routines in METIS
8 *
9 * Started 11/4/97
10 * George
11 *
12 * $Id: estmem.c,v 1.1 1998/11/27 17:59:13 karypis Exp $
13 *
14 */
15
16 #include "metis.h"
17
18 /*************************************************************************
19 * This function computes how much memory will be required by the various
20 * routines in METIS
21 **************************************************************************/
METIS_EstimateMemory(int * nvtxs,idxtype * xadj,idxtype * adjncy,int * numflag,int * optype,int * nbytes)22 void METIS_EstimateMemory(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *optype, int *nbytes)
23 {
24 int i, j, k, nedges, nlevels;
25 float vfraction, efraction, vmult, emult;
26 int coresize, gdata, rdata;
27
28 if (*numflag == 1)
29 Change2CNumbering(*nvtxs, xadj, adjncy);
30
31 nedges = xadj[*nvtxs];
32
33 InitRandom(-1);
34 EstimateCFraction(*nvtxs, xadj, adjncy, &vfraction, &efraction);
35
36 /* Estimate the amount of memory for coresize */
37 if (*optype == 2)
38 coresize = nedges;
39 else
40 coresize = 0;
41 coresize += nedges + 11*(*nvtxs) + 4*1024 + 2*(NEG_GAINSPAN+PLUS_GAINSPAN+1)*(sizeof(ListNodeType *)/sizeof(idxtype));
42 coresize += 2*(*nvtxs); /* add some more fore other vectors */
43
44 gdata = nedges; /* Assume that the user does not pass weights */
45
46 nlevels = (int)(log(100.0/(*nvtxs))/log(vfraction) + .5);
47 vmult = 0.5 + (1.0 - pow(vfraction, nlevels))/(1.0 - vfraction);
48 emult = 1.0 + (1.0 - pow(efraction, nlevels+1))/(1.0 - efraction);
49
50 gdata += (int) vmult*4*(*nvtxs) + emult*2*nedges;
51 if ((vmult-1.0)*4*(*nvtxs) + (emult-1.0)*2*nedges < 5*(*nvtxs))
52 rdata = 0;
53 else
54 rdata = 5*(*nvtxs);
55
56 *nbytes = sizeof(idxtype)*(coresize+gdata+rdata+(*nvtxs));
57
58 if (*numflag == 1)
59 Change2FNumbering2(*nvtxs, xadj, adjncy);
60 }
61
62
63 /*************************************************************************
64 * This function finds a matching using the HEM heuristic
65 **************************************************************************/
EstimateCFraction(int nvtxs,idxtype * xadj,idxtype * adjncy,float * vfraction,float * efraction)66 void EstimateCFraction(int nvtxs, idxtype *xadj, idxtype *adjncy, float *vfraction, float *efraction)
67 {
68 int i, ii, j, cnvtxs, cnedges, maxidx;
69 idxtype *match, *cmap, *perm;
70
71 cmap = idxmalloc(nvtxs, "cmap");
72 match = idxsmalloc(nvtxs, UNMATCHED, "match");
73 perm = idxmalloc(nvtxs, "perm");
74 RandomPermute(nvtxs, perm, 1);
75
76 cnvtxs = 0;
77 for (ii=0; ii<nvtxs; ii++) {
78 i = perm[ii];
79
80 if (match[i] == UNMATCHED) { /* Unmatched */
81 maxidx = i;
82
83 /* Find a random matching, subject to maxvwgt constraints */
84 for (j=xadj[i]; j<xadj[i+1]; j++) {
85 if (match[adjncy[j]] == UNMATCHED) {
86 maxidx = adjncy[j];
87 break;
88 }
89 }
90
91 cmap[i] = cmap[maxidx] = cnvtxs++;
92 match[i] = maxidx;
93 match[maxidx] = i;
94 }
95 }
96
97 cnedges = ComputeCoarseGraphSize(nvtxs, xadj, adjncy, cnvtxs, cmap, match, perm);
98
99 *vfraction = (1.0*cnvtxs)/(1.0*nvtxs);
100 *efraction = (1.0*cnedges)/(1.0*xadj[nvtxs]);
101
102 GKfree((void**) &cmap, (void**) &match, (void**) &perm, LTERM);
103 }
104
105
106
107
108 /*************************************************************************
109 * This function computes the size of the coarse graph
110 **************************************************************************/
ComputeCoarseGraphSize(int nvtxs,idxtype * xadj,idxtype * adjncy,int cnvtxs,idxtype * cmap,idxtype * match,idxtype * perm)111 int ComputeCoarseGraphSize(int nvtxs, idxtype *xadj, idxtype *adjncy, int cnvtxs, idxtype *cmap, idxtype *match, idxtype *perm)
112 {
113 int i, j, k, istart, iend, nedges, cnedges, v, u;
114 idxtype *htable;
115
116 htable = idxsmalloc(cnvtxs, -1, "htable");
117
118 cnvtxs = cnedges = 0;
119 for (i=0; i<nvtxs; i++) {
120 v = perm[i];
121 if (cmap[v] != cnvtxs)
122 continue;
123
124 htable[cnvtxs] = cnvtxs;
125
126 u = match[v];
127
128 istart = xadj[v];
129 iend = xadj[v+1];
130 for (j=istart; j<iend; j++) {
131 k = cmap[adjncy[j]];
132 if (htable[k] != cnvtxs) {
133 htable[k] = cnvtxs;
134 cnedges++;
135 }
136 }
137
138 if (v != u) {
139 istart = xadj[u];
140 iend = xadj[u+1];
141 for (j=istart; j<iend; j++) {
142 k = cmap[adjncy[j]];
143 if (htable[k] != cnvtxs) {
144 htable[k] = cnvtxs;
145 cnedges++;
146 }
147 }
148 }
149 cnvtxs++;
150 }
151
152 GKfree((void**) &htable, LTERM);
153
154 return cnedges;
155 }
156
157
158