// Graph ADT interface for Ass2 (COMP2521)
#include "CentralityMeasures.h"
#include "Dijkstra.h"
#include "PQ.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h> /////======i included this, are we allowed? I think.


static double* createValueArray (int noNodes);
static void accumulateBetweenness(ShortestPaths paths, double *values, int *dividers);

//for each node, iterate through the adjacency list,
//count the number of outincident edges and add that to the corresponding values array
NodeValues outDegreeCentrality(Graph g){
	//printf("Entering out deg func\n");
	assert(g!= NULL);
	NodeValues throwAway = {0};
	int numNodes = numVerticies(g);
	//printf("num nodes %d\n", numNodes);
	throwAway.noNodes = numNodes;
	throwAway.values = createValueArray(numNodes);
	for (int v = 0; v < numNodes; v++){
		int count = 0;
		AdjList outIncList = outIncident(g, v);
		AdjList curr = outIncList;
		if (curr == NULL){ //edge case1 - no items in adjlist
			count = 0;
			throwAway.values[v] = count;
			//printf("count = %d\n", count);
			continue;
		}
		if (curr->next == NULL){//edge case 2 - 1 item in adj list
			count = 1;
			throwAway.values[v] = count;
			//printf("count = %d\n", count);
			continue;
		}
		while (curr->next != NULL){ //iterate through list
			count ++;
			curr = curr->next;
		}
		count ++; //add one extra to count for the first one.
		throwAway.values[v] = count;
		//printf("count = %d\n", count);
	}
	return throwAway;
}
NodeValues inDegreeCentrality(Graph g){
	assert(g!= NULL);
	NodeValues throwAway = {0};
	int numNodes = numVerticies(g);
	//printf("num nodes %d\n", numNodes);
	throwAway.noNodes = numNodes;
	throwAway.values = createValueArray(numNodes);
	for (int v = 0; v < numNodes; v++){
		int count = 0;
		AdjList inIncList = inIncident(g, v);
		AdjList curr = inIncList;
		if (curr == NULL){ //edge case1 - no items in adjlist
			count = 0;
			throwAway.values[v] = count;
			//printf("count = %d\n", count);
			continue;
		}
		if (curr->next == NULL){//edge case 2 - 1 item in adj list
			count = 1;
			throwAway.values[v] = count;
			//printf("count = %d\n", count);
			continue;
		}
		while (curr->next != NULL){ //iterate through list
			count ++;
			curr = curr->next;
		}
		count ++; //add one extra to count for the first one.
		throwAway.values[v] = count;
		//printf("count = %d\n", count);
	}
	return throwAway;
}
NodeValues degreeCentrality(Graph g) {
	assert(g!= NULL);
	NodeValues throwAway = {0};
	int numNodes = numVerticies(g);
	//printf("num nodes %d\n", numNodes);
	throwAway.noNodes = numNodes;
	throwAway.values = createValueArray(numNodes);
	for (int v = 0; v < numNodes; v++){
		int count = 0;
		AdjList outIncList = outIncident(g, v);
		AdjList curr = outIncList;
		if (curr == NULL){ //edge case1 - no items in adjlist
			count = 0;
			throwAway.values[v] = count;
			//printf("count = %d\n", count);
			continue;
		}
		if (curr->next == NULL){//edge case 2 - 1 item in adj list
			count = 1;
			throwAway.values[v] = count;
			//printf("count = %d\n", count);
			continue;
		}
		while (curr->next != NULL){ //iterate through list
			count ++;
			curr = curr->next;
		}
		count ++; //add one extra to count for the first one.
		throwAway.values[v] = count;
		//printf("count = %d\n", count);
	}
		for (int v = 0; v < numNodes; v++){
		int count = 0;
		AdjList inIncList = inIncident(g, v);
		AdjList curr = inIncList;
		if (curr == NULL){ //edge case1 - no items in adjlist
			count = 0;
			throwAway.values[v] = throwAway.values[v] + count;
			//printf("count = %d\n", count);
			continue;
		}
		if (curr->next == NULL){//edge case 2 - 1 item in adj list
			count = 1;
			throwAway.values[v] = throwAway.values[v] + count;
			//printf("count = %d\n", count);
			continue;
		}
		while (curr->next != NULL){ //iterate through list
			count ++;
			curr = curr->next;
		}
		count ++; //add one extra to count for the first one.
		throwAway.values[v] = throwAway.values[v] + count;
		//printf("count = %d\n", count);
	}
	return throwAway;
}
/*This function might break if you can have edges of weight 0!
because we calculate reachability using the distance array (if distance = 0).*/
NodeValues closenessCentrality(Graph g){
	assert(g!= NULL);
	NodeValues throwAway = {0};
	int numNodes = numVerticies(g);
	//printf("num nodes %d\n", numNodes);
	throwAway.noNodes = numNodes;
	throwAway.values = createValueArray(numNodes);


	for (int v = 0; v< numNodes; v++){
		//====according to formula ===
		//v = vertex
		//n = out incidence of v
		//N = numNodes in graph
		//can get shortest path with dijk.dist[v]
		//the sum of the shortest paths of v to all other nodes

		//count the number of out incident edges of v. -- should make into new function.
		/*AdjList outIncList = outIncident(g, v);
		AdjList curr = outIncList;
		int count = 0;
		if (curr == NULL){ //edge case1 - no items in adjlist
			count = -1; //-1 because it will add one once it finishes this loop
			//printf("count = %d\n", count);
		}
		else if (curr->next == NULL){//edge case 2 - 1 item in adj list
			count = 0; // 0 because adds one after finishes loop
			//printf("count = %d\n", count);
		}
		while (curr->next != NULL){ //iterate through list
			count ++;
			curr = curr->next;
		}
		count ++; //add one extra to count for the first one.
		int numOutInc = count;*/
		int reachableNodes = 0; //will not include itself.


		ShortestPaths shortestPaths = dijkstra(g, v);
		int sumShortestPaths = 0;
		for (int destVertex = 0; destVertex < numNodes; destVertex++){
				if (destVertex != v) {//we cant add the shortest path from v to v.
					if (shortestPaths.dist[destVertex] != 0) { //if the node is reachable!
						reachableNodes++;
					}
					sumShortestPaths = sumShortestPaths + shortestPaths.dist[destVertex];
				}  //add the distances up to create this sum

		}
		//printf("ReachabeNodes = %d\n sumShortestPaths = %d\n numnodes = %d \n ", reachableNodes, sumShortestPaths, numNodes);
		if (((numNodes - 1) == 0 )| (sumShortestPaths == 0)) { //if we are going to have a divide by 0 error.
			throwAway.values[v] = 0;
			continue;
		}
		double LHSAnswer = (double)(reachableNodes) / (numNodes-1);
		double RHSAnswer = (double)(reachableNodes)/(sumShortestPaths);
		//printf("LHS Answer = %lf \n, RHS Answer = %lf\n", LHSAnswer, RHSAnswer);
		double answer = LHSAnswer*RHSAnswer;
		throwAway.values[v] = answer;

	}




	return throwAway;
}

