#include <stdio.h>
#include <iostream>
#include <string>
#include <sstream>
#include <malloc.h>
#include <fstream>
#include <limits>

#include <queue>
#include <vector>
#include <list>
#include <map>

using namespace std;

#define INFINITY std::numeric_limits<int>::max( )

struct struct_Node_File {
	std::map<int, int> nodeEdges;
};

struct struct_Node_MinSpanningTree {
	int shortestDistance;
	int prevPath;
	std::map<int, int> nodeEdges;
};

struct struct_Sorting_Edge {
	int dest;	//destination
	//int source2dest_weight;	//source to destination weight
	int source;	//source
	//int dest2source_weight;	//destination to source weight
	int average_Weight;
};

// this is an strucure which implements the 
// operator overlading 
struct CompareWeight {
	bool operator()(struct_Sorting_Edge const& edge1, struct_Sorting_Edge const& edge2)
	{
		// return "true" if "edge1" is ordered before "edge2"
		return edge1.average_Weight > edge2.average_Weight;
	}
};

int main()
{
	//Initialize graph's nodes
	std::map<int, struct_Node_File> mapFile;

	//Read graph's nodes connection from a file and build the graph
	std::ifstream inputfile("graph2.txt");
	int node_count = 0;
	if (inputfile.is_open())
	{
		string sLine;
		while (getline(inputfile, sLine)) {

			//Save input file data into 'mapFile'
			vector<string> vectorStr;
			stringstream ss(sLine);
			string item;

			while (getline(ss, item, ' '))
			{
				vectorStr.push_back(item);
			}


			struct_Node_File tmp_node;
			int tmp_Dest = 0, tmp_Weight = 0, tmpEdgesCount = 0;
			for (auto i : vectorStr)
			{
				if (tmpEdgesCount % 2 == 0)
					tmp_Dest = stoi(i);
				else
					tmp_Weight = stoi(i);
				
				tmp_node.nodeEdges[tmp_Dest] = tmp_Weight;
				tmpEdgesCount++;
			}

			mapFile[node_count] = tmp_node;
			node_count++;
		}
		inputfile.close();
	}
	cout << "Graph established." << endl;


	//Ascending Order by weight for all Edges
	std::priority_queue <struct_Sorting_Edge, std::vector<struct_Sorting_Edge>, CompareWeight > asc_sorted_travelDist;
	struct_Sorting_Edge tmp_struct_NodeEdge;

	for (int i = 0; i < node_count; i++)
	{
		for (auto curr_nodeEdge : mapFile[i].nodeEdges)
		{
			tmp_struct_NodeEdge.average_Weight = curr_nodeEdge.second;
			tmp_struct_NodeEdge.source = i;
			tmp_struct_NodeEdge.dest = curr_nodeEdge.first;

			asc_sorted_travelDist.push(tmp_struct_NodeEdge);
		}
	}
	cout << endl;

	//Print asc_sorted_travelDist
	std::priority_queue <struct_Sorting_Edge, std::vector<struct_Sorting_Edge>, CompareWeight > tmp_asc_sorted_travelDist = asc_sorted_travelDist;
	while (!tmp_asc_sorted_travelDist.empty())
	{

		cout << tmp_asc_sorted_travelDist.top().source << ": dest = " << tmp_asc_sorted_travelDist.top().dest << ", weight = " << tmp_asc_sorted_travelDist.top().average_Weight << endl;
		tmp_asc_sorted_travelDist.pop();
	}
	cout << endl;

	//Create minimum-spanning-tree graph
	std::map<int, struct_Node_MinSpanningTree> graph_MinSpanningTree;
	while (!asc_sorted_travelDist.empty())
	{
		if (graph_MinSpanningTree.find(asc_sorted_travelDist.top().source) == graph_MinSpanningTree.end())
		{
			struct_Node_MinSpanningTree tmp_struct_Node_MinSpanningTree;
			graph_MinSpanningTree[asc_sorted_travelDist.top().source] = tmp_struct_Node_MinSpanningTree;
		}

		if (graph_MinSpanningTree.find(asc_sorted_travelDist.top().dest) == graph_MinSpanningTree.end())
		{
			struct_Node_MinSpanningTree tmp_struct_Node_MinSpanningTree;
			graph_MinSpanningTree[asc_sorted_travelDist.top().dest] = tmp_struct_Node_MinSpanningTree;
		}

		if (graph_MinSpanningTree[asc_sorted_travelDist.top().source].nodeEdges.empty() || graph_MinSpanningTree[asc_sorted_travelDist.top().dest].nodeEdges.empty())
		{
			graph_MinSpanningTree[asc_sorted_travelDist.top().source].nodeEdges[asc_sorted_travelDist.top().dest] = asc_sorted_travelDist.top().average_Weight;
			graph_MinSpanningTree[asc_sorted_travelDist.top().dest].nodeEdges[asc_sorted_travelDist.top().source] = asc_sorted_travelDist.top().average_Weight;
		}
		else
		{
			//Re-initialize graph
			for (int i = 0; i < node_count; i++) {
				graph_MinSpanningTree[i].shortestDistance = INFINITY;
				graph_MinSpanningTree[i].prevPath = -1;
			}
			graph_MinSpanningTree[asc_sorted_travelDist.top().source].shortestDistance = 0;

			//check if there an existing path from priority queue top node to destination node by using Shortest Path derivation
			std::priority_queue <int, std::vector<int>, std::greater<int> > q;
			q.push(asc_sorted_travelDist.top().source);

			bool breakExecution = false;
			int top = -1, sum = 0;
			while (!q.empty() && !breakExecution) {
				if (top == q.top())
					q.pop();
				else
				{
					top = q.top();
					q.pop();

					for (auto tmpNodeEdge : graph_MinSpanningTree[top].nodeEdges) {
						sum = graph_MinSpanningTree[top].shortestDistance + tmpNodeEdge.second;
						if (graph_MinSpanningTree[tmpNodeEdge.first].shortestDistance > sum) {
							graph_MinSpanningTree[tmpNodeEdge.first].shortestDistance = sum;
							graph_MinSpanningTree[tmpNodeEdge.first].prevPath = top;

							q.push(tmpNodeEdge.first);

							//We can stop any further checking when found a path from source node to destination node
							if (top == asc_sorted_travelDist.top().dest)
								breakExecution = true;
						}
					}
				}
			}

			if (graph_MinSpanningTree[asc_sorted_travelDist.top().dest].shortestDistance == INFINITY)
			{
				graph_MinSpanningTree[asc_sorted_travelDist.top().source].nodeEdges[asc_sorted_travelDist.top().dest] = asc_sorted_travelDist.top().average_Weight;
				graph_MinSpanningTree[asc_sorted_travelDist.top().dest].nodeEdges[asc_sorted_travelDist.top().source] = asc_sorted_travelDist.top().average_Weight;
			}
		}

		asc_sorted_travelDist.pop();
	}
	cout << "Print Minimum Spanning Tree graph" << endl;
	for (int i = 0; i < node_count; i++) {
		for (auto curr_nodeEdge3 : graph_MinSpanningTree[i].nodeEdges)
			cout << i << ": dest = " << curr_nodeEdge3.first << ", weight = " << curr_nodeEdge3.second << endl;
	}
	cout << endl;

	//Save Min Spanning Tree graph into file 'MinSpanningTree_result.txt'
	ofstream myfile;
	myfile.open("MinSpanningTree_result.txt");
	for (int i = 0; i < node_count; i++) {
		for (auto curr_nodeEdge3 : graph_MinSpanningTree[i].nodeEdges)
			myfile << curr_nodeEdge3.first << " " << curr_nodeEdge3.second << " ";

		myfile << "\n";
	}
	myfile.close();

	return 0;
}