Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
estmem.c
Go to the documentation of this file.
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 
#define ComputeCoarseGraphSize
Definition: rename.h:54
void METIS_EstimateMemory(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *optype, int *nbytes)
Definition: estmem.c:22
#define LTERM
Definition: defs.h:18
int idxtype
Definition: struct.h:19
#define InitRandom
Definition: rename.h:412
#define u(a, b, c)
#define idxsmalloc
Definition: rename.h:386
#define Change2CNumbering
Definition: rename.h:62
#define Change2FNumbering2
Definition: rename.h:64
void GKfree(void **ptr1,...)
Definition: util.c:121
#define NEG_GAINSPAN
Definition: defs.h:24
#define EstimateCFraction
Definition: rename.h:53
#define PLUS_GAINSPAN
Definition: defs.h:23
#define idxmalloc
Definition: rename.h:383
#define v(a, b, c)
#define RandomPermute
Definition: rename.h:410
#define UNMATCHED
Definition: defs.h:131