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

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

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

	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 (tc[s][k] && tc[k][t]) {
					tc[s][t] = true;
				}
			}
		}
	}

	return tc;
}