In C

/* SpMV-based BFS implementation input parameters: These are 'consumed' by this function int** int_array input array representing the adjacency matrix int rows # of rows of the adajcency matrix int cols # of cols of the adajcency matrix int source source vertex for the BFS These are 'produced' by this function int* color color array int* distance distance array return parameters: none */ 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); }

Plese sepecify what information you need besides this.