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

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

bool **warshall(Graph g);

int main(void) {
	Graph g = GraphRead(stdin);

	printf("Graph:\n");
	GraphShow(g);

	bool **tc = warshall(g);

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

	GraphFree(g);
	if (tc != NULL) { // i.e., if warshall() has been implemented
		for (int i = 0; i < g->nV; i++) {
			free(tc[i]);
		}
		free(tc);
	}
}

bool **warshall(Graph g) {

	bool **tc = malloc(sizeof(bool *)*g->nV);
	for(int i=0; i<g->nV; i++) {
		tc[i] = malloc(sizeof(bool)*g->nV);
		for(int j=0; j<g->nV; j++) {
			tc[i][j] = g->edges[i][j];
		}
	}


	// we start with the matrix telling us when s can reach t directy
	// consider node 0
		// consider all s and t's, can s reach t if it goes via 0?
	// now we have a matrix telling us when s can reach t either directly, or via node 0
	// consider node 1
		// consider all s and t's, can s reach t if it goes via 0 (already in place) and/or 1? 

	for(int k=0; k<g->nV; k++) {
		for(int s=0; s<g->nV; s++) {
			for(int t=0; t<g->nV; t++) {
				// if s can reach k and k can reach t
				if (tc[s][k] && tc[k][t]) {
					// then s can reach t
					tc[s][t] = true;
				}
			}	
		}
	}

	return tc;
}