GKlib/graph.c
Go to the documentation of this file.
1 
10 #include <GKlib.h>
11 
12 #define OMPMINOPS 50000
13 
14 /*************************************************************************/
18 /**************************************************************************/
20 {
22 
23  graph = (gk_graph_t *)gk_malloc(sizeof(gk_graph_t), "gk_graph_Create: graph");
24 
25  gk_graph_Init(graph);
26 
27  return graph;
28 }
29 
30 
31 /*************************************************************************/
35 /*************************************************************************/
37 {
38  memset(graph, 0, sizeof(gk_graph_t));
39  graph->nvtxs = -1;
40 }
41 
42 
43 /*************************************************************************/
47 /*************************************************************************/
49 {
50  if (*graph == NULL)
51  return;
52  gk_graph_FreeContents(*graph);
53  gk_free((void **)graph, LTERM);
54 }
55 
56 
57 /*************************************************************************/
62 /*************************************************************************/
64 {
65  gk_free((void *)&graph->xadj, &graph->adjncy,
66  &graph->iadjwgt, &graph->fadjwgt,
67  &graph->ivwgts, &graph->fvwgts,
68  &graph->ivsizes, &graph->fvsizes,
69  &graph->vlabels,
70  LTERM);
71 }
72 
73 
74 /**************************************************************************/
84 /**************************************************************************/
85 gk_graph_t *gk_graph_Read(char *filename, int format, int isfewgts,
86  int isfvwgts, int isfvsizes)
87 {
88  ssize_t i, k, l;
89  size_t nfields, nvtxs, nedges, fmt, ncon, lnlen;
90  int32_t ival;
91  float fval;
92  int readsizes=0, readwgts=0, readvals=0, numbering=0;
93  char *line=NULL, *head, *tail, fmtstr[256];
94  FILE *fpin=NULL;
96 
97 
98  if (!gk_fexists(filename))
99  gk_errexit(SIGERR, "File %s does not exist!\n", filename);
100 
101  if (format == GK_GRAPH_FMT_METIS) {
102  fpin = gk_fopen(filename, "r", "gk_graph_Read: fpin");
103  do {
104  if (gk_getline(&line, &lnlen, fpin) <= 0)
105  gk_errexit(SIGERR, "Premature end of input file: file:%s\n", filename);
106  } while (line[0] == '%');
107 
108  fmt = ncon = 0;
109  nfields = sscanf(line, "%zu %zu %zu %zu", &nvtxs, &nedges, &fmt, &ncon);
110  if (nfields < 2)
111  gk_errexit(SIGERR, "Header line must contain at least 2 integers (#vtxs and #edges).\n");
112 
113  nedges *= 2;
114 
115  if (fmt > 111)
116  gk_errexit(SIGERR, "Cannot read this type of file format [fmt=%zu]!\n", fmt);
117 
118  sprintf(fmtstr, "%03zu", fmt%1000);
119  readsizes = (fmtstr[0] == '1');
120  readwgts = (fmtstr[1] == '1');
121  readvals = (fmtstr[2] == '1');
122  numbering = 1;
123  ncon = (ncon == 0 ? 1 : ncon);
124  }
125  else {
126  gk_errexit(SIGERR, "Unrecognized format: %d\n", format);
127  }
128 
129  graph = gk_graph_Create();
130 
131  graph->nvtxs = nvtxs;
132 
133  graph->xadj = gk_zmalloc(nvtxs+1, "gk_graph_Read: xadj");
134  graph->adjncy = gk_i32malloc(nedges, "gk_graph_Read: adjncy");
135  if (readvals) {
136  if (isfewgts)
137  graph->fadjwgt = gk_fmalloc(nedges, "gk_graph_Read: fadjwgt");
138  else
139  graph->iadjwgt = gk_i32malloc(nedges, "gk_graph_Read: iadjwgt");
140  }
141 
142  if (readsizes) {
143  if (isfvsizes)
144  graph->fvsizes = gk_fmalloc(nvtxs, "gk_graph_Read: fvsizes");
145  else
146  graph->ivsizes = gk_i32malloc(nvtxs, "gk_graph_Read: ivsizes");
147  }
148 
149  if (readwgts) {
150  if (isfvwgts)
151  graph->fvwgts = gk_fmalloc(nvtxs*ncon, "gk_graph_Read: fvwgts");
152  else
153  graph->ivwgts = gk_i32malloc(nvtxs*ncon, "gk_graph_Read: ivwgts");
154  }
155 
156 
157  /*----------------------------------------------------------------------
158  * Read the sparse graph file
159  *---------------------------------------------------------------------*/
160  numbering = (numbering ? - 1 : 0);
161  for (graph->xadj[0]=0, k=0, i=0; i<nvtxs; i++) {
162  do {
163  if (gk_getline(&line, &lnlen, fpin) == -1)
164  gk_errexit(SIGERR, "Pregraphure end of input file: file while reading row %d\n", i);
165  } while (line[0] == '%');
166 
167  head = line;
168  tail = NULL;
169 
170  /* Read vertex sizes */
171  if (readsizes) {
172  if (isfvsizes) {
173 #ifdef __MSC__
174  graph->fvsizes[i] = (float)strtod(head, &tail);
175 #else
176  graph->fvsizes[i] = strtof(head, &tail);
177 #endif
178  if (tail == head)
179  gk_errexit(SIGERR, "The line for vertex %zd does not have size information\n", i+1);
180  if (graph->fvsizes[i] < 0)
181  gk_errexit(SIGERR, "The size for vertex %zd must be >= 0\n", i+1);
182  }
183  else {
184  graph->ivsizes[i] = strtol(head, &tail, 0);
185  if (tail == head)
186  gk_errexit(SIGERR, "The line for vertex %zd does not have size information\n", i+1);
187  if (graph->ivsizes[i] < 0)
188  gk_errexit(SIGERR, "The size for vertex %zd must be >= 0\n", i+1);
189  }
190  head = tail;
191  }
192 
193  /* Read vertex weights */
194  if (readwgts) {
195  for (l=0; l<ncon; l++) {
196  if (isfvwgts) {
197 #ifdef __MSC__
198  graph->fvwgts[i*ncon+l] = (float)strtod(head, &tail);
199 #else
200  graph->fvwgts[i*ncon+l] = strtof(head, &tail);
201 #endif
202  if (tail == head)
203  gk_errexit(SIGERR, "The line for vertex %zd does not have enough weights "
204  "for the %d constraints.\n", i+1, ncon);
205  if (graph->fvwgts[i*ncon+l] < 0)
206  gk_errexit(SIGERR, "The weight vertex %zd and constraint %zd must be >= 0\n", i+1, l);
207  }
208  else {
209  graph->ivwgts[i*ncon+l] = strtol(head, &tail, 0);
210  if (tail == head)
211  gk_errexit(SIGERR, "The line for vertex %zd does not have enough weights "
212  "for the %d constraints.\n", i+1, ncon);
213  if (graph->ivwgts[i*ncon+l] < 0)
214  gk_errexit(SIGERR, "The weight vertex %zd and constraint %zd must be >= 0\n", i+1, l);
215  }
216  head = tail;
217  }
218  }
219 
220 
221  /* Read the rest of the row */
222  while (1) {
223  ival = (int)strtol(head, &tail, 0);
224  if (tail == head)
225  break;
226  head = tail;
227 
228  if ((graph->adjncy[k] = ival + numbering) < 0)
229  gk_errexit(SIGERR, "Error: Invalid column number %d at row %zd.\n", ival, i);
230 
231  if (readvals) {
232  if (isfewgts) {
233 #ifdef __MSC__
234  fval = (float)strtod(head, &tail);
235 #else
236  fval = strtof(head, &tail);
237 #endif
238  if (tail == head)
239  gk_errexit(SIGERR, "Value could not be found for edge! Vertex:%zd, NNZ:%zd\n", i, k);
240 
241  graph->fadjwgt[k] = fval;
242  }
243  else {
244  ival = strtol(head, &tail, 0);
245  if (tail == head)
246  gk_errexit(SIGERR, "Value could not be found for edge! Vertex:%zd, NNZ:%zd\n", i, k);
247 
248  graph->iadjwgt[k] = ival;
249  }
250  head = tail;
251  }
252  k++;
253  }
254  graph->xadj[i+1] = k;
255  }
256 
257  if (k != nedges)
258  gk_errexit(SIGERR, "gk_graph_Read: Something wrong with the number of edges in "
259  "the input file. nedges=%zd, Actualnedges=%zd.\n", nedges, k);
260 
261  gk_fclose(fpin);
262 
263  gk_free((void **)&line, LTERM);
264 
265  return graph;
266 }
267 
268 
269 /**************************************************************************/
276 /**************************************************************************/
278 {
279  ssize_t i, j;
280  int hasvwgts, hasvsizes, hasewgts;
281  FILE *fpout;
282 
283  if (format != GK_GRAPH_FMT_METIS)
284  gk_errexit(SIGERR, "Unknown file format. %d\n", format);
285 
286  if (filename)
287  fpout = gk_fopen(filename, "w", "gk_graph_Write: fpout");
288  else
289  fpout = stdout;
290 
291 
292  hasewgts = (graph->iadjwgt || graph->fadjwgt);
293  hasvwgts = (graph->ivwgts || graph->fvwgts);
294  hasvsizes = (graph->ivsizes || graph->fvsizes);
295 
296  /* write the header line */
297  fprintf(fpout, "%d %zd", graph->nvtxs, graph->xadj[graph->nvtxs]/2);
298  if (hasvwgts || hasvsizes || hasewgts)
299  fprintf(fpout, " %d%d%d", hasvsizes, hasvwgts, hasewgts);
300  fprintf(fpout, "\n");
301 
302 
303  for (i=0; i<graph->nvtxs; i++) {
304  if (hasvsizes) {
305  if (graph->ivsizes)
306  fprintf(fpout, " %d", graph->ivsizes[i]);
307  else
308  fprintf(fpout, " %f", graph->fvsizes[i]);
309  }
310 
311  if (hasvwgts) {
312  if (graph->ivwgts)
313  fprintf(fpout, " %d", graph->ivwgts[i]);
314  else
315  fprintf(fpout, " %f", graph->fvwgts[i]);
316  }
317 
318  for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++) {
319  fprintf(fpout, " %d", graph->adjncy[j]+1);
320  if (hasewgts) {
321  if (graph->iadjwgt)
322  fprintf(fpout, " %d", graph->iadjwgt[j]);
323  else
324  fprintf(fpout, " %f", graph->fadjwgt[j]);
325  }
326  }
327  fprintf(fpout, "\n");
328  }
329  if (filename)
330  gk_fclose(fpout);
331 }
332 
333 
334 /*************************************************************************/
339 /**************************************************************************/
341 {
342  gk_graph_t *ngraph;
343 
344  ngraph = gk_graph_Create();
345 
346  ngraph->nvtxs = graph->nvtxs;
347 
348  /* copy the adjacency structure */
349  if (graph->xadj)
350  ngraph->xadj = gk_zcopy(graph->nvtxs+1, graph->xadj,
351  gk_zmalloc(graph->nvtxs+1, "gk_graph_Dup: xadj"));
352  if (graph->ivwgts)
353  ngraph->ivwgts = gk_i32copy(graph->nvtxs, graph->ivwgts,
354  gk_i32malloc(graph->nvtxs, "gk_graph_Dup: ivwgts"));
355  if (graph->ivsizes)
356  ngraph->ivsizes = gk_i32copy(graph->nvtxs, graph->ivsizes,
357  gk_i32malloc(graph->nvtxs, "gk_graph_Dup: ivsizes"));
358  if (graph->vlabels)
359  ngraph->vlabels = gk_i32copy(graph->nvtxs, graph->vlabels,
360  gk_i32malloc(graph->nvtxs, "gk_graph_Dup: ivlabels"));
361  if (graph->fvwgts)
362  ngraph->fvwgts = gk_fcopy(graph->nvtxs, graph->fvwgts,
363  gk_fmalloc(graph->nvtxs, "gk_graph_Dup: fvwgts"));
364  if (graph->fvsizes)
365  ngraph->fvsizes = gk_fcopy(graph->nvtxs, graph->fvsizes,
366  gk_fmalloc(graph->nvtxs, "gk_graph_Dup: fvsizes"));
367 
368 
369  if (graph->adjncy)
370  ngraph->adjncy = gk_i32copy(graph->xadj[graph->nvtxs], graph->adjncy,
371  gk_i32malloc(graph->xadj[graph->nvtxs], "gk_graph_Dup: adjncy"));
372  if (graph->iadjwgt)
373  ngraph->iadjwgt = gk_i32copy(graph->xadj[graph->nvtxs], graph->iadjwgt,
374  gk_i32malloc(graph->xadj[graph->nvtxs], "gk_graph_Dup: iadjwgt"));
375  if (graph->fadjwgt)
376  ngraph->fadjwgt = gk_fcopy(graph->xadj[graph->nvtxs], graph->fadjwgt,
377  gk_fmalloc(graph->xadj[graph->nvtxs], "gk_graph_Dup: fadjwgt"));
378 
379  return ngraph;
380 }
381 
382 
383 /*************************************************************************/
390 /**************************************************************************/
392 {
393  ssize_t i;
394  gk_graph_t *ngraph;
395 
396  if (vstart+nvtxs > graph->nvtxs)
397  return NULL;
398 
399  ngraph = gk_graph_Create();
400 
401  ngraph->nvtxs = nvtxs;
402 
403  /* copy the adjancy structure */
404  if (graph->xadj)
405  ngraph->xadj = gk_zcopy(nvtxs+1, graph->xadj+vstart,
406  gk_zmalloc(nvtxs+1, "gk_graph_ExtractSubgraph: xadj"));
407  for (i=nvtxs; i>=0; i--)
408  ngraph->xadj[i] -= ngraph->xadj[0];
409  ASSERT(ngraph->xadj[0] == 0);
410 
411  if (graph->ivwgts)
412  ngraph->ivwgts = gk_i32copy(nvtxs, graph->ivwgts+vstart,
413  gk_i32malloc(nvtxs, "gk_graph_ExtractSubgraph: ivwgts"));
414  if (graph->ivsizes)
415  ngraph->ivsizes = gk_i32copy(nvtxs, graph->ivsizes+vstart,
416  gk_i32malloc(nvtxs, "gk_graph_ExtractSubgraph: ivsizes"));
417  if (graph->vlabels)
418  ngraph->vlabels = gk_i32copy(nvtxs, graph->vlabels+vstart,
419  gk_i32malloc(nvtxs, "gk_graph_ExtractSubgraph: vlabels"));
420 
421  if (graph->fvwgts)
422  ngraph->fvwgts = gk_fcopy(nvtxs, graph->fvwgts+vstart,
423  gk_fmalloc(nvtxs, "gk_graph_ExtractSubgraph: fvwgts"));
424  if (graph->fvsizes)
425  ngraph->fvsizes = gk_fcopy(nvtxs, graph->fvsizes+vstart,
426  gk_fmalloc(nvtxs, "gk_graph_ExtractSubgraph: fvsizes"));
427 
428 
429  ASSERT(ngraph->xadj[nvtxs] == graph->xadj[vstart+nvtxs]-graph->xadj[vstart]);
430  if (graph->adjncy)
431  ngraph->adjncy = gk_i32copy(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
432  graph->adjncy+graph->xadj[vstart],
433  gk_i32malloc(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
434  "gk_graph_ExtractSubgraph: adjncy"));
435  if (graph->iadjwgt)
436  ngraph->iadjwgt = gk_i32copy(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
437  graph->iadjwgt+graph->xadj[vstart],
438  gk_i32malloc(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
439  "gk_graph_ExtractSubgraph: iadjwgt"));
440  if (graph->fadjwgt)
441  ngraph->fadjwgt = gk_fcopy(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
442  graph->fadjwgt+graph->xadj[vstart],
443  gk_fmalloc(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
444  "gk_graph_ExtractSubgraph: fadjwgt"));
445 
446  return ngraph;
447 }
448 
449 
450 /*************************************************************************/
459 /**************************************************************************/
461 {
462  ssize_t j, jj, *xadj;
463  int i, k, u, v, nvtxs;
464  int freeperm=0, freeiperm=0;
465  int32_t *adjncy;
466  gk_graph_t *ngraph;
467 
468  if (perm == NULL && iperm == NULL)
469  return NULL;
470 
471  ngraph = gk_graph_Create();
472 
473  ngraph->nvtxs = nvtxs = graph->nvtxs;
474  xadj = graph->xadj;
475  adjncy = graph->adjncy;
476 
477  /* allocate memory for the different structures that are present in graph */
478  if (graph->xadj)
479  ngraph->xadj = gk_zmalloc(nvtxs+1, "gk_graph_Reorder: xadj");
480 
481  if (graph->ivwgts)
482  ngraph->ivwgts = gk_i32malloc(nvtxs, "gk_graph_Reorder: ivwgts");
483 
484  if (graph->ivsizes)
485  ngraph->ivsizes = gk_i32malloc(nvtxs, "gk_graph_Reorder: ivsizes");
486 
487  if (graph->vlabels)
488  ngraph->vlabels = gk_i32malloc(nvtxs, "gk_graph_Reorder: ivlabels");
489 
490  if (graph->fvwgts)
491  ngraph->fvwgts = gk_fmalloc(nvtxs, "gk_graph_Reorder: fvwgts");
492 
493  if (graph->fvsizes)
494  ngraph->fvsizes = gk_fmalloc(nvtxs, "gk_graph_Reorder: fvsizes");
495 
496 
497  if (graph->adjncy)
498  ngraph->adjncy = gk_i32malloc(graph->xadj[nvtxs], "gk_graph_Reorder: adjncy");
499 
500  if (graph->iadjwgt)
501  ngraph->iadjwgt = gk_i32malloc(graph->xadj[nvtxs], "gk_graph_Reorder: iadjwgt");
502 
503  if (graph->fadjwgt)
504  ngraph->fadjwgt = gk_fmalloc(graph->xadj[nvtxs], "gk_graph_Reorder: fadjwgt");
505 
506 
507  /* create perm/iperm if not provided */
508  if (perm == NULL) {
509  freeperm = 1;
510  perm = gk_i32malloc(nvtxs, "gk_graph_Reorder: perm");
511  for (i=0; i<nvtxs; i++)
512  perm[iperm[i]] = i;
513  }
514  if (iperm == NULL) {
515  freeiperm = 1;
516  iperm = gk_i32malloc(nvtxs, "gk_graph_Reorder: iperm");
517  for (i=0; i<nvtxs; i++)
518  iperm[perm[i]] = i;
519  }
520 
521  /* fill-in the information of the re-ordered graph */
522  ngraph->xadj[0] = jj = 0;
523  for (v=0; v<nvtxs; v++) {
524  u = iperm[v];
525  for (j=xadj[u]; j<xadj[u+1]; j++, jj++) {
526  ngraph->adjncy[jj] = perm[adjncy[j]];
527  if (graph->iadjwgt)
528  ngraph->iadjwgt[jj] = graph->iadjwgt[j];
529  if (graph->fadjwgt)
530  ngraph->fadjwgt[jj] = graph->fadjwgt[j];
531  }
532  if (graph->ivwgts)
533  ngraph->ivwgts[v] = graph->ivwgts[u];
534  if (graph->fvwgts)
535  ngraph->fvwgts[v] = graph->fvwgts[u];
536  if (graph->ivsizes)
537  ngraph->ivsizes[v] = graph->ivsizes[u];
538  if (graph->fvsizes)
539  ngraph->fvsizes[v] = graph->fvsizes[u];
540  if (graph->vlabels)
541  ngraph->vlabels[v] = graph->vlabels[u];
542 
543  ngraph->xadj[v+1] = jj;
544  }
545 
546 
547  /* free memory */
548  if (freeperm)
549  gk_free((void **)&perm, LTERM);
550  if (freeiperm)
551  gk_free((void **)&iperm, LTERM);
552 
553  return ngraph;
554 }
555 
556 
557 /*************************************************************************/
571 /*************************************************************************/
573 {
574  ssize_t i, ii, j, jj, k, nvtxs, first, last, ntodo, ncmps;
575  ssize_t *xadj;
576  int32_t *adjncy, *pos, *todo;
577  int32_t mustfree_ccsr=0, mustfree_where=0;
578 
579  nvtxs = graph->nvtxs;
580  xadj = graph->xadj;
581  adjncy = graph->adjncy;
582 
583  /* Deal with NULL supplied cptr/cind vectors */
584  if (cptr == NULL) {
585  cptr = gk_i32malloc(nvtxs+1, "gk_graph_FindComponents: cptr");
586  cind = gk_i32malloc(nvtxs, "gk_graph_FindComponents: cind");
587  mustfree_ccsr = 1;
588  }
589 
590  /* The list of vertices that have not been touched yet.
591  The valid entries are from [0..ntodo). */
592  todo = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: todo"));
593 
594  /* For a vertex that has not been visited, pos[i] is the position in the
595  todo list that this vertex is stored.
596  If a vertex has been visited, pos[i] = -1. */
597  pos = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: pos"));
598 
599 
600  /* Find the connected componends */
601  ncmps = -1;
602  ntodo = nvtxs; /* All vertices have not been visited */
603  first = last = 0; /* Point to the first and last vertices that have been touched
604  but not explored.
605  These vertices are stored in cind[first]...cind[last-1]. */
606  while (ntodo > 0) {
607  if (first == last) { /* Find another starting vertex */
608  cptr[++ncmps] = first; /* Mark the end of the current CC */
609 
610  ASSERT(pos[todo[0]] != -1);
611  i = todo[0];
612 
613  cind[last++] = i;
614  pos[i] = -1;
615  }
616 
617  i = cind[first++]; /* Get the first visited but unexplored vertex */
618 
619  /* Remove i from the todo list and put the last item in the todo
620  list at the position that i was so that the todo list will be
621  consequtive. The pos[] array is updated accordingly to keep track
622  the location of the vertices in the todo[] list. */
623  k = pos[i];
624  j = todo[k] = todo[--ntodo];
625  pos[j] = k;
626 
627  for (j=xadj[i]; j<xadj[i+1]; j++) {
628  k = adjncy[j];
629  if (pos[k] != -1) {
630  cind[last++] = k;
631  pos[k] = -1;
632  }
633  }
634  }
635  cptr[++ncmps] = first;
636 
637  if (mustfree_ccsr)
638  gk_free((void **)&cptr, &cind, LTERM);
639 
640  gk_free((void **)&pos, &todo, LTERM);
641 
642  return (int) ncmps;
643 }
644 
645 
646 /*************************************************************************/
664 /*************************************************************************/
666  int32_t **r_iperm)
667 {
668  ssize_t j, *xadj;
669  int i, k, nvtxs, first, last;
670  int32_t *adjncy, *cot, *pos;
671 
672  if (graph->nvtxs <= 0)
673  return;
674 
675  nvtxs = graph->nvtxs;
676  xadj = graph->xadj;
677  adjncy = graph->adjncy;
678 
679  /* This array will function like pos + touched of the CC method */
680  pos = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_ComputeBFSOrdering: pos"));
681 
682  /* This array ([C]losed[O]pen[T]odo => cot) serves three purposes.
683  Positions from [0...first) is the current iperm[] vector of the explored vertices;
684  Positions from [first...last) is the OPEN list (i.e., visited vertices);
685  Positions from [last...nvtxs) is the todo list. */
686  cot = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_ComputeBFSOrdering: cot"));
687 
688 
689  /* put v at the front of the todo list */
690  pos[0] = cot[0] = v;
691  pos[v] = cot[v] = 0;
692 
693  /* Find the connected componends induced by the partition */
694  first = last = 0;
695  while (first < nvtxs) {
696  if (first == last) { /* Find another starting vertex */
697  k = cot[last];
698  ASSERT(pos[k] != -1);
699  pos[k] = -1; /* mark node as being visited */
700  last++;
701  }
702 
703  i = cot[first++]; /* the ++ advances the explored vertices */
704  for (j=xadj[i]; j<xadj[i+1]; j++) {
705  k = adjncy[j];
706  /* if a node has already been visited, its perm[] will be -1 */
707  if (pos[k] != -1) {
708  /* pos[k] is the location within iperm of where k resides (it is in the 'todo' part);
709  It is placed in that location cot[last] (end of OPEN list) that we
710  are about to overwrite and update pos[cot[last]] to reflect that. */
711  cot[pos[k]] = cot[last]; /* put the head of the todo list to
712  where k was in the todo list */
713  pos[cot[last]] = pos[k]; /* update perm to reflect the move */
714 
715  cot[last++] = k; /* put node at the end of the OPEN list */
716  pos[k] = -1; /* mark node as being visited */
717  }
718  }
719  }
720 
721  /* time to decide what to return */
722  if (r_perm != NULL) {
723  /* use the 'pos' array to build the perm array */
724  for (i=0; i<nvtxs; i++)
725  pos[cot[i]] = i;
726 
727  *r_perm = pos;
728  pos = NULL;
729  }
730 
731  if (r_iperm != NULL) {
732  *r_iperm = cot;
733  cot = NULL;
734  }
735 
736 
737  /* cleanup memory */
738  gk_free((void **)&pos, &cot, LTERM);
739 
740 }
741 
742 
743 /*************************************************************************/
761 /*************************************************************************/
763  int32_t **r_perm, int32_t **r_iperm)
764 {
765  ssize_t j, jj, *xadj;
766  int i, k, u, nvtxs;
767  int32_t *adjncy, *perm, *degrees, *minIDs, *open;
768  gk_i32pq_t *queue;
769 
770  if (graph->nvtxs <= 0)
771  return;
772 
773  nvtxs = graph->nvtxs;
774  xadj = graph->xadj;
775  adjncy = graph->adjncy;
776 
777  /* the degree of the vertices in the closed list */
778  degrees = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: degrees");
779 
780  /* the minimum vertex ID of an open vertex to the closed list */
781  minIDs = gk_i32smalloc(nvtxs, nvtxs+1, "gk_graph_ComputeBestFOrdering: minIDs");
782 
783  /* the open list */
784  open = gk_i32malloc(nvtxs, "gk_graph_ComputeBestFOrdering: open");
785 
786  /* if perm[i] >= 0, then perm[i] is the order of vertex i;
787  otherwise perm[i] == -1.
788  */
789  perm = gk_i32smalloc(nvtxs, -1, "gk_graph_ComputeBestFOrdering: perm");
790 
791  /* create the queue and put everything in it */
792  queue = gk_i32pqCreate(nvtxs);
793  for (i=0; i<nvtxs; i++)
794  gk_i32pqInsert(queue, i, 0);
795  gk_i32pqUpdate(queue, v, 1);
796 
797  open[0] = v;
798 
799  /* start processing the nodes */
800  for (i=0; i<nvtxs; i++) {
801  if ((v = gk_i32pqGetTop(queue)) == -1)
802  gk_errexit(SIGERR, "The priority queue got empty ahead of time [i=%d].\n", i);
803  if (perm[v] != -1)
804  gk_errexit(SIGERR, "The perm[%d] has already been set.\n", v);
805  perm[v] = i;
806 
807 
808  for (j=xadj[v]; j<xadj[v+1]; j++) {
809  u = adjncy[j];
810  if (perm[u] == -1) {
811  degrees[u]++;
812  minIDs[u] = (i < minIDs[u] ? i : minIDs[u]);
813 
814  switch (type) {
815  case 1: /* DFS */
816  gk_i32pqUpdate(queue, u, 1);
817  break;
818  case 2: /* Max in closed degree */
819  gk_i32pqUpdate(queue, u, degrees[u]);
820  break;
821  case 3: /* Sum of orders in closed list */
822  for (k=0, jj=xadj[u]; jj<xadj[u+1]; jj++) {
823  if (perm[adjncy[jj]] != -1)
824  k += perm[adjncy[jj]];
825  }
826  gk_i32pqUpdate(queue, u, k);
827  break;
828  case 4: /* Sum of order-differences (w.r.t. current number) in closed
829  list (updated once in a while) */
830  for (k=0, jj=xadj[u]; jj<xadj[u+1]; jj++) {
831  if (perm[adjncy[jj]] != -1)
832  k += (i-perm[adjncy[jj]]);
833  }
834  gk_i32pqUpdate(queue, u, k);
835  break;
836  default:
837  ;
838  }
839  }
840  }
841  }
842 
843 
844  /* time to decide what to return */
845  if (r_perm != NULL) {
846  *r_perm = perm;
847  perm = NULL;
848  }
849 
850  if (r_iperm != NULL) {
851  /* use the 'degrees' array to build the iperm array */
852  for (i=0; i<nvtxs; i++)
853  degrees[perm[i]] = i;
854 
855  *r_iperm = degrees;
856  degrees = NULL;
857  }
858 
859 
860 
861  /* cleanup memory */
862  gk_i32pqDestroy(queue);
863  gk_free((void **)&perm, &degrees, &minIDs, &open, LTERM);
864 
865 }
866 
867 
868 /*************************************************************************/
886 /*************************************************************************/
888  int32_t **r_perm, int32_t **r_iperm)
889 {
890  ssize_t j, jj, *xadj;
891  int i, k, u, nvtxs, nopen, ntodo;
892  int32_t *adjncy, *perm, *degrees, *wdegrees, *sod, *level, *ot, *pos;
893  gk_i32pq_t *queue;
894 
895  if (graph->nvtxs <= 0)
896  return;
897 
898  nvtxs = graph->nvtxs;
899  xadj = graph->xadj;
900  adjncy = graph->adjncy;
901 
902  /* the degree of the vertices in the closed list */
903  degrees = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: degrees");
904 
905  /* the weighted degree of the vertices in the closed list for type==3 */
906  wdegrees = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: wdegrees");
907 
908  /* the sum of differences for type==4 */
909  sod = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: sod");
910 
911  /* the encountering level of a vertex type==5 */
912  level = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: level");
913 
914  /* The open+todo list of vertices.
915  The vertices from [0..nopen] are the open vertices.
916  The vertices from [nopen..ntodo) are the todo vertices.
917  */
918  ot = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: ot"));
919 
920  /* For a vertex that has not been explored, pos[i] is the position in the ot list. */
921  pos = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: pos"));
922 
923  /* if perm[i] >= 0, then perm[i] is the order of vertex i; otherwise perm[i] == -1. */
924  perm = gk_i32smalloc(nvtxs, -1, "gk_graph_ComputeBestFOrdering: perm");
925 
926  /* create the queue and put the starting vertex in it */
927  queue = gk_i32pqCreate(nvtxs);
928  gk_i32pqInsert(queue, v, 1);
929 
930  /* put v at the front of the open list */
931  pos[0] = ot[0] = v;
932  pos[v] = ot[v] = 0;
933  nopen = 1;
934  ntodo = nvtxs;
935 
936  /* start processing the nodes */
937  for (i=0; i<nvtxs; i++) {
938  if (nopen == 0) { /* deal with non-connected graphs */
939  gk_i32pqInsert(queue, ot[0], 1);
940  nopen++;
941  }
942 
943  if ((v = gk_i32pqGetTop(queue)) == -1)
944  gk_errexit(SIGERR, "The priority queue got empty ahead of time [i=%d].\n", i);
945 
946  if (perm[v] != -1)
947  gk_errexit(SIGERR, "The perm[%d] has already been set.\n", v);
948  perm[v] = i;
949 
950  if (ot[pos[v]] != v)
951  gk_errexit(SIGERR, "Something went wrong [ot[pos[%d]]!=%d.\n", v, v);
952  if (pos[v] >= nopen)
953  gk_errexit(SIGERR, "The position of v is not in open list. pos[%d]=%d is >=%d.\n", v, pos[v], nopen);
954 
955  /* remove v from the open list and re-arrange the todo part of the list */
956  ot[pos[v]] = ot[nopen-1];
957  pos[ot[nopen-1]] = pos[v];
958  if (ntodo > nopen) {
959  ot[nopen-1] = ot[ntodo-1];
960  pos[ot[ntodo-1]] = nopen-1;
961  }
962  nopen--;
963  ntodo--;
964 
965  for (j=xadj[v]; j<xadj[v+1]; j++) {
966  u = adjncy[j];
967  if (perm[u] == -1) {
968  /* update ot list, if u is not in the open list by putting it at the end
969  of the open list. */
970  if (degrees[u] == 0) {
971  ot[pos[u]] = ot[nopen];
972  pos[ot[nopen]] = pos[u];
973  ot[nopen] = u;
974  pos[u] = nopen;
975  nopen++;
976 
977  level[u] = level[v]+1;
978  gk_i32pqInsert(queue, u, 0);
979  }
980 
981 
982  /* update the in-closed degree */
983  degrees[u]++;
984 
985  /* update the queues based on the type */
986  switch (type) {
987  case 1: /* DFS */
988  gk_i32pqUpdate(queue, u, 1000*(i+1)+degrees[u]);
989  break;
990 
991  case 2: /* Max in closed degree */
992  gk_i32pqUpdate(queue, u, degrees[u]);
993  break;
994 
995  case 3: /* Sum of orders in closed list */
996  wdegrees[u] += i;
997  gk_i32pqUpdate(queue, u, wdegrees[u]);
998  break;
999 
1000  case 4: /* Sum of order-differences */
1001  /* this is handled at the end of the loop */
1002  ;
1003  break;
1004 
1005  case 5: /* BFS with in degree priority */
1006  gk_i32pqUpdate(queue, u, -(1000*level[u] - degrees[u]));
1007  break;
1008 
1009  case 6: /* Hybrid of 1+2 */
1010  gk_i32pqUpdate(queue, u, (i+1)*degrees[u]);
1011  break;
1012 
1013  default:
1014  ;
1015  }
1016  }
1017  }
1018 
1019  if (type == 4) { /* update all the vertices in the open list */
1020  for (j=0; j<nopen; j++) {
1021  u = ot[j];
1022  if (perm[u] != -1)
1023  gk_errexit(SIGERR, "For i=%d, the open list contains a closed vertex: ot[%zd]=%d, perm[%d]=%d.\n", i, j, u, u, perm[u]);
1024  sod[u] += degrees[u];
1025  if (i<1000 || i%25==0)
1026  gk_i32pqUpdate(queue, u, sod[u]);
1027  }
1028  }
1029 
1030  /*
1031  for (j=0; j<ntodo; j++) {
1032  if (pos[ot[j]] != j)
1033  gk_errexit(SIGERR, "pos[ot[%zd]] != %zd.\n", j, j);
1034  }
1035  */
1036 
1037  }
1038 
1039 
1040  /* time to decide what to return */
1041  if (r_perm != NULL) {
1042  *r_perm = perm;
1043  perm = NULL;
1044  }
1045 
1046  if (r_iperm != NULL) {
1047  /* use the 'degrees' array to build the iperm array */
1048  for (i=0; i<nvtxs; i++)
1049  degrees[perm[i]] = i;
1050 
1051  *r_iperm = degrees;
1052  degrees = NULL;
1053  }
1054 
1055 
1056 
1057  /* cleanup memory */
1058  gk_i32pqDestroy(queue);
1059  gk_free((void **)&perm, &degrees, &wdegrees, &sod, &ot, &pos, &level, LTERM);
1060 
1061 }
1062 
1063 
1064 /*************************************************************************/
1083 /*************************************************************************/
1085 {
1086  ssize_t *xadj;
1087  int i, u, nvtxs;
1088  int32_t *adjncy, *inqueue;
1089 
1090  if (graph->nvtxs <= 0)
1091  return;
1092 
1093  nvtxs = graph->nvtxs;
1094  xadj = graph->xadj;
1095  adjncy = graph->adjncy;
1096 
1097  inqueue = gk_i32smalloc(nvtxs, 0, "gk_graph_SingleSourceShortestPaths: inqueue");
1098 
1099  /* determine if you will be computing using int32_t or float and proceed from there */
1100  if (graph->iadjwgt != NULL) {
1101  gk_i32pq_t *queue;
1102  int32_t *adjwgt;
1103  int32_t *sps;
1104 
1105  adjwgt = graph->iadjwgt;
1106 
1107  queue = gk_i32pqCreate(nvtxs);
1108  gk_i32pqInsert(queue, v, 0);
1109  inqueue[v] = 1;
1110 
1111  sps = gk_i32smalloc(nvtxs, -1, "gk_graph_SingleSourceShortestPaths: sps");
1112  sps[v] = 0;
1113 
1114  /* start processing the nodes */
1115  while ((v = gk_i32pqGetTop(queue)) != -1) {
1116  inqueue[v] = 2;
1117 
1118  /* relax the adjacent edges */
1119  for (i=xadj[v]; i<xadj[v+1]; i++) {
1120  u = adjncy[i];
1121  if (inqueue[u] == 2)
1122  continue;
1123 
1124  if (sps[u] < 0 || sps[v]+adjwgt[i] < sps[u]) {
1125  sps[u] = sps[v]+adjwgt[i];
1126 
1127  if (inqueue[u])
1128  gk_i32pqUpdate(queue, u, -sps[u]);
1129  else {
1130  gk_i32pqInsert(queue, u, -sps[u]);
1131  inqueue[u] = 1;
1132  }
1133  }
1134  }
1135  }
1136 
1137  *r_sps = (void *)sps;
1138 
1139  gk_i32pqDestroy(queue);
1140  }
1141  else {
1142  gk_fpq_t *queue;
1143  float *adjwgt;
1144  float *sps;
1145 
1146  adjwgt = graph->fadjwgt;
1147 
1148  queue = gk_fpqCreate(nvtxs);
1149  gk_fpqInsert(queue, v, 0);
1150  inqueue[v] = 1;
1151 
1152  sps = gk_fsmalloc(nvtxs, -1, "gk_graph_SingleSourceShortestPaths: sps");
1153  sps[v] = 0;
1154 
1155  /* start processing the nodes */
1156  while ((v = gk_fpqGetTop(queue)) != -1) {
1157  inqueue[v] = 2;
1158 
1159  /* relax the adjacent edges */
1160  for (i=xadj[v]; i<xadj[v+1]; i++) {
1161  u = adjncy[i];
1162  if (inqueue[u] == 2)
1163  continue;
1164 
1165  if (sps[u] < 0 || sps[v]+adjwgt[i] < sps[u]) {
1166  sps[u] = sps[v]+adjwgt[i];
1167 
1168  if (inqueue[u])
1169  gk_fpqUpdate(queue, u, -sps[u]);
1170  else {
1171  gk_fpqInsert(queue, u, -sps[u]);
1172  inqueue[u] = 1;
1173  }
1174  }
1175  }
1176  }
1177 
1178  *r_sps = (void *)sps;
1179 
1180  gk_fpqDestroy(queue);
1181  }
1182 
1183  gk_free((void **)&inqueue, LTERM);
1184 
1185 }
1186 
1187 
1188 
1189 #ifdef XXX
1190 
1191 /*************************************************************************/
1195 /**************************************************************************/
1196 void gk_graph_SortAdjacencies(gk_graph_t *graph)
1197 {
1198  int n, nn=0;
1199  ssize_t *ptr;
1200  int *ind;
1201  float *val;
1202 
1203  switch (what) {
1204  case GK_CSR_ROW:
1205  if (!graph->rowptr)
1206  gk_errexit(SIGERR, "Row-based view of the graphrix does not exists.\n");
1207 
1208  n = graph->nrows;
1209  ptr = graph->rowptr;
1210  ind = graph->rowind;
1211  val = graph->rowval;
1212  break;
1213 
1214  case GK_CSR_COL:
1215  if (!graph->colptr)
1216  gk_errexit(SIGERR, "Column-based view of the graphrix does not exists.\n");
1217 
1218  n = graph->ncols;
1219  ptr = graph->colptr;
1220  ind = graph->colind;
1221  val = graph->colval;
1222  break;
1223 
1224  default:
1225  gk_errexit(SIGERR, "Invalid index type of %d.\n", what);
1226  return;
1227  }
1228 
1229  #pragma omp parallel if (n > 100)
1230  {
1231  ssize_t i, j, k;
1232  gk_ikv_t *cand;
1233  float *tval;
1234 
1235  #pragma omp single
1236  for (i=0; i<n; i++)
1237  nn = gk_max(nn, ptr[i+1]-ptr[i]);
1238 
1239  cand = gk_ikvmalloc(nn, "gk_graph_SortIndices: cand");
1240  tval = gk_fmalloc(nn, "gk_graph_SortIndices: tval");
1241 
1242  #pragma omp for schedule(static)
1243  for (i=0; i<n; i++) {
1244  for (k=0, j=ptr[i]; j<ptr[i+1]; j++) {
1245  if (j > ptr[i] && ind[j] < ind[j-1])
1246  k = 1; /* an inversion */
1247  cand[j-ptr[i]].val = j-ptr[i];
1248  cand[j-ptr[i]].key = ind[j];
1249  tval[j-ptr[i]] = val[j];
1250  }
1251  if (k) {
1252  gk_ikvsorti(ptr[i+1]-ptr[i], cand);
1253  for (j=ptr[i]; j<ptr[i+1]; j++) {
1254  ind[j] = cand[j-ptr[i]].key;
1255  val[j] = tval[cand[j-ptr[i]].val];
1256  }
1257  }
1258  }
1259 
1260  gk_free((void **)&cand, &tval, LTERM);
1261  }
1262 
1263 }
1264 
1265 
1266 /*************************************************************************/
1273 /**************************************************************************/
1274 gk_graph_t *gk_graph_ExtractRows(gk_graph_t *graph, int nrows, int *rind)
1275 {
1276  ssize_t i, ii, j, nnz;
1277  gk_graph_t *ngraph;
1278 
1279  ngraph = gk_graph_Create();
1280 
1281  ngraph->nrows = nrows;
1282  ngraph->ncols = graph->ncols;
1283 
1284  for (nnz=0, i=0; i<nrows; i++)
1285  nnz += graph->rowptr[rind[i]+1]-graph->rowptr[rind[i]];
1286 
1287  ngraph->rowptr = gk_zmalloc(ngraph->nrows+1, "gk_graph_ExtractPartition: rowptr");
1288  ngraph->rowind = gk_imalloc(nnz, "gk_graph_ExtractPartition: rowind");
1289  ngraph->rowval = gk_fmalloc(nnz, "gk_graph_ExtractPartition: rowval");
1290 
1291  ngraph->rowptr[0] = 0;
1292  for (nnz=0, j=0, ii=0; ii<nrows; ii++) {
1293  i = rind[ii];
1294  gk_icopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowind+graph->rowptr[i], ngraph->rowind+nnz);
1295  gk_fcopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowval+graph->rowptr[i], ngraph->rowval+nnz);
1296  nnz += graph->rowptr[i+1]-graph->rowptr[i];
1297  ngraph->rowptr[++j] = nnz;
1298  }
1299  ASSERT(j == ngraph->nrows);
1300 
1301  return ngraph;
1302 }
1303 
1304 
1305 /*************************************************************************/
1312 /**************************************************************************/
1313 gk_graph_t *gk_graph_ExtractPartition(gk_graph_t *graph, int *part, int pid)
1314 {
1315  ssize_t i, j, nnz;
1316  gk_graph_t *ngraph;
1317 
1318  ngraph = gk_graph_Create();
1319 
1320  ngraph->nrows = 0;
1321  ngraph->ncols = graph->ncols;
1322 
1323  for (nnz=0, i=0; i<graph->nrows; i++) {
1324  if (part[i] == pid) {
1325  ngraph->nrows++;
1326  nnz += graph->rowptr[i+1]-graph->rowptr[i];
1327  }
1328  }
1329 
1330  ngraph->rowptr = gk_zmalloc(ngraph->nrows+1, "gk_graph_ExtractPartition: rowptr");
1331  ngraph->rowind = gk_imalloc(nnz, "gk_graph_ExtractPartition: rowind");
1332  ngraph->rowval = gk_fmalloc(nnz, "gk_graph_ExtractPartition: rowval");
1333 
1334  ngraph->rowptr[0] = 0;
1335  for (nnz=0, j=0, i=0; i<graph->nrows; i++) {
1336  if (part[i] == pid) {
1337  gk_icopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowind+graph->rowptr[i], ngraph->rowind+nnz);
1338  gk_fcopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowval+graph->rowptr[i], ngraph->rowval+nnz);
1339  nnz += graph->rowptr[i+1]-graph->rowptr[i];
1340  ngraph->rowptr[++j] = nnz;
1341  }
1342  }
1343  ASSERT(j == ngraph->nrows);
1344 
1345  return ngraph;
1346 }
1347 
1348 
1349 /*************************************************************************/
1359 /**************************************************************************/
1360 gk_graph_t **gk_graph_Split(gk_graph_t *graph, int *color)
1361 {
1362  ssize_t i, j;
1363  int nrows, ncolors;
1364  ssize_t *rowptr;
1365  int *rowind;
1366  float *rowval;
1367  gk_graph_t **sgraphs;
1368 
1369  nrows = graph->nrows;
1370  rowptr = graph->rowptr;
1371  rowind = graph->rowind;
1372  rowval = graph->rowval;
1373 
1374  ncolors = gk_imax(rowptr[nrows], color)+1;
1375 
1376  sgraphs = (gk_graph_t **)gk_malloc(sizeof(gk_graph_t *)*ncolors, "gk_graph_Split: sgraphs");
1377  for (i=0; i<ncolors; i++) {
1378  sgraphs[i] = gk_graph_Create();
1379  sgraphs[i]->nrows = graph->nrows;
1380  sgraphs[i]->ncols = graph->ncols;
1381  sgraphs[i]->rowptr = gk_zsmalloc(nrows+1, 0, "gk_graph_Split: sgraphs[i]->rowptr");
1382  }
1383 
1384  for (i=0; i<nrows; i++) {
1385  for (j=rowptr[i]; j<rowptr[i+1]; j++)
1386  sgraphs[color[j]]->rowptr[i]++;
1387  }
1388  for (i=0; i<ncolors; i++)
1389  MAKECSR(j, nrows, sgraphs[i]->rowptr);
1390 
1391  for (i=0; i<ncolors; i++) {
1392  sgraphs[i]->rowind = gk_imalloc(sgraphs[i]->rowptr[nrows], "gk_graph_Split: sgraphs[i]->rowind");
1393  sgraphs[i]->rowval = gk_fmalloc(sgraphs[i]->rowptr[nrows], "gk_graph_Split: sgraphs[i]->rowval");
1394  }
1395 
1396  for (i=0; i<nrows; i++) {
1397  for (j=rowptr[i]; j<rowptr[i+1]; j++) {
1398  sgraphs[color[j]]->rowind[sgraphs[color[j]]->rowptr[i]] = rowind[j];
1399  sgraphs[color[j]]->rowval[sgraphs[color[j]]->rowptr[i]] = rowval[j];
1400  sgraphs[color[j]]->rowptr[i]++;
1401  }
1402  }
1403 
1404  for (i=0; i<ncolors; i++)
1405  SHIFTCSR(j, nrows, sgraphs[i]->rowptr);
1406 
1407  return sgraphs;
1408 }
1409 
1410 
1411 /*************************************************************************/
1427 /**************************************************************************/
1428 gk_graph_t *gk_graph_Prune(gk_graph_t *graph, int what, int minf, int maxf)
1429 {
1430  ssize_t i, j, nnz;
1431  int nrows, ncols;
1432  ssize_t *rowptr, *nrowptr;
1433  int *rowind, *nrowind, *collen;
1434  float *rowval, *nrowval;
1435  gk_graph_t *ngraph;
1436 
1437  ngraph = gk_graph_Create();
1438 
1439  nrows = ngraph->nrows = graph->nrows;
1440  ncols = ngraph->ncols = graph->ncols;
1441 
1442  rowptr = graph->rowptr;
1443  rowind = graph->rowind;
1444  rowval = graph->rowval;
1445 
1446  nrowptr = ngraph->rowptr = gk_zmalloc(nrows+1, "gk_graph_Prune: nrowptr");
1447  nrowind = ngraph->rowind = gk_imalloc(rowptr[nrows], "gk_graph_Prune: nrowind");
1448  nrowval = ngraph->rowval = gk_fmalloc(rowptr[nrows], "gk_graph_Prune: nrowval");
1449 
1450 
1451  switch (what) {
1452  case GK_CSR_COL:
1453  collen = gk_ismalloc(ncols, 0, "gk_graph_Prune: collen");
1454 
1455  for (i=0; i<nrows; i++) {
1456  for (j=rowptr[i]; j<rowptr[i+1]; j++) {
1457  ASSERT(rowind[j] < ncols);
1458  collen[rowind[j]]++;
1459  }
1460  }
1461  for (i=0; i<ncols; i++)
1462  collen[i] = (collen[i] >= minf && collen[i] <= maxf ? 1 : 0);
1463 
1464  nrowptr[0] = 0;
1465  for (nnz=0, i=0; i<nrows; i++) {
1466  for (j=rowptr[i]; j<rowptr[i+1]; j++) {
1467  if (collen[rowind[j]]) {
1468  nrowind[nnz] = rowind[j];
1469  nrowval[nnz] = rowval[j];
1470  nnz++;
1471  }
1472  }
1473  nrowptr[i+1] = nnz;
1474  }
1475  gk_free((void **)&collen, LTERM);
1476  break;
1477 
1478  case GK_CSR_ROW:
1479  nrowptr[0] = 0;
1480  for (nnz=0, i=0; i<nrows; i++) {
1481  if (rowptr[i+1]-rowptr[i] >= minf && rowptr[i+1]-rowptr[i] <= maxf) {
1482  for (j=rowptr[i]; j<rowptr[i+1]; j++, nnz++) {
1483  nrowind[nnz] = rowind[j];
1484  nrowval[nnz] = rowval[j];
1485  }
1486  }
1487  nrowptr[i+1] = nnz;
1488  }
1489  break;
1490 
1491  default:
1492  gk_graph_Free(&ngraph);
1493  gk_errexit(SIGERR, "Unknown prunning type of %d\n", what);
1494  return NULL;
1495  }
1496 
1497  return ngraph;
1498 }
1499 
1500 
1501 
1502 /*************************************************************************/
1510 /**************************************************************************/
1511 void gk_graph_Normalize(gk_graph_t *graph, int what, int norm)
1512 {
1513  ssize_t i, j;
1514  int n;
1515  ssize_t *ptr;
1516  float *val, sum;
1517 
1518  if (what&GK_CSR_ROW && graph->rowval) {
1519  n = graph->nrows;
1520  ptr = graph->rowptr;
1521  val = graph->rowval;
1522 
1523  #pragma omp parallel if (ptr[n] > OMPMINOPS)
1524  {
1525  #pragma omp for private(j,sum) schedule(static)
1526  for (i=0; i<n; i++) {
1527  for (sum=0.0, j=ptr[i]; j<ptr[i+1]; j++){
1528  if (norm == 2)
1529  sum += val[j]*val[j];
1530  else if (norm == 1)
1531  sum += val[j]; /* assume val[j] > 0 */
1532  }
1533  if (sum > 0) {
1534  if (norm == 2)
1535  sum=1.0/sqrt(sum);
1536  else if (norm == 1)
1537  sum=1.0/sum;
1538  for (j=ptr[i]; j<ptr[i+1]; j++)
1539  val[j] *= sum;
1540 
1541  }
1542  }
1543  }
1544  }
1545 
1546  if (what&GK_CSR_COL && graph->colval) {
1547  n = graph->ncols;
1548  ptr = graph->colptr;
1549  val = graph->colval;
1550 
1551  #pragma omp parallel if (ptr[n] > OMPMINOPS)
1552  {
1553  #pragma omp for private(j,sum) schedule(static)
1554  for (i=0; i<n; i++) {
1555  for (sum=0.0, j=ptr[i]; j<ptr[i+1]; j++)
1556  if (norm == 2)
1557  sum += val[j]*val[j];
1558  else if (norm == 1)
1559  sum += val[j];
1560  if (sum > 0) {
1561  if (norm == 2)
1562  sum=1.0/sqrt(sum);
1563  else if (norm == 1)
1564  sum=1.0/sum;
1565  for (j=ptr[i]; j<ptr[i+1]; j++)
1566  val[j] *= sum;
1567  }
1568  }
1569  }
1570  }
1571 }
1572 
1573 
1574 #endif
int32_t * iadjwgt
Definition: gk_struct.h:93
FILE * gk_fopen(char *, char *, const char *)
Definition: GKlib/io.c:24
int32_t * adjncy
Definition: gk_struct.h:92
gk_graph_t * gk_graph_Read(char *filename, int format, int isfewgts, int isfvwgts, int isfvsizes)
Definition: GKlib/graph.c:85
void gk_ikvsorti(size_t, gk_ikv_t *)
Definition: sort.c:157
int32_t * ivsizes
Definition: gk_struct.h:97
int gk_graph_FindComponents(gk_graph_t *graph, int32_t *cptr, int32_t *cind)
Definition: GKlib/graph.c:572
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t idx_t idx_t idx_t * part
ssize_t * xadj
Definition: gk_struct.h:91
void gk_graph_Free(gk_graph_t **graph)
Definition: GKlib/graph.c:48
#define MAKECSR(i, n, a)
Definition: gk_macros.h:73
idx_t idx_t * xadj
int gk_fexists(char *fname)
Definition: fs.c:21
int n
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE FixedSegmentReturnType< internal::get_fixed_value< NType >::value >::Type tail(NType n)
float * fadjwgt
Definition: gk_struct.h:94
gk_graph_t * gk_graph_ExtractSubgraph(gk_graph_t *graph, int vstart, int nvtxs)
Definition: GKlib/graph.c:391
idx_t idx_t idx_t idx_t idx_t idx_t * iperm
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:77
EIGEN_CONSTEXPR Index first(const T &x) EIGEN_NOEXCEPT
NonlinearFactorGraph graph
static const symbolic::SymbolExpr< internal::symbolic_last_tag > last
#define GK_CSR_ROW
Definition: gk_defs.h:42
#define ASSERT(expression)
Definition: ccolamd.c:872
static const Line3 l(Rot3(), 1, 1)
gk_idx_t gk_getline(char **lineptr, size_t *n, FILE *stream)
Definition: GKlib/io.c:57
#define GK_GRAPH_FMT_METIS
Definition: gk_defs.h:67
int32_t * ivwgts
Definition: gk_struct.h:95
#define SIGERR
Definition: gk_defs.h:38
std::vector< int > ind
#define gk_max(a, b)
Definition: gk_macros.h:16
void gk_graph_FreeContents(gk_graph_t *graph)
Definition: GKlib/graph.c:63
Array< int, Dynamic, 1 > v
signed int int32_t
Definition: ms_stdint.h:82
idx_t idx_t idx_t idx_t idx_t * perm
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
void gk_graph_Init(gk_graph_t *graph)
Definition: GKlib/graph.c:36
void gk_graph_Write(gk_graph_t *graph, char *filename, int format)
Definition: GKlib/graph.c:277
#define SHIFTCSR(i, n, a)
Definition: gk_macros.h:80
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
idx_t * nn
float * fvwgts
Definition: gk_struct.h:96
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
void gk_free(void **ptr1,...)
Definition: memory.c:202
void gk_graph_ComputeBestFOrdering(gk_graph_t *graph, int v, int type, int32_t **r_perm, int32_t **r_iperm)
Definition: GKlib/graph.c:887
gk_graph_t * gk_graph_Reorder(gk_graph_t *graph, int32_t *perm, int32_t *iperm)
Definition: GKlib/graph.c:460
#define GK_CSR_COL
Definition: gk_defs.h:43
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE FixedSegmentReturnType< internal::get_fixed_value< NType >::value >::Type head(NType n)
idx_t idx_t idx_t * adjncy
void gk_graph_SingleSourceShortestPaths(gk_graph_t *graph, int v, void **r_sps)
Definition: GKlib/graph.c:1084
std::string format(const std::string &str, const std::vector< std::string > &find, const std::vector< std::string > &replace)
void gk_graph_ComputeBFSOrdering(gk_graph_t *graph, int v, int32_t **r_perm, int32_t **r_iperm)
Definition: GKlib/graph.c:665
float * fvsizes
Definition: gk_struct.h:98
Jet< T, N > sqrt(const Jet< T, N > &f)
Definition: jet.h:418
void gk_fclose(FILE *)
Definition: GKlib/io.c:44
gk_graph_t * gk_graph_Dup(gk_graph_t *graph)
Definition: GKlib/graph.c:340
int32_t nvtxs
Definition: gk_struct.h:90
std::ptrdiff_t j
int32_t * vlabels
Definition: gk_struct.h:99
Definition: pytypes.h:1370
gk_graph_t * gk_graph_Create()
Definition: GKlib/graph.c:19
#define LTERM
Definition: gk_defs.h:14
void gk_graph_ComputeBestFOrdering0(gk_graph_t *graph, int v, int type, int32_t **r_perm, int32_t **r_iperm)
Definition: GKlib/graph.c:762


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:19