Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
stat.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * stat.c
5  *
6  * This file computes various statistics
7  *
8  * Started 7/25/97
9  * George
10  *
11  * $Id: stat.c,v 1.1 1998/11/27 17:59:31 karypis Exp $
12  *
13  */
14 
15 #include <metis.h>
16 
17 
18 /*************************************************************************
19 * This function computes cuts and balance information
20 **************************************************************************/
21 void ComputePartitionInfo(GraphType *graph, int nparts, idxtype *where)
22 {
23  int i, j, k, nvtxs, ncon, mustfree=0;
24  idxtype *xadj, *adjncy, *vwgt, *adjwgt, *kpwgts, *tmpptr;
25  idxtype *padjncy, *padjwgt, *padjcut;
26 
27  nvtxs = graph->nvtxs;
28  ncon = graph->ncon;
29  xadj = graph->xadj;
30  adjncy = graph->adjncy;
31  vwgt = graph->vwgt;
32  adjwgt = graph->adjwgt;
33 
34  if (vwgt == NULL) {
35  vwgt = graph->vwgt = idxsmalloc(nvtxs, 1, "vwgt");
36  mustfree = 1;
37  }
38  if (adjwgt == NULL) {
39  adjwgt = graph->adjwgt = idxsmalloc(xadj[nvtxs], 1, "adjwgt");
40  mustfree += 2;
41  }
42 
43  printf("%d-way Cut: %5d, Vol: %5d, ", nparts, ComputeCut(graph, where), ComputeVolume(graph, where));
44 
45  /* Compute balance information */
46  kpwgts = idxsmalloc(ncon*nparts, 0, "ComputePartitionInfo: kpwgts");
47 
48  for (i=0; i<nvtxs; i++) {
49  for (j=0; j<ncon; j++)
50  kpwgts[where[i]*ncon+j] += vwgt[i*ncon+j];
51  }
52 
53  if (ncon == 1) {
54  printf("\tBalance: %5.3f out of %5.3f\n",
55  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)),
56  1.0*nparts*vwgt[idxamax(nvtxs, vwgt)]/(1.0*idxsum(nparts, kpwgts)));
57  }
58  else {
59  printf("\tBalance:");
60  for (j=0; j<ncon; j++)
61  printf(" (%5.3f out of %5.3f)",
62  1.0*nparts*kpwgts[ncon*idxamax_strd(nparts, kpwgts+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)),
63  1.0*nparts*vwgt[ncon*idxamax_strd(nvtxs, vwgt+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)));
64  printf("\n");
65  }
66 
67 
68  /* Compute p-adjncy information */
69  padjncy = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjncy");
70  padjwgt = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
71  padjcut = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
72 
73  idxset(nparts, 0, kpwgts);
74  for (i=0; i<nvtxs; i++) {
75  for (j=xadj[i]; j<xadj[i+1]; j++) {
76  if (where[i] != where[adjncy[j]]) {
77  padjncy[where[i]*nparts+where[adjncy[j]]] = 1;
78  padjcut[where[i]*nparts+where[adjncy[j]]] += adjwgt[j];
79  if (kpwgts[where[adjncy[j]]] == 0) {
80  padjwgt[where[i]*nparts+where[adjncy[j]]]++;
81  kpwgts[where[adjncy[j]]] = 1;
82  }
83  }
84  }
85  for (j=xadj[i]; j<xadj[i+1]; j++)
86  kpwgts[where[adjncy[j]]] = 0;
87  }
88 
89  for (i=0; i<nparts; i++)
90  kpwgts[i] = idxsum(nparts, padjncy+i*nparts);
91  printf("Min/Max/Avg/Bal # of adjacent subdomains: %5d %5d %5.2f %7.3f\n",
92  kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)],
93  1.0*idxsum(nparts, kpwgts)/(1.0*nparts),
94  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
95 
96  for (i=0; i<nparts; i++)
97  kpwgts[i] = idxsum(nparts, padjcut+i*nparts);
98  printf("Min/Max/Avg/Bal # of adjacent subdomain cuts: %5d %5d %5d %7.3f\n",
99  kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts,
100  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
101 
102  for (i=0; i<nparts; i++)
103  kpwgts[i] = idxsum(nparts, padjwgt+i*nparts);
104  printf("Min/Max/Avg/Bal/Frac # of interface nodes: %5d %5d %5d %7.3f %7.3f\n",
105  kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts,
106  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)), 1.0*idxsum(nparts, kpwgts)/(1.0*nvtxs));
107 
108  tmpptr = graph->where;
109  graph->where = where;
110  for (i=0; i<nparts; i++)
111  IsConnectedSubdomain(NULL, graph, i, 1);
112  graph->where = tmpptr;
113 
114  if (mustfree == 1 || mustfree == 3) {
115  free(vwgt);
116  graph->vwgt = NULL;
117  }
118  if (mustfree == 2 || mustfree == 3) {
119  free(adjwgt);
120  graph->adjwgt = NULL;
121  }
122 
123  GKfree(&kpwgts, &padjncy, &padjwgt, &padjcut, LTERM);
124 }
125 
126 
127 /*************************************************************************
128 * This function computes cuts and balance information
129 **************************************************************************/
131 {
132  int i, j, k, nvtxs, ncon, mustfree=0;
133  idxtype *xadj, *adjncy, *vwgt, *vsize, *adjwgt, *kpwgts, *tmpptr;
134  idxtype *padjncy, *padjwgt, *padjcut;
135 
136  nvtxs = graph->nvtxs;
137  ncon = graph->ncon;
138  xadj = graph->xadj;
139  adjncy = graph->adjncy;
140  vwgt = graph->vwgt;
141  vsize = graph->vsize;
142  adjwgt = graph->adjwgt;
143 
144  if (vwgt == NULL) {
145  vwgt = graph->vwgt = idxsmalloc(nvtxs, 1, "vwgt");
146  mustfree = 1;
147  }
148  if (adjwgt == NULL) {
149  adjwgt = graph->adjwgt = idxsmalloc(xadj[nvtxs], 1, "adjwgt");
150  mustfree += 2;
151  }
152 
153  printf("%d-way Cut: %5d, Vol: %5d, ", nparts, ComputeCut(graph, where), ComputeVolume(graph, where));
154 
155  /* Compute balance information */
156  kpwgts = idxsmalloc(ncon*nparts, 0, "ComputePartitionInfo: kpwgts");
157 
158  for (i=0; i<nvtxs; i++) {
159  for (j=0; j<ncon; j++)
160  kpwgts[where[i]*ncon+j] += vwgt[i*ncon+j];
161  }
162 
163  if (ncon == 1) {
164  printf("\tBalance: %5.3f out of %5.3f\n",
165  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)),
166  1.0*nparts*vwgt[idxamax(nvtxs, vwgt)]/(1.0*idxsum(nparts, kpwgts)));
167  }
168  else {
169  printf("\tBalance:");
170  for (j=0; j<ncon; j++)
171  printf(" (%5.3f out of %5.3f)",
172  1.0*nparts*kpwgts[ncon*idxamax_strd(nparts, kpwgts+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)),
173  1.0*nparts*vwgt[ncon*idxamax_strd(nvtxs, vwgt+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)));
174  printf("\n");
175  }
176 
177 
178  /* Compute p-adjncy information */
179  padjncy = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjncy");
180  padjwgt = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
181  padjcut = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
182 
183  idxset(nparts, 0, kpwgts);
184  for (i=0; i<nvtxs; i++) {
185  for (j=xadj[i]; j<xadj[i+1]; j++) {
186  if (where[i] != where[adjncy[j]]) {
187  padjncy[where[i]*nparts+where[adjncy[j]]] = 1;
188  padjcut[where[i]*nparts+where[adjncy[j]]] += adjwgt[j];
189  if (kpwgts[where[adjncy[j]]] == 0) {
190  padjwgt[where[i]*nparts+where[adjncy[j]]] += vsize[i];
191  kpwgts[where[adjncy[j]]] = 1;
192  }
193  }
194  }
195  for (j=xadj[i]; j<xadj[i+1]; j++)
196  kpwgts[where[adjncy[j]]] = 0;
197  }
198 
199  for (i=0; i<nparts; i++)
200  kpwgts[i] = idxsum(nparts, padjncy+i*nparts);
201  printf("Min/Max/Avg/Bal # of adjacent subdomains: %5d %5d %5d %7.3f\n",
202  kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts,
203  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
204 
205  for (i=0; i<nparts; i++)
206  kpwgts[i] = idxsum(nparts, padjcut+i*nparts);
207  printf("Min/Max/Avg/Bal # of adjacent subdomain cuts: %5d %5d %5d %7.3f\n",
208  kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts,
209  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
210 
211  for (i=0; i<nparts; i++)
212  kpwgts[i] = idxsum(nparts, padjwgt+i*nparts);
213  printf("Min/Max/Avg/Bal/Frac # of interface nodes: %5d %5d %5d %7.3f %7.3f\n",
214  kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts,
215  1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)), 1.0*idxsum(nparts, kpwgts)/(1.0*nvtxs));
216 
217 
218  if (mustfree == 1 || mustfree == 3) {
219  free(vwgt);
220  graph->vwgt = NULL;
221  }
222  if (mustfree == 2 || mustfree == 3) {
223  free(adjwgt);
224  graph->adjwgt = NULL;
225  }
226 
227  GKfree(&kpwgts, &padjncy, &padjwgt, &padjcut, LTERM);
228 }
229 
230 
231 
232 /*************************************************************************
233 * This function computes the balance of the partitioning
234 **************************************************************************/
235 void ComputePartitionBalance(GraphType *graph, int nparts, idxtype *where, float *ubvec)
236 {
237  int i, j, nvtxs, ncon;
238  idxtype *kpwgts, *vwgt;
239  float balance;
240 
241  nvtxs = graph->nvtxs;
242  ncon = graph->ncon;
243  vwgt = graph->vwgt;
244 
245  kpwgts = idxsmalloc(nparts, 0, "ComputePartitionInfo: kpwgts");
246 
247  if (vwgt == NULL) {
248  for (i=0; i<nvtxs; i++)
249  kpwgts[where[i]]++;
250  ubvec[0] = 1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*nvtxs);
251  }
252  else {
253  for (j=0; j<ncon; j++) {
254  idxset(nparts, 0, kpwgts);
255  for (i=0; i<graph->nvtxs; i++)
256  kpwgts[where[i]] += vwgt[i*ncon+j];
257 
258  ubvec[j] = 1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts));
259  }
260  }
261 
262  free(kpwgts);
263 
264 }
265 
266 
267 /*************************************************************************
268 * This function computes the balance of the element partitioning
269 **************************************************************************/
270 float ComputeElementBalance(int ne, int nparts, idxtype *where)
271 {
272  int i;
273  idxtype *kpwgts;
274  float balance;
275 
276  kpwgts = idxsmalloc(nparts, 0, "ComputeElementBalance: kpwgts");
277 
278  for (i=0; i<ne; i++)
279  kpwgts[where[i]]++;
280 
281  balance = 1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts));
282 
283  free(kpwgts);
284 
285  return balance;
286 
287 }
#define ComputeElementBalance
Definition: rename.h:358
#define ComputePartitionBalance
Definition: rename.h:357
#define ComputePartitionInfo
Definition: rename.h:356
#define idxsum
Definition: rename.h:399
#define idxamax_strd
Definition: rename.h:394
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
int idxtype
Definition: struct.h:19
#define idxsmalloc
Definition: rename.h:386
void ComputePartitionInfoBipartite(GraphType *, int, idxtype *)
Definition: stat.c:130
#define IsConnectedSubdomain
Definition: rename.h:77
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxamin
Definition: rename.h:397
#define ComputeVolume
Definition: rename.h:122
void GKfree(void **ptr1,...)
Definition: util.c:121
int ncon
Definition: struct.h:194
#define idxamax
Definition: rename.h:393
idxtype * vwgt
Definition: struct.h:163
int nvtxs
Definition: struct.h:161
#define idxsum_strd
Definition: rename.h:400
#define ComputeCut
Definition: rename.h:43
idxtype * vsize
Definition: struct.h:164
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162