programs/stat.c
Go to the documentation of this file.
1 
14 #include "metisbin.h"
15 
16 
17 /****************************************************************************/
19 /****************************************************************************/
21 {
22  idx_t i, ii, j, k, nvtxs, ncon, nparts, tvwgt;
23  idx_t *xadj, *adjncy, *vwgt, *adjwgt, *kpwgts;
24  real_t *tpwgts, unbalance;
25  idx_t pid, ndom, maxndom, minndom, tndom, *pptr, *pind, *pdom;
26  idx_t ncmps, nover, *cptr, *cind, *cpwgts;
27 
28  nvtxs = graph->nvtxs;
29  ncon = graph->ncon;
30  xadj = graph->xadj;
31  adjncy = graph->adjncy;
32  vwgt = graph->vwgt;
33  adjwgt = graph->adjwgt;
34 
35  nparts = params->nparts;
36  tpwgts = params->tpwgts;
37 
38  /* Compute objective-related infomration */
39  printf(" - Edgecut: %"PRIDX", communication volume: %"PRIDX".\n\n",
40  ComputeCut(graph, where), ComputeVolume(graph, where));
41 
42 
43  /* Compute constraint-related information */
44  kpwgts = ismalloc(ncon*nparts, 0, "ComputePartitionInfo: kpwgts");
45 
46  for (i=0; i<nvtxs; i++) {
47  for (j=0; j<ncon; j++)
48  kpwgts[where[i]*ncon+j] += vwgt[i*ncon+j];
49  }
50 
51  /* Report on balance */
52  printf(" - Balance:\n");
53  for (j=0; j<ncon; j++) {
54  tvwgt = isum(nparts, kpwgts+j, ncon);
55  for (k=0, unbalance=1.0*kpwgts[k*ncon+j]/(tpwgts[k*ncon+j]*tvwgt), i=1; i<nparts; i++) {
56  if (unbalance < 1.0*kpwgts[i*ncon+j]/(tpwgts[i*ncon+j]*tvwgt)) {
57  unbalance = 1.0*kpwgts[i*ncon+j]/(tpwgts[i*ncon+j]*tvwgt);
58  k = i;
59  }
60  }
61  printf(" constraint #%"PRIDX": %5.3"PRREAL" out of %5.3"PRREAL"\n",
62  j, unbalance,
63  1.0*nparts*vwgt[ncon*iargmax_strd(nvtxs, vwgt+j, ncon)+j]/
64  (1.0*isum(nparts, kpwgts+j, ncon)));
65  }
66  printf("\n");
67 
68  if (ncon == 1) {
69  tvwgt = isum(nparts, kpwgts, 1);
70  for (k=0, unbalance=kpwgts[k]/(tpwgts[k]*tvwgt), i=1; i<nparts; i++) {
71  if (unbalance < kpwgts[i]/(tpwgts[i]*tvwgt)) {
72  unbalance = kpwgts[i]/(tpwgts[i]*tvwgt);
73  k = i;
74  }
75  }
76 
77  printf(" - Most overweight partition:\n"
78  " pid: %"PRIDX", actual: %"PRIDX", desired: %"PRIDX", ratio: %.2"PRREAL".\n\n",
79  k, kpwgts[k], (idx_t)(tvwgt*tpwgts[k]), unbalance);
80  }
81 
82  gk_free((void **)&kpwgts, LTERM);
83 
84 
85  /* Compute subdomain adjacency information */
86  pptr = imalloc(nparts+1, "ComputePartitionInfo: pptr");
87  pind = imalloc(nvtxs, "ComputePartitionInfo: pind");
88  pdom = imalloc(nparts, "ComputePartitionInfo: pdom");
89 
90  iarray2csr(nvtxs, nparts, where, pptr, pind);
91 
92  maxndom = nparts+1;
93  minndom = 0;
94  for (tndom=0, pid=0; pid<nparts; pid++) {
95  iset(nparts, 0, pdom);
96  for (ii=pptr[pid]; ii<pptr[pid+1]; ii++) {
97  i = pind[ii];
98  for (j=xadj[i]; j<xadj[i+1]; j++)
99  pdom[where[adjncy[j]]] += adjwgt[j];
100  }
101  pdom[pid] = 0;
102  for (ndom=0, i=0; i<nparts; i++)
103  ndom += (pdom[i] > 0 ? 1 : 0);
104  tndom += ndom;
105  if (pid == 0 || maxndom < ndom)
106  maxndom = ndom;
107  if (pid == 0 || minndom > ndom)
108  minndom = ndom;
109  }
110 
111  printf(" - Subdomain connectivity: max: %"PRIDX", min: %"PRIDX", avg: %.2"PRREAL"\n\n",
112  maxndom, minndom, 1.0*tndom/nparts);
113 
114  gk_free((void **)&pptr, &pind, &pdom, LTERM);
115 
116 
117  /* Compute subdomain adjacency information */
118  cptr = imalloc(nvtxs+1, "ComputePartitionInfo: cptr");
119  cind = imalloc(nvtxs, "ComputePartitionInfo: cind");
120  cpwgts = ismalloc(nparts, 0, "ComputePartitionInfo: cpwgts");
121 
122  ncmps = FindPartitionInducedComponents(graph, where, cptr, cind);
123  if (ncmps == nparts)
124  printf(" - Each partition is contiguous.\n");
125  else {
126  if (IsConnected(graph, 0)) {
127  for (nover=0, i=0; i<ncmps; i++) {
128  cpwgts[where[cind[cptr[i]]]]++;
129  if (cpwgts[where[cind[cptr[i]]]] == 2)
130  nover++;
131  }
132  printf(" - There are %"PRIDX" non-contiguous partitions.\n"
133  " Total components after removing the cut edges: %"PRIDX",\n"
134  " max components: %"PRIDX" for pid: %"PRIDX".\n",
135  nover, ncmps, imax(nparts, cpwgts), (idx_t)iargmax(nparts, cpwgts));
136  }
137  else {
138  printf(" - The original graph had %"PRIDX" connected components and the resulting\n"
139  " partitioning after removing the cut edges has %"PRIDX" components.",
140  FindPartitionInducedComponents(graph, NULL, NULL, NULL), ncmps);
141  }
142  }
143 
144  gk_free((void **)&cptr, &cind, &cpwgts, LTERM);
145 
146 }
147 
148 
idx_t idx_t idx_t idx_t * vwgt
Definition: fis.c:15
#define iarray2csr
Definition: gklib_rename.h:26
idx_t * xadj
#define imalloc
Definition: gklib_rename.h:42
idx_t * adjwgt
#define ismalloc
Definition: gklib_rename.h:68
idx_t idx_t * xadj
real_t * tpwgts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
idx_t nvtxs
#define iargmax
Definition: gklib_rename.h:23
NonlinearFactorGraph graph
static const SmartProjectionParams params
#define PRIDX
#define iargmax_strd
Definition: rename.h:242
void ComputePartitionInfo(params_t *params, graph_t *graph, idx_t *where)
Definition: programs/stat.c:20
int32_t idx_t
#define IsConnected
Definition: rename.h:54
idx_t ncon
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
#define ComputeVolume
Definition: rename.h:63
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
#define isum
Definition: gklib_rename.h:72
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define iset
Definition: gklib_rename.h:67
void gk_free(void **ptr1,...)
Definition: memory.c:202
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
idx_t idx_t idx_t * adjncy
#define PRREAL
#define imax
Definition: gklib_rename.h:43
idx_t nparts
#define ComputeCut
Definition: rename.h:62
std::ptrdiff_t j
#define FindPartitionInducedComponents
Definition: rename.h:53
#define LTERM
Definition: gk_defs.h:14
idx_t * vwgt


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:36:20