code. compile. run. debug. share.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "load.h"
#include "matrix.h"
#include "graph.h"
void usage(int argc, char** argv)
{
if(argc != 3) {
printf("usage: %s <matrix file> <source vertex>\n", argv[0]);
exit(EXIT_FAILURE);
}
}
int main(int argc, char** argv)
{
usage(argc, argv);
// load the adjacency matrix from file
int** int_array = NULL;
uint32_t row = 0;
uint32_t col = 0;
uint32_t nnz = 0;
load_matrix(argv[1], &int_array, &row, &col, &nnz);
assert((row > 0) && (col > 0));
#if DEBUG
print_matrix(int_array, row, col);
#endif
// Read the source vertex for BFS
int src = atoi(argv[2]);
// Construct an adjacency list for the graph
// adj_list is an array of size `row', and each element in this array
// points to the head of each row's adjacency list
adj_node_t** adj_list = NULL;
construct_adj_list(int_array, row, col, &adj_list);
#if DEBUG
print_adj_list(adj_list, row);
#endif
// Allocate memory for the required data structures for doing BFS
// color, distance, and parent node list
int* color = (int*) malloc(sizeof(int) * row);
assert(color);
memset(color, -2, sizeof(int) * row);
int* distance = (int*) malloc(sizeof(int) * row);
assert(distance);
memset(distance, -2, sizeof(int) * row);
int* parent = (int*) malloc(sizeof(int) * row);
assert(parent);
memset(parent, -2, sizeof(int) * row);
// Do the list-based BFS and calculate the distance from the source vertex
// for every other vertex
bfs(adj_list, row, src, color, distance, parent);
// Save output to a file
save_result(distance, row, src, 0);
// Matrix-based BFS
// Declare and allocate the color and distance arrays
// Parent is not required for the SpMV BFS algorithm
int* color_mat = (int*) malloc(sizeof(int) * row);
assert(color_mat);
memset(color_mat, -2, sizeof(int) * row);
int* distance_mat = (int*) malloc(sizeof(int) * row);
assert(distance_mat);
memset(distance_mat, -2, sizeof(int) * row);
bfs_spmv(int_array, row, col, src, color_mat, distance_mat);
// Save output to a file
save_result(distance_mat, row, src, 1);
// Clean up after your memory
free_2d_array(int_array, row);
free_adj_list(adj_list, row);
free(color_mat);
free(distance_mat);
free(color);
free(distance);
free(parent);
return 0;
}
#ifndef _GRAPH_H_
#define _GRAPH_H_
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct adj_node_struct_t {
int vid; // vertex ID
struct adj_node_struct_t *next; // pointer to next adj node
} adj_node_t;
adj_node_t *create_node(int vid);
void add_node(adj_node_t** list, int row, adj_node_t* node);
int remove_node(adj_node_t **list);
void construct_adj_list(int **adj_mat, int rows, int cols, adj_node_t ***list);
void print_adj_list(adj_node_t **list, int rows);
void free_adj_list(adj_node_t **list, int rows);
void print_bfs_result(int rows, int *color, int *distance, int *parent);
void bfs(adj_node_t **list, int rows, int source,
int *color, int *distance, int *parent);
#endif
#include "graph.h"
/* This function initializes an adjacency list for a graph.
input parameters:
The following are 'consumed' by this function
int rows # of rows (or vertices)
The following are 'produced' by this function
adj_node_t*** list initialized linked list of adjacencies for each
vertex
return parameters:
none
*/
void init_adj_list(adj_node_t*** list, int rows)
{
// Allocate memory
adj_node_t** tmpList = (adj_node_t**) malloc(sizeof(adj_node_t*) * rows);
assert(tmpList);
// Initialize each list to point to NULL
for(int i = 0; i < rows; i++) {
tmpList[i] = NULL;
}
// Return list
*list = tmpList;
}
/* This function creates a new adj_node_t node for a vertex and initializes
it with node->vid = vid and node->next = NULL (i.e., no neighbor)
The function then returns this node
input parameters:
int vid the ID of the vertex
return parameters:
adj_node_t newNode the new node for the vertex
*/
adj_node_t* create_node(int vid)
{
adj_node_t* newNode = (adj_node_t*) malloc(sizeof(adj_node_t));
assert(newNode);
newNode->vid = vid;
newNode->next = NULL;
return newNode;
}
/* Pass in a linked list that represents an adjacnecy list and the row (or
vertex) to which you need to add a new node.
First check that the adjacency list for the current row is not
empty (i.e., NULL). If it is NULL, this is the first adjacent node.
Otherwise, traverse the list until you reach the end, and then add
the new node.
input parameters:
adj_node_t** list adjacency list for the current graph
int row vertex that has this node as adjacent
adj_node_t* node the node that needs to be added
return parameters:
none
*/
void add_node(adj_node_t** list, int row, adj_node_t* node)
{
if(list[row] == NULL) {
// empty list - the head points to this node
list[row] = node;
} else {
// otherwise, find the end, and add it to the end
adj_node_t* next = list[row];
while(next->next != NULL) {
next = next->next;
}
next->next = node;
}
}
/* Deqeueu a node from linked list and return the vertex id of the
removed node.
Note that the input parameters is of type adj_node_t**, but in the
beginning, it dereferences it to adj_node_t* head. So you are
essentially passing in a pointer to adj_node_t*.
input parameters:
adj_node_t** pointer to an adj_node_t* , whic is essentially
the adjacency list of a PARTICULAR vertex, but
passed in by refrence.
return parameters:
int vid the vertex ID (vid) of the removed node
*/
int remove_node(adj_node_t** list)
{
int vid = -1;
// if list valid - this should really never happen
if(list != NULL) {
adj_node_t* head = *list;
// if list is not empty - this can happen if this
// vertex has no neighbors left
if(head != NULL) {
adj_node_t* tmp = head;
vid = head->vid;
head = head->next;
// don't foget to free the removed node
free(tmp);
}
*list = head;
} else {
fprintf(stderr, "Adjacency list is NULL\n");
exit(EXIT_FAILURE);
}
return vid;
}
/* This function constructs an adjacency list for a graph from an adjacency
matrix
input parameters:
The following are 'consumed' by this function
int** adj_mat 2D array that stores the adjacency matrix
int rows # of rows in the matrix
int cols # of columns in the matrix
The following are 'produced' by this function
adj_node_t*** list a linked list of adjacencies
return parameters:
none
adj_node_t*** list is passed in by reference from the main function so that
it can be malloc'd via the init_adj_list function.
After initializing it go through each row and add its adjacent nodes
*/
void construct_adj_list(int** adj_mat, int rows, int cols, adj_node_t*** list)
{
// verify that the adj matrix is correct
if(rows != cols) {
fprintf(stderr, "Adjacency matrix is not square\n");
exit(EXIT_FAILURE);
}
fprintf(stdout, "Constructing the adjacency list for this graph ... ");
// Initialize the linked list
init_adj_list(list, rows);
// Since list was passed in by reference, accessing its
// elements would require dereferencing it every time.
// To make it easier, create a copy of the dereferenced
// list and store it in myList for use in this function
adj_node_t** myList = *list;
// INSERT YOUR CODE HERE
// HINT: You will need to use create_node() and add_node() here
// Go through each vertex and construct its adjacency list
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(adj_mat[i][j] == 1) {
adj_node_t* node = create_node(j);
add_node(myList, i, node);
}
}
}
fprintf(stdout, "done\n");
}
/* This function takes in an adjacency ilst and prints out the list,
one row/vertext at a time
input parameters:
adj_node_t** list adjacency list for the graph
int rows # of rows/vertices in the graph
return parameters:
none
*/
void print_adj_list(adj_node_t** list, int rows)
{
assert(list);
fprintf(stdout, "---- Print Adj. List ----\n");
for(int i = 0; i < rows; i++) {
fprintf(stdout, "|%d| -> ", i);
adj_node_t* next = list[i];
while(next != NULL) {
fprintf(stdout, "%d -> ", next->vid);
next = next->next;
}
fprintf(stdout, "END\n");
}
fprintf(stdout, "--------\n\n");
}
void free_adj_list(adj_node_t** list, int rows)
{
if(list != NULL) {
for(int i = 0; i < rows; i++) {
if(list[i] != NULL) {
adj_node_t* head = list[i];
do {
adj_node_t* tmp = head;
head = head->next;
free(tmp);
} while(head != NULL);
}
}
free(list);
}
}
void print_bfs_result(int rows, int* color, int* distance, int* parent)
{
assert(color);
assert(distance);
assert(parent);
printf("---- Print BFS Result ----\n");
printf("Vert\tCol\tDis\tParent\n");
for(int i = 0; i < rows; i++) {
printf("%d\t%d\t%d\t%d\n", i, color[i], distance[i], parent[i]);
}
printf("--------\n\n");
}
/* Do the list-based BFS, given the source node and the graph's adjacency
list.
Go through each vertices in a BFS manner, and then calculate the dsitance
from the source vertex.
input parameters:
The following are 'consumed' by this function
adj_node_t** list adjacency list for the graph
int rows number of rows/vertices in the graph
int source BFS source
The following are 'produced' by this function
int* color keeps track of color during BFS
int* distance distance from the source
int* parent parent of each vertex
return parameters:
none
*/
void bfs(adj_node_t** list, int rows, int source,
int* color, int* distance, int* parent)
{
// Make sure the source is a valid vertex
if(source >= rows) {
fprintf(stderr, "Invalid source vertex\n");
exit(EXIT_FAILURE);
}
// Make sure the adjacency list is not NULL
// Even if this is a completely unconnected graph,
// it should still NOT be NULL (see init_adj_list)
if(list == NULL) {
fprintf(stderr, "There is nothing in the adjacency list\n");
exit(EXIT_FAILURE);
}
// Make sure all these are properly allocated (i.e., not NULL)
assert(color);
assert(distance);
assert(parent);
fprintf(stdout, "Breadth first search on the grahp using linked list ... ");
// INSERT YOUR CODE HERE
// Initialize the vertices
// color should be initialized to 0
// distance should be initialized to -1 for infinity
// parent should be initialized to -1 for NIL
for(int i = 0; i < rows; i++) {
color[i] = 0;
distance[i] = -1;
parent[i] = -1;
}
// Initialize the source vertex
// distance for the source vertex is 0, so it should be initialized as such
// it has no parent, so initialize it to -1
// color should be initialized to 1
distance[source] = 0;
color[source] = 1;
parent[source] = -1;
// Initialize the queue with the source vertex
// HINT: use create_node(source) and add_node
adj_node_t* node = create_node(source);
add_node(list, source, node);
// bfs iteration
// HINT: use remove_node (to fetch & dequeu the vertex)
// HINT: you will also need create_node an add_node here
while(list[source] != NULL) {
int vertex = remove_node(list);
adj_node_t* current = list[vertex];
while(current != NULL) {
int neighbor = current->vid;
if(color[neighbor] == 0) {
color[neighbor] = 1;
distance[neighbor] = distance[vertex] + 1;
parent[neighbor] = vertex;
adj_node_t* node = create_node(neighbor);
add_node(list, neighbor, node);
}
current = current->next;
}
color[vertex] = 2;
}
fprintf(stdout, "done\n");
#if DEBUG
print_bfs_result(rows, color, distance, parent);
#endif
}
#include "load.h"
/* This function loads matrix from a text file.
The first line of the text file should have
# rows # cols # non-zeros (e.g., 10 10 7)
Each subsequent line should be a single row of the matrix, with
each number delilmited by a space. (i.e., 0 1 1 0 1 1 0 1 0 0)
*/
void load_matrix(char* mat_name, int*** int_array,
uint32_t* row, uint32_t* col, uint32_t* nnz)
{
FILE *fp = NULL;
fp = fopen(mat_name, "r");
if(fp == NULL) {
fprintf(stderr, "Error while loading the file\n");
exit(EXIT_FAILURE);
}
int r = 0;
int c = 0;
int z = 0;
fscanf(fp, "%d", &r);
fscanf(fp, "%d", &c);
fscanf(fp, "%d", &z);
// Count the number of elements and non-zeros of the matrix in the file
int cnt = 0;
int cnt_nz = 0;
int tmp = 0;
while(fscanf(fp, "%d", &tmp) == 1) {
cnt++;
if(tmp > 0) {
cnt_nz++;
}
}
fclose(fp);
// Check if they match what was on the first line (i.e., # rows, # cols,
// and # non-zeros)
if((r * c == cnt) && (z == cnt_nz)) {
fprintf(stdout, "Loading is a %d x %d matrix with %d non-zeros ... ",
r, c, z);
} else {
fprintf(stderr,
"Something does not match: %d x %d != %d or %d nz != %d\n",
r, c, cnt, z, cnt_nz);
exit(EXIT_FAILURE);
}
// Allocate memory to temporary pointers
int **tmp_array = (int**) malloc(sizeof(int*) * r);
assert(tmp_array);
for(int i = 0; i < r; i++) {
tmp_array[i] = (int*) malloc(sizeof(int) * c);
assert(tmp_array[i]);
}
fp = fopen(mat_name, "r");
if(fp == NULL) {
fprintf(stderr, "Error while loading the file\n");
exit(EXIT_FAILURE);
}
// Read the first line (not needed anymore)
fscanf(fp, "%d", &tmp);
fscanf(fp, "%d", &tmp);
fscanf(fp, "%d", &tmp);
// Read the matrix
cnt = 0;
tmp = 0;
while (fscanf(fp, "%d", &tmp) == 1) {
// store the read integer in the correct place in the 2-D array
tmp_array[cnt / c][cnt % c] = tmp;
cnt++;
}
fclose(fp);
fprintf(stdout, "done\n");
*int_array = tmp_array;
*row = r;
*col = c;
*nnz = z;
}
/* This function saves the calculate distance out to a file
input parameters:
int* vector the distance array to save to a file
int rows # of vertices in the graph (i.e., size of the vector)
int src source vertex of the BFS
int ll_or_spmv whether the result is from linked list version (= 0) or
from the SpMV version (1)
return parameters:
none
*/
void save_result(int* vector, int rows, int src, int ll_or_spmv)
{
char fileName[100];
if(ll_or_spmv == 0) {
sprintf(fileName, "distance_%d_LL.txt", src);
} else {
sprintf(fileName, "distance_%d_SpMV.txt", src);
}
FILE* fp = fopen(fileName, "w");
for(int i = 0; i < rows; i++) {
if(vector[i] != -1) {
fprintf(fp, "%d\n", vector[i]);
} else {
fprintf(fp, "Inf\n");
}
}
fclose(fp);
}
#ifndef _LOAD_H_
#define _LOAD_H_
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdint.h>
void load_matrix(char *mat_name, int ***int_array,
uint32_t *row, uint32_t *col, uint32_t *nnz);
void save_result(int* vector, int rows, int src, int ll_or_spmv);
#endif
#include "matrix.h"
/* Debugging code that prints the BFS result for a particular iteration
input parameters:
int rows # of vertices
int* color array of color for the vertices
int* distance array of distance for the vertices
return parameters:
none
*/
void print_bfs_matrix_result(int rows, int* color, int* distance)
{
assert(color);
assert(distance);
fprintf(stdout, "---- Print BFS Matrix Result ----\n");
fprintf(stdout, "Vert\tCol\tDis\n");
for(int i = 0; i < rows; i++) {
fprintf(stdout, "%d\t%d\t%d\n", i, color[i], distance[i]);
}
fprintf(stdout, "--------\n\n");
}
/* Debugging code that prints a vector
input parameters:
int* vector vector whose content we wish to print
int rows # of elements in the vector
return parameters:
none
*/
void print_vector(int* vector, int rows)
{
assert(vector);
fprintf(stdout, "---- Print Vector ----\n");
for(int i = 0; i < rows; i++) {
fprintf(stdout, "%d\n", vector[i]);
}
fprintf(stdout, "--------\n\n");
}
/* Debugging code that prints the content of a 2D matrix
input parameters:
int* matrix 2D matrix we wish to print2D matrix we wish to print
int rows # of rows of the input matrix
int cols # of cols of the input matrix
return parameters:
none
*/
void print_matrix(int **matrix, int rows, int cols)
{
assert(matrix);
fprintf(stdout, "---- Print Matrix ----\n");
fprintf(stdout, "This matrix is %d x %d\n", rows, cols);
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
fprintf(stdout, "%d ", matrix[i][j]);
}
fprintf(stdout, "\n");
}
fprintf(stdout, "--------\n\n");
}
/* This function takes in a 2D matrix (src), transposes it and
then stores it in a destination 2D matrix (dst).
Transpose operation takes each src[i][j] element and stores it
in dst[j][i]
input parameters:
int** dst Where you store the transpose of src
Dimensions are cols x rows
int** src Matrix you want to transpose
Dimensions are rows x cols
int rows # of rows of input matrix (src)
int cols # of cols of input matrix (src)
return parameters:
none
*/
void matrix_transpose(int** dst, int** src, int rows, int cols)
{
assert(dst);
assert(src);
assert(rows == cols);
// INSERT YOUR CODE HERE
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
dst[j][i] = src[i][j];
}
}
}
/* This function 'resets a vetor to have all
zero value
input parameters:
int* vector the input vector to reset
int rows the number of elements in the vector
return parameters:
none
*/
void reset_vector(int* vector, int rows)
{
assert(vector);
for(int i = 0; i < rows; i++) {
vector[i] = 0;
}
}
void spmv(int** int_array, int rows, int cols, int* src, int* dst) {
for(int i = 0; i < rows; i++) {
dst[i] = 0;
for(int j = 0; j < cols; j++) {
dst[i] += int_array[i][j] * src[j];
}
}
}
/* 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\n");
exit(EXIT_FAILURE);
}
if(source >= rows) {
fprintf(stderr, "Invalid source vertex\n");
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
spmv(mat_trans, rows, cols, src, dst);
// color the source vertices for this iteration `black'
for(int i = 0; i < cols; i++) {
if(src[i] == 1) {
color[i] = 2;
}
}
// store the distance for the newly discovered neighbors
for(int i = 0; i < cols; i++) {
if(dst[i] == 1) {
color[i] = 1;
distance[i] = iter;
}
}
// Before we begin, eliminate vertices that have already been visited
for(int i = 0; i < cols; i++) {
if(color[i] == 2) {
dst[i] = 0;
}
}
// Check to see if no neighbors were found,
// in which case, we are done
done = 1;
for(int i = 0; i < cols; i++) {
if(color[i] == 0) {
done = 0;
break;
}
}
iter++;
int *tmp = src;
src = dst;
dst = tmp;
reset_vector(dst, cols);
// iter is equivalent to each `breadth' searched (i.e., distance from
// the source vertex)
}
fprintf(stdout, "done\n");
#if DEBUG
print_bfs_matrix_result(rows, color, distance);
#endif
free_2d_array(mat_trans, cols);
free(vec);
free(res);
}
/* This function allocates memory for a 2D array of size rows x cols
input parameters
int*** arr reference to the 2D array you want to init
int rows # of rows in the 2D array
int cols # of columns in the 2D array
return parameters:
none
*/
void init_2d_array(int*** arr, int rows, int cols)
{
int** tmpArr = (int**) malloc(sizeof(int*) * rows);
assert(tmpArr);
for(int i = 0; i < rows; i++) {
tmpArr[i] = (int*) malloc(sizeof(int) * cols);
assert(tmpArr[i]);
}
*arr = tmpArr;
}
/* This function frees memory allocated to a 2D array.
input parameters:
int** arr the 2D array to deallocate
int rows # of rows of the matrix
return parameters:
none
*/
void free_2d_array(int** arr, int rows)
{
for(int i = 0; i < rows; i++) {
// free each row
free(arr[i]);
}
// free the matrix
free(arr);
}
#ifndef _MATRIX_H_
#define _MATRIX_H_
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
void matrix_transpose(int **dst, int **src, int rows, int cols);
void reset_vector(int *vector, int rows);
void print_bfs_matrix_result(int rows, int *color, int *distance);
void print_matrix(int **matrix, int rows, int cols);
void bfs_spmv(int **int_array, int rows, int cols, int source,
int *color, int *distance);
void init_2d_array(int ***arr, int rows, int cols);
void free_2d_array(int **arr, int rows);
#endif
10 10 20
0 0 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 1 0
0 0 0 1 1 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0 1 0
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|