You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1940 lines
61 KiB
1940 lines
61 KiB
/*!
|
|
* \file
|
|
*
|
|
* \brief Various routines with dealing with sparse graphs
|
|
*
|
|
* \author George Karypis
|
|
* \version\verbatim $Id: graph.c 22415 2019-09-05 16:55:00Z karypis $ \endverbatim
|
|
*/
|
|
|
|
#include <GKlib.h>
|
|
|
|
#define OMPMINOPS 50000
|
|
|
|
/*************************************************************************/
|
|
/*! Allocate memory for a graph and initializes it
|
|
\returns the allocated graph. The various fields are set to NULL.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_Create()
|
|
{
|
|
gk_graph_t *graph;
|
|
|
|
graph = (gk_graph_t *)gk_malloc(sizeof(gk_graph_t), "gk_graph_Create: graph");
|
|
|
|
gk_graph_Init(graph);
|
|
|
|
return graph;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Initializes the graph.
|
|
\param graph is the graph to be initialized.
|
|
*/
|
|
/*************************************************************************/
|
|
void gk_graph_Init(gk_graph_t *graph)
|
|
{
|
|
memset(graph, 0, sizeof(gk_graph_t));
|
|
graph->nvtxs = -1;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Frees all the memory allocated for a graph.
|
|
\param graph is the graph to be freed.
|
|
*/
|
|
/*************************************************************************/
|
|
void gk_graph_Free(gk_graph_t **graph)
|
|
{
|
|
if (*graph == NULL)
|
|
return;
|
|
gk_graph_FreeContents(*graph);
|
|
gk_free((void **)graph, LTERM);
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Frees only the memory allocated for the graph's different fields and
|
|
sets them to NULL.
|
|
\param graph is the graph whose contents will be freed.
|
|
*/
|
|
/*************************************************************************/
|
|
void gk_graph_FreeContents(gk_graph_t *graph)
|
|
{
|
|
gk_free((void *)&graph->xadj, &graph->adjncy,
|
|
&graph->iadjwgt, &graph->fadjwgt,
|
|
&graph->ivwgts, &graph->fvwgts,
|
|
&graph->ivsizes, &graph->fvsizes,
|
|
&graph->vlabels,
|
|
LTERM);
|
|
}
|
|
|
|
|
|
/**************************************************************************/
|
|
/*! Reads a sparse graph from the supplied file
|
|
\param filename is the file that stores the data.
|
|
\param format is the graph format. The supported values are:
|
|
GK_GRAPH_FMT_METIS, GK_GRAPH_FMT_IJV.
|
|
\param hasvals is 1 if the input file has values
|
|
\param numbering is 1 if the input file numbering starts from one
|
|
\param isfewgts is 1 if the edge-weights should be read as floats
|
|
\param isfvwgts is 1 if the vertex-weights should be read as floats
|
|
\param isfvsizes is 1 if the vertex-sizes should be read as floats
|
|
\returns the graph that was read.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_Read(char *filename, int format, int hasvals,
|
|
int numbering, int isfewgts, int isfvwgts, int isfvsizes)
|
|
{
|
|
ssize_t i, k, l;
|
|
size_t nfields, nvtxs, nedges, fmt, ncon, lnlen;
|
|
ssize_t *xadj;
|
|
int32_t ival, *iinds=NULL, *jinds=NULL, *ivals=NULL, *adjncy, *iadjwgt;
|
|
float fval, *fvals=NULL, *fadjwgt;
|
|
int readsizes=0, readwgts=0, readvals=0;
|
|
char *line=NULL, *head, *tail, fmtstr[256];
|
|
FILE *fpin=NULL;
|
|
gk_graph_t *graph=NULL;
|
|
|
|
|
|
if (!gk_fexists(filename))
|
|
gk_errexit(SIGERR, "File %s does not exist!\n", filename);
|
|
|
|
switch (format) {
|
|
case GK_GRAPH_FMT_METIS:
|
|
fpin = gk_fopen(filename, "r", "gk_graph_Read: fpin");
|
|
do {
|
|
if (gk_getline(&line, &lnlen, fpin) <= 0)
|
|
gk_errexit(SIGERR, "Premature end of input file: file:%s\n", filename);
|
|
} while (line[0] == '%');
|
|
|
|
fmt = ncon = 0;
|
|
nfields = sscanf(line, "%zu %zu %zu %zu", &nvtxs, &nedges, &fmt, &ncon);
|
|
if (nfields < 2)
|
|
gk_errexit(SIGERR, "Header line must contain at least 2 integers (#vtxs and #edges).\n");
|
|
|
|
nedges *= 2;
|
|
|
|
if (fmt > 111)
|
|
gk_errexit(SIGERR, "Cannot read this type of file format [fmt=%zu]!\n", fmt);
|
|
|
|
sprintf(fmtstr, "%03zu", fmt%1000);
|
|
readsizes = (fmtstr[0] == '1');
|
|
readwgts = (fmtstr[1] == '1');
|
|
readvals = (fmtstr[2] == '1');
|
|
numbering = 1;
|
|
ncon = (ncon == 0 ? 1 : ncon);
|
|
|
|
graph = gk_graph_Create();
|
|
|
|
graph->nvtxs = nvtxs;
|
|
|
|
graph->xadj = gk_zmalloc(nvtxs+1, "gk_graph_Read: xadj");
|
|
graph->adjncy = gk_i32malloc(nedges, "gk_graph_Read: adjncy");
|
|
if (readvals) {
|
|
if (isfewgts)
|
|
graph->fadjwgt = gk_fmalloc(nedges, "gk_graph_Read: fadjwgt");
|
|
else
|
|
graph->iadjwgt = gk_i32malloc(nedges, "gk_graph_Read: iadjwgt");
|
|
}
|
|
|
|
if (readsizes) {
|
|
if (isfvsizes)
|
|
graph->fvsizes = gk_fmalloc(nvtxs, "gk_graph_Read: fvsizes");
|
|
else
|
|
graph->ivsizes = gk_i32malloc(nvtxs, "gk_graph_Read: ivsizes");
|
|
}
|
|
|
|
if (readwgts) {
|
|
if (isfvwgts)
|
|
graph->fvwgts = gk_fmalloc(nvtxs*ncon, "gk_graph_Read: fvwgts");
|
|
else
|
|
graph->ivwgts = gk_i32malloc(nvtxs*ncon, "gk_graph_Read: ivwgts");
|
|
}
|
|
|
|
|
|
/*----------------------------------------------------------------------
|
|
* Read the sparse graph file
|
|
*---------------------------------------------------------------------*/
|
|
numbering = (numbering ? - 1 : 0);
|
|
for (graph->xadj[0]=0, k=0, i=0; i<nvtxs; i++) {
|
|
do {
|
|
if (gk_getline(&line, &lnlen, fpin) == -1)
|
|
gk_errexit(SIGERR, "Pregraphure end of input file: file while reading row %d\n", i);
|
|
} while (line[0] == '%');
|
|
|
|
head = line;
|
|
tail = NULL;
|
|
|
|
/* Read vertex sizes */
|
|
if (readsizes) {
|
|
if (isfvsizes) {
|
|
#ifdef __MSC__
|
|
graph->fvsizes[i] = (float)strtod(head, &tail);
|
|
#else
|
|
graph->fvsizes[i] = strtof(head, &tail);
|
|
#endif
|
|
if (tail == head)
|
|
gk_errexit(SIGERR, "The line for vertex %zd does not have size information\n", i+1);
|
|
if (graph->fvsizes[i] < 0)
|
|
gk_errexit(SIGERR, "The size for vertex %zd must be >= 0\n", i+1);
|
|
}
|
|
else {
|
|
graph->ivsizes[i] = strtol(head, &tail, 0);
|
|
if (tail == head)
|
|
gk_errexit(SIGERR, "The line for vertex %zd does not have size information\n", i+1);
|
|
if (graph->ivsizes[i] < 0)
|
|
gk_errexit(SIGERR, "The size for vertex %zd must be >= 0\n", i+1);
|
|
}
|
|
head = tail;
|
|
}
|
|
|
|
/* Read vertex weights */
|
|
if (readwgts) {
|
|
for (l=0; l<ncon; l++) {
|
|
if (isfvwgts) {
|
|
#ifdef __MSC__
|
|
graph->fvwgts[i*ncon+l] = (float)strtod(head, &tail);
|
|
#else
|
|
graph->fvwgts[i*ncon+l] = strtof(head, &tail);
|
|
#endif
|
|
if (tail == head)
|
|
gk_errexit(SIGERR, "The line for vertex %zd does not have enough weights "
|
|
"for the %d constraints.\n", i+1, ncon);
|
|
if (graph->fvwgts[i*ncon+l] < 0)
|
|
gk_errexit(SIGERR, "The weight vertex %zd and constraint %zd must be >= 0\n", i+1, l);
|
|
}
|
|
else {
|
|
graph->ivwgts[i*ncon+l] = strtol(head, &tail, 0);
|
|
if (tail == head)
|
|
gk_errexit(SIGERR, "The line for vertex %zd does not have enough weights "
|
|
"for the %d constraints.\n", i+1, ncon);
|
|
if (graph->ivwgts[i*ncon+l] < 0)
|
|
gk_errexit(SIGERR, "The weight vertex %zd and constraint %zd must be >= 0\n", i+1, l);
|
|
}
|
|
head = tail;
|
|
}
|
|
}
|
|
|
|
|
|
/* Read the rest of the row */
|
|
while (1) {
|
|
ival = (int)strtol(head, &tail, 0);
|
|
if (tail == head)
|
|
break;
|
|
head = tail;
|
|
|
|
if ((graph->adjncy[k] = ival + numbering) < 0)
|
|
gk_errexit(SIGERR, "Error: Invalid column number %d at row %zd.\n", ival, i);
|
|
|
|
if (readvals) {
|
|
if (isfewgts) {
|
|
#ifdef __MSC__
|
|
fval = (float)strtod(head, &tail);
|
|
#else
|
|
fval = strtof(head, &tail);
|
|
#endif
|
|
if (tail == head)
|
|
gk_errexit(SIGERR, "Value could not be found for edge! Vertex:%zd, NNZ:%zd\n", i, k);
|
|
|
|
graph->fadjwgt[k] = fval;
|
|
}
|
|
else {
|
|
ival = strtol(head, &tail, 0);
|
|
if (tail == head)
|
|
gk_errexit(SIGERR, "Value could not be found for edge! Vertex:%zd, NNZ:%zd\n", i, k);
|
|
|
|
graph->iadjwgt[k] = ival;
|
|
}
|
|
head = tail;
|
|
}
|
|
k++;
|
|
}
|
|
graph->xadj[i+1] = k;
|
|
}
|
|
|
|
if (k != nedges)
|
|
gk_errexit(SIGERR, "gk_graph_Read: Something wrong with the number of edges in "
|
|
"the input file. nedges=%zd, Actualnedges=%zd.\n", nedges, k);
|
|
|
|
gk_fclose(fpin);
|
|
|
|
gk_free((void **)&line, LTERM);
|
|
|
|
break;
|
|
|
|
case GK_GRAPH_FMT_IJV:
|
|
case GK_GRAPH_FMT_HIJV:
|
|
gk_getfilestats(filename, &nvtxs, &nedges, NULL, NULL);
|
|
|
|
if (format == GK_GRAPH_FMT_HIJV) { /* remove the #rows/#cols values and row */
|
|
nedges -= 2;
|
|
nvtxs -= 1;
|
|
}
|
|
|
|
if (hasvals == 1 && 3*nvtxs != nedges)
|
|
gk_errexit(SIGERR, "Error: The number of numbers (%zd %d) in the input file is not a multiple of 3.\n", nedges, hasvals);
|
|
if (hasvals == 0 && 2*nvtxs != nedges)
|
|
gk_errexit(SIGERR, "Error: The number of numbers (%zd %d) in the input file is not a multiple of 2.\n", nedges, hasvals);
|
|
|
|
nedges = nvtxs;
|
|
numbering = (numbering ? -1 : 0);
|
|
|
|
/* read the data into three arrays */
|
|
iinds = gk_i32malloc(nedges, "iinds");
|
|
jinds = gk_i32malloc(nedges, "jinds");
|
|
if (hasvals) {
|
|
if (isfewgts)
|
|
fvals = gk_fmalloc(nedges, "fvals");
|
|
else
|
|
ivals = gk_i32malloc(nedges, "ivals");
|
|
}
|
|
|
|
fpin = gk_fopen(filename, "r", "gk_graph_Read: fpin");
|
|
|
|
if (format == GK_GRAPH_FMT_HIJV) { /* read and ignore the #rows/#cols values */
|
|
if (fscanf(fpin, "%zd %zd", &i, &i) != 2)
|
|
gk_errexit(SIGERR, "Error: Failed to read the header line.\n");
|
|
}
|
|
|
|
for (nvtxs=0, i=0; i<nedges; i++) {
|
|
if (hasvals) {
|
|
if (isfewgts) {
|
|
if (fscanf(fpin, "%"PRId32" %"PRId32" %f", &iinds[i], &jinds[i], &fvals[i]) != 3)
|
|
gk_errexit(SIGERR, "Error: Failed to read (i, j, val) for nedge: %zd.\n", i);
|
|
}
|
|
else {
|
|
if (fscanf(fpin, "%"PRId32" %"PRId32" %"PRId32, &iinds[i], &jinds[i], &ivals[i]) != 3)
|
|
gk_errexit(SIGERR, "Error: Failed to read (i, j, val) for nedge: %zd.\n", i);
|
|
}
|
|
}
|
|
else {
|
|
if (fscanf(fpin, "%"PRId32" %"PRId32, &iinds[i], &jinds[i]) != 2)
|
|
gk_errexit(SIGERR, "Error: Failed to read (i, j) value for nedge: %zd.\n", i);
|
|
}
|
|
iinds[i] += numbering;
|
|
jinds[i] += numbering;
|
|
|
|
if (nvtxs < iinds[i])
|
|
nvtxs = iinds[i];
|
|
if (nvtxs < jinds[i])
|
|
nvtxs = jinds[i];
|
|
}
|
|
gk_fclose(fpin);
|
|
|
|
/* convert (i, j, v) into a graph format */
|
|
graph = gk_graph_Create();
|
|
graph->nvtxs = ++nvtxs;
|
|
xadj = graph->xadj = gk_zsmalloc(nvtxs+1, 0, "xadj");
|
|
adjncy = graph->adjncy = gk_i32malloc(nedges, "adjncy");
|
|
if (hasvals) {
|
|
if (isfewgts)
|
|
fadjwgt = graph->fadjwgt = gk_fmalloc(nedges, "fadjwgt");
|
|
else
|
|
iadjwgt = graph->iadjwgt = gk_i32malloc(nedges, "iadjwgt");
|
|
}
|
|
|
|
for (i=0; i<nedges; i++)
|
|
xadj[iinds[i]]++;
|
|
MAKECSR(i, nvtxs, xadj);
|
|
|
|
for (i=0; i<nedges; i++) {
|
|
adjncy[xadj[iinds[i]]] = jinds[i];
|
|
if (hasvals) {
|
|
if (isfewgts)
|
|
fadjwgt[xadj[iinds[i]]] = fvals[i];
|
|
else
|
|
iadjwgt[xadj[iinds[i]]] = ivals[i];
|
|
}
|
|
xadj[iinds[i]]++;
|
|
}
|
|
SHIFTCSR(i, nvtxs, xadj);
|
|
|
|
gk_free((void **)&iinds, &jinds, &fvals, &ivals, LTERM);
|
|
break;
|
|
|
|
default:
|
|
gk_errexit(SIGERR, "Unrecognized format: %d\n", format);
|
|
}
|
|
|
|
return graph;
|
|
}
|
|
|
|
|
|
/**************************************************************************/
|
|
/*! Writes a graph into a file.
|
|
\param graph is the graph to be written,
|
|
\param filename is the name of the output file.
|
|
\param format specifies the format of the output file.
|
|
\param numbering is either 0 or 1, indicating if the first vertex
|
|
will be numbered 0 or 1. Some formats ignore this.
|
|
*/
|
|
/**************************************************************************/
|
|
void gk_graph_Write(gk_graph_t *graph, char *filename, int format, int numbering)
|
|
{
|
|
int32_t i;
|
|
ssize_t j;
|
|
int hasvwgts, hasvsizes, hasewgts;
|
|
FILE *fpout;
|
|
|
|
if (filename)
|
|
fpout = gk_fopen(filename, "w", "gk_graph_Write: fpout");
|
|
else
|
|
fpout = stdout;
|
|
|
|
|
|
hasewgts = (graph->iadjwgt || graph->fadjwgt);
|
|
hasvwgts = (graph->ivwgts || graph->fvwgts);
|
|
hasvsizes = (graph->ivsizes || graph->fvsizes);
|
|
|
|
switch (format) {
|
|
case GK_GRAPH_FMT_METIS:
|
|
/* write the header line */
|
|
fprintf(fpout, "%d %zd", graph->nvtxs, graph->xadj[graph->nvtxs]/2);
|
|
if (hasvwgts || hasvsizes || hasewgts)
|
|
fprintf(fpout, " %d%d%d", hasvsizes, hasvwgts, hasewgts);
|
|
fprintf(fpout, "\n");
|
|
|
|
|
|
for (i=0; i<graph->nvtxs; i++) {
|
|
if (hasvsizes) {
|
|
if (graph->ivsizes)
|
|
fprintf(fpout, " %d", graph->ivsizes[i]);
|
|
else
|
|
fprintf(fpout, " %f", graph->fvsizes[i]);
|
|
}
|
|
|
|
if (hasvwgts) {
|
|
if (graph->ivwgts)
|
|
fprintf(fpout, " %d", graph->ivwgts[i]);
|
|
else
|
|
fprintf(fpout, " %f", graph->fvwgts[i]);
|
|
}
|
|
|
|
for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++) {
|
|
fprintf(fpout, " %d", graph->adjncy[j]+1);
|
|
if (hasewgts) {
|
|
if (graph->iadjwgt)
|
|
fprintf(fpout, " %d", graph->iadjwgt[j]);
|
|
else
|
|
fprintf(fpout, " %f", graph->fadjwgt[j]);
|
|
}
|
|
}
|
|
fprintf(fpout, "\n");
|
|
}
|
|
break;
|
|
|
|
case GK_GRAPH_FMT_IJV:
|
|
for (i=0; i<graph->nvtxs; i++) {
|
|
for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++) {
|
|
fprintf(fpout, "%d %d ", i+numbering, graph->adjncy[j]+numbering);
|
|
if (hasewgts) {
|
|
if (graph->iadjwgt)
|
|
fprintf(fpout, " %d\n", graph->iadjwgt[j]);
|
|
else
|
|
fprintf(fpout, " %f\n", graph->fadjwgt[j]);
|
|
}
|
|
else {
|
|
fprintf(fpout, " 1\n");
|
|
}
|
|
}
|
|
}
|
|
break;
|
|
|
|
default:
|
|
gk_errexit(SIGERR, "Unknown file format. %d\n", format);
|
|
}
|
|
|
|
if (filename)
|
|
gk_fclose(fpout);
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Returns a copy of a graph.
|
|
\param graph is the graph to be duplicated.
|
|
\returns the newly created copy of the graph.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_Dup(gk_graph_t *graph)
|
|
{
|
|
gk_graph_t *ngraph;
|
|
|
|
ngraph = gk_graph_Create();
|
|
|
|
ngraph->nvtxs = graph->nvtxs;
|
|
|
|
/* copy the adjacency structure */
|
|
if (graph->xadj)
|
|
ngraph->xadj = gk_zcopy(graph->nvtxs+1, graph->xadj,
|
|
gk_zmalloc(graph->nvtxs+1, "gk_graph_Dup: xadj"));
|
|
if (graph->ivwgts)
|
|
ngraph->ivwgts = gk_i32copy(graph->nvtxs, graph->ivwgts,
|
|
gk_i32malloc(graph->nvtxs, "gk_graph_Dup: ivwgts"));
|
|
if (graph->ivsizes)
|
|
ngraph->ivsizes = gk_i32copy(graph->nvtxs, graph->ivsizes,
|
|
gk_i32malloc(graph->nvtxs, "gk_graph_Dup: ivsizes"));
|
|
if (graph->vlabels)
|
|
ngraph->vlabels = gk_i32copy(graph->nvtxs, graph->vlabels,
|
|
gk_i32malloc(graph->nvtxs, "gk_graph_Dup: ivlabels"));
|
|
if (graph->fvwgts)
|
|
ngraph->fvwgts = gk_fcopy(graph->nvtxs, graph->fvwgts,
|
|
gk_fmalloc(graph->nvtxs, "gk_graph_Dup: fvwgts"));
|
|
if (graph->fvsizes)
|
|
ngraph->fvsizes = gk_fcopy(graph->nvtxs, graph->fvsizes,
|
|
gk_fmalloc(graph->nvtxs, "gk_graph_Dup: fvsizes"));
|
|
|
|
|
|
if (graph->adjncy)
|
|
ngraph->adjncy = gk_i32copy(graph->xadj[graph->nvtxs], graph->adjncy,
|
|
gk_i32malloc(graph->xadj[graph->nvtxs], "gk_graph_Dup: adjncy"));
|
|
if (graph->iadjwgt)
|
|
ngraph->iadjwgt = gk_i32copy(graph->xadj[graph->nvtxs], graph->iadjwgt,
|
|
gk_i32malloc(graph->xadj[graph->nvtxs], "gk_graph_Dup: iadjwgt"));
|
|
if (graph->fadjwgt)
|
|
ngraph->fadjwgt = gk_fcopy(graph->xadj[graph->nvtxs], graph->fadjwgt,
|
|
gk_fmalloc(graph->xadj[graph->nvtxs], "gk_graph_Dup: fadjwgt"));
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Returns the transpose of a graph.
|
|
\param graph is the graph to be transposed.
|
|
\returns the newly created copy of the graph.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_Transpose(gk_graph_t *graph)
|
|
{
|
|
int32_t vi, vj;
|
|
ssize_t ei;
|
|
|
|
gk_graph_t *ngraph;
|
|
|
|
ngraph = gk_graph_Create();
|
|
|
|
ngraph->nvtxs = graph->nvtxs;
|
|
ngraph->xadj = gk_zsmalloc(graph->nvtxs+1, 0, "gk_graph_Transpose: xadj");
|
|
ngraph->adjncy = gk_i32malloc(graph->xadj[graph->nvtxs], "gk_graph_Transpose: adjncy");
|
|
|
|
if (graph->iadjwgt)
|
|
ngraph->iadjwgt = gk_i32malloc(graph->xadj[graph->nvtxs], "gk_graph_Transpose: iadjwgt");
|
|
if (graph->fadjwgt)
|
|
ngraph->fadjwgt = gk_fmalloc(graph->xadj[graph->nvtxs], "gk_graph_Transpose: fadjwgt");
|
|
|
|
for (vi=0; vi<graph->nvtxs; vi++) {
|
|
for (ei=graph->xadj[vi]; ei<graph->xadj[vi+1]; ei++)
|
|
ngraph->xadj[graph->adjncy[ei]]++;
|
|
}
|
|
MAKECSR(vi, ngraph->nvtxs, ngraph->xadj);
|
|
|
|
for (vi=0; vi<graph->nvtxs; vi++) {
|
|
for (ei=graph->xadj[vi]; ei<graph->xadj[vi+1]; ei++) {
|
|
vj = graph->adjncy[ei];
|
|
ngraph->adjncy[ngraph->xadj[vj]] = vi;
|
|
if (ngraph->iadjwgt)
|
|
ngraph->iadjwgt[ngraph->xadj[vj]] = graph->iadjwgt[ei];
|
|
if (ngraph->fadjwgt)
|
|
ngraph->fadjwgt[ngraph->xadj[vj]] = graph->fadjwgt[ei];
|
|
ngraph->xadj[vj]++;
|
|
}
|
|
}
|
|
SHIFTCSR(vi, ngraph->nvtxs, ngraph->xadj);
|
|
|
|
/* copy vertex attributes */
|
|
if (graph->ivwgts)
|
|
ngraph->ivwgts = gk_i32copy(graph->nvtxs, graph->ivwgts,
|
|
gk_i32malloc(graph->nvtxs, "gk_graph_Transpose: ivwgts"));
|
|
if (graph->ivsizes)
|
|
ngraph->ivsizes = gk_i32copy(graph->nvtxs, graph->ivsizes,
|
|
gk_i32malloc(graph->nvtxs, "gk_graph_Transpose: ivsizes"));
|
|
if (graph->vlabels)
|
|
ngraph->vlabels = gk_i32copy(graph->nvtxs, graph->vlabels,
|
|
gk_i32malloc(graph->nvtxs, "gk_graph_Transpose: ivlabels"));
|
|
if (graph->fvwgts)
|
|
ngraph->fvwgts = gk_fcopy(graph->nvtxs, graph->fvwgts,
|
|
gk_fmalloc(graph->nvtxs, "gk_graph_Transpose: fvwgts"));
|
|
if (graph->fvsizes)
|
|
ngraph->fvsizes = gk_fcopy(graph->nvtxs, graph->fvsizes,
|
|
gk_fmalloc(graph->nvtxs, "gk_graph_Transpose: fvsizes"));
|
|
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Returns a subgraph containing a set of consecutive vertices.
|
|
\param graph is the original graph.
|
|
\param vstart is the starting vertex.
|
|
\param nvtxs is the number of vertices from vstart to extract.
|
|
\returns the newly created subgraph.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_ExtractSubgraph(gk_graph_t *graph, int vstart, int nvtxs)
|
|
{
|
|
ssize_t i;
|
|
gk_graph_t *ngraph;
|
|
|
|
if (vstart+nvtxs > graph->nvtxs)
|
|
return NULL;
|
|
|
|
ngraph = gk_graph_Create();
|
|
|
|
ngraph->nvtxs = nvtxs;
|
|
|
|
/* copy the adjancy structure */
|
|
if (graph->xadj)
|
|
ngraph->xadj = gk_zcopy(nvtxs+1, graph->xadj+vstart,
|
|
gk_zmalloc(nvtxs+1, "gk_graph_ExtractSubgraph: xadj"));
|
|
for (i=nvtxs; i>=0; i--)
|
|
ngraph->xadj[i] -= ngraph->xadj[0];
|
|
ASSERT(ngraph->xadj[0] == 0);
|
|
|
|
if (graph->ivwgts)
|
|
ngraph->ivwgts = gk_i32copy(nvtxs, graph->ivwgts+vstart,
|
|
gk_i32malloc(nvtxs, "gk_graph_ExtractSubgraph: ivwgts"));
|
|
if (graph->ivsizes)
|
|
ngraph->ivsizes = gk_i32copy(nvtxs, graph->ivsizes+vstart,
|
|
gk_i32malloc(nvtxs, "gk_graph_ExtractSubgraph: ivsizes"));
|
|
if (graph->vlabels)
|
|
ngraph->vlabels = gk_i32copy(nvtxs, graph->vlabels+vstart,
|
|
gk_i32malloc(nvtxs, "gk_graph_ExtractSubgraph: vlabels"));
|
|
|
|
if (graph->fvwgts)
|
|
ngraph->fvwgts = gk_fcopy(nvtxs, graph->fvwgts+vstart,
|
|
gk_fmalloc(nvtxs, "gk_graph_ExtractSubgraph: fvwgts"));
|
|
if (graph->fvsizes)
|
|
ngraph->fvsizes = gk_fcopy(nvtxs, graph->fvsizes+vstart,
|
|
gk_fmalloc(nvtxs, "gk_graph_ExtractSubgraph: fvsizes"));
|
|
|
|
|
|
ASSERT(ngraph->xadj[nvtxs] == graph->xadj[vstart+nvtxs]-graph->xadj[vstart]);
|
|
if (graph->adjncy)
|
|
ngraph->adjncy = gk_i32copy(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
|
|
graph->adjncy+graph->xadj[vstart],
|
|
gk_i32malloc(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
|
|
"gk_graph_ExtractSubgraph: adjncy"));
|
|
if (graph->iadjwgt)
|
|
ngraph->iadjwgt = gk_i32copy(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
|
|
graph->iadjwgt+graph->xadj[vstart],
|
|
gk_i32malloc(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
|
|
"gk_graph_ExtractSubgraph: iadjwgt"));
|
|
if (graph->fadjwgt)
|
|
ngraph->fadjwgt = gk_fcopy(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
|
|
graph->fadjwgt+graph->xadj[vstart],
|
|
gk_fmalloc(graph->xadj[vstart+nvtxs]-graph->xadj[vstart],
|
|
"gk_graph_ExtractSubgraph: fadjwgt"));
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Returns a graph that has been reordered according to the permutation.
|
|
\param[IN] graph is the graph to be re-ordered.
|
|
\param[IN] perm is the new ordering of the graph's vertices
|
|
\param[IN] iperm is the original ordering of the re-ordered graph's vertices
|
|
\returns the newly created copy of the graph.
|
|
|
|
\note Either perm or iperm can be NULL but not both.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_Reorder(gk_graph_t *graph, int32_t *perm, int32_t *iperm)
|
|
{
|
|
ssize_t j, jj, *xadj;
|
|
int i, k, u, v, nvtxs;
|
|
int freeperm=0, freeiperm=0;
|
|
int32_t *adjncy;
|
|
gk_graph_t *ngraph;
|
|
|
|
if (perm == NULL && iperm == NULL)
|
|
return NULL;
|
|
|
|
ngraph = gk_graph_Create();
|
|
|
|
ngraph->nvtxs = nvtxs = graph->nvtxs;
|
|
xadj = graph->xadj;
|
|
adjncy = graph->adjncy;
|
|
|
|
/* allocate memory for the different structures that are present in graph */
|
|
if (graph->xadj)
|
|
ngraph->xadj = gk_zmalloc(nvtxs+1, "gk_graph_Reorder: xadj");
|
|
|
|
if (graph->ivwgts)
|
|
ngraph->ivwgts = gk_i32malloc(nvtxs, "gk_graph_Reorder: ivwgts");
|
|
|
|
if (graph->ivsizes)
|
|
ngraph->ivsizes = gk_i32malloc(nvtxs, "gk_graph_Reorder: ivsizes");
|
|
|
|
if (graph->vlabels)
|
|
ngraph->vlabels = gk_i32malloc(nvtxs, "gk_graph_Reorder: ivlabels");
|
|
|
|
if (graph->fvwgts)
|
|
ngraph->fvwgts = gk_fmalloc(nvtxs, "gk_graph_Reorder: fvwgts");
|
|
|
|
if (graph->fvsizes)
|
|
ngraph->fvsizes = gk_fmalloc(nvtxs, "gk_graph_Reorder: fvsizes");
|
|
|
|
|
|
if (graph->adjncy)
|
|
ngraph->adjncy = gk_i32malloc(graph->xadj[nvtxs], "gk_graph_Reorder: adjncy");
|
|
|
|
if (graph->iadjwgt)
|
|
ngraph->iadjwgt = gk_i32malloc(graph->xadj[nvtxs], "gk_graph_Reorder: iadjwgt");
|
|
|
|
if (graph->fadjwgt)
|
|
ngraph->fadjwgt = gk_fmalloc(graph->xadj[nvtxs], "gk_graph_Reorder: fadjwgt");
|
|
|
|
|
|
/* create perm/iperm if not provided */
|
|
if (perm == NULL) {
|
|
freeperm = 1;
|
|
perm = gk_i32malloc(nvtxs, "gk_graph_Reorder: perm");
|
|
for (i=0; i<nvtxs; i++)
|
|
perm[iperm[i]] = i;
|
|
}
|
|
if (iperm == NULL) {
|
|
freeiperm = 1;
|
|
iperm = gk_i32malloc(nvtxs, "gk_graph_Reorder: iperm");
|
|
for (i=0; i<nvtxs; i++)
|
|
iperm[perm[i]] = i;
|
|
}
|
|
|
|
/* fill-in the information of the re-ordered graph */
|
|
ngraph->xadj[0] = jj = 0;
|
|
for (v=0; v<nvtxs; v++) {
|
|
u = iperm[v];
|
|
for (j=xadj[u]; j<xadj[u+1]; j++, jj++) {
|
|
ngraph->adjncy[jj] = perm[adjncy[j]];
|
|
if (graph->iadjwgt)
|
|
ngraph->iadjwgt[jj] = graph->iadjwgt[j];
|
|
if (graph->fadjwgt)
|
|
ngraph->fadjwgt[jj] = graph->fadjwgt[j];
|
|
}
|
|
if (graph->ivwgts)
|
|
ngraph->ivwgts[v] = graph->ivwgts[u];
|
|
if (graph->fvwgts)
|
|
ngraph->fvwgts[v] = graph->fvwgts[u];
|
|
if (graph->ivsizes)
|
|
ngraph->ivsizes[v] = graph->ivsizes[u];
|
|
if (graph->fvsizes)
|
|
ngraph->fvsizes[v] = graph->fvsizes[u];
|
|
if (graph->vlabels)
|
|
ngraph->vlabels[v] = graph->vlabels[u];
|
|
|
|
ngraph->xadj[v+1] = jj;
|
|
}
|
|
|
|
|
|
/* free memory */
|
|
if (freeperm)
|
|
gk_free((void **)&perm, LTERM);
|
|
if (freeiperm)
|
|
gk_free((void **)&iperm, LTERM);
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! This function finds the connected components in a graph.
|
|
|
|
\param graph is the graph structure
|
|
\param cptr is the ptr structure of the CSR representation of the
|
|
components. The length of this vector must be graph->nvtxs+1.
|
|
\param cind is the indices structure of the CSR representation of
|
|
the components. The length of this vector must be graph->nvtxs.
|
|
|
|
\returns the number of components that it found.
|
|
|
|
\note The cptr and cind parameters can be NULL, in which case only the
|
|
number of connected components is returned.
|
|
*/
|
|
/*************************************************************************/
|
|
int gk_graph_FindComponents(gk_graph_t *graph, int32_t *cptr, int32_t *cind)
|
|
{
|
|
ssize_t i, ii, j, jj, k, nvtxs, first, last, ntodo, ncmps;
|
|
ssize_t *xadj;
|
|
int32_t *adjncy, *pos, *todo;
|
|
int32_t mustfree_ccsr=0;
|
|
|
|
nvtxs = graph->nvtxs;
|
|
xadj = graph->xadj;
|
|
adjncy = graph->adjncy;
|
|
|
|
/* Deal with NULL supplied cptr/cind vectors */
|
|
if (cptr == NULL) {
|
|
cptr = gk_i32malloc(nvtxs+1, "gk_graph_FindComponents: cptr");
|
|
cind = gk_i32malloc(nvtxs, "gk_graph_FindComponents: cind");
|
|
mustfree_ccsr = 1;
|
|
}
|
|
|
|
/* The list of vertices that have not been touched yet.
|
|
The valid entries are from [0..ntodo). */
|
|
todo = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: todo"));
|
|
|
|
/* For a vertex that has not been visited, pos[i] is the position in the
|
|
todo list that this vertex is stored.
|
|
If a vertex has been visited, pos[i] = -1. */
|
|
pos = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: pos"));
|
|
|
|
|
|
/* Find the connected componends */
|
|
ncmps = -1;
|
|
ntodo = nvtxs; /* All vertices have not been visited */
|
|
first = last = 0; /* Point to the first and last vertices that have been touched
|
|
but not explored.
|
|
These vertices are stored in cind[first]...cind[last-1]. */
|
|
while (1) {
|
|
if (first == last) { /* Find another starting vertex */
|
|
cptr[++ncmps] = first; /* Mark the end of the current CC */
|
|
|
|
if (ntodo > 0) {
|
|
/* put the first vertex in the todo list as the start of the new CC */
|
|
GKASSERT(pos[todo[0]] != -1);
|
|
cind[last++] = todo[0];
|
|
|
|
pos[todo[0]] = -1;
|
|
todo[0] = todo[--ntodo];
|
|
pos[todo[0]] = 0;
|
|
}
|
|
else {
|
|
break;
|
|
}
|
|
}
|
|
|
|
i = cind[first++]; /* Get the first visited but unexplored vertex */
|
|
|
|
for (j=xadj[i]; j<xadj[i+1]; j++) {
|
|
k = adjncy[j];
|
|
if (pos[k] != -1) {
|
|
cind[last++] = k;
|
|
|
|
/* Remove k from the todo list and put the last item in the todo
|
|
list at the position that k was so that the todo list will be
|
|
consequtive. The pos[] array is updated accordingly to keep track
|
|
the location of the vertices in the todo[] list. */
|
|
todo[pos[k]] = todo[--ntodo];
|
|
pos[todo[pos[k]]] = pos[k];
|
|
pos[k] = -1;
|
|
}
|
|
}
|
|
}
|
|
GKASSERT(first == nvtxs);
|
|
|
|
if (mustfree_ccsr)
|
|
gk_free((void **)&cptr, &cind, LTERM);
|
|
|
|
gk_free((void **)&pos, &todo, LTERM);
|
|
|
|
return (int) ncmps;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! This function computes a permutation of the vertices based on a
|
|
breadth-first-traversal. It can be used for re-ordering the graph
|
|
to reduce its bandwidth for better cache locality.
|
|
The algorithm used is a simplified version of the method used to find
|
|
the connected components.
|
|
|
|
\param[IN] graph is the graph structure
|
|
\param[IN] v is the starting vertex of the BFS
|
|
\param[OUT] perm[i] stores the ID of vertex i in the re-ordered graph.
|
|
\param[OUT] iperm[i] stores the ID of the vertex that corresponds to
|
|
the ith vertex in the re-ordered graph.
|
|
|
|
\note The perm or iperm (but not both) can be NULL, at which point,
|
|
the corresponding arrays are not returned. Though the program
|
|
works fine when both are NULL, doing that is not smart.
|
|
The returned arrays should be freed with gk_free().
|
|
*/
|
|
/*************************************************************************/
|
|
void gk_graph_ComputeBFSOrdering(gk_graph_t *graph, int v, int32_t **r_perm,
|
|
int32_t **r_iperm)
|
|
{
|
|
ssize_t j, *xadj;
|
|
int i, k, nvtxs, first, last;
|
|
int32_t *adjncy, *cot, *pos;
|
|
|
|
if (graph->nvtxs <= 0)
|
|
return;
|
|
|
|
nvtxs = graph->nvtxs;
|
|
xadj = graph->xadj;
|
|
adjncy = graph->adjncy;
|
|
|
|
/* This array will function like pos + touched of the CC method */
|
|
pos = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_ComputeBFSOrdering: pos"));
|
|
|
|
/* This array ([C]losed[O]pen[T]odo => cot) serves three purposes.
|
|
Positions from [0...first) is the current iperm[] vector of the explored vertices;
|
|
Positions from [first...last) is the OPEN list (i.e., visited vertices);
|
|
Positions from [last...nvtxs) is the todo list. */
|
|
cot = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_ComputeBFSOrdering: cot"));
|
|
|
|
|
|
/* put v at the front of the todo list */
|
|
pos[0] = cot[0] = v;
|
|
pos[v] = cot[v] = 0;
|
|
|
|
/* compute a BFS ordering from the seed vertex */
|
|
first = last = 0;
|
|
while (first < nvtxs) {
|
|
if (first == last) { /* Find another starting vertex */
|
|
k = cot[last];
|
|
ASSERT(pos[k] != -1);
|
|
pos[k] = -1; /* mark node as being visited */
|
|
last++;
|
|
}
|
|
|
|
i = cot[first++]; /* the ++ advances the explored vertices */
|
|
for (j=xadj[i]; j<xadj[i+1]; j++) {
|
|
k = adjncy[j];
|
|
/* if a node has already been visited, its pos[] will be -1 */
|
|
if (pos[k] != -1) {
|
|
/* pos[k] is the location within cot[] where k resides (it is in the 'todo' part);
|
|
It is placed in that location cot[last] (end of OPEN list) that we
|
|
are about to overwrite and update pos[cot[last]] to reflect that. */
|
|
cot[pos[k]] = cot[last]; /* put the head of the todo list to
|
|
where k was in the todo list */
|
|
pos[cot[last]] = pos[k]; /* update perm to reflect the move */
|
|
|
|
cot[last++] = k; /* put node at the end of the OPEN list */
|
|
pos[k] = -1; /* mark node as being visited */
|
|
}
|
|
}
|
|
}
|
|
|
|
/* time to decide what to return */
|
|
if (r_perm != NULL) {
|
|
/* use the 'pos' array to build the perm array */
|
|
for (i=0; i<nvtxs; i++)
|
|
pos[cot[i]] = i;
|
|
|
|
*r_perm = pos;
|
|
pos = NULL;
|
|
}
|
|
|
|
if (r_iperm != NULL) {
|
|
*r_iperm = cot;
|
|
cot = NULL;
|
|
}
|
|
|
|
|
|
/* cleanup memory */
|
|
gk_free((void **)&pos, &cot, LTERM);
|
|
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! This function computes a permutation of the vertices based on a
|
|
best-first-traversal. It can be used for re-ordering the graph
|
|
to reduce its bandwidth for better cache locality.
|
|
|
|
\param[IN] graph is the graph structure.
|
|
\param[IN] v is the starting vertex of the best-first traversal.
|
|
\param[IN] type indicates the criteria to use to measure the 'bestness'
|
|
of a vertex.
|
|
\param[OUT] perm[i] stores the ID of vertex i in the re-ordered graph.
|
|
\param[OUT] iperm[i] stores the ID of the vertex that corresponds to
|
|
the ith vertex in the re-ordered graph.
|
|
|
|
\note The perm or iperm (but not both) can be NULL, at which point,
|
|
the corresponding arrays are not returned. Though the program
|
|
works fine when both are NULL, doing that is not smart.
|
|
The returned arrays should be freed with gk_free().
|
|
*/
|
|
/*************************************************************************/
|
|
void gk_graph_ComputeBestFOrdering0(gk_graph_t *graph, int v, int type,
|
|
int32_t **r_perm, int32_t **r_iperm)
|
|
{
|
|
ssize_t j, jj, *xadj;
|
|
int i, k, u, nvtxs;
|
|
int32_t *adjncy, *perm, *degrees, *minIDs, *open;
|
|
gk_i32pq_t *queue;
|
|
|
|
if (graph->nvtxs <= 0)
|
|
return;
|
|
|
|
nvtxs = graph->nvtxs;
|
|
xadj = graph->xadj;
|
|
adjncy = graph->adjncy;
|
|
|
|
/* the degree of the vertices in the closed list */
|
|
degrees = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: degrees");
|
|
|
|
/* the minimum vertex ID of an open vertex to the closed list */
|
|
minIDs = gk_i32smalloc(nvtxs, nvtxs+1, "gk_graph_ComputeBestFOrdering: minIDs");
|
|
|
|
/* the open list */
|
|
open = gk_i32malloc(nvtxs, "gk_graph_ComputeBestFOrdering: open");
|
|
|
|
/* if perm[i] >= 0, then perm[i] is the order of vertex i;
|
|
otherwise perm[i] == -1.
|
|
*/
|
|
perm = gk_i32smalloc(nvtxs, -1, "gk_graph_ComputeBestFOrdering: perm");
|
|
|
|
/* create the queue and put everything in it */
|
|
queue = gk_i32pqCreate(nvtxs);
|
|
for (i=0; i<nvtxs; i++)
|
|
gk_i32pqInsert(queue, i, 0);
|
|
gk_i32pqUpdate(queue, v, 1);
|
|
|
|
open[0] = v;
|
|
|
|
/* start processing the nodes */
|
|
for (i=0; i<nvtxs; i++) {
|
|
if ((v = gk_i32pqGetTop(queue)) == -1)
|
|
gk_errexit(SIGERR, "The priority queue got empty ahead of time [i=%d].\n", i);
|
|
if (perm[v] != -1)
|
|
gk_errexit(SIGERR, "The perm[%d] has already been set.\n", v);
|
|
perm[v] = i;
|
|
|
|
|
|
for (j=xadj[v]; j<xadj[v+1]; j++) {
|
|
u = adjncy[j];
|
|
if (perm[u] == -1) {
|
|
degrees[u]++;
|
|
minIDs[u] = (i < minIDs[u] ? i : minIDs[u]);
|
|
|
|
switch (type) {
|
|
case 1: /* DFS */
|
|
gk_i32pqUpdate(queue, u, 1);
|
|
break;
|
|
case 2: /* Max in closed degree */
|
|
gk_i32pqUpdate(queue, u, degrees[u]);
|
|
break;
|
|
case 3: /* Sum of orders in closed list */
|
|
for (k=0, jj=xadj[u]; jj<xadj[u+1]; jj++) {
|
|
if (perm[adjncy[jj]] != -1)
|
|
k += perm[adjncy[jj]];
|
|
}
|
|
gk_i32pqUpdate(queue, u, k);
|
|
break;
|
|
case 4: /* Sum of order-differences (w.r.t. current number) in closed
|
|
list (updated once in a while) */
|
|
for (k=0, jj=xadj[u]; jj<xadj[u+1]; jj++) {
|
|
if (perm[adjncy[jj]] != -1)
|
|
k += (i-perm[adjncy[jj]]);
|
|
}
|
|
gk_i32pqUpdate(queue, u, k);
|
|
break;
|
|
default:
|
|
;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
/* time to decide what to return */
|
|
if (r_perm != NULL) {
|
|
*r_perm = perm;
|
|
perm = NULL;
|
|
}
|
|
|
|
if (r_iperm != NULL) {
|
|
/* use the 'degrees' array to build the iperm array */
|
|
for (i=0; i<nvtxs; i++)
|
|
degrees[perm[i]] = i;
|
|
|
|
*r_iperm = degrees;
|
|
degrees = NULL;
|
|
}
|
|
|
|
|
|
|
|
/* cleanup memory */
|
|
gk_i32pqDestroy(queue);
|
|
gk_free((void **)&perm, °rees, &minIDs, &open, LTERM);
|
|
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! This function computes a permutation of the vertices based on a
|
|
best-first-traversal. It can be used for re-ordering the graph
|
|
to reduce its bandwidth for better cache locality.
|
|
|
|
\param[IN] graph is the graph structure.
|
|
\param[IN] v is the starting vertex of the best-first traversal.
|
|
\param[IN] type indicates the criteria to use to measure the 'bestness'
|
|
of a vertex.
|
|
\param[OUT] perm[i] stores the ID of vertex i in the re-ordered graph.
|
|
\param[OUT] iperm[i] stores the ID of the vertex that corresponds to
|
|
the ith vertex in the re-ordered graph.
|
|
|
|
\note The perm or iperm (but not both) can be NULL, at which point,
|
|
the corresponding arrays are not returned. Though the program
|
|
works fine when both are NULL, doing that is not smart.
|
|
The returned arrays should be freed with gk_free().
|
|
*/
|
|
/*************************************************************************/
|
|
void gk_graph_ComputeBestFOrdering(gk_graph_t *graph, int v, int type,
|
|
int32_t **r_perm, int32_t **r_iperm)
|
|
{
|
|
ssize_t j, jj, *xadj;
|
|
int i, k, u, nvtxs, nopen, ntodo;
|
|
int32_t *adjncy, *perm, *degrees, *sod, *level, *ot, *pos;
|
|
int64_t *wdegrees;
|
|
gk_i32pq_t *queue;
|
|
|
|
if (graph->nvtxs <= 0)
|
|
return;
|
|
|
|
nvtxs = graph->nvtxs;
|
|
xadj = graph->xadj;
|
|
adjncy = graph->adjncy;
|
|
|
|
/* the degree of the vertices in the closed list */
|
|
degrees = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: degrees");
|
|
|
|
/* the weighted degree of the vertices in the closed list for type==3 */
|
|
wdegrees = gk_i64smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: wdegrees");
|
|
|
|
/* the sum of differences for type==4 */
|
|
sod = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: sod");
|
|
|
|
/* the encountering level of a vertex type==5 */
|
|
level = gk_i32smalloc(nvtxs, 0, "gk_graph_ComputeBestFOrdering: level");
|
|
|
|
/* The open+todo list of vertices.
|
|
The vertices from [0..nopen] are the open vertices.
|
|
The vertices from [nopen..ntodo) are the todo vertices.
|
|
*/
|
|
ot = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: ot"));
|
|
|
|
/* For a vertex that has not been explored, pos[i] is the position in the ot list. */
|
|
pos = gk_i32incset(nvtxs, 0, gk_i32malloc(nvtxs, "gk_graph_FindComponents: pos"));
|
|
|
|
/* if perm[i] >= 0, then perm[i] is the order of vertex i; otherwise perm[i] == -1. */
|
|
perm = gk_i32smalloc(nvtxs, -1, "gk_graph_ComputeBestFOrdering: perm");
|
|
|
|
/* create the queue and put the starting vertex in it */
|
|
queue = gk_i32pqCreate(nvtxs);
|
|
gk_i32pqInsert(queue, v, 1);
|
|
|
|
/* put v at the front of the open list */
|
|
pos[0] = ot[0] = v;
|
|
pos[v] = ot[v] = 0;
|
|
nopen = 1;
|
|
ntodo = nvtxs;
|
|
|
|
/* start processing the nodes */
|
|
for (i=0; i<nvtxs; i++) {
|
|
if (nopen == 0) { /* deal with non-connected graphs */
|
|
gk_i32pqInsert(queue, ot[0], 1);
|
|
nopen++;
|
|
}
|
|
|
|
if ((v = gk_i32pqGetTop(queue)) == -1)
|
|
gk_errexit(SIGERR, "The priority queue got empty ahead of time [i=%d].\n", i);
|
|
|
|
if (perm[v] != -1)
|
|
gk_errexit(SIGERR, "The perm[%d] has already been set.\n", v);
|
|
perm[v] = i;
|
|
|
|
if (ot[pos[v]] != v)
|
|
gk_errexit(SIGERR, "Something went wrong [ot[pos[%d]]!=%d.\n", v, v);
|
|
if (pos[v] >= nopen)
|
|
gk_errexit(SIGERR, "The position of v is not in open list. pos[%d]=%d is >=%d.\n", v, pos[v], nopen);
|
|
|
|
/* remove v from the open list and re-arrange the todo part of the list */
|
|
ot[pos[v]] = ot[nopen-1];
|
|
pos[ot[nopen-1]] = pos[v];
|
|
if (ntodo > nopen) {
|
|
ot[nopen-1] = ot[ntodo-1];
|
|
pos[ot[ntodo-1]] = nopen-1;
|
|
}
|
|
nopen--;
|
|
ntodo--;
|
|
|
|
for (j=xadj[v]; j<xadj[v+1]; j++) {
|
|
u = adjncy[j];
|
|
if (perm[u] == -1) {
|
|
/* update ot list, if u is not in the open list by putting it at the end
|
|
of the open list. */
|
|
if (degrees[u] == 0) {
|
|
ot[pos[u]] = ot[nopen];
|
|
pos[ot[nopen]] = pos[u];
|
|
ot[nopen] = u;
|
|
pos[u] = nopen;
|
|
nopen++;
|
|
|
|
level[u] = level[v]+1;
|
|
gk_i32pqInsert(queue, u, 0);
|
|
}
|
|
|
|
|
|
/* update the in-closed degree */
|
|
degrees[u]++;
|
|
|
|
/* update the queues based on the type */
|
|
switch (type) {
|
|
case 1: /* DFS */
|
|
gk_i32pqUpdate(queue, u, 1000*(i+1)+degrees[u]);
|
|
break;
|
|
|
|
case 2: /* Max in closed degree */
|
|
gk_i32pqUpdate(queue, u, degrees[u]);
|
|
break;
|
|
|
|
case 3: /* Sum of orders in closed list */
|
|
wdegrees[u] += i;
|
|
gk_i32pqUpdate(queue, u, (int32_t)sqrt(wdegrees[u]));
|
|
break;
|
|
|
|
case 4: /* Sum of order-differences */
|
|
/* this is handled at the end of the loop */
|
|
;
|
|
break;
|
|
|
|
case 5: /* BFS with in degree priority */
|
|
gk_i32pqUpdate(queue, u, -(1000*level[u] - degrees[u]));
|
|
break;
|
|
|
|
case 6: /* Hybrid of 1+2 */
|
|
gk_i32pqUpdate(queue, u, (i+1)*degrees[u]);
|
|
break;
|
|
|
|
default:
|
|
;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (type == 4) { /* update all the vertices in the open list */
|
|
for (j=0; j<nopen; j++) {
|
|
u = ot[j];
|
|
if (perm[u] != -1)
|
|
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]);
|
|
sod[u] += degrees[u];
|
|
if (i<1000 || i%25==0)
|
|
gk_i32pqUpdate(queue, u, sod[u]);
|
|
}
|
|
}
|
|
|
|
/*
|
|
for (j=0; j<ntodo; j++) {
|
|
if (pos[ot[j]] != j)
|
|
gk_errexit(SIGERR, "pos[ot[%zd]] != %zd.\n", j, j);
|
|
}
|
|
*/
|
|
|
|
}
|
|
|
|
|
|
/* time to decide what to return */
|
|
if (r_perm != NULL) {
|
|
*r_perm = perm;
|
|
perm = NULL;
|
|
}
|
|
|
|
if (r_iperm != NULL) {
|
|
/* use the 'degrees' array to build the iperm array */
|
|
for (i=0; i<nvtxs; i++)
|
|
degrees[perm[i]] = i;
|
|
|
|
*r_iperm = degrees;
|
|
degrees = NULL;
|
|
}
|
|
|
|
|
|
|
|
/* cleanup memory */
|
|
gk_i32pqDestroy(queue);
|
|
gk_free((void **)&perm, °rees, &wdegrees, &sod, &ot, &pos, &level, LTERM);
|
|
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! This function computes the single-source shortest path lengths from the
|
|
root node to all the other nodes in the graph. If the graph is not
|
|
connected then, the sortest part to the vertices in the other components
|
|
is -1.
|
|
|
|
\param[IN] graph is the graph structure.
|
|
\param[IN] v is the root of the single-source shortest path computations.
|
|
\param[IN] type indicates the criteria to use to measure the 'bestness'
|
|
of a vertex.
|
|
\param[OUT] sps[i] stores the length of the shortest path from v to vertex i.
|
|
If no such path exists, then it is -1. Note that the returned
|
|
array will be either an array of int32_t or an array of floats.
|
|
The specific type is determined by the existance of non NULL
|
|
iadjwgt and fadjwgt arrays. If both of these arrays exist, then
|
|
priority is given to iadjwgt.
|
|
|
|
\note The returned array should be freed with gk_free().
|
|
*/
|
|
/*************************************************************************/
|
|
void gk_graph_SingleSourceShortestPaths(gk_graph_t *graph, int v, void **r_sps)
|
|
{
|
|
ssize_t *xadj;
|
|
int i, u, nvtxs;
|
|
int32_t *adjncy, *inqueue;
|
|
|
|
if (graph->nvtxs <= 0)
|
|
return;
|
|
|
|
nvtxs = graph->nvtxs;
|
|
xadj = graph->xadj;
|
|
adjncy = graph->adjncy;
|
|
|
|
inqueue = gk_i32smalloc(nvtxs, 0, "gk_graph_SingleSourceShortestPaths: inqueue");
|
|
|
|
/* determine if you will be computing using int32_t or float and proceed from there */
|
|
if (graph->iadjwgt != NULL) {
|
|
gk_i32pq_t *queue;
|
|
int32_t *adjwgt;
|
|
int32_t *sps;
|
|
|
|
adjwgt = graph->iadjwgt;
|
|
|
|
queue = gk_i32pqCreate(nvtxs);
|
|
gk_i32pqInsert(queue, v, 0);
|
|
inqueue[v] = 1;
|
|
|
|
sps = gk_i32smalloc(nvtxs, -1, "gk_graph_SingleSourceShortestPaths: sps");
|
|
sps[v] = 0;
|
|
|
|
/* start processing the nodes */
|
|
while ((v = gk_i32pqGetTop(queue)) != -1) {
|
|
inqueue[v] = 2;
|
|
|
|
/* relax the adjacent edges */
|
|
for (i=xadj[v]; i<xadj[v+1]; i++) {
|
|
u = adjncy[i];
|
|
if (inqueue[u] == 2)
|
|
continue;
|
|
|
|
if (sps[u] < 0 || sps[v]+adjwgt[i] < sps[u]) {
|
|
sps[u] = sps[v]+adjwgt[i];
|
|
|
|
if (inqueue[u])
|
|
gk_i32pqUpdate(queue, u, -sps[u]);
|
|
else {
|
|
gk_i32pqInsert(queue, u, -sps[u]);
|
|
inqueue[u] = 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
*r_sps = (void *)sps;
|
|
|
|
gk_i32pqDestroy(queue);
|
|
}
|
|
else {
|
|
gk_fpq_t *queue;
|
|
float *adjwgt;
|
|
float *sps;
|
|
|
|
adjwgt = graph->fadjwgt;
|
|
|
|
queue = gk_fpqCreate(nvtxs);
|
|
gk_fpqInsert(queue, v, 0);
|
|
inqueue[v] = 1;
|
|
|
|
sps = gk_fsmalloc(nvtxs, -1, "gk_graph_SingleSourceShortestPaths: sps");
|
|
sps[v] = 0;
|
|
|
|
/* start processing the nodes */
|
|
while ((v = gk_fpqGetTop(queue)) != -1) {
|
|
inqueue[v] = 2;
|
|
|
|
/* relax the adjacent edges */
|
|
for (i=xadj[v]; i<xadj[v+1]; i++) {
|
|
u = adjncy[i];
|
|
if (inqueue[u] == 2)
|
|
continue;
|
|
|
|
if (sps[u] < 0 || sps[v]+adjwgt[i] < sps[u]) {
|
|
sps[u] = sps[v]+adjwgt[i];
|
|
|
|
if (inqueue[u])
|
|
gk_fpqUpdate(queue, u, -sps[u]);
|
|
else {
|
|
gk_fpqInsert(queue, u, -sps[u]);
|
|
inqueue[u] = 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
*r_sps = (void *)sps;
|
|
|
|
gk_fpqDestroy(queue);
|
|
}
|
|
|
|
gk_free((void **)&inqueue, LTERM);
|
|
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Sorts the adjacency lists in increasing vertex order
|
|
\param graph the graph itself,
|
|
*/
|
|
/**************************************************************************/
|
|
void gk_graph_SortAdjacencies(gk_graph_t *graph)
|
|
{
|
|
int32_t nvtxs, nn=0;
|
|
ssize_t *xadj;
|
|
int32_t *adjncy;
|
|
int32_t *iadjwgt;
|
|
float *fadjwgt;
|
|
|
|
nvtxs = graph->nvtxs;
|
|
xadj = graph->xadj;
|
|
adjncy = graph->adjncy;
|
|
iadjwgt = graph->iadjwgt;
|
|
fadjwgt = graph->fadjwgt;
|
|
|
|
#pragma omp parallel if (nvtxs > 100)
|
|
{
|
|
ssize_t i, j, k;
|
|
gk_ikv_t *cand;
|
|
int32_t *itwgts=NULL;
|
|
float *ftwgts=NULL;
|
|
|
|
#pragma omp single
|
|
for (i=0; i<nvtxs; i++)
|
|
nn = gk_max(nn, xadj[i+1]-xadj[i]);
|
|
|
|
cand = gk_ikvmalloc(nn, "gk_graph_SortIndices: cand");
|
|
if (iadjwgt)
|
|
itwgts = gk_i32malloc(nn, "gk_graph_SortIndices: itwgts");
|
|
if (fadjwgt)
|
|
ftwgts = gk_fmalloc(nn, "gk_graph_SortIndices: ftwgts");
|
|
|
|
#pragma omp for schedule(static)
|
|
for (i=0; i<nvtxs; i++) {
|
|
for (k=0, j=xadj[i]; j<xadj[i+1]; j++) {
|
|
if (j > xadj[i] && adjncy[j] < adjncy[j-1])
|
|
k = 1; /* an inversion */
|
|
cand[j-xadj[i]].val = (int32_t)(j-xadj[i]);
|
|
cand[j-xadj[i]].key = adjncy[j];
|
|
if (itwgts)
|
|
itwgts[j-xadj[i]] = iadjwgt[j];
|
|
if (ftwgts)
|
|
ftwgts[j-xadj[i]] = fadjwgt[j];
|
|
}
|
|
if (k) {
|
|
gk_ikvsorti(xadj[i+1]-xadj[i], cand);
|
|
for (j=xadj[i]; j<xadj[i+1]; j++) {
|
|
adjncy[j] = cand[j-xadj[i]].key;
|
|
if (itwgts)
|
|
iadjwgt[j] = itwgts[cand[j-xadj[i]].val];
|
|
if (ftwgts)
|
|
fadjwgt[j] = ftwgts[cand[j-xadj[i]].val];
|
|
}
|
|
}
|
|
}
|
|
|
|
gk_free((void **)&cand, &itwgts, &ftwgts, LTERM);
|
|
}
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Returns a symmetric version of a graph. The symmetric version
|
|
is constructed by applying an A op A^T operation, where op is one of
|
|
GK_GRAPH_SYM_SUM, GK_GRAPH_SYM_MIN, GK_GRAPH_SYM_MAX, GK_GRAPH_SYM_AVG.
|
|
|
|
\param mat the matrix to be symmetrized,
|
|
\param op indicates the operation to be performed. The possible values are
|
|
GK_GRAPH_SYM_SUM, GK_GRAPH_SYM_MIN, GK_GRAPH_SYM_MAX, and GK_GRAPH_SYM_AVG.
|
|
|
|
\returns the symmetrized matrix consisting only of its row-based structure.
|
|
The input matrix is not modified.
|
|
|
|
TODO: Need to deal with all vertex attributes that are currently do not get
|
|
copied over.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_MakeSymmetric(gk_graph_t *graph, int op)
|
|
{
|
|
ssize_t i, j, k, nnz;
|
|
int nrows, nadj, hasvals;
|
|
ssize_t *rowptr, *colptr, *nrowptr;
|
|
int *rowind, *colind, *nrowind, *marker, *ids;
|
|
float *rowval=NULL, *colval=NULL, *nrowval=NULL, *wgts=NULL;
|
|
int32_t *irowval=NULL, *icolval=NULL, *nirowval=NULL, *iwgts=NULL;
|
|
gk_graph_t *ngraph;
|
|
|
|
hasvals = (graph->iadjwgt != NULL || graph->fadjwgt != NULL);
|
|
|
|
nrows = graph->nvtxs;
|
|
rowptr = graph->xadj;
|
|
rowind = graph->adjncy;
|
|
if (hasvals) {
|
|
irowval = graph->iadjwgt;
|
|
rowval = graph->fadjwgt;
|
|
}
|
|
|
|
/* create the column view for efficient processing */
|
|
colptr = gk_zsmalloc(nrows+1, 0, "colptr");
|
|
colind = gk_i32malloc(rowptr[nrows], "colind");
|
|
if (hasvals) {
|
|
if (rowval)
|
|
colval = gk_fmalloc(rowptr[nrows], "colval");
|
|
if (irowval)
|
|
icolval = gk_i32malloc(rowptr[nrows], "icolval");
|
|
}
|
|
|
|
for (i=0; i<nrows; i++) {
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++)
|
|
colptr[rowind[j]]++;
|
|
}
|
|
MAKECSR(i, nrows, colptr);
|
|
|
|
for (i=0; i<nrows; i++) {
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++) {
|
|
colind[colptr[rowind[j]]] = i;
|
|
if (hasvals) {
|
|
if (rowval)
|
|
colval[colptr[rowind[j]]] = rowval[j];
|
|
if (irowval)
|
|
icolval[colptr[rowind[j]]] = irowval[j];
|
|
}
|
|
colptr[rowind[j]]++;
|
|
}
|
|
}
|
|
SHIFTCSR(i, nrows, colptr);
|
|
|
|
|
|
ngraph = gk_graph_Create();
|
|
ngraph->nvtxs = graph->nvtxs;
|
|
|
|
nrowptr = ngraph->xadj = gk_zmalloc(nrows+1, "gk_csr_MakeSymmetric: nrowptr");
|
|
nrowind = ngraph->adjncy = gk_imalloc(2*rowptr[nrows], "gk_csr_MakeSymmetric: nrowind");
|
|
if (hasvals) {
|
|
if (rowval)
|
|
nrowval = graph->fadjwgt = gk_fmalloc(2*rowptr[nrows], "gk_csr_MakeSymmetric: nrowval");
|
|
if (irowval)
|
|
nirowval = graph->iadjwgt = gk_i32malloc(2*rowptr[nrows], "gk_csr_MakeSymmetric: nrowval");
|
|
}
|
|
|
|
marker = gk_ismalloc(nrows, -1, "marker");
|
|
ids = gk_imalloc(nrows, "ids");
|
|
if (hasvals) {
|
|
if (rowval)
|
|
wgts = gk_fmalloc(nrows, "wgts");
|
|
if (irowval)
|
|
iwgts = gk_i32malloc(nrows, "wgts");
|
|
}
|
|
|
|
nrowptr[0] = nnz = 0;
|
|
for (i=0; i<nrows; i++) {
|
|
nadj = 0;
|
|
/* out-edges */
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++) {
|
|
ids[nadj] = rowind[j];
|
|
if (wgts)
|
|
wgts[nadj] = (op == GK_CSR_SYM_AVG ? 0.5*rowval[j] : rowval[j]);
|
|
if (iwgts)
|
|
iwgts[nadj] = (op == GK_CSR_SYM_AVG ? 0.5*irowval[j] : irowval[j]);
|
|
marker[rowind[j]] = nadj++;
|
|
}
|
|
|
|
/* in-edges */
|
|
for (j=colptr[i]; j<colptr[i+1]; j++) {
|
|
if (marker[colind[j]] == -1) {
|
|
if (op != GK_CSR_SYM_MIN) {
|
|
ids[nadj] = colind[j];
|
|
if (wgts)
|
|
wgts[nadj] = (op == GK_CSR_SYM_AVG ? 0.5*colval[j] : colval[j]);
|
|
if (iwgts)
|
|
iwgts[nadj] = (op == GK_CSR_SYM_AVG ? 0.5*icolval[j] : icolval[j]);
|
|
nadj++;
|
|
}
|
|
}
|
|
else {
|
|
if (wgts) {
|
|
switch (op) {
|
|
case GK_CSR_SYM_MAX:
|
|
wgts[marker[colind[j]]] = gk_max(colval[j], wgts[marker[colind[j]]]);
|
|
break;
|
|
case GK_CSR_SYM_MIN:
|
|
wgts[marker[colind[j]]] = gk_min(colval[j], wgts[marker[colind[j]]]);
|
|
break;
|
|
case GK_CSR_SYM_SUM:
|
|
wgts[marker[colind[j]]] += colval[j];
|
|
break;
|
|
case GK_CSR_SYM_AVG:
|
|
wgts[marker[colind[j]]] = 0.5*(wgts[marker[colind[j]]] + colval[j]);
|
|
break;
|
|
default:
|
|
errexit("Unsupported op for MakeSymmetric!\n");
|
|
}
|
|
}
|
|
if (iwgts) {
|
|
switch (op) {
|
|
case GK_CSR_SYM_MAX:
|
|
iwgts[marker[colind[j]]] = gk_max(icolval[j], iwgts[marker[colind[j]]]);
|
|
break;
|
|
case GK_CSR_SYM_MIN:
|
|
iwgts[marker[colind[j]]] = gk_min(icolval[j], iwgts[marker[colind[j]]]);
|
|
break;
|
|
case GK_CSR_SYM_SUM:
|
|
iwgts[marker[colind[j]]] += icolval[j];
|
|
break;
|
|
case GK_CSR_SYM_AVG:
|
|
iwgts[marker[colind[j]]] = 0.5*(wgts[marker[colind[j]]] + icolval[j]);
|
|
break;
|
|
default:
|
|
errexit("Unsupported op for MakeSymmetric!\n");
|
|
}
|
|
}
|
|
marker[colind[j]] = -1;
|
|
}
|
|
}
|
|
|
|
/* go over out edges again to resolve any edges that were not found in the in
|
|
* edges */
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++) {
|
|
if (marker[rowind[j]] != -1) {
|
|
if (op == GK_CSR_SYM_MIN)
|
|
ids[marker[rowind[j]]] = -1;
|
|
marker[rowind[j]] = -1;
|
|
}
|
|
}
|
|
|
|
/* put the non '-1' entries in ids[] into i's row */
|
|
for (j=0; j<nadj; j++) {
|
|
if (ids[j] != -1) {
|
|
nrowind[nnz] = ids[j];
|
|
if (wgts)
|
|
nrowval[nnz] = wgts[j];
|
|
if (iwgts)
|
|
nirowval[nnz] = iwgts[j];
|
|
nnz++;
|
|
}
|
|
}
|
|
nrowptr[i+1] = nnz;
|
|
}
|
|
|
|
gk_free((void **)&colptr, &colind, &colval, &icolval, &marker, &ids, &wgts, &iwgts, LTERM);
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
|
|
#ifdef XXX
|
|
|
|
/*************************************************************************/
|
|
/*! Returns a subgraphrix containing a certain set of rows.
|
|
\param graph is the original graphrix.
|
|
\param nrows is the number of rows to extract.
|
|
\param rind is the set of row numbers to extract.
|
|
\returns the row structure of the newly created subgraphrix.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_ExtractRows(gk_graph_t *graph, int nrows, int *rind)
|
|
{
|
|
ssize_t i, ii, j, nnz;
|
|
gk_graph_t *ngraph;
|
|
|
|
ngraph = gk_graph_Create();
|
|
|
|
ngraph->nrows = nrows;
|
|
ngraph->ncols = graph->ncols;
|
|
|
|
for (nnz=0, i=0; i<nrows; i++)
|
|
nnz += graph->rowptr[rind[i]+1]-graph->rowptr[rind[i]];
|
|
|
|
ngraph->rowptr = gk_zmalloc(ngraph->nrows+1, "gk_graph_ExtractPartition: rowptr");
|
|
ngraph->rowind = gk_imalloc(nnz, "gk_graph_ExtractPartition: rowind");
|
|
ngraph->rowval = gk_fmalloc(nnz, "gk_graph_ExtractPartition: rowval");
|
|
|
|
ngraph->rowptr[0] = 0;
|
|
for (nnz=0, j=0, ii=0; ii<nrows; ii++) {
|
|
i = rind[ii];
|
|
gk_icopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowind+graph->rowptr[i], ngraph->rowind+nnz);
|
|
gk_fcopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowval+graph->rowptr[i], ngraph->rowval+nnz);
|
|
nnz += graph->rowptr[i+1]-graph->rowptr[i];
|
|
ngraph->rowptr[++j] = nnz;
|
|
}
|
|
ASSERT(j == ngraph->nrows);
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Returns a subgraphrix corresponding to a specified partitioning of rows.
|
|
\param graph is the original graphrix.
|
|
\param part is the partitioning vector of the rows.
|
|
\param pid is the partition ID that will be extracted.
|
|
\returns the row structure of the newly created subgraphrix.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_ExtractPartition(gk_graph_t *graph, int *part, int pid)
|
|
{
|
|
ssize_t i, j, nnz;
|
|
gk_graph_t *ngraph;
|
|
|
|
ngraph = gk_graph_Create();
|
|
|
|
ngraph->nrows = 0;
|
|
ngraph->ncols = graph->ncols;
|
|
|
|
for (nnz=0, i=0; i<graph->nrows; i++) {
|
|
if (part[i] == pid) {
|
|
ngraph->nrows++;
|
|
nnz += graph->rowptr[i+1]-graph->rowptr[i];
|
|
}
|
|
}
|
|
|
|
ngraph->rowptr = gk_zmalloc(ngraph->nrows+1, "gk_graph_ExtractPartition: rowptr");
|
|
ngraph->rowind = gk_imalloc(nnz, "gk_graph_ExtractPartition: rowind");
|
|
ngraph->rowval = gk_fmalloc(nnz, "gk_graph_ExtractPartition: rowval");
|
|
|
|
ngraph->rowptr[0] = 0;
|
|
for (nnz=0, j=0, i=0; i<graph->nrows; i++) {
|
|
if (part[i] == pid) {
|
|
gk_icopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowind+graph->rowptr[i], ngraph->rowind+nnz);
|
|
gk_fcopy(graph->rowptr[i+1]-graph->rowptr[i], graph->rowval+graph->rowptr[i], ngraph->rowval+nnz);
|
|
nnz += graph->rowptr[i+1]-graph->rowptr[i];
|
|
ngraph->rowptr[++j] = nnz;
|
|
}
|
|
}
|
|
ASSERT(j == ngraph->nrows);
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Splits the graphrix into multiple sub-graphrices based on the provided
|
|
color array.
|
|
\param graph is the original graphrix.
|
|
\param color is an array of size equal to the number of non-zeros
|
|
in the graphrix (row-wise structure). The graphrix is split into
|
|
as many parts as the number of colors. For meaningfull results,
|
|
the colors should be numbered consecutively starting from 0.
|
|
\returns an array of graphrices for each supplied color number.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t **gk_graph_Split(gk_graph_t *graph, int *color)
|
|
{
|
|
ssize_t i, j;
|
|
int nrows, ncolors;
|
|
ssize_t *rowptr;
|
|
int *rowind;
|
|
float *rowval;
|
|
gk_graph_t **sgraphs;
|
|
|
|
nrows = graph->nrows;
|
|
rowptr = graph->rowptr;
|
|
rowind = graph->rowind;
|
|
rowval = graph->rowval;
|
|
|
|
ncolors = gk_imax(rowptr[nrows], color)+1;
|
|
|
|
sgraphs = (gk_graph_t **)gk_malloc(sizeof(gk_graph_t *)*ncolors, "gk_graph_Split: sgraphs");
|
|
for (i=0; i<ncolors; i++) {
|
|
sgraphs[i] = gk_graph_Create();
|
|
sgraphs[i]->nrows = graph->nrows;
|
|
sgraphs[i]->ncols = graph->ncols;
|
|
sgraphs[i]->rowptr = gk_zsmalloc(nrows+1, 0, "gk_graph_Split: sgraphs[i]->rowptr");
|
|
}
|
|
|
|
for (i=0; i<nrows; i++) {
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++)
|
|
sgraphs[color[j]]->rowptr[i]++;
|
|
}
|
|
for (i=0; i<ncolors; i++)
|
|
MAKECSR(j, nrows, sgraphs[i]->rowptr);
|
|
|
|
for (i=0; i<ncolors; i++) {
|
|
sgraphs[i]->rowind = gk_imalloc(sgraphs[i]->rowptr[nrows], "gk_graph_Split: sgraphs[i]->rowind");
|
|
sgraphs[i]->rowval = gk_fmalloc(sgraphs[i]->rowptr[nrows], "gk_graph_Split: sgraphs[i]->rowval");
|
|
}
|
|
|
|
for (i=0; i<nrows; i++) {
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++) {
|
|
sgraphs[color[j]]->rowind[sgraphs[color[j]]->rowptr[i]] = rowind[j];
|
|
sgraphs[color[j]]->rowval[sgraphs[color[j]]->rowptr[i]] = rowval[j];
|
|
sgraphs[color[j]]->rowptr[i]++;
|
|
}
|
|
}
|
|
|
|
for (i=0; i<ncolors; i++)
|
|
SHIFTCSR(j, nrows, sgraphs[i]->rowptr);
|
|
|
|
return sgraphs;
|
|
}
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Prunes certain rows/columns of the graphrix. The prunning takes place
|
|
by analyzing the row structure of the graphrix. The prunning takes place
|
|
by removing rows/columns but it does not affect the numbering of the
|
|
remaining rows/columns.
|
|
|
|
\param graph the graphrix to be prunned,
|
|
\param what indicates if the rows (GK_CSR_ROW) or the columns (GK_CSR_COL)
|
|
of the graphrix will be prunned,
|
|
\param minf is the minimum number of rows (columns) that a column (row) must
|
|
be present in order to be kept,
|
|
\param maxf is the maximum number of rows (columns) that a column (row) must
|
|
be present at in order to be kept.
|
|
\returns the prunned graphrix consisting only of its row-based structure.
|
|
The input graphrix is not modified.
|
|
*/
|
|
/**************************************************************************/
|
|
gk_graph_t *gk_graph_Prune(gk_graph_t *graph, int what, int minf, int maxf)
|
|
{
|
|
ssize_t i, j, nnz;
|
|
int nrows, ncols;
|
|
ssize_t *rowptr, *nrowptr;
|
|
int *rowind, *nrowind, *collen;
|
|
float *rowval, *nrowval;
|
|
gk_graph_t *ngraph;
|
|
|
|
ngraph = gk_graph_Create();
|
|
|
|
nrows = ngraph->nrows = graph->nrows;
|
|
ncols = ngraph->ncols = graph->ncols;
|
|
|
|
rowptr = graph->rowptr;
|
|
rowind = graph->rowind;
|
|
rowval = graph->rowval;
|
|
|
|
nrowptr = ngraph->rowptr = gk_zmalloc(nrows+1, "gk_graph_Prune: nrowptr");
|
|
nrowind = ngraph->rowind = gk_imalloc(rowptr[nrows], "gk_graph_Prune: nrowind");
|
|
nrowval = ngraph->rowval = gk_fmalloc(rowptr[nrows], "gk_graph_Prune: nrowval");
|
|
|
|
|
|
switch (what) {
|
|
case GK_CSR_COL:
|
|
collen = gk_ismalloc(ncols, 0, "gk_graph_Prune: collen");
|
|
|
|
for (i=0; i<nrows; i++) {
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++) {
|
|
ASSERT(rowind[j] < ncols);
|
|
collen[rowind[j]]++;
|
|
}
|
|
}
|
|
for (i=0; i<ncols; i++)
|
|
collen[i] = (collen[i] >= minf && collen[i] <= maxf ? 1 : 0);
|
|
|
|
nrowptr[0] = 0;
|
|
for (nnz=0, i=0; i<nrows; i++) {
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++) {
|
|
if (collen[rowind[j]]) {
|
|
nrowind[nnz] = rowind[j];
|
|
nrowval[nnz] = rowval[j];
|
|
nnz++;
|
|
}
|
|
}
|
|
nrowptr[i+1] = nnz;
|
|
}
|
|
gk_free((void **)&collen, LTERM);
|
|
break;
|
|
|
|
case GK_CSR_ROW:
|
|
nrowptr[0] = 0;
|
|
for (nnz=0, i=0; i<nrows; i++) {
|
|
if (rowptr[i+1]-rowptr[i] >= minf && rowptr[i+1]-rowptr[i] <= maxf) {
|
|
for (j=rowptr[i]; j<rowptr[i+1]; j++, nnz++) {
|
|
nrowind[nnz] = rowind[j];
|
|
nrowval[nnz] = rowval[j];
|
|
}
|
|
}
|
|
nrowptr[i+1] = nnz;
|
|
}
|
|
break;
|
|
|
|
default:
|
|
gk_graph_Free(&ngraph);
|
|
gk_errexit(SIGERR, "Unknown prunning type of %d\n", what);
|
|
return NULL;
|
|
}
|
|
|
|
return ngraph;
|
|
}
|
|
|
|
|
|
|
|
/*************************************************************************/
|
|
/*! Normalizes the rows/columns of the graphrix to be unit
|
|
length.
|
|
\param graph the graphrix itself,
|
|
\param what indicates what will be normalized and is obtained by
|
|
specifying GK_CSR_ROW, GK_CSR_COL, GK_CSR_ROW|GK_CSR_COL.
|
|
\param norm indicates what norm is to normalize to, 1: 1-norm, 2: 2-norm
|
|
*/
|
|
/**************************************************************************/
|
|
void gk_graph_Normalize(gk_graph_t *graph, int what, int norm)
|
|
{
|
|
ssize_t i, j;
|
|
int n;
|
|
ssize_t *ptr;
|
|
float *val, sum;
|
|
|
|
if (what&GK_CSR_ROW && graph->rowval) {
|
|
n = graph->nrows;
|
|
ptr = graph->rowptr;
|
|
val = graph->rowval;
|
|
|
|
#pragma omp parallel if (ptr[n] > OMPMINOPS)
|
|
{
|
|
#pragma omp for private(j,sum) schedule(static)
|
|
for (i=0; i<n; i++) {
|
|
for (sum=0.0, j=ptr[i]; j<ptr[i+1]; j++){
|
|
if (norm == 2)
|
|
sum += val[j]*val[j];
|
|
else if (norm == 1)
|
|
sum += val[j]; /* assume val[j] > 0 */
|
|
}
|
|
if (sum > 0) {
|
|
if (norm == 2)
|
|
sum=1.0/sqrt(sum);
|
|
else if (norm == 1)
|
|
sum=1.0/sum;
|
|
for (j=ptr[i]; j<ptr[i+1]; j++)
|
|
val[j] *= sum;
|
|
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (what&GK_CSR_COL && graph->colval) {
|
|
n = graph->ncols;
|
|
ptr = graph->colptr;
|
|
val = graph->colval;
|
|
|
|
#pragma omp parallel if (ptr[n] > OMPMINOPS)
|
|
{
|
|
#pragma omp for private(j,sum) schedule(static)
|
|
for (i=0; i<n; i++) {
|
|
for (sum=0.0, j=ptr[i]; j<ptr[i+1]; j++)
|
|
if (norm == 2)
|
|
sum += val[j]*val[j];
|
|
else if (norm == 1)
|
|
sum += val[j];
|
|
if (sum > 0) {
|
|
if (norm == 2)
|
|
sum=1.0/sqrt(sum);
|
|
else if (norm == 1)
|
|
sum=1.0/sum;
|
|
for (j=ptr[i]; j<ptr[i+1]; j++)
|
|
val[j] *= sum;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
#endif
|
|
|