/* 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);

}