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 9942 2011-05-17 22:09:52Z karypis $
12 *
13 */
14
15 #include "metislib.h"
16
17
18 /*************************************************************************
19 * This function computes cuts and balance information
20 **************************************************************************/
ComputePartitionInfoBipartite(graph_t * graph,idx_t nparts,idx_t * where)21 void ComputePartitionInfoBipartite(graph_t *graph, idx_t nparts, idx_t *where)
22 {
23 idx_t i, j, k, nvtxs, ncon, mustfree=0;
24 idx_t *xadj, *adjncy, *vwgt, *vsize, *adjwgt, *kpwgts, *tmpptr;
25 idx_t *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 vsize = graph->vsize;
33 adjwgt = graph->adjwgt;
34
35 if (vwgt == NULL) {
36 vwgt = graph->vwgt = ismalloc(nvtxs, 1, "vwgt");
37 mustfree = 1;
38 }
39 if (adjwgt == NULL) {
40 adjwgt = graph->adjwgt = ismalloc(xadj[nvtxs], 1, "adjwgt");
41 mustfree += 2;
42 }
43
44 printf("%"PRIDX"-way Cut: %5"PRIDX", Vol: %5"PRIDX", ", nparts, ComputeCut(graph, where), ComputeVolume(graph, where));
45
46 /* Compute balance information */
47 kpwgts = ismalloc(ncon*nparts, 0, "ComputePartitionInfo: kpwgts");
48
49 for (i=0; i<nvtxs; i++) {
50 for (j=0; j<ncon; j++)
51 kpwgts[where[i]*ncon+j] += vwgt[i*ncon+j];
52 }
53
54 if (ncon == 1) {
55 printf("\tBalance: %5.3"PRREAL" out of %5.3"PRREAL"\n",
56 1.0*nparts*kpwgts[iargmax(nparts, kpwgts)]/(1.0*isum(nparts, kpwgts, 1)),
57 1.0*nparts*vwgt[iargmax(nvtxs, vwgt)]/(1.0*isum(nparts, kpwgts, 1)));
58 }
59 else {
60 printf("\tBalance:");
61 for (j=0; j<ncon; j++)
62 printf(" (%5.3"PRREAL" out of %5.3"PRREAL")",
63 1.0*nparts*kpwgts[ncon*iargmax_strd(nparts, kpwgts+j, ncon)+j]/(1.0*isum(nparts, kpwgts+j, ncon)),
64 1.0*nparts*vwgt[ncon*iargmax_strd(nvtxs, vwgt+j, ncon)+j]/(1.0*isum(nparts, kpwgts+j, ncon)));
65 printf("\n");
66 }
67
68
69 /* Compute p-adjncy information */
70 padjncy = ismalloc(nparts*nparts, 0, "ComputePartitionInfo: padjncy");
71 padjwgt = ismalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
72 padjcut = ismalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
73
74 iset(nparts, 0, kpwgts);
75 for (i=0; i<nvtxs; i++) {
76 for (j=xadj[i]; j<xadj[i+1]; j++) {
77 if (where[i] != where[adjncy[j]]) {
78 padjncy[where[i]*nparts+where[adjncy[j]]] = 1;
79 padjcut[where[i]*nparts+where[adjncy[j]]] += adjwgt[j];
80 if (kpwgts[where[adjncy[j]]] == 0) {
81 padjwgt[where[i]*nparts+where[adjncy[j]]] += vsize[i];
82 kpwgts[where[adjncy[j]]] = 1;
83 }
84 }
85 }
86 for (j=xadj[i]; j<xadj[i+1]; j++)
87 kpwgts[where[adjncy[j]]] = 0;
88 }
89
90 for (i=0; i<nparts; i++)
91 kpwgts[i] = isum(nparts, padjncy+i*nparts, 1);
92 printf("Min/Max/Avg/Bal # of adjacent subdomains: %5"PRIDX" %5"PRIDX" %5"PRIDX" %7.3"PRREAL"\n",
93 kpwgts[iargmin(nparts, kpwgts)], kpwgts[iargmax(nparts, kpwgts)], isum(nparts, kpwgts, 1)/nparts,
94 1.0*nparts*kpwgts[iargmax(nparts, kpwgts)]/(1.0*isum(nparts, kpwgts, 1)));
95
96 for (i=0; i<nparts; i++)
97 kpwgts[i] = isum(nparts, padjcut+i*nparts, 1);
98 printf("Min/Max/Avg/Bal # of adjacent subdomain cuts: %5"PRIDX" %5"PRIDX" %5"PRIDX" %7.3"PRREAL"\n",
99 kpwgts[iargmin(nparts, kpwgts)], kpwgts[iargmax(nparts, kpwgts)], isum(nparts, kpwgts, 1)/nparts,
100 1.0*nparts*kpwgts[iargmax(nparts, kpwgts)]/(1.0*isum(nparts, kpwgts, 1)));
101
102 for (i=0; i<nparts; i++)
103 kpwgts[i] = isum(nparts, padjwgt+i*nparts, 1);
104 printf("Min/Max/Avg/Bal/Frac # of interface nodes: %5"PRIDX" %5"PRIDX" %5"PRIDX" %7.3"PRREAL" %7.3"PRREAL"\n",
105 kpwgts[iargmin(nparts, kpwgts)], kpwgts[iargmax(nparts, kpwgts)], isum(nparts, kpwgts, 1)/nparts,
106 1.0*nparts*kpwgts[iargmax(nparts, kpwgts)]/(1.0*isum(nparts, kpwgts, 1)), 1.0*isum(nparts, kpwgts, 1)/(1.0*nvtxs));
107
108
109 if (mustfree == 1 || mustfree == 3) {
110 gk_free((void **)&vwgt, LTERM);
111 graph->vwgt = NULL;
112 }
113 if (mustfree == 2 || mustfree == 3) {
114 gk_free((void **)&adjwgt, LTERM);
115 graph->adjwgt = NULL;
116 }
117
118 gk_free((void **)&kpwgts, &padjncy, &padjwgt, &padjcut, LTERM);
119 }
120
121
122 /*************************************************************************
123 * This function computes the balance of the partitioning
124 **************************************************************************/
ComputePartitionBalance(graph_t * graph,idx_t nparts,idx_t * where,real_t * ubvec)125 void ComputePartitionBalance(graph_t *graph, idx_t nparts, idx_t *where, real_t *ubvec)
126 {
127 idx_t i, j, nvtxs, ncon;
128 idx_t *kpwgts, *vwgt;
129 real_t balance;
130
131 nvtxs = graph->nvtxs;
132 ncon = graph->ncon;
133 vwgt = graph->vwgt;
134
135 kpwgts = ismalloc(nparts, 0, "ComputePartitionInfo: kpwgts");
136
137 if (vwgt == NULL) {
138 for (i=0; i<nvtxs; i++)
139 kpwgts[where[i]]++;
140 ubvec[0] = 1.0*nparts*kpwgts[iargmax(nparts, kpwgts)]/(1.0*nvtxs);
141 }
142 else {
143 for (j=0; j<ncon; j++) {
144 iset(nparts, 0, kpwgts);
145 for (i=0; i<graph->nvtxs; i++)
146 kpwgts[where[i]] += vwgt[i*ncon+j];
147
148 ubvec[j] = 1.0*nparts*kpwgts[iargmax(nparts, kpwgts)]/(1.0*isum(nparts, kpwgts, 1));
149 }
150 }
151
152 gk_free((void **)&kpwgts, LTERM);
153
154 }
155
156
157 /*************************************************************************
158 * This function computes the balance of the element partitioning
159 **************************************************************************/
ComputeElementBalance(idx_t ne,idx_t nparts,idx_t * where)160 real_t ComputeElementBalance(idx_t ne, idx_t nparts, idx_t *where)
161 {
162 idx_t i;
163 idx_t *kpwgts;
164 real_t balance;
165
166 kpwgts = ismalloc(nparts, 0, "ComputeElementBalance: kpwgts");
167
168 for (i=0; i<ne; i++)
169 kpwgts[where[i]]++;
170
171 balance = 1.0*nparts*kpwgts[iargmax(nparts, kpwgts)]/(1.0*isum(nparts, kpwgts, 1));
172
173 gk_free((void **)&kpwgts, LTERM);
174
175 return balance;
176
177 }
178
179
180