compress.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * compress.c
5  *
6  * This file contains code for compressing nodes with identical adjacency
7  * structure and for prunning dense columns
8  *
9  * Started 9/17/97
10  * George
11  */
12 
13 #include "metislib.h"
14 
15 /*************************************************************************/
24 /**************************************************************************/
26  idx_t *vwgt, idx_t *cptr, idx_t *cind)
27 {
28  idx_t i, ii, iii, j, jj, k, l, cnvtxs, cnedges;
29  idx_t *cxadj, *cadjncy, *cvwgt, *mark, *map;
30  ikv_t *keys;
32 
33  mark = ismalloc(nvtxs, -1, "CompressGraph: mark");
34  map = ismalloc(nvtxs, -1, "CompressGraph: map");
35  keys = ikvmalloc(nvtxs, "CompressGraph: keys");
36 
37  /* Compute a key for each adjacency list */
38  for (i=0; i<nvtxs; i++) {
39  k = 0;
40  for (j=xadj[i]; j<xadj[i+1]; j++)
41  k += adjncy[j];
42  keys[i].key = k+i; /* Add the diagonal entry as well */
43  keys[i].val = i;
44  }
45 
46  ikvsorti(nvtxs, keys);
47 
48  l = cptr[0] = 0;
49  for (cnvtxs=i=0; i<nvtxs; i++) {
50  ii = keys[i].val;
51  if (map[ii] == -1) {
52  mark[ii] = i; /* Add the diagonal entry */
53  for (j=xadj[ii]; j<xadj[ii+1]; j++)
54  mark[adjncy[j]] = i;
55 
56  map[ii] = cnvtxs;
57  cind[l++] = ii;
58 
59  for (j=i+1; j<nvtxs; j++) {
60  iii = keys[j].val;
61 
62  if (keys[i].key != keys[j].key || xadj[ii+1]-xadj[ii] != xadj[iii+1]-xadj[iii])
63  break; /* Break if keys or degrees are different */
64 
65  if (map[iii] == -1) { /* Do a comparison if iii has not been mapped */
66  for (jj=xadj[iii]; jj<xadj[iii+1]; jj++) {
67  if (mark[adjncy[jj]] != i)
68  break;
69  }
70 
71  if (jj == xadj[iii+1]) { /* Identical adjacency structure */
72  map[iii] = cnvtxs;
73  cind[l++] = iii;
74  }
75  }
76  }
77 
78  cptr[++cnvtxs] = l;
79  }
80  }
81 
82  IFSET(ctrl->dbglvl, METIS_DBG_INFO,
83  printf(" Compression: reduction in # of vertices: %"PRIDX".\n", nvtxs-cnvtxs));
84 
85 
86  if (cnvtxs < COMPRESSION_FRACTION*nvtxs) {
87  /* Sufficient compression is possible, so go ahead and create the
88  compressed graph */
89 
90  graph = CreateGraph();
91 
92  cnedges = 0;
93  for (i=0; i<cnvtxs; i++) {
94  ii = cind[cptr[i]];
95  cnedges += xadj[ii+1]-xadj[ii];
96  }
97 
98  /* Allocate memory for the compressed graph */
99  cxadj = graph->xadj = imalloc(cnvtxs+1, "CompressGraph: xadj");
100  cvwgt = graph->vwgt = ismalloc(cnvtxs, 0, "CompressGraph: vwgt");
101  cadjncy = graph->adjncy = imalloc(cnedges, "CompressGraph: adjncy");
102  graph->adjwgt = ismalloc(cnedges, 1, "CompressGraph: adjwgt");
103 
104  /* Now go and compress the graph */
105  iset(nvtxs, -1, mark);
106  l = cxadj[0] = 0;
107  for (i=0; i<cnvtxs; i++) {
108  mark[i] = i; /* Remove any dioganal entries in the compressed graph */
109  for (j=cptr[i]; j<cptr[i+1]; j++) {
110  ii = cind[j];
111 
112  /* accumulate the vertex weights of the consistuent vertices */
113  cvwgt[i] += (vwgt == NULL ? 1 : vwgt[ii]);
114 
115  /* generate the combined adjancency list */
116  for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
117  k = map[adjncy[jj]];
118  if (mark[k] != i) {
119  mark[k] = i;
120  cadjncy[l++] = k;
121  }
122  }
123  }
124  cxadj[i+1] = l;
125  }
126 
127  graph->nvtxs = cnvtxs;
128  graph->nedges = l;
129  graph->ncon = 1;
130 
133  }
134 
135  gk_free((void **)&keys, &map, &mark, LTERM);
136 
137  return graph;
138 
139 }
140 
141 
142 
143 /*************************************************************************/
149 /*************************************************************************/
151  idx_t *vwgt, idx_t *iperm, real_t factor)
152 {
153  idx_t i, j, k, l, nlarge, pnvtxs, pnedges;
154  idx_t *pxadj, *padjncy, *padjwgt, *pvwgt;
155  idx_t *perm;
156  graph_t *graph=NULL;
157 
158  perm = imalloc(nvtxs, "PruneGraph: perm");
159 
160  factor = factor*xadj[nvtxs]/nvtxs;
161 
162  pnvtxs = pnedges = nlarge = 0;
163  for (i=0; i<nvtxs; i++) {
164  if (xadj[i+1]-xadj[i] < factor) {
165  perm[i] = pnvtxs;
166  iperm[pnvtxs++] = i;
167  pnedges += xadj[i+1]-xadj[i];
168  }
169  else {
170  perm[i] = nvtxs - ++nlarge;
171  iperm[nvtxs-nlarge] = i;
172  }
173  }
174 
175  IFSET(ctrl->dbglvl, METIS_DBG_INFO,
176  printf(" Pruned %"PRIDX" of %"PRIDX" vertices.\n", nlarge, nvtxs));
177 
178 
179  if (nlarge > 0 && nlarge < nvtxs) {
180  /* Prunning is possible, so go ahead and create the prunned graph */
181  graph = CreateGraph();
182 
183  /* Allocate memory for the prunned graph*/
184  pxadj = graph->xadj = imalloc(pnvtxs+1, "PruneGraph: xadj");
185  pvwgt = graph->vwgt = imalloc(pnvtxs, "PruneGraph: vwgt");
186  padjncy = graph->adjncy = imalloc(pnedges, "PruneGraph: adjncy");
187  graph->adjwgt = ismalloc(pnedges, 1, "PruneGraph: adjwgt");
188 
189  pxadj[0] = pnedges = l = 0;
190  for (i=0; i<nvtxs; i++) {
191  if (xadj[i+1]-xadj[i] < factor) {
192  pvwgt[l] = (vwgt == NULL ? 1 : vwgt[i]);
193 
194  for (j=xadj[i]; j<xadj[i+1]; j++) {
195  k = perm[adjncy[j]];
196  if (k < pnvtxs)
197  padjncy[pnedges++] = k;
198  }
199  pxadj[++l] = pnedges;
200  }
201  }
202 
203  graph->nvtxs = pnvtxs;
204  graph->nedges = pnedges;
205  graph->ncon = 1;
206 
209  }
210  else if (nlarge > 0 && nlarge == nvtxs) {
211  IFSET(ctrl->dbglvl, METIS_DBG_INFO,
212  printf(" Pruning is ignored as it removes all vertices.\n"));
213  nlarge = 0;
214  }
215 
216 
217  gk_free((void **)&perm, LTERM);
218 
219  return graph;
220 }
221 
222 
223 
224 
225 
226 
227 
228 
229 
SetupGraph_tvwgt
#define SetupGraph_tvwgt
Definition: rename.h:92
perm
idx_t idx_t idx_t idx_t idx_t * perm
Definition: include/metis.h:223
SetupGraph_label
#define SetupGraph_label
Definition: rename.h:93
CreateGraph
#define CreateGraph
Definition: rename.h:95
keys
const KeyVector keys
Definition: testRegularImplicitSchurFactor.cpp:40
gk_free
void gk_free(void **ptr1,...)
Definition: memory.c:202
ctrl_t
Definition: libmetis/struct.h:139
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
imalloc
#define imalloc
Definition: gklib_rename.h:42
ikvmalloc
#define ikvmalloc
Definition: gklib_rename.h:35
IFSET
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
CompressGraph
graph_t * CompressGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *cptr, idx_t *cind)
Definition: compress.c:25
ikvsorti
#define ikvsorti
Definition: gklib_rename.h:40
ismalloc
#define ismalloc
Definition: gklib_rename.h:68
iperm
idx_t idx_t idx_t idx_t idx_t idx_t * iperm
Definition: include/metis.h:223
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
METIS_DBG_INFO
@ METIS_DBG_INFO
Definition: include/metis.h:340
l
static const Line3 l(Rot3(), 1, 1)
LTERM
#define LTERM
Definition: gk_defs.h:14
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
key
const gtsam::Symbol key('X', 0)
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
iset
#define iset
Definition: gklib_rename.h:67
PruneGraph
graph_t * PruneGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *iperm, real_t factor)
Definition: compress.c:150
PRIDX
#define PRIDX
Definition: include/metis.h:107
real_t
float real_t
Definition: include/metis.h:132
ctrl_t::dbglvl
mdbglvl_et dbglvl
Definition: libmetis/struct.h:142
NULL
#define NULL
Definition: ccolamd.c:609
metislib.h
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
COMPRESSION_FRACTION
#define COMPRESSION_FRACTION
Definition: libmetis/defs.h:47
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:02:01