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

#include "Graph.h"
#include "GraphPrivate.h"
#include "Queue.h"

void bfs(Graph g, Vertex src) {
	printf("BFS starting from %d: ", src);

	int *predecessor = malloc(g->nV * sizeof(int));
	Queue q = QueueNew();

	for (int i = 0; i < g->nV; i++) {
		predecessor[i] = -1;
	}

	predecessor[src] = src;
	QueueEnqueue(q, src);

	while (QueueSize(q) > 0) {
		// dequeue vertex v
		Vertex v = QueueDequeue(q);

		printf("%d ", v);

		// explore v
		struct adjNode *curr = g->edges[v];
		for (; curr != NULL; curr = curr->next) {
			Vertex w = curr->v;

			// if w hasn't been visited
			if (predecessor[w] == -1) {
				predecessor[w] = v;
				QueueEnqueue(q, w);
			}
		}
	}

	printf("\n");

	free(predecessor);
	QueueFree(q);
}

void bfsFindPath(Graph g, Vertex src, Vertex dest) {
	int *predecessor = malloc(g->nV * sizeof(int));
	Queue q = QueueNew();

	for (int i = 0; i < g->nV; i++) {
		predecessor[i] = -1;
	}

	predecessor[src] = src;
	QueueEnqueue(q, src);

	while (QueueSize(q) > 0) {
		// dequeue vertex v
		Vertex v = QueueDequeue(q);

		// explore v
		struct adjNode *curr = g->edges[v];
		for (; curr != NULL; curr = curr->next) {
			Vertex w = curr->v;

			// if w hasn't been visited
			if (predecessor[w] == -1) {
				predecessor[w] = v;
				QueueEnqueue(q, w);
			}
		}
	}

	if (predecessor[dest] != -1) {
		printf("Path from %d to %d: ", src, dest);

		Vertex curr = dest;
		while (curr != src) {
			printf("%d <- ", curr);
			curr = predecessor[curr];
		}
		printf("%d\n", src);
	} else {
		printf("No path from %d to %d\n", src, dest);
	}

	free(predecessor);
	QueueFree(q);
}