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

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

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

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

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

	printf("\n");

	for (int i = 0; i < g->nV; ++i) {
		printf("%d ", pred[i]);
	}
	printf("\n");
}

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

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

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

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

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

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

	printf("\n");
}