Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
graph.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * graph.c
5  *
6  * This file contains functions that deal with setting up the graphs
7  * for METIS.
8  *
9  * Started 7/25/97
10  * George
11  *
12  * $Id: graph.c,v 1.1 1998/11/27 17:59:15 karypis Exp $
13  *
14  */
15 
16 #include <metis.h>
17 
18 /*************************************************************************
19 * This function sets up the graph from the user input
20 **************************************************************************/
21 void SetUpGraph(GraphType *graph, int OpType, int nvtxs, int ncon,
22  idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int wgtflag)
23 {
24  int i, j, k, sum, gsize;
25  float *nvwgt;
26  idxtype tvwgt[MAXNCON];
27 
28  if (OpType == OP_KMETIS && ncon == 1 && (wgtflag&2) == 0 && (wgtflag&1) == 0) {
29  SetUpGraphKway(graph, nvtxs, xadj, adjncy);
30  return;
31  }
32 
33  InitGraph(graph);
34 
35  graph->nvtxs = nvtxs;
36  graph->nedges = xadj[nvtxs];
37  graph->ncon = ncon;
38  graph->xadj = xadj;
39  graph->adjncy = adjncy;
40 
41  if (ncon == 1) { /* We are in the non mC mode */
42  gsize = 0;
43  if ((wgtflag&2) == 0)
44  gsize += nvtxs;
45  if ((wgtflag&1) == 0)
46  gsize += graph->nedges;
47 
48  gsize += 2*nvtxs;
49 
50  graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
51 
52  /* Create the vertex/edge weight vectors if they are not supplied */
53  gsize = 0;
54  if ((wgtflag&2) == 0) {
55  vwgt = graph->vwgt = idxset(nvtxs, 1, graph->gdata);
56  gsize += nvtxs;
57  }
58  else
59  graph->vwgt = vwgt;
60 
61  if ((wgtflag&1) == 0) {
62  adjwgt = graph->adjwgt = idxset(graph->nedges, 1, graph->gdata+gsize);
63  gsize += graph->nedges;
64  }
65  else
66  graph->adjwgt = adjwgt;
67 
68 
69  /* Compute the initial values of the adjwgtsum */
70  graph->adjwgtsum = graph->gdata + gsize;
71  gsize += nvtxs;
72 
73  for (i=0; i<nvtxs; i++) {
74  sum = 0;
75  for (j=xadj[i]; j<xadj[i+1]; j++)
76  sum += adjwgt[j];
77  graph->adjwgtsum[i] = sum;
78  }
79 
80  graph->cmap = graph->gdata + gsize;
81  gsize += nvtxs;
82 
83  }
84  else { /* Set up the graph in MOC mode */
85  gsize = 0;
86  if ((wgtflag&1) == 0)
87  gsize += graph->nedges;
88 
89  gsize += 2*nvtxs;
90 
91  graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
92  gsize = 0;
93 
94  for (i=0; i<ncon; i++)
95  tvwgt[i] = idxsum_strd(nvtxs, vwgt+i, ncon);
96 
97  nvwgt = graph->nvwgt = fmalloc(ncon*nvtxs, "SetUpGraph: nvwgt");
98 
99  for (i=0; i<nvtxs; i++) {
100  for (j=0; j<ncon; j++)
101  nvwgt[i*ncon+j] = (1.0*vwgt[i*ncon+j])/(1.0*tvwgt[j]);
102  }
103 
104 
105  /* Create the edge weight vectors if they are not supplied */
106  if ((wgtflag&1) == 0) {
107  adjwgt = graph->adjwgt = idxset(graph->nedges, 1, graph->gdata+gsize);
108  gsize += graph->nedges;
109  }
110  else
111  graph->adjwgt = adjwgt;
112 
113  /* Compute the initial values of the adjwgtsum */
114  graph->adjwgtsum = graph->gdata + gsize;
115  gsize += nvtxs;
116 
117  for (i=0; i<nvtxs; i++) {
118  sum = 0;
119  for (j=xadj[i]; j<xadj[i+1]; j++)
120  sum += adjwgt[j];
121  graph->adjwgtsum[i] = sum;
122  }
123 
124  graph->cmap = graph->gdata + gsize;
125  gsize += nvtxs;
126 
127  }
128 
129  if (OpType != OP_KMETIS && OpType != OP_KVMETIS) {
130  graph->label = idxmalloc(nvtxs, "SetUpGraph: label");
131 
132  for (i=0; i<nvtxs; i++)
133  graph->label[i] = i;
134  }
135 
136 }
137 
138 
139 /*************************************************************************
140 * This function sets up the graph from the user input
141 **************************************************************************/
142 void SetUpGraphKway(GraphType *graph, int nvtxs, idxtype *xadj, idxtype *adjncy)
143 {
144  int i;
145 
146  InitGraph(graph);
147 
148  graph->nvtxs = nvtxs;
149  graph->nedges = xadj[nvtxs];
150  graph->ncon = 1;
151  graph->xadj = xadj;
152  graph->vwgt = NULL;
153  graph->adjncy = adjncy;
154  graph->adjwgt = NULL;
155 
156  graph->gdata = idxmalloc(2*nvtxs, "SetUpGraph: gdata");
157  graph->adjwgtsum = graph->gdata;
158  graph->cmap = graph->gdata + nvtxs;
159 
160  /* Compute the initial values of the adjwgtsum */
161  for (i=0; i<nvtxs; i++)
162  graph->adjwgtsum[i] = xadj[i+1]-xadj[i];
163 
164 }
165 
166 
167 
168 /*************************************************************************
169 * This function sets up the graph from the user input
170 **************************************************************************/
171 void SetUpGraph2(GraphType *graph, int nvtxs, int ncon, idxtype *xadj,
172  idxtype *adjncy, float *nvwgt, idxtype *adjwgt)
173 {
174  int i, j, sum;
175 
176  InitGraph(graph);
177 
178  graph->nvtxs = nvtxs;
179  graph->nedges = xadj[nvtxs];
180  graph->ncon = ncon;
181  graph->xadj = xadj;
182  graph->adjncy = adjncy;
183  graph->adjwgt = adjwgt;
184 
185  graph->nvwgt = fmalloc(nvtxs*ncon, "SetUpGraph2: graph->nvwgt");
186  scopy(nvtxs*ncon, nvwgt, graph->nvwgt);
187 
188  graph->gdata = idxmalloc(2*nvtxs, "SetUpGraph: gdata");
189 
190  /* Compute the initial values of the adjwgtsum */
191  graph->adjwgtsum = graph->gdata;
192  for (i=0; i<nvtxs; i++) {
193  sum = 0;
194  for (j=xadj[i]; j<xadj[i+1]; j++)
195  sum += adjwgt[j];
196  graph->adjwgtsum[i] = sum;
197  }
198 
199  graph->cmap = graph->gdata+nvtxs;
200 
201  graph->label = idxmalloc(nvtxs, "SetUpGraph: label");
202  for (i=0; i<nvtxs; i++)
203  graph->label[i] = i;
204 
205 }
206 
207 
208 /*************************************************************************
209 * This function sets up the graph from the user input
210 **************************************************************************/
211 void VolSetUpGraph(GraphType *graph, int OpType, int nvtxs, int ncon, idxtype *xadj,
212  idxtype *adjncy, idxtype *vwgt, idxtype *vsize, int wgtflag)
213 {
214  int i, j, k, sum, gsize;
215  idxtype *adjwgt;
216  float *nvwgt;
217  idxtype tvwgt[MAXNCON];
218 
219  InitGraph(graph);
220 
221  graph->nvtxs = nvtxs;
222  graph->nedges = xadj[nvtxs];
223  graph->ncon = ncon;
224  graph->xadj = xadj;
225  graph->adjncy = adjncy;
226 
227  if (ncon == 1) { /* We are in the non mC mode */
228  gsize = graph->nedges; /* This is for the edge weights */
229  if ((wgtflag&2) == 0)
230  gsize += nvtxs; /* vwgts */
231  if ((wgtflag&1) == 0)
232  gsize += nvtxs; /* vsize */
233 
234  gsize += 2*nvtxs;
235 
236  graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
237 
238  /* Create the vertex/edge weight vectors if they are not supplied */
239  gsize = 0;
240  if ((wgtflag&2) == 0) {
241  vwgt = graph->vwgt = idxset(nvtxs, 1, graph->gdata);
242  gsize += nvtxs;
243  }
244  else
245  graph->vwgt = vwgt;
246 
247  if ((wgtflag&1) == 0) {
248  vsize = graph->vsize = idxset(nvtxs, 1, graph->gdata);
249  gsize += nvtxs;
250  }
251  else
252  graph->vsize = vsize;
253 
254  /* Allocate memory for edge weights and initialize them to the sum of the vsize */
255  adjwgt = graph->adjwgt = graph->gdata+gsize;
256  gsize += graph->nedges;
257 
258  for (i=0; i<nvtxs; i++) {
259  for (j=xadj[i]; j<xadj[i+1]; j++)
260  adjwgt[j] = 1+vsize[i]+vsize[adjncy[j]];
261  }
262 
263 
264  /* Compute the initial values of the adjwgtsum */
265  graph->adjwgtsum = graph->gdata + gsize;
266  gsize += nvtxs;
267 
268  for (i=0; i<nvtxs; i++) {
269  sum = 0;
270  for (j=xadj[i]; j<xadj[i+1]; j++)
271  sum += adjwgt[j];
272  graph->adjwgtsum[i] = sum;
273  }
274 
275  graph->cmap = graph->gdata + gsize;
276  gsize += nvtxs;
277 
278  }
279  else { /* Set up the graph in MOC mode */
280  gsize = graph->nedges;
281  if ((wgtflag&1) == 0)
282  gsize += nvtxs;
283 
284  gsize += 2*nvtxs;
285 
286  graph->gdata = idxmalloc(gsize, "SetUpGraph: gdata");
287  gsize = 0;
288 
289  /* Create the normalized vertex weights along each constrain */
290  if ((wgtflag&2) == 0)
291  vwgt = idxsmalloc(nvtxs, 1, "SetUpGraph: vwgt");
292 
293  for (i=0; i<ncon; i++)
294  tvwgt[i] = idxsum_strd(nvtxs, vwgt+i, ncon);
295 
296  nvwgt = graph->nvwgt = fmalloc(ncon*nvtxs, "SetUpGraph: nvwgt");
297 
298  for (i=0; i<nvtxs; i++) {
299  for (j=0; j<ncon; j++)
300  nvwgt[i*ncon+j] = (1.0*vwgt[i*ncon+j])/(1.0*tvwgt[j]);
301  }
302  if ((wgtflag&2) == 0)
303  free(vwgt);
304 
305 
306  /* Create the vsize vector if it is not supplied */
307  if ((wgtflag&1) == 0) {
308  vsize = graph->vsize = idxset(nvtxs, 1, graph->gdata);
309  gsize += nvtxs;
310  }
311  else
312  graph->vsize = vsize;
313 
314  /* Allocate memory for edge weights and initialize them to the sum of the vsize */
315  adjwgt = graph->adjwgt = graph->gdata+gsize;
316  gsize += graph->nedges;
317 
318  for (i=0; i<nvtxs; i++) {
319  for (j=xadj[i]; j<xadj[i+1]; j++)
320  adjwgt[j] = 1+vsize[i]+vsize[adjncy[j]];
321  }
322 
323  /* Compute the initial values of the adjwgtsum */
324  graph->adjwgtsum = graph->gdata + gsize;
325  gsize += nvtxs;
326 
327  for (i=0; i<nvtxs; i++) {
328  sum = 0;
329  for (j=xadj[i]; j<xadj[i+1]; j++)
330  sum += adjwgt[j];
331  graph->adjwgtsum[i] = sum;
332  }
333 
334  graph->cmap = graph->gdata + gsize;
335  gsize += nvtxs;
336 
337  }
338 
339  if (OpType != OP_KVMETIS) {
340  graph->label = idxmalloc(nvtxs, "SetUpGraph: label");
341 
342  for (i=0; i<nvtxs; i++)
343  graph->label[i] = i;
344  }
345 
346 }
347 
348 
349 /*************************************************************************
350 * This function randomly permutes the adjacency lists of a graph
351 **************************************************************************/
353 {
354  int i, j, k, l, tmp, nvtxs;
355  idxtype *xadj, *adjncy, *adjwgt;
356 
357  nvtxs = graph->nvtxs;
358  xadj = graph->xadj;
359  adjncy = graph->adjncy;
360  adjwgt = graph->adjwgt;
361 
362  for (i=0; i<nvtxs; i++) {
363  l = xadj[i+1]-xadj[i];
364  for (j=xadj[i]; j<xadj[i+1]; j++) {
365  k = xadj[i] + RandomInRange(l);
366  SWAP(adjncy[j], adjncy[k], tmp);
367  SWAP(adjwgt[j], adjwgt[k], tmp);
368  }
369  }
370 }
371 
372 
373 /*************************************************************************
374 * This function checks whether or not partition pid is contigous
375 **************************************************************************/
376 int IsConnectedSubdomain(CtrlType *ctrl, GraphType *graph, int pid, int report)
377 {
378  int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
379  idxtype *xadj, *adjncy, *where, *touched, *queue;
380  idxtype *cptr;
381 
382  nvtxs = graph->nvtxs;
383  xadj = graph->xadj;
384  adjncy = graph->adjncy;
385  where = graph->where;
386 
387  touched = idxsmalloc(nvtxs, 0, "IsConnected: touched");
388  queue = idxmalloc(nvtxs, "IsConnected: queue");
389  cptr = idxmalloc(nvtxs, "IsConnected: cptr");
390 
391  nleft = 0;
392  for (i=0; i<nvtxs; i++) {
393  if (where[i] == pid)
394  nleft++;
395  }
396 
397  for (i=0; i<nvtxs; i++) {
398  if (where[i] == pid)
399  break;
400  }
401 
402  touched[i] = 1;
403  queue[0] = i;
404  first = 0; last = 1;
405 
406  cptr[0] = 0; /* This actually points to queue */
407  ncmps = 0;
408  while (first != nleft) {
409  if (first == last) { /* Find another starting vertex */
410  cptr[++ncmps] = first;
411  for (i=0; i<nvtxs; i++) {
412  if (where[i] == pid && !touched[i])
413  break;
414  }
415  queue[last++] = i;
416  touched[i] = 1;
417  }
418 
419  i = queue[first++];
420  for (j=xadj[i]; j<xadj[i+1]; j++) {
421  k = adjncy[j];
422  if (where[k] == pid && !touched[k]) {
423  queue[last++] = k;
424  touched[k] = 1;
425  }
426  }
427  }
428  cptr[++ncmps] = first;
429 
430  if (ncmps > 1 && report) {
431  printf("The graph has %d connected components in partition %d:\t", ncmps, pid);
432  for (i=0; i<ncmps; i++) {
433  wgt = 0;
434  for (j=cptr[i]; j<cptr[i+1]; j++)
435  wgt += graph->vwgt[queue[j]];
436  printf("[%5d %5d] ", cptr[i+1]-cptr[i], wgt);
437  /*
438  if (cptr[i+1]-cptr[i] == 1)
439  printf("[%d %d] ", queue[cptr[i]], xadj[queue[cptr[i]]+1]-xadj[queue[cptr[i]]]);
440  */
441  }
442  printf("\n");
443  }
444 
445  GKfree(&touched, &queue, &cptr, LTERM);
446 
447  return (ncmps == 1 ? 1 : 0);
448 }
449 
450 
451 /*************************************************************************
452 * This function checks whether a graph is contigous or not
453 **************************************************************************/
454 int IsConnected(CtrlType *ctrl, GraphType *graph, int report)
455 {
456  int i, j, k, nvtxs, first, last;
457  idxtype *xadj, *adjncy, *touched, *queue;
458 
459  nvtxs = graph->nvtxs;
460  xadj = graph->xadj;
461  adjncy = graph->adjncy;
462 
463  touched = idxsmalloc(nvtxs, 0, "IsConnected: touched");
464  queue = idxmalloc(nvtxs, "IsConnected: queue");
465 
466  touched[0] = 1;
467  queue[0] = 0;
468  first = 0; last = 1;
469 
470  while (first < last) {
471  i = queue[first++];
472  for (j=xadj[i]; j<xadj[i+1]; j++) {
473  k = adjncy[j];
474  if (!touched[k]) {
475  queue[last++] = k;
476  touched[k] = 1;
477  }
478  }
479  }
480 
481  if (first != nvtxs && report)
482  printf("The graph is not connected. It has %d disconnected vertices!\n", nvtxs-first);
483 
484  return (first == nvtxs ? 1 : 0);
485 }
486 
487 
488 /*************************************************************************
489 * This function checks whether or not partition pid is contigous
490 **************************************************************************/
491 int IsConnected2(GraphType *graph, int report)
492 {
493  int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
494  idxtype *xadj, *adjncy, *where, *touched, *queue;
495  idxtype *cptr;
496 
497  nvtxs = graph->nvtxs;
498  xadj = graph->xadj;
499  adjncy = graph->adjncy;
500  where = graph->where;
501 
502  touched = idxsmalloc(nvtxs, 0, "IsConnected: touched");
503  queue = idxmalloc(nvtxs, "IsConnected: queue");
504  cptr = idxmalloc(nvtxs, "IsConnected: cptr");
505 
506  nleft = nvtxs;
507  touched[0] = 1;
508  queue[0] = 0;
509  first = 0; last = 1;
510 
511  cptr[0] = 0; /* This actually points to queue */
512  ncmps = 0;
513  while (first != nleft) {
514  if (first == last) { /* Find another starting vertex */
515  cptr[++ncmps] = first;
516  for (i=0; i<nvtxs; i++) {
517  if (!touched[i])
518  break;
519  }
520  queue[last++] = i;
521  touched[i] = 1;
522  }
523 
524  i = queue[first++];
525  for (j=xadj[i]; j<xadj[i+1]; j++) {
526  k = adjncy[j];
527  if (!touched[k]) {
528  queue[last++] = k;
529  touched[k] = 1;
530  }
531  }
532  }
533  cptr[++ncmps] = first;
534 
535  if (ncmps > 1 && report) {
536  printf("%d connected components:\t", ncmps);
537  for (i=0; i<ncmps; i++) {
538  if (cptr[i+1]-cptr[i] > 200)
539  printf("[%5d] ", cptr[i+1]-cptr[i]);
540  }
541  printf("\n");
542  }
543 
544  GKfree(&touched, &queue, &cptr, LTERM);
545 
546  return (ncmps == 1 ? 1 : 0);
547 }
548 
549 
550 /*************************************************************************
551 * This function returns the number of connected components in cptr,cind
552 * The separator of the graph is used to split it and then find its components.
553 **************************************************************************/
555 {
556  int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
557  idxtype *xadj, *adjncy, *where, *touched, *queue;
558 
559  nvtxs = graph->nvtxs;
560  xadj = graph->xadj;
561  adjncy = graph->adjncy;
562  where = graph->where;
563 
564  touched = idxsmalloc(nvtxs, 0, "IsConnected: queue");
565 
566  for (i=0; i<graph->nbnd; i++)
567  touched[graph->bndind[i]] = 1;
568 
569  queue = cind;
570 
571  nleft = 0;
572  for (i=0; i<nvtxs; i++) {
573  if (where[i] != 2)
574  nleft++;
575  }
576 
577  for (i=0; i<nvtxs; i++) {
578  if (where[i] != 2)
579  break;
580  }
581 
582  touched[i] = 1;
583  queue[0] = i;
584  first = 0; last = 1;
585 
586  cptr[0] = 0; /* This actually points to queue */
587  ncmps = 0;
588  while (first != nleft) {
589  if (first == last) { /* Find another starting vertex */
590  cptr[++ncmps] = first;
591  for (i=0; i<nvtxs; i++) {
592  if (!touched[i])
593  break;
594  }
595  queue[last++] = i;
596  touched[i] = 1;
597  }
598 
599  i = queue[first++];
600  for (j=xadj[i]; j<xadj[i+1]; j++) {
601  k = adjncy[j];
602  if (!touched[k]) {
603  queue[last++] = k;
604  touched[k] = 1;
605  }
606  }
607  }
608  cptr[++ncmps] = first;
609 
610  free(touched);
611 
612  return ncmps;
613 }
614 
615 
616 
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
#define RandomizeGraph
Definition: rename.h:76
int nbnd
Definition: struct.h:177
#define scopy(n, a, b)
Definition: macros.h:43
#define RandomInRange(u)
Definition: macros.h:23
#define SetUpGraph
Definition: rename.h:72
#define fmalloc
Definition: rename.h:384
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
int idxtype
Definition: struct.h:19
#define SetUpGraphKway
Definition: rename.h:73
#define SetUpGraph2
Definition: rename.h:74
#define idxsmalloc
Definition: rename.h:386
#define OP_KVMETIS
Definition: defs.h:94
idxtype * label
Definition: struct.h:170
#define IsConnected2
Definition: rename.h:79
#define IsConnected
Definition: rename.h:78
#define IsConnectedSubdomain
Definition: rename.h:77
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
void GKfree(void **ptr1,...)
Definition: util.c:121
int ncon
Definition: struct.h:194
#define MAXNCON
Definition: defs.h:20
#define VolSetUpGraph
Definition: rename.h:75
idxtype * bndind
Definition: struct.h:178
#define FindComponents
Definition: rename.h:80
#define OP_KMETIS
Definition: defs.h:90
idxtype * vwgt
Definition: struct.h:163
int nedges
Definition: struct.h:161
#define idxmalloc
Definition: rename.h:383
idxtype * gdata
Definition: struct.h:157
int nvtxs
Definition: struct.h:161
#define SWAP(a, b, tmp)
Definition: macros.h:36
#define idxsum_strd
Definition: rename.h:400
float * nvwgt
Definition: struct.h:195
idxtype * vsize
Definition: struct.h:164
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define InitGraph
Definition: rename.h:168