#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);

	// bool *visited = calloc(g->nV, sizeof(bool));
	Vertex *pred = malloc(g->nV * sizeof(Vertex));
	for (int i = 0; i < g->nV; i++) {
		pred[i] = -1;
	}
	Queue q = QueueNew();

	// visited[src] = true;
	pred[src] = src;
	QueueEnqueue(q, src);

	while (QueueSize(q) > 0) {
		Vertex v = QueueDequeue(q);
		printf("%d ", v);

		struct adjNode *curr = g->edges[v];
		for (; curr != NULL; curr = curr->next) {
			Vertex w = curr->v;
			// if (!visited[w]) {
			if (pred[w] == -1) {
				// visited[w] = true;
				pred[w] = v;
				QueueEnqueue(q, w);
			}
		}
	}

	// free(visited);
	free(pred);
	QueueFree(q);

	printf("\n");
}

void bfsFindPath(Graph g, Vertex src, Vertex dest) {
	printf("BFS path from %d to %d: ", src, dest);

	Vertex *pred = malloc(g->nV * sizeof(Vertex));
	for (int i = 0; i < g->nV; i++) {
		pred[i] = -1;
	}
	Queue q = QueueNew();

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

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

		struct adjNode *curr = g->edges[v];
		for (; curr != NULL; curr = curr->next) {
			Vertex w = curr->v;
			if (pred[w] == -1) {
				pred[w] = v;
				QueueEnqueue(q, w);
			}
		}
	}

	if (pred[dest] == -1) {
		printf("No path");
	} else {
		Vertex curr = dest;
		while (curr != src) {
			printf("%d <- ", curr);
			curr = pred[curr];
		}
		printf("%d", src);
	}

	free(pred);
	QueueFree(q);

	printf("\n");
}