libmetis/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 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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 
ubvec
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t * ubvec
Definition: include/metis.h:199
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:198
gk_free
void gk_free(void **ptr1,...)
Definition: memory.c:202
vsize
idx_t idx_t idx_t idx_t idx_t * vsize
Definition: include/metis.h:198
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
iargmin
#define iargmin
Definition: gklib_rename.h:25
PRREAL
#define PRREAL
Definition: include/metis.h:135
ismalloc
#define ismalloc
Definition: gklib_rename.h:68
ComputeVolume
#define ComputeVolume
Definition: rename.h:63
ncon
idx_t * ncon
Definition: include/metis.h:197
ComputePartitionBalance
void ComputePartitionBalance(graph_t *graph, idx_t nparts, idx_t *where, real_t *ubvec)
Definition: libmetis/stat.c:125
nparts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
Definition: include/metis.h:199
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
ComputeCut
#define ComputeCut
Definition: rename.h:62
LTERM
#define LTERM
Definition: gk_defs.h:14
iargmax_strd
#define iargmax_strd
Definition: rename.h:242
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
ComputePartitionInfoBipartite
void ComputePartitionInfoBipartite(graph_t *graph, idx_t nparts, idx_t *where)
Definition: libmetis/stat.c:21
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
iset
#define iset
Definition: gklib_rename.h:67
isum
#define isum
Definition: gklib_rename.h:72
PRIDX
#define PRIDX
Definition: include/metis.h:107
real_t
float real_t
Definition: include/metis.h:132
NULL
#define NULL
Definition: ccolamd.c:609
metislib.h
where
idx_t idx_t idx_t idx_t * where
Definition: include/metis.h:240
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
iargmax
#define iargmax
Definition: gklib_rename.h:23
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
ComputeElementBalance
real_t ComputeElementBalance(idx_t ne, idx_t nparts, idx_t *where)
Definition: libmetis/stat.c:160
graph_t
Definition: libmetis/struct.h:82
idx_t
int32_t idx_t
Definition: include/metis.h:101


gtsam
Author(s):
autogenerated on Sat Nov 16 2024 04:05:00