DS Project 7: Basic Graph Operations

題目

In this project you need to implement some basic graph operations. Suppose program name is graph and distance.txt is a text file. After the "distance.txt" has been read in the memory and the data structure built, the program will enter interactive mode by prompting > to let user enter commands. The program should print > for prompting after the execution of each command. Input Data: a text file containing two locations and distance between two locations in a line. For example:

Taipei Ilan 4
Taipei Tainan 8
Ilan Tainan 11
Ilan Taoyuan 8
Taoyuan Hsinchu 7
Taoyuan Chiayi 4
Hsinchu Chiayi 14
Hsinchu Taichung 9
Taichung Chiayi 10
Tainan Kaohsiung 7
Taoyuan Kaohsiung 2

##Interactive Mode DFS node : DFS from node. Order is not neccsary the same as problem's.

BFS node : BFS from node.

SP nodeS nodeT : shortest path from nodeS to nodeT using Dijkstar's algorithm.

MST : print minimum spanning tree using Kruskal's algorithm.

Example

> DFS 
Taipei
Taipei
Ilan
Taoyuan
Hsinchu
Taichung
Chiayi
Kaohsiung
Tainan

> BFS
Taipei
Taipei
Ilan
Tainan
Taoyuan
Kaohsiung
Hsinchu
Chiayi
Taichung 

> SP Taipei Taichung
minimum cost : 26 
Taipei -> Ilan -> Taoyuan -> Chiayi -> Taichung

> MST 
Taoyuan Kaohsiung 2
Taipei Ilan 4
Taoyuan Chiayi 4
Taoyuan Hsinchu 7
Tainan Kaohsiung 7
Ilan Taoyuan 8
Hsinchu Taichung 9

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct
{
	int from, to, cost;
} Edge;

int edge_cmp(const void* a, const void* b) {
	Edge* ea = (Edge*) a;
	Edge* eb = (Edge*) b;
	return (ea->cost) - (eb->cost);
}



char* translate[1000];
int t_idx = 0;

int graph[1000][1000];

int get_idx(char* s) {
	for (int i=0; i<t_idx; i++)
		if (strcmp(s, translate[i]) == 0)
			return i;
	return -1;
}

int encode(char* s) {
	int search = get_idx(s);
	if (search != -1)
		return search;

	translate[t_idx] = (char*) malloc (sizeof(char) * (strlen(s)+1));
	strcpy(translate[t_idx], s);
	t_idx++;

	return t_idx-1;
}

char* decode(int i) {
	return translate[i];
}

bool is_str_digit(const char* s) {
	int len = strlen(s);
	for (int i=0; i<len; i++)
		if (s[i] < '0' || s[i] > '9')
			return false;
	return true;
}

void print_dfs(int start) {
	const int N  = t_idx;

	int stack[N];
	memset(stack, 0, sizeof(stack));
	int st_idx = 0;

	bool added[N];
	memset(added, false, sizeof(added));

	stack[st_idx++] = start;
	added[start] = true;

	while (st_idx != 0) {
		int top = stack[--st_idx];

		printf("%s\n", decode(top));

		for (int i=N; i>=0; i--) {
			if (added[i] == false && graph[top][i] != -1) {
				stack[st_idx++] = i;
				added[i] = true;
			}
		}
	}
}

void print_bfs(int start) {
	// This implementation gives guaranteee that len(queue) <= N at any time.
	const int N = t_idx;

	int queue[N];
	memset(queue, 0, sizeof(queue));
	int head = 0;
	int tail = 0;

	bool added[N];
	memset(added, false, sizeof(added));

	queue[tail++] = start;
	added[start] = true;

	while (head != tail) {
		int front = queue[head++];

		printf("%s\n", decode(front));

		for (int i=0; i<N; i++) {
			if (added[i] == false && graph[front][i] != -1) {
				queue[tail++] = i;
				added[i] = true;
			}
		}
	}
}

void print_dijkstra(int from, int to) {
	const int N = t_idx;

	int dist[N];
	int prev[N];
	bool included[N];
	memset(dist, 1e6, sizeof(dist));
	memset(prev, -1, sizeof(prev));
	memset(included, 0, sizeof(included));

	dist[from] = 0;
	prev[from] = -1;

	for (int i=0; i<N; i++) {
		// find min edge
		int min_edge = 1e6;
		int min_edge_v = -1;
		for (int j=0; j<N; j++) {
			if (included[j] == false && dist[j] < min_edge) {
				min_edge = dist[j];
				min_edge_v = j;
			}
		}

		//printf("found: %d, %d\n", min_edge_v, min_edge);

		included[min_edge_v] = true;

		if (min_edge_v == to) break;

		// update
		for (int j=0; j<N; j++) {
			if (included[j] == false && graph[min_edge_v][j] != -1) {
				if (dist[j] > dist[min_edge_v] + graph[min_edge_v][j]) {
					dist[j] = dist[min_edge_v] + graph[min_edge_v][j];
					prev[j] = min_edge_v;
				}
			}
		}
	}

	printf("total: %d\n", dist[to]);

	int data[1000];
	int idx = 0;

	while (prev[to] != -1) {
		data[idx++] = to;
		to = prev[to];
	}

	data[idx++] = from;

	for (int i=idx-1; i>=0; i--) {
		printf("%s", decode(data[i]));
		if (i != 0)
			printf(" -> ");
	}
	puts("");
}

