ece368/ece368-proj3/shortestpath.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "shortestpath.h"

#define INFINITE 1500000
#define INVALID_INDEX -1

void read_num_nodes(FILE *mfptr, int *num_nodes){
	// read first value in file
	if((fscanf(mfptr, "%d", num_nodes)) == EOF){
		return;
	}
}

void read_map(FILE *mfptr, int num_nodes, int **adjacent, int **verticies){
	// declare variables
	int a, b, c = 0; // store values
	int i = 0; // incrementor

	// ensure the fptr is at the beginning
	rewind(mfptr);

	// allocate memory and move fptr to correct spot
	fscanf(mfptr, "%d %d", &a, &b); // move past line 1
	//printf("%d %d\n", a, b); // for testing
	for(i = 0; i < num_nodes; i++){
		verticies[i] = calloc(2, sizeof(int)); // init to 0
		adjacent[i] = calloc(num_nodes, sizeof(int)); // init to 0
		fscanf(mfptr, "%d\t%d\t%d", &a, &b, &c); // move through 
		verticies[i][0] = b;
		verticies[i][1] = c;
	}

	// scan relevent values
	while(fscanf(mfptr, "%d %d", &a, &b) != EOF){
		//printf("%d %d\n", a, b); // for testing
		adjacent[a][b] = 1;
		adjacent[b][a] = 1;
	}
}

void read_num_queries(FILE *qfptr, int *num_queries){
	// read first value in file
	if((fscanf(qfptr, "%d", num_queries)) == EOF){
		return;
	}
}

void read_queries(FILE *qfptr, int num_queries, int *queries){
	int a, b = 0; // store values
	int i = 0; // incrementor
	
	rewind(qfptr);
	
	fscanf(qfptr, "%d\n", &a); // move past line 1
	
	for(i = 0; i < num_queries; i++){
		fscanf(qfptr, "%d %d", &a, &b);
		queries[2 * i] = a;
		queries[2 * i + 1] = b;
	}
}
// 
// void read_verticies(FILE *mfptr, int num_nodes, int **verticies){
// 	// declare variables
// 	int a, b, c = 0; // store values
// 	int i = 0; // incrementor
// 
// 	// ensure the fptr is at the beginning
// 	rewind(mfptr);
// 
// 	// allocate memory and move fptr to correct spot
// 	fscanf(mfptr, "%d %d", &a, &b); // move past line 1
// 	//printf("%d %d\n", a, b); // for testing
// 	for(i = 0; i < num_nodes; i++){
// 		verticies[i] = calloc(2, sizeof(int)); // init to 0
// 		fscanf(mfptr, "%d\t%d\t%d", &a, &b, &c); // move through
// 		verticies[i][0] = b;
// 		verticies[i][1] = c;
// 		//printf("%d\t%d\t%d\n", a, b, c); // for testing
// 	}
// }

int all_visited(int num_nodes, int *visited){
	int i = 0;
	for(i = 0; i < num_nodes; i++){
		if(visited[i] == 0){
			return 0;
		}
	}
	return 1;
}

void calculate_distances(int num_nodes, int **adjacent, int **verticies){
	int i, j = 0;
	for(i = 0; i < num_nodes; i++){
		for(j = 0; j < num_nodes; j++){
			if(i == j){
				adjacent[i][j] = 0;
			}else{
				if(adjacent[i][j] > 0){
					adjacent[i][j] = sqrt(pow(verticies[j][0] - verticies[i][0], 2) + pow(verticies[j][1] - verticies[i][1], 2));
				}else{
					adjacent[i][j] = INFINITE;
				}
			}
		}
	}
}

int dijkstra(int num_nodes, int source, int dest, int **adjacent){
	int *distance = calloc(num_nodes, sizeof(int));
	int *previous = calloc(num_nodes, sizeof(int));
	int *visited = calloc(num_nodes, sizeof(int));
	int *path = calloc(num_nodes, sizeof(int));
	int i, m, min, start, d, j = 0;

	for(i = 1; i < num_nodes; i++){
		distance[i] = adjacent[source][i];
		previous[i] = INVALID_INDEX;
	}
		
	start = source;
	visited[start] = 1;
	distance[start] = 0;
	
	while(visited[dest] == 0){
		min = INFINITE;
		m = 0;
		for(i = 1; i < num_nodes; i++){
			d = distance[start] + adjacent[start][i];
			if((d < distance[i]) && (visited[i] == 0)){
				distance[i] = d;
				previous[i] = start;
			}
			if((min > distance[i]) && (visited[i] == 0)){
				min = distance[i];
				m = i;
			}
		}
		start = m;
		visited[start] = 1;
	}
	
	start = dest;
	j = 0;
	while(start != -1){
		path[j++] = start;
		start = previous[start];
	}
	path[j] = source;
	printf("\n%d\n", distance[dest]);
	while(j >= 0){
		printf("%d  ", path[j]);
		j--;
	}
	printf("\n");
	
	return distance[dest];
	
}

int main (int argc, char **argv){


	int num_nodes = 0;
	int num_queries = 0;

	// open files for reading
	FILE *mfptr = fopen(argv[1], "r");
	if (mfptr == NULL){ // check for error
		printf("Map file name error.\n");
		return EXIT_FAILURE;
	}
	
 	FILE *qfptr = fopen(argv[2], "r");
 	if (qfptr == NULL){ // check for error
 		printf("Query file name error.\n");
 		return EXIT_FAILURE;
 	}

	read_num_nodes(mfptr, &num_nodes);
	int **adjacent = malloc(num_nodes * sizeof(int *));	
	int **verticies = malloc(num_nodes * sizeof(int *));
	read_map(mfptr, num_nodes, adjacent, verticies);
	
	calculate_distances(num_nodes, adjacent, verticies);
	
	read_num_queries(qfptr, &num_queries);
	int *queries = calloc(num_queries * 2 + 1, sizeof(int));
	read_queries(qfptr, num_queries, queries);
			
	int i = 0;
	for(i = 0; i < num_queries; i++){
		dijkstra(num_nodes, queries[2 * i], queries[2 * i + 1], adjacent);
	}

	// clean up
	for(i = 0; i < num_nodes; i++){
		free(adjacent[i]);
	}
	free(adjacent);
	fclose(mfptr);
	//fclose(qfptr);


	return EXIT_SUCCESS;
}