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

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

void dfsRec(Graph g, Vertex v, bool *visited);
void dfsFindPathRec(Graph g, Vertex v, Vertex dest, Vertex *pred);

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

	// TODO
	bool *visited = calloc(g->nV, sizeof(bool));
	dfsRec(g, src, visited);
	free(visited);

	printf("\n");
}

void dfsRec(Graph g, Vertex v, bool *visited) {
	visited[v] = true;
	printf("%d ", v);

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

		if (!visited[w]) {
			dfsRec(g, w, visited);
		}
	}
}

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

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

	pred[src] = src;
	dfsFindPathRec(g, src, dest, pred);

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

	printf("\n");
}

void dfsFindPathRec(Graph g, Vertex v, Vertex dest, Vertex *pred) {
	if (v == dest) {
		return;
	}

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