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 += 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(&cmap, &match, &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(&htable, LTERM);
153 
154   return cnedges;
155 }
156 
157 
158