NodeValues betweennessCentrality(Graph g){
	double *values = createValueArray(numVerticies(g));
	int *dividers = malloc(numVerticies(g) * sizeof(int)); // Holds ints to scale values array down (because betweenness centrality for a given node is less if there are other shortest paths between two points that don't go through the node)

	for (int v = 0; v < numVerticies(g); v++) {
	    ShortestPaths paths = dijkstra(g, v);
        accumulateBetweenness(paths, values, dividers);
	}




	NodeValues throwAway = {0};
	return throwAway;
}

NodeValues betweennessCentralityNormalised(Graph g){
	NodeValues throwAway = {0};
	return throwAway;
}

void showNodeValues(NodeValues values){
	for (int v = 0; v < values.noNodes; v++){
		printf("%d: %lf\n", v, values.values[v]);
	}

}

void freeNodeValues(NodeValues values){
	free(values.values);
}

static double * createValueArray (int noNodes){
	double * values = malloc(noNodes * sizeof(double)); //malloc an array of doubles to be pointed to by the struct.
	assert(values != NULL);
	for (int i = 0; i < noNodes; i++){
		values[i] = 0;
	}
	return values;
}


static void accumulateBetweenness(ShortestPaths paths, double *values, int *dividers) {
	    for (int u = 0; u < paths.noNodes; u++) { // Accumulating betweeness and dividers for each node with a path to the source
	        if (paths.src == u) continue; // skip checking path from source to source

	        paths->pred[u]

	    }
    return;
}