int djset_find(int* parent, int x) {
	if (parent[x] == x)
		return x;
	else
		return (parent[x] = djset_find(parent, parent[x]));
	return -1;
}

void djset_union(int* parent, int* rank, int x, int y) {
	x = djset_find(parent, x);
	y = djset_find(parent, y);

	if (x == y) return;

	if (rank[x] < rank[y])
		parent[x] = y;
	else if (rank[x] > rank[y])
		parent[y] = x;
	else {
		parent[x] = y;
		rank[x]++;
	}
}

bool djset_same(int* parent, int* rank, int x, int y) {
	return (djset_find(parent, x) == djset_find(parent, y));
}

void print_kruskal() {
	// Disjoint Set
	const int N = t_idx;
	int parent[N];
	int rank[N];
	for (int i=0; i<N; i++) {
		parent[i] = i;
		rank[i] = 0;
	}

	//assume |E| < 10000
	// Establish edge
	Edge edge[10000];
	int edge_cnt = 0;
	for (int i=0; i<N; i++)
		for (int j=0; j<N; j++)
			if (graph[i][j] != -1) {
				edge[edge_cnt].from = i;
				edge[edge_cnt].to = j;
				edge[edge_cnt].cost = graph[i][j];
				edge_cnt++;
			}

	qsort(edge, edge_cnt, sizeof(Edge), edge_cmp);

	int total = 0;
	for (int i=0; i<edge_cnt; i++) {
		Edge e = edge[i];
		if (djset_same(parent, rank, e.from, e.to) == false) {
			djset_union(parent, rank, e.from, e.to);
			printf("Add Edge(%s, %s, %d)\n", decode(e.from), decode(e.to), e.cost);
			total += e.cost;
		}
	}

	printf("total: %d\n", total);
}

int main(int argc, char* argv[]) {
	if (argc != 2)
		return -1;

	FILE* f = fopen(argv[1], "r");
	if (f == NULL) {
		puts("File not exist!");
		return -1;
	}

	memset(graph, -1, sizeof(graph));
	memset(translate, 0, sizeof(translate));

	char input[1024];
	while (fgets(input, 1024, f) != NULL) {
		int len = strlen(input);
		if (input[len-1] == '\n') {
			input[len-1] = '\0';
			len--;
		}

		if (len == 0) continue;

		char* place1 = strtok(input, " ");
		char* place2 = strtok(NULL, " ");
		char* distance = strtok(NULL, " ");

		if (place1 == NULL || place2 == NULL ||
								is_str_digit(distance) == false) {
			puts("Illegal Data!");
			continue;
		}

		int idx1 = encode(place1);
		int idx2 = encode(place2);
		int weight = atoi(distance);

		graph[idx1][idx2] = weight;
		graph[idx2][idx1] = weight;

		printf("Edge(%s(%d), %s(%d)) = %d\n", place1, idx1, place2,idx2, weight);
	}

	puts("----------------------------------------");

	while (true) {
		printf("> ");
		fgets(input, 1024, stdin);

		int len = strlen(input);
		if (input[len-1] == '\n') {
			input[len-1] = '\0';
			len--;
		}

		if (strcmp(input, "q") == 0)
			break;

		if (len == 0)
			continue;

		char* cmd = strtok(input, " ");
		char* arg1 = strtok(NULL, " ");
		char* arg2 = strtok(NULL, " ");

		if (strcmp(cmd, "MST") == 0 && arg1 == NULL && arg2 == NULL) {
			print_kruskal();
		}
		else if (strcmp(cmd, "DFS") == 0 && arg1 != NULL && arg2 == NULL) {
			int idx = get_idx(arg1);
			if (idx == -1) {
				puts("Illegal Place!");
				continue;
			}

			print_dfs(idx);
		}
		else if (strcmp(cmd, "BFS") == 0 && arg1 != NULL && arg2 == NULL) {
			int idx = get_idx(arg1);
			if (idx == -1) {
				puts("Illegal Place!");
				continue;
			}

			print_bfs(idx);
		}
		else if (strcmp(cmd, "SP") == 0 && arg1 != NULL && arg2 != NULL) {
			int from = get_idx(arg1);
			int to = get_idx(arg2);
			if (from == -1 || to == -1) {
				puts("Illegal Place!");
				continue;
			}

			print_dijkstra(from, to);
		}
		else {
			puts("Illegal input!");
		}
	}

	for (int i=0; i<t_idx; i++)
		free(translate[i]);

	return 0;
}

amoshyc/DS_project7.md

題目

Example

Code