#pragma once

#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include "graph.hpp"

using namespace std;

// 最小生成树（树枝权值和最小）
template <typename TVertex, typename TWeight>
class MinimunSpanTree
{
protected:
	graph::Edge<TVertex, TWeight>* mst_edges_;	// 最小生成树边数组
	int max_size_;								// 边数上限
	int size_;									// 当前边数量

public:
	explicit MinimunSpanTree(int max_size)
		:max_size_(max_size), size_(0)
	{
		this->mst_edges_ = new graph::Edge<TVertex, TWeight>[this->max_size_];
		if (!this->mst_edges)
			throw bad_alloc();
	}

	int insert(graph::Edge<TVertex, TWeight>& edge)
	{
		// 合法性判断
		if (this->size_ >= this->max_size_)
			return -1;	// 插入失败

		// 执行插入
		this->mst_edges_[this->size_] = edge;
		this->size_++;

		return this->size_ - 1;
	}

	void print()
	{
		TWeight total_weight = 0;
		for (int i = 0; i < this->size_; i++)
		{
			total_weight += this->mst_edges_[i].weight;
			cout << "starting_vertex：" << this->mst_edges_[i].starting_vertex
				<< "，ending_vertex：" << this->mst_edges_[i].ending_vertex
				<< "，weight：" << this->mst_edges_[i].weight << endl;
		}

		cout << "最小生成树边总权值为：" << total_weight << endl;
	}

};

template <typename TVertex,typename TWeight>
void Dfs(const graph::Graph<TVertex, TWeight>& graph, const TVertex& vertex);

template <typename TVertex,typename TWeight>
void DfsOnVertexRecursive(const graph::Graph<TVertex, TWeight>& graph, const TVertex& vertex, set<TVertex>& visited_vertex_set);

template <typename TVertex,typename TWeight>
void Bfs(const graph::Graph<TVertex, TWeight>& graph, const TVertex& vertex);

template <typename TVertex,typename TWeight>
bool topologicalSort(const graph::Graph<TVertex,TWeight>& graph,const TVertex& starting_vertex,vector<TVertex>& topology_sorted_list);

template <typename TVertex,typename TWeight>
void topologicalSortRecursive_(const graph::Graph<TVertex,TWeight>& graph, TVertex starting_vertex,set<TVertex>& visited_vertex_set,vector<TVertex>& topology_sorted_list);

template <typename TVertex,typename TWeight>
int components(const graph::Graph<TVertex,TWeight>& graph);

template <typename TVertex,typename TWeight>
bool prim(const graph::Graph<TVertex,TWeight>& graph, MinimunSpanTree<TVertex,TWeight>& min_span_tree);

template <typename TVertex,typename TWeight>
void kruskal(const graph::Graph<TVertex,TWeight>& graph, MinimunSpanTree<TVertex,TWeight>& min_span_tree);

template <typename TVertex,typename TWeight>
void dijkstra(const graph::Graph<TVertex,TWeight>& graph, const TVertex& starting_vertex, TWeight distance[], int predecessor[]);

template <typename TVertex,typename TWeight>
bool bellmanFord(const graph::Graph<TVertex,TWeight>& graph,const TVertex& starting_vertex,TWeight distance[],int predecessor[]);

template <typename TVertex, typename TWeight>
void floyd(const graph::Graph<TVertex,TWeight>& graph, vector<vector<TWeight>>& distance, vector<vector<int>>& predecessor);

template <typename TVertex,typename TWeight>
void printSingleSourceShortestPath(const graph::Graph<TVertex,TWeight>& graph, const TVertex& starting_vertex,TWeight distance[],const int predecessor[]);

template <typename TVertex, typename TWeight>
void printMultipleSourceShortestPath(const graph::Graph<TVertex, TWeight>& graph, const vector<vector<TWeight>>& distance, const vector<vector<int>>& predecessor);

template <typename TVertex, typename TWeight>
bool printSingleSourceShortestPathInMultipleSourceShortestPath(const graph::Graph<TVertex, TWeight>& graph, vector<vector<int> > predecessor, int starting_vertex_index, int ending_vertex_index);

template <typename TVertex,typename TWeight>
vector<graph::Edge<TVertex, TWeight>> getCriticalPath(const graph::Graph<TVertex,TWeight>& graph, const TVertex& starting_vertex);