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

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

static void dfsRec(Graph g, Vertex v, bool *visited);
static bool dfsFindPathRec(Graph g, Vertex v, Vertex dest, int *predecessor);

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

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

	printf("\n");
}

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

			// backtracking to v
			// printf("%d ", v);
		}
	}
}

void dfsFindPath(Graph g, Vertex src, Vertex dest) {
	int *predecessor = malloc(g->nV * sizeof(int));
	for (int i = 0; i < g->nV; i++) {
		predecessor[i] = -1;
	}

	predecessor[src] = src;
	bool result = dfsFindPathRec(g, src, dest, predecessor);

	if (result) {
		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);
}

static bool dfsFindPathRec(Graph g, Vertex v, Vertex dest, int *predecessor) {
	if (v == dest) {
		return true;
	}

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

	return false;
}