Question: I need help with the following function; there is no spmv function declared previous to this one: void bfs_spmv(int** int_array, int rows, int cols, int
I need help with the following function; there is no spmv function declared previous to this one:
void bfs_spmv(int** int_array, int rows, int cols, int source,
int* color, int* distance)
{
// check the input parameters to see if they are valid
if(rows != cols) {
fprintf(stderr, "Not an adjacency matrix ");
exit(EXIT_FAILURE);
}
if(source >= rows) {
fprintf(stderr, "Invalid source vertex ");
exit(EXIT_FAILURE);
}
assert(int_array);
assert(color);
assert(distance);
fprintf(stdout, "Breadth first search on the graph using SpMV ... ");
// Transpose the adjacency matrix
int** mat_trans = NULL;
init_2d_array(&mat_trans, cols, rows);
matrix_transpose(mat_trans, int_array, rows, cols);
#if DEBUG
print_matrix(mat_trans, cols, rows);
#endif
// Initialize the various data structures
int* vec = (int*) malloc(sizeof(int) * rows);
assert(vec);
for(int i = 0; i < rows; i++) {
if(i == source) {
vec[i] = 1;
color[i] = 2;
distance[i] = 0;
} else {
vec[i] = 0;
color[i] = 0;
distance[i] = -1;
}
}
int* res = (int*) malloc(sizeof(int) * cols);
assert(res);
reset_vector(res, cols);
int iter = 1;
int done = 0;
int *src = vec;
int *dst = res;
// Do BFS until done
while(!done) {
// INSERT YOUR CODE HERE
// given a vector of source vetices, find the neighbors
// HINT: spmv
// color the source vertices for this iteration `black'
// store the distance for the newly discovered neighbors
// Before we begin, eliminate vertices that have already been visited
// Check to see if no neighbors were found,
// in which case, we are done
// iter is equivalent to each `breadth' searched (i.e., distance from
// the source vertex)
}
fprintf(stdout, "done ");
#if DEBUG
print_bfs_matrix_result(rows, color, distance);
#endif
free_2d_array(mat_trans, cols);
free(vec);
free(res);
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
