1 /* This software was developed by Bruce Hendrickson and Robert Leland *
2 * at Sandia National Laboratories under US Department of Energy *
3 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
4
5 #include <stdio.h>
6 #include "defs.h"
7 #include "structs.h"
8
9
makecgraph2(graph,nvtxs,nedges,pcgraph,pcnvtxs,pcnedges,mflag,v2cv,nmerged,using_ewgts,igeom,coords,ccoords)10 void makecgraph2(graph, nvtxs, nedges, pcgraph, pcnvtxs, pcnedges, mflag,
11 v2cv, nmerged, using_ewgts, igeom, coords, ccoords)
12 struct vtx_data **graph; /* array of vtx data for graph */
13 int nvtxs; /* number of vertices in graph */
14 int nedges; /* number of edges in graph */
15 struct vtx_data ***pcgraph; /* coarsened version of graph */
16 int *pcnvtxs; /* number of vtxs in coarsened graph */
17 int *pcnedges; /* number of edges in coarsened graph */
18 int *mflag; /* flag indicating vtx matched or not */
19 int *v2cv; /* mapping from vtxs to coarsened vtxs */
20 int nmerged; /* number of merged vertices */
21 int using_ewgts; /* are edge weights being used? */
22 int igeom; /* dimensions of geometric data */
23 float **coords; /* coordinates for vertices */
24 float **ccoords; /* coordinates for coarsened vertices */
25 {
26 extern double make_cgraph_time;
27 extern int DEBUG_COARSEN; /* debug flag for coarsening output */
28 extern int COARSEN_VWGTS; /* turn off vertex weights in coarse graph? */
29 extern int COARSEN_EWGTS; /* turn off edge weights in coarse graph? */
30 struct vtx_data **cgraph; /* coarsened version of graph */
31 struct vtx_data *links; /* space for all the vertex data */
32 struct vtx_data **gptr; /* loops through cgraph */
33 struct vtx_data *cgptr; /* loops through cgraph */
34 int *iptr; /* loops through integer arrays */
35 int *seenflag; /* flags for vtxs already put in edge list */
36 int *sptr; /* loops through seenflags */
37 float *eweights; /* space for edge weights in coarsened graph */
38 float *ewptr; /* loops through eweights */
39 float *fptr; /* loops through eweights */
40 float ewgt; /* edge weight */
41 double ewgt_sum; /* sum of edge weights */
42 double time; /* timing parameters */
43 int nseen; /* number of edges of coarse graph seen so far */
44 int cnvtxs; /* number of vtxs in coarsened graph */
45 int cnedges; /* twice number of edges in coarsened graph */
46 int neighbor; /* neighboring vertex */
47 int size; /* space needed for coarsened graph */
48 int *edges; /* space for edges in coarsened graph */
49 int *eptr; /* loops through edges data structure */
50 int cvtx; /* vertex number in coarsened graph */
51 int cneighbor; /* neighboring vertex number in coarsened graph */
52 double m1, m2; /* vertex weights of vertices being merged */
53 int v1, v2; /* vertices being merged */
54 int i, j; /* loop counters */
55 double *smalloc(), *srealloc();
56 double seconds();
57 int sfree();
58 void makev2cv();
59
60 /* Compute the number of vertices and edges in the coarsened graph, */
61 /* and construct start pointers into coarsened edge array. */
62 time = seconds();
63
64 *pcnvtxs = cnvtxs = nvtxs - nmerged;
65
66 /* Construct mapping from original graph vtxs to coarsened graph vtxs. */
67 makev2cv(mflag, nvtxs, v2cv);
68
69 /* Compute an upper bound on the number of coarse graph edges. */
70 cnedges = nedges - nmerged;
71
72 /* Now allocate space for the new graph. */
73 *pcgraph = cgraph = (struct vtx_data **) smalloc((unsigned) (cnvtxs + 1) * sizeof(struct vtx_data *));
74 links = (struct vtx_data *) smalloc((unsigned) cnvtxs * sizeof(struct vtx_data));
75
76 size = 2 * cnedges + cnvtxs;
77 edges = (int *) smalloc((unsigned) size * sizeof(int));
78 if (COARSEN_EWGTS) {
79 ewptr = eweights = (float *) smalloc((unsigned) size * sizeof(float));
80 }
81
82 /* Zero all the seen flags. */
83 seenflag = (int *) smalloc((unsigned) (cnvtxs + 1) * sizeof(int));
84 sptr = seenflag;
85 for (i = cnvtxs; i; i--) {
86 *(++sptr) = 0;
87 }
88
89 /* Use the renumbering to fill in the edge lists for the new graph. */
90 /* Note: This assumes coarse graph vertices are encountered in order. */
91 cnedges = 0;
92 eptr = edges;
93 ewgt = 1;
94 sptr = seenflag;
95
96 for (i = 1; i <= nvtxs; i++) {
97 if (mflag[i] > i || mflag[i] == 0) {
98 /* Unmatched edge, or first appearance of matched edge. */
99 nseen = 1;
100 cvtx = v2cv[i];
101 cgptr = cgraph[cvtx] = links++;
102
103 if (COARSEN_VWGTS)
104 cgptr->vwgt = 0;
105 else
106 cgptr->vwgt = 1;
107
108 eptr[0] = cvtx;
109 cgptr->edges = eptr;
110 if (COARSEN_EWGTS) {
111 cgptr->ewgts = ewptr;
112 }
113 else
114 cgptr->ewgts = NULL;
115 *(++sptr) = 0;
116
117 ewgt_sum = 0;
118
119 iptr = graph[i]->edges;
120 if (using_ewgts)
121 fptr = graph[i]->ewgts;
122 for (j = graph[i]->nedges - 1; j; j--) {
123 neighbor = *(++iptr);
124 cneighbor = v2cv[neighbor];
125 if (cneighbor != cvtx) {
126 if (using_ewgts)
127 ewgt = *(++fptr);
128 ewgt_sum += ewgt;
129
130 /* Seenflags being used as map from cvtx to index. */
131 if (seenflag[cneighbor] == 0) { /* New neighbor. */
132 cgptr->edges[nseen] = cneighbor;
133 if (COARSEN_EWGTS)
134 cgptr->ewgts[nseen] = ewgt;
135 seenflag[cneighbor] = nseen++;
136 }
137 else { /* Already seen neighbor. */
138 if (COARSEN_EWGTS)
139 cgptr->ewgts[seenflag[cneighbor]] += ewgt;
140 }
141 }
142 else if (using_ewgts)
143 ++fptr;
144 }
145
146 if (mflag[i] > i) { /* Now handle the matched vertex. */
147 iptr = graph[mflag[i]]->edges;
148 if (using_ewgts)
149 fptr = graph[mflag[i]]->ewgts;
150 for (j = graph[mflag[i]]->nedges - 1; j; j--) {
151 neighbor = *(++iptr);
152 cneighbor = v2cv[neighbor];
153 if (cneighbor != cvtx) {
154 if (using_ewgts)
155 ewgt = *(++fptr);
156 ewgt_sum += ewgt;
157
158 if (seenflag[cneighbor] == 0) { /* New neighbor. */
159 cgptr->edges[nseen] = cneighbor;
160 if (COARSEN_EWGTS)
161 cgptr->ewgts[nseen] = ewgt;
162 seenflag[cneighbor] = nseen++;
163 }
164 else { /* Already seen neighbor. */
165 if (COARSEN_EWGTS)
166 cgptr->ewgts[seenflag[cneighbor]] += ewgt;
167 }
168 }
169 else if (using_ewgts)
170 ++fptr;
171 }
172 }
173 if (COARSEN_EWGTS)
174 cgptr->ewgts[0] = -ewgt_sum;
175 /* Increment pointers into edges list. */
176 cgptr->nedges = nseen;
177 eptr += nseen;
178 if (COARSEN_EWGTS) {
179 ewptr += nseen;
180 }
181
182 /* Now clear the seenflag values. */
183 iptr = cgptr->edges;
184 for (j = nseen - 1; j; j--) {
185 seenflag[*(++iptr)] = 0;
186 }
187
188 cnedges += nseen - 1;
189 }
190 }
191
192 sfree((char *) seenflag);
193
194 /* Form new vertex weights by adding those from contracted edges. */
195 if (COARSEN_VWGTS) {
196 gptr = graph;
197 for (i = 1; i <= nvtxs; i++) {
198 cgraph[v2cv[i]]->vwgt += (*(++gptr))->vwgt;
199 }
200 }
201
202 /* If desired, make new vtx coordinates = center-of-mass of their parents. */
203 if (coords != NULL && ccoords != NULL && igeom > 0) {
204 for (i = 0; i < igeom; i++) {
205 ccoords[i] = (float *) smalloc((unsigned) (cnvtxs + 1) * sizeof(float));
206 }
207 for (j = 1; j <= nvtxs; j++) {
208 if (mflag[j] == 0) {/* If unmatched, leave it alone. */
209 for (i = 0; i < igeom; i++) {
210 ccoords[i][v2cv[j]] = coords[i][j];
211 }
212 }
213 else if (j < mflag[j]) { /* If matched, use center of mass. */
214 v1 = j;
215 v2 = mflag[j];
216 m1 = graph[v1]->vwgt;
217 m2 = graph[v2]->vwgt;
218 for (i = 0; i < igeom; i++) {
219 ccoords[i][v2cv[j]] = (m1 * coords[i][v1] + m2 * coords[i][v2]) / (m1 + m2);
220 }
221 }
222 }
223 }
224
225 cnedges /= 2;
226 *pcnedges = cnedges;
227 size = 2 * cnedges + cnvtxs;
228 edges = (int *) srealloc((char *) edges, (unsigned) size * sizeof(int));
229 if (COARSEN_EWGTS) {
230 eweights = (float *) srealloc((char *) eweights,
231 (unsigned) size * sizeof(float));
232 }
233
234 if (DEBUG_COARSEN > 0) {
235 printf(" Coarse graph has %d vertices and %d edges\n", cnvtxs, cnedges);
236 }
237
238 make_cgraph_time += seconds() - time;
239 }
240