// AlgoProject4.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#include <limits>

using namespace std;


struct Edge
{
	int from, to, cost;
	Edge(int from, int to, int cost)
	{
		this->from = from;
		this->to = to;
		this->cost = cost;
	}
};

struct Edge_Compare
{
	bool operator() (Edge a, Edge b) const
	{
		return a.cost > b.cost;
	}
};

void init(vector<vector<Edge>>& graph, int& node_degree,
	priority_queue<int, vector<Edge>, Edge_Compare>& next_to_connect)
{
	int num_nodes;
	cout << "Enter the number of nodes in the graph: ";
	cin >> num_nodes;
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	graph.resize(num_nodes);

	int num_edges, from, to, cost;
	cout << "Enter the number of distinct edges in your graph \n(Edges entered must be"
		<< " distinct. i.e. no backwards edges): ";
	cin >> num_edges;
	cout << endl;
	cin.ignore(numeric_limits<streamsize>::max(), '\n');





	for (int edge_itr = 0; edge_itr < num_edges; edge_itr++)
	{
		cout << "Enter a from_edge value followed by a to_edge value followed \nby an to edge_cost value: ";
		cin >> from;
		cin >> to;
		cin >> cost;
		Edge input = Edge(from, to, cost);
		graph[from].push_back(input);
		graph[to].push_back(input);
		next_to_connect.push(input);
		cout << endl;
		cin.ignore(numeric_limits<streamsize>::max(), '\n');

	}


}





int Kruskal(const vector<vector<Edge>>& graph, string& mst_nodes, int node_degree,
	priority_queue<int, vector<Edge>, Edge_Compare>& next_to_connect)
{
	unordered_map<int, int> nodes_to_chain;
	vector<vector<int>> chains;
	int num_chains = 0, nodes_to_retain = next_to_connect.size() - node_degree, mst_cost = 0;
	for (int i = 0; i < graph.size(); i++)
		nodes_to_chain.insert(pair<int, int>(i, -1));

	while (!next_to_connect.empty() /*&& next_to_connect.size() > nodes_to_retain*/)
	{
		Edge connect = next_to_connect.top();

		if (nodes_to_chain.at(connect.from) == -1) //from node is unconnected
		{
			if (nodes_to_chain.at(connect.to) == -1) //to node is unconnected
			{
				chains.push_back(vector<int>());
				nodes_to_chain.at(connect.from) = chains.size() - 1;
				nodes_to_chain.at(connect.to) = chains.size() - 1;
				chains[chains.size() - 1].push_back(connect.from);
				chains[chains.size() - 1].push_back(connect.to);
				mst_nodes += to_string(connect.from) + "-" + to_string(connect.to) + ", ";
				mst_cost += connect.cost;
			}
			else //to node is connected
			{
				nodes_to_chain.at(connect.from) = nodes_to_chain.at(connect.to);
				chains[nodes_to_chain.at(connect.to)].push_back(connect.from);
				mst_nodes += to_string(connect.from) + "-" + to_string(connect.to) + ", ";
				mst_cost += connect.cost;
			}
		}
		else //from node is connected
		{
			if (nodes_to_chain.at(connect.to) == -1) //to node is unconnected
			{
				nodes_to_chain.at(connect.to) = nodes_to_chain.at(connect.from);
				chains[nodes_to_chain.at(connect.from)].push_back(connect.to);
				mst_nodes += to_string(connect.from) + "-" + to_string(connect.to) + ", ";
				mst_cost += connect.cost;
			}
			else if (nodes_to_chain.at(connect.from) != nodes_to_chain.at(connect.to)) //from node and to node
				//are connected but are also in different chains
			{
				chains.push_back(vector<int>());
				for (int node : chains[nodes_to_chain.at(connect.from)])
				{
					chains[chains.size() - 1].push_back(node);
					nodes_to_chain.at(node) = chains.size() - 1;
				}
				nodes_to_chain.at(connect.from) = chains.size() - 1;
				for (int node : chains[nodes_to_chain.at(connect.to)])
				{
					chains[chains.size() - 1].push_back(node);
					nodes_to_chain.at(node) = chains.size() - 1;
				}
				nodes_to_chain.at(connect.to) = chains.size() - 1;

				mst_nodes += to_string(connect.from) + "-" + to_string(connect.to) + ", ";
				mst_cost += connect.cost;
				/*If the two connecting nodes are actually from different groups then we must
				place every node in each chain into the same chain.*/
			}

			/*If connecting nodes are in the same chain, then that would form a cycle. Instead, we do not
			connect two nodes that are in the same chain.*/
		}

		next_to_connect.pop();
	}

	return mst_cost;
}

int Prim(const vector<vector<Edge>>& graph, string& mst_nodes, int node_degree,
	priority_queue<int, vector<Edge>, Edge_Compare>& next_to_connect)
{
	vector<bool> visited(graph.size());
	int mst_cost = 0;
	visited[0] = true;
	for (Edge e : graph[0])
		next_to_connect.push(e);

	while (!next_to_connect.empty())
	{
		if (!visited[next_to_connect.top().to] ||
			visited[next_to_connect.top().to] && !visited[next_to_connect.top().from])
		{

			int to = !visited[next_to_connect.top().to] ? next_to_connect.top().to :
				next_to_connect.top().from;

			mst_cost += next_to_connect.top().cost;
			mst_nodes += to_string(next_to_connect.top().from)
				+ "-" + to_string(next_to_connect.top().to) + ", ";
			visited[to] = true;
			next_to_connect.pop();
			for (Edge e : graph[to])
				next_to_connect.push(e);

		}
		else
			next_to_connect.pop();


	}

	return mst_cost;
}


int main()
{
	vector<vector<Edge>> graph;
	priority_queue <int, vector<Edge>, Edge_Compare> next_to_connect;
	string mst_nodes = "{ ";
	int node_degree, mst_cost; //if a node_degree is supplied and it is less than the number of nodes in the graph,
	//then the path is not spanning. Only node_degree nodes are in the path. Otherwise, the path is spanning.

	init(graph, node_degree, next_to_connect);
	node_degree = graph.size();

	mst_cost = Kruskal(graph, mst_nodes, node_degree, next_to_connect);
	mst_nodes += "}";

	cout << "The Minimum Spanning Tree path cost with Kruskal's is: " << mst_cost << endl;
	cout << "The edges in the Minimum Spanning Tree of degree " << node_degree << " are: " << mst_nodes << endl;

	mst_nodes = "{ ";

	mst_cost = Prim(graph, mst_nodes, node_degree, next_to_connect);
	mst_nodes += "}";

	cout << "The Minimum Spanning Tree path cost with Prim's is: " << mst_cost << endl;
	cout << "The edges in the Minimum Spanning Tree of degree " << node_degree << " are: " << mst_nodes << endl;



	return 0;
}
/*
Sample Input:
6
9
0 1 7
0 2 8
1 2 3
1 3 6
2 3 4
2 4 3
3 4 2
3 5 5
4 5 2

7
11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
*/