#pragma once

#include <iostream>
#include <iomanip>
#include <map>
#include "graph.hpp"
#include <algorithm>

using namespace std;

// 用邻接矩阵存储图
template <class TVertex,class TWeight>
class MatrixGraph :public graph::Graph<TVertex, TWeight>
{
	// 重载>>，实现输入功能
	friend istream& operator>> <>(istream& in, MatrixGraph<TVertex, TWeight>& graph);

	// 重载<<，实现打印功能
	friend ostream& operator<< <>(ostream& out, MatrixGraph<TVertex, TWeight>& graph);

private:
	TWeight** adjacency_matrix_;	// 邻接矩阵

public:
	/// <summary>
	/// 构造函数
	/// </summary>
	/// <param name="max_vertex_count">节点数上限</param>
	/// <param name="max_weight">边权值上限</param>
	MatrixGraph(int max_vertex_count, TWeight max_weight);

	/// <summary>
	/// 构造函数
	/// </summary>
	/// <param name="type">图类型</param>
	/// <param name="max_vertex_count">结点数上限</param>
	/// <param name="max_weight">边权值上限</param>
	MatrixGraph(int type, int max_vertex_count, TWeight max_weight);

	/// <summary>
	/// 构造函数
	/// </summary>
	/// <param name="max_vertex_count">结点数上限</param>
	/// <param name="max_weight">边权值上限</param>
	/// <param name="edges">边vector</param>
	/// <param name="vertices">结点vector</param>
	MatrixGraph(int max_vertex_count,
				TWeight max_weight,
				const vector<graph::Edge<TVertex,TWeight>>& edges,
				const vector<TVertex>& vertices);

	/// <summary>
	/// 构造函数
	/// </summary>
	/// <param name="type">图类型</param>
	/// <param name="max_vertex_count">结点数上限</param>
	/// <param name="max_weight">边权值上限</param>
	/// <param name="edges">边vector</param>
	/// <param name="vertices">结点vector</param>
	MatrixGraph(int type,
				int max_vertex_count,
				TWeight max_weight,
				const vector<graph::Edge<TVertex, TWeight>>& edges,
				const vector<TVertex>& vertices);

	// 拷贝构造函数 
	MatrixGraph(const MatrixGraph<TVertex, TWeight>& graph);

	~MatrixGraph();

	// 通过索引获取结点
	virtual bool getVertexByIndex(int vertex_index, TVertex& vertex) const override;
	
	// 通过结点获取边权值
	virtual bool getWeight(const TVertex& starting_vertex, const TVertex& ending_vertex, TWeight& weight) const override;
	
	// 通过始末边的索引获取边权值
	virtual bool getWeightByVertexIndex(int starting_vertex_index, int ending_vertex_index, TWeight& weight) const override;
	
	/// <summary>
	/// 获取结点的第一个相邻结点（第一个表示在vector容器中最先被找到与该结点有边的其他点）
	/// </summary>
	/// <param name="vertex">当前结点</param>
	/// <param name="first_neighbor">找到的第一个相邻结点</param>
	/// <returns></returns>
	virtual bool getFirstNeighborVertex(const TVertex& vertex, TVertex& first_neighbor) const override;
	
	/// <summary>
	/// 获取结点的下一个相邻结点
	/// </summary>
	/// <param name="vertex">当前结点</param>
	/// <param name="neighbor_vertex">当前结点的相邻结点</param>
	/// <param name="next_neighbor">当前结点的下一个相邻结点</param>
	/// <returns></returns>
	virtual bool getNextNeighborVertex(const TVertex& vertex, const TVertex& neighbor_vertex, TVertex& next_neighbor) const override;

	// 插入结点
	virtual bool insertVertex(const TVertex& vertex) override;
	
	// 插入边
	virtual bool insertEdge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight) override;
	
	// 删除结点
	virtual bool removeVertex(const TVertex& vertex) override;
	
	// 删除边
	virtual bool removeEdge(const TVertex& starting_vertex, const TVertex& ending_vertex) override;
	
	// 获取结点索引
	virtual int getVertexIndex(const TVertex& vertex) const override;

	// 打印邻接数组
	void printMatrix();

	// 重载=，实现赋值功能
	MatrixGraph<TVertex, TWeight>& operator=(const MatrixGraph<TVertex,TWeight>& m_graph);
};

template <typename TVertex, typename TWeight>
istream& operator>><>(istream& in, MatrixGraph<TVertex, TWeight>& graph)
{
	vector<int>* degrees = new vector<int>();					// 度vector（无向图使用）
	vector<int>* in_degrees = new vector<int>();				// 入度vector（有向图使用）
	vector<int>* out_degrees = new vector<int>();				// 出度vector（有向图使用）


	cout << "开始初始化图（用邻接表的形式）............" << endl;

	int type;
	cout << "请问该图是有向图还是无向图？（默认无向图，输入1代表有向图）" << endl;
	in >> type;

	int max_vertex_count = 20;
	cout << "请问该图的结点上限是多大？" << endl;
	in >> max_vertex_count;

	int max_weight;
	cout << "请问该图的边权值上限是多大？" << endl;
	in >> max_weight;

	int vertex_count = 0;	// 记录有多少个点
	vector<TVertex> vertices;
	cout << "输入点的“值”(#代表结束)" << endl;
	string s;
	do
	{
		in >> s;
		if (s == "#");
		else
		{
			if (is_same<TVertex, int>::value)
			{
				int s2i = stoi(s);
				typename vector<TVertex>::iterator itor = find(vertices.begin(),vertices.end(),s2i);
				if (itor != vertices.end())	// 容器中已有该元素
				{
					cout << "不能添加重复的点！" << endl;
					continue;
				}

				// 容器中没有该元素
				vertices.push_back(s2i);
			}
			else if (is_same<TVertex, char>::value)
			{
				char s2c = s.c_str();
				auto itor = find(vertices.begin(), vertices.end(), s2c);
				if (itor != vertices.end())	// 容器中已有该元素
				{
					cout << "不能添加重复的点！" << endl;
					continue;
				}

				// 容器中没有该元素
				vertices.push_back(s2c);
			}
			else
			{
				auto itor = find(vertices.begin(), vertices.end(), s);
				if (itor != vertices.end())	// 容器中已有该元素
				{
					cout << "不能添加重复的点！" << endl;
					continue;
				}

				// 容器中没有该元素
				vertices.push_back(s);
			}

			vertex_count++;
		}
	} while (s != "#");


	int edge_count = 0;	// 记录有多少条边
	vector<graph::Edge<TVertex,TWeight>> edges;
	cout << "输入边的“起始点、终点、权值”(#代表结束)" << endl;
	string s;
	int starting_vertex_index, ending_vertex_index;
	TWeight weight;
	do
	{
		graph::Edge<TVertex, TWeight> edge;

		cout << "开始输入起始点：" << endl;
		in >> s;
		if (s == "#")
			break;
		if (is_same<TVertex, int>::value)
		{
			int s2i = stoi(s);
			typename vector<TVertex>::iterator itor = find(vertices.begin(), vertices.end(), s2i);
			
			if (itor == vertices.end())
			{
				cout << "不存在以该点为起点的边！" << endl;
				continue;
			}

			starting_vertex_index = distance(vertices.begin(), itor);

			edge.starting_vertex = s2i;
		}

		else if (is_same<TVertex, char>::value)
		{
			int s2c = s.c_str();
			auto itor = find(vertices.begin(), vertices.end(), s2c);

			if (itor == vertices.end())
			{
				cout << "不存在以该点为起点的边！" << endl;
				continue;
			}

			starting_vertex_index = distance(vertices.begin(), itor);

			edge.starting_vertex = s2c;
		}
		else
		{
			auto itor = find(vertices.begin(), vertices.end(), s);

			if (itor == vertices.end())
			{
				cout << "不存在以该点为起点的边！" << endl;
				continue;
			}

			starting_vertex_index = distance(vertices.begin(), itor);

			edge.starting_vertex = s;
		}
		
		cout << "开始输入终点：" << endl;
		in >> s;
		if (s == "#")
			break;
		if (is_same<TVertex, int>::value)
		{
			int s2i = stoi(s);
			typename vector<TVertex>::iterator itor = find(vertices.begin(), vertices.end(), s2i);

			if (itor == vertices.end())
			{
				cout << "不存在以该点为终点的边！" << endl;
				continue;
			}

			ending_vertex_index = distance(vertices.begin(), itor);

			edge.ending_vertex = s2i;
		}
		else if (is_same<TVertex, char>::value)
		{
			int s2c = s.c_str();
			auto itor = find(vertices.begin(), vertices.end(), s2c);

			if (itor == vertices.end())
			{
				cout << "不存在以该点为终点的边！" << endl;
				continue;
			}

			ending_vertex_index = distance(vertices.begin(), itor);

			edge.ending_vertex = s2c;
		}
		else
		{
			auto itor = find(vertices.begin(), vertices.end(), s);

			if (itor == vertices.end())
			{
				cout << "不存在以该点为终点的边！" << endl;
				continue;
			}

			ending_vertex_index = distance(vertices.begin(), itor);

			edge.ending_vertex = s;
		}

		cout << "开始输入该边的权值" << endl;
		in >> weight;
		edge.weight = weight;

		typename vector<graph::Edge<TVertex, TWeight>>::iterator itor = find(edges.begin(), edges.end(), edge);
		// auto itor = find(edges.begin(), edges.end(), edge);

		// 已有 starting_vertex --> ending_vertex 的边
		if (itor != edges.end())
			continue;
		
		// 调整该边对应两个点的度
		//		如果是无向图
		if (type != 1)
		{
			(*degrees)[starting_vertex_index]++;
			(*degrees)[ending_vertex_index]++;
		}
		else
		{
			(*out_degrees)[starting_vertex_index]++;
			(*in_degrees)[ending_vertex_index]++;
		}
		
		// 注意到这里edge是局部变量，函数执行完成后会被系统自动回收（随方法栈弹出），这里push的是edge在另外一块不会被回收的内存上的副本
		edges.push_back(edge);
		edge_count++;
	} while (s != "#");

	if (type == graph::Graph<TVertex, TWeight>::DIRECTED) // 有向图
	{
		MatrixGraph<TVertex, TWeight> new_graph(type, max_vertex_count, max_weight, edges, vertices);
		new_graph.vertex_count_ = vertex_count;
		new_graph.edge_count_ = edge_count;
		new_graph.in_degrees_ = *in_degrees;
		new_graph.out_degrees_ = *out_degrees;

		graph = new_graph;
	}		
	else // 无向图
	{
		MatrixGraph<TVertex, TWeight> new_graph(max_vertex_count, max_weight, edges, vertices);
		new_graph.vertex_count_ = vertex_count;
		new_graph.edge_count_ = edge_count;
		new_graph.degrees_ = *degrees;

		graph = new_graph;
	}


	return in;
}

template <typename TVertex, typename TWeight>
ostream& operator<<<>(ostream& out, MatrixGraph<TVertex, TWeight>& graph)
{
	// 打印图的各种信息
	out << "# 基本信息 #" << endl;

	// 打印结点信息
	out << "结点信息：" << graph.vertexCount() << endl;
	for (int i = 0; i < graph.vertexCount(); i++)
	{
		TVertex vertex;
		graph.getVertexByIndex(i,vertex);
		out << vertex << " ";
	}
	cout << endl;

	// 打印边信息
	out << "边数量：" << graph.edgeCount() << endl;
	for (int i = 0; i < graph.edgeCount(); i++)
	{
		graph::Edge<TVertex, TWeight> edge = graph.getEdge(i);
		out << "(" << edge.starting_vertex << "，" << edge.ending_vertex << ")，权重：" << edge.weight << endl;
	}
	cout << endl;

	// 打印邻接表信息
	out << "# 邻接表信息 #" << endl;
	for (int row_index = 0; row_index < graph.vertexCount(); row_index++)
	{
		for (int col_index = 0; col_index < graph.vertexCount(); col_index++)
		{
			TWeight weight;
			bool res = graph.getWeightByVertexIndex(row_index,col_index,weight);
			if (!res)
				continue;
			out << "[" << row_index << "][" << col_index << "]：" << weight << endl;
		}
	}

	return out;
}

template<class TVertex, class TWeight>
inline MatrixGraph<TVertex, TWeight>::MatrixGraph(int max_vertex_count, TWeight max_weight)
{
	// 设置部分成员变量
	this->type_ = graph::Graph<TVertex, TWeight>::UNDIRECTED;	// 默认无向图

	this->max_weight_ = max_weight;
	this->max_vertex_count_ = max_vertex_count;

	this->vertex_count_ = 0;
	this->edge_count_ = 0;

	// 设置邻接矩阵，初始化二维矩阵
	//		分配邻接矩阵内存
	this->adjacency_matrix_ = new TWeight * [this->max_vertex_count_];
	if (!this->adjacency_matrix_)
		throw bad_alloc();

	//		分配邻接矩阵每行的内存，并初始化
	for (int row = 0; row < this->max_vertex_count_; row++)
	{
		this->adjacency_matrix_[row] = new TWeight[this->max_vertex_count_];
		if (!this->adjacency_matrix_[row])
			throw bad_alloc();

		for (int col = 0; col < this->max_vertex_count_; col++)
		{
			// 二维矩阵赋初值
			this->adjacency_matrix_[row][col] = TWeight();
		}
	}
}

template<class TVertex, class TWeight>
inline MatrixGraph<TVertex, TWeight>::MatrixGraph(int type, int max_vertex_count, TWeight max_weight)
{
	// 设置部分成员变量
	this->type_ = type;

	this->max_weight_ = max_weight;
	this->max_vertex_count_ = max_vertex_count;

	this->vertex_count_ = 0;
	this->edge_count_ = 0;

	// 设置邻接矩阵，初始化二维矩阵
	//		分配邻接矩阵内存
	this->adjacency_matrix_ = new TWeight * [this->max_vertex_count_];
	if (!this->adjacency_matrix_)
		throw bad_alloc();

	//		分配邻接矩阵每行的内存，并初始化
	for (int row = 0; row < this->max_vertex_count_; row++)
	{
		this->adjacency_matrix_[row] = new TWeight[this->max_vertex_count_];
		if (!this->adjacency_matrix_[row])
			throw bad_alloc();

		for (int col = 0; col < this->max_vertex_count_; col++)
		{
			// 二维矩阵赋初值
			this->adjacency_matrix_[row][col] = TWeight();
		}
	}
}

template<class TVertex, class TWeight>
inline MatrixGraph<TVertex, TWeight>::MatrixGraph(int max_vertex_count, TWeight max_weight, const vector<graph::Edge<TVertex, TWeight>>& edges, const vector<TVertex>& vertices)
{
	// 设置部分成员变量
	this->type_ = graph::Graph<TVertex, TWeight>::UNDIRECTED;	// 默认无向图

	this->max_weight_ = max_weight;
	this->max_vertex_count_ = max_vertex_count;

	this->vertex_count_ = 0;
	this->edge_count_ = 0;

	// 设置邻接矩阵，初始化二维矩阵
	//		分配邻接矩阵内存
	this->adjacency_matrix_ = new TWeight * [this->max_vertex_count_];
	if (!this->adjacency_matrix_)
		throw bad_alloc();

	//		分配邻接矩阵每行的内存，并初始化
	for (int row = 0; row < this->max_vertex_count_; row++)
	{
		this->adjacency_matrix_[row] = new TWeight[this->max_vertex_count_];
		if (!this->adjacency_matrix_[row])
			throw bad_alloc();

		for (int col = 0; col < this->max_vertex_count_; col++)
		{
			// 二维矩阵赋初值
			this->adjacency_matrix_[row][col] = TWeight();
		}
	}

	// 插入结点和边
	//		插入vertices
	for (int i = 0; i < vertices.size(); i++)
		this->insertVertex(vertices[i]);

	//		将edges插入
	for (int i = 0; i < edges.size(); i++)
		this->insertEdge(edges[i].starting_index,edges[i].ending_vertex,edges[i].weight);
}

template<class TVertex, class TWeight>
inline MatrixGraph<TVertex, TWeight>::MatrixGraph(int type, int max_vertex_count, TWeight max_weight, const vector<graph::Edge<TVertex, TWeight>>& edges, const vector<TVertex>& vertices)
{
	// 设置部分成员变量
	this->type_ = type;

	this->max_weight_ = max_weight;
	this->max_vertex_count_ = max_vertex_count;

	this->vertex_count_ = 0;
	this->edge_count_ = 0;

	// 设置邻接矩阵，初始化二维矩阵
	//		分配邻接矩阵内存
	this->adjacency_matrix_ = new TWeight * [this->max_vertex_count_];
	if (!this->adjacency_matrix_)
		throw bad_alloc();

	//		分配邻接矩阵每行的内存，并初始化
	for (int row = 0; row < this->max_vertex_count_; row++)
	{
		this->adjacency_matrix_[row] = new TWeight[this->max_vertex_count_];
		if (!this->adjacency_matrix_[row])
			throw bad_alloc();

		for (int col = 0; col < this->max_vertex_count_; col++)
		{
			// 二维矩阵赋初值
			this->adjacency_matrix_[row][col] = TWeight();
		}
	}

	// 插入结点和边
	//		插入vertices
	for (int i = 0; i < vertices.size(); i++)
		this->insertVertex(vertices[i]);

	//		将edges插入
	for (int i = 0; i < edges.size(); i++)
		this->insertEdge(edges[i].starting_index, edges[i].ending_vertex, edges[i].weight);
}

template<class TVertex, class TWeight>
inline MatrixGraph<TVertex, TWeight>::MatrixGraph(const MatrixGraph<TVertex, TWeight>& graph)
{
	this->max_vertex_count_ = graph.maxVertexCount();
	this->max_weight_ = graph.maxWeight();
	this->edge_count_ = graph.edgeCount();
	this->vertex_count_ = graph.vertexCount();
	this->type_ = graph.type();
	
	this->vertices_ = graph.vertices();
	this->degrees_ = graph.degrees_;
	this->in_degrees_ = graph.in_degrees_;
	this->out_degrees_ = graph.out_degrees_;
	this->edges_ = graph.edges();
	this->adjacency_matrix_ = graph.adjacency_matrix_;
}

template<class TVertex, class TWeight>
inline MatrixGraph<TVertex, TWeight>::~MatrixGraph()
{
	for (int row = 0; row < this->vertex_count_; row++)
		delete[] this->adjacency_matrix_[row]; // 先释放数组数组的每一个元素内存

	// 回收数组数组的内存
	delete[] this->adjacency_matrix_;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::getVertexByIndex(int vertex_index, TVertex& vertex) const
{
	// 判断合法性
	if (vertex_index < 0 && vertex_index >= this->vertex_count_)
		return false;

	// 获取结点
	vertex = this->vertices_[vertex_index];

	// 返回结果
	return true;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::getWeight(const TVertex& starting_vertex, const TVertex& ending_vertex, TWeight& weight) const
{
	// 判断合法性
	int starting_vertex_index = this->getVertexIndex(starting_vertex);
	int ending_vertex_index = this->getVertexIndex(ending_vertex);
	
	if (starting_vertex_index < 0 || ending_vertex_index < 0 
		|| starting_vertex_index == ending_vertex_index
		|| this->adjacency_matrix_[starting_vertex_index][ending_vertex_index] == TWeight() // 边权值为“空”
		)
		return false;

	// 获取边权值
	bool res = this->getWeightByVertexIndex(starting_vertex_index,ending_vertex_index,weight);

	if (!res)
		return true;

	return false;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::getWeightByVertexIndex(int starting_vertex_index, int ending_vertex_index, TWeight& weight) const
{
	if (starting_vertex_index < 0 || ending_vertex_index < 0
		|| starting_vertex_index == ending_vertex_index
		|| this->adjacency_matrix_[starting_vertex_index][ending_vertex_index] == TWeight() // 边权值为“空”
		)
		return false;

	weight = this->adjacency_matrix_[starting_vertex_index][ending_vertex_index];
	return true;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::getFirstNeighborVertex(const TVertex& vertex, TVertex& first_neighbor) const
{
	// 判断合法性
	int vertex_index = this->getVertexIndex(vertex);
	// 图目前没有当前点
	if (vertex_index < 0)
		return false;

	// 遍历结点找到第一个相邻结点
	for (int i = 0; i < this->vertex_count_; i++)
	{
		TWeight weight;
		TVertex cur_vertex;

		bool res = this->getVertexByIndex(i,cur_vertex);

		// 判断合法性
		if (!res)
			continue;

		res = this->getWeight(vertex,cur_vertex,weight);

		if (res)
		{
			first_neighbor = cur_vertex;
			return true;
		}
	}
	return true;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::getNextNeighborVertex(const TVertex& vertex, const TVertex& neighbor_vertex, TVertex& next_neighbor) const
{
	// 判断合法性
	int vertex_index = this->getVertexIndex(vertex);
	int neighbor_vertex_index = this->getVertexIndex(neighbor_vertex);

	if (vertex_index < 0 || neighbor_vertex_index < 0)
		return false;

	// 遍历结点找到下一个相邻结点
	for (int i = neighbor_vertex_index + 1; i < this->vertex_count_; i++)
	{
		TWeight weight;
		TVertex cur_vertex;

		bool res = this->getVertexByIndex(i,cur_vertex);
		
		// 判断合法性
		if (!res)
			continue;

		res = this->getWeight(vertex,cur_vertex,weight);

		if (res)
		{
			next_neighbor = cur_vertex;
			return true;
		}
	}
	return false;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::insertVertex(const TVertex& vertex)
{
	// 判断合法性，超出该图能存储的点上限
	if (this->vertex_count_ >= this->max_vertex_count_)
		return false;

	// 执行插入
	this->vertices_.push_back(vertex);
	
	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)
		this->degrees_.push_back(0);
	else
	{
		this->in_degrees_.push_back(0);
		this->out_degrees_.push_back(0);
	}

	// vector容器：vertices、degrees_、in_degrees_、out_degrees_对应位置元素是一一对应的

	this->vertex_count_++;

	return true;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::insertEdge(const TVertex& starting_vertex, const TVertex& ending_vertex, const TWeight& weight)
{
	// 合法性检查和相关处理

	// 结点检查和相关处理
	// 如果在当前点集中没找到相应点，方法返回负数
	int starting_vertex_index = this->getVertexIndex(starting_vertex);
	int ending_vertex_index = this->getVertexIndex(ending_vertex);

	if (starting_vertex_index < 0)
	{
		bool res = this->insertVertex(starting_vertex);
		if (!res)
			return false;

		// 获取新插入端点在vector里的索引
		starting_vertex_index = this->getVertexIndex(starting_vertex);
	}

	if (ending_vertex_index < 0)
	{
		bool res = this->insertVertex(ending_vertex);
		if (!res)
			return false;

		// 获取新插入端点在vector里的索引
		ending_vertex_index = this->getVertexIndex(ending_vertex);
	}

	// 插入失败和起始点是同一个的情况
	if (starting_vertex_index < 0 || ending_vertex_index < 0
		|| starting_vertex_index == ending_vertex_index)
		return false;

	// 边检查
	for (int i = 0; i < this->edges_.size(); i++)
	{
		// 如果是无向图
		if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)
		{
			if ((this->edges_[i].starting_vertex == starting_vertex &&
				this->edges_[i].ending_vertex == ending_vertex)
				||
				(this->edges_[i].starting_vertex == ending_vertex &&
					this->edges_[i].ending_vertex == starting_vertex))
				// 已存在相应的边，插入新边失败
				return false;
		}
		else
		{
			// 如果是有向图
			if (this->edges_[i].starting_vertex == starting_vertex &&
				this->edges_[i].ending_vertex == ending_vertex)
				// 已存在相应的边，插入新边失败
				return false;
		}
	}

	// 邻接矩阵检查
	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)	// 无向图
	{
		if (this->adjacency_matrix_[starting_vertex_index][ending_vertex_index] != TWeight()
			|| this->adjacency_matrix_[ending_vertex_index][starting_vertex_index] != TWeight())
			return false;

	}
	else if (this->type_ == graph::Graph<TVertex, TWeight>::DIRECTED)	// 有向图
	{
		if (this->adjacency_matrix_[starting_vertex_index][ending_vertex_index] != TWeight())
			return false;
	}

	// 执行插入
	//		边插入
	this->adjacency_matrix_[starting_vertex_index][ending_vertex_index] = weight;
	graph::Edge<TVertex, TWeight> edge(starting_vertex,ending_vertex,weight);
	this->edges_.push_back(edge);
	//			如果是无向图，邻接矩阵是对称矩阵，要再在邻接矩阵中插入一条数据
	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)
		this->adjacency_matrix_[ending_vertex_index][starting_vertex_index] = weight;

	//		边数+1
	this->edge_count_++;

	// 结点度处理
	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)	// 无向图
	{
		this->degrees_[starting_vertex_index]++;
		this->degrees_[ending_vertex_index]++;
	}
	else // 有向图
	{
		this->in_degrees_[ending_vertex_index]++;
		this->out_degrees_[starting_vertex_index]++;
	}

	// 退出函数
	return true;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::removeVertex(const TVertex& vertex)
{
	// 判断删除合理性
	// 找到结点在vector中的下标
	int vertex_index = this->getVertexIndex(vertex);
	if (vertex_index < 0 || vertex_index >= this->vertex_count_)
		return false;

	// 邻接矩阵执行删除，操作adjacency_matrix_
	//		用索引vertex_count_ - 1的结点，替换待删除结点vertex
	for (int i = 0; i < this->vertex_count_; i++)
	{
		if (i == vertex_index)
			continue;

		TWeight weight;

		bool res = this->getWeightByVertexIndex(vertex_index,i,weight);

		if (res)	// 起始顶点是vertex和索引下标为i的顶点有边
		{
			if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)	// 无向图
				this->degrees_[i]--; // 与vertex结点相连的结点度-1
			else // 有向图
			{
				this->in_degrees_[i]--;	// 结点i入度-1
			}
		}

		res = this->getWeightByVertexIndex(i,vertex_index,weight);
		if (res)
		{
			if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED);	// 无向图
				// 上面已经减过了
			else // 有向图
			{
				this->out_degrees_[i]--;	// 结点i出度-1
			}
		}

		// 邻接矩阵“缩小一圈”
		this->adjacency_matrix_[vertex_index][i] = this->adjacency_matrix_[this->vertex_count_ - 1][i];
		this->adjacency_matrix_[i][vertex_index] = this->adjacency_matrix_[i][this->vertex_count_ - 1];
	}

	// 替换待删除结点度容器中对应的元素，操作degrees_、in_degrees_、out_degrees_
	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)
	{
		this->degrees_[vertex_index] = this->degrees_[this->vertex_count_ - 1];
		//	从 degrees_ 容器中删除最后一个元素
		this->degrees_.erase(this->degrees_.begin()+this->vertex_count_ - 1);
	}
	else 
	{
		this->in_degrees_[vertex_index] = this->in_degrees_[this->vertex_count_ - 1];
		this->in_degrees_.erase(this->in_degrees_.begin() + this->vertex_count_ - 1);

		this->out_degrees_[vertex_index] = this->out_degrees_[this->vertex_count_ - 1];
		this->out_degrees_.erase(this->out_degrees_.begin() + this->vertex_count_ - 1);
	}

	// 删除与结点vertex关联的边，操作edges_
	for (typename vector<graph::Edge<TVertex, TWeight>>::iterator iter = this->edges_.begin(); iter != this->edges_.end();)
	{
		if (iter->ending_vertex == vertex || iter->starting_vertex == vertex)
		{
			// this->edges_.erase(iter) 返回的是指向被删除元素之后的下一个元素的迭代器。因此，将返回值赋值给 iter 是合适的。
			iter = this->edges_.erase(iter);
			this->edge_count_--;
		}
		else
			iter++;
	}

	// 删除结点，操作vertices_
	this->vertices_[vertex_index] = this->vertices_[this->vertex_count_ - 1];
	this->vertices_.erase(this->vertices_.begin() + this->vertex_count_ - 1);

	this->vertex_count_--; // 结点数-1

	return true;
}

template<class TVertex, class TWeight>
inline bool MatrixGraph<TVertex, TWeight>::removeEdge(const TVertex& starting_vertex, const TVertex& ending_vertex)
{
	// 合法性检查

	int starting_vertex_index = this->getVertexIndex(starting_vertex);
	int ending_vertex_index = this->getVertexIndex(ending_vertex);
	if (starting_vertex_index < 0 || ending_vertex_index < 0)
		return false;

	// 检查vertices_
	int target_edge_index = -1;
	if (this->type_ == graph::Graph<TVertex, TWeight>::DIRECTED)	// 有向图
	{
		for (int i = 0; i < this->edges_.size(); i++)
		{
			if (this->edges_[i].starting_vertex == starting_vertex
				&& this->edges_[i].ending_vertex == ending_vertex)
			{
				target_edge_index = i;
				break;
			}
		}
	}
	else // 无向图
	{
		for (int i = 0; i < this->edges_.size(); i++)
		{
			if ((this->edges_[i].starting_vertex == starting_vertex && this->edges_[i].ending_vertex == ending_vertex) ||
				(this->edges_[i].starting_vertex == ending_vertex && this->edges_[i].ending_vertex == starting_vertex))
			{
				target_edge_index = i;
				break;
			}
		}
	}

	if (target_edge_index == -1)	// 没找到对应的边
		return false;

	// 检查邻接矩阵
	TWeight weight;
	bool res = this->getWeight(starting_vertex,ending_vertex,weight);
	if (!res)
		return false;

	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)
	{
		res = this->getWeight(ending_vertex,starting_vertex,weight);
		if (!res)
			return false;
	}

	// 在edges和邻接矩阵做删除
	// 有向图和无向图：起点---->终点方向删除
	this->adjacency_matrix_[starting_vertex_index][ending_vertex_index] = TWeight();
	this->edges_.erase(this->edges_.begin() + target_edge_index);

	// 无向图还要删除终点---->起点方向
	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRECTED)
		this->adjacency_matrix_[ending_vertex_index][starting_vertex_index] = TWeight();

	// 边总数-1
	this->edge_count_--;

	// 度容器调整
	if (this->type_ == graph::Graph<TVertex, TWeight>::UNDIRCTED)	// 无向图起始顶点度各减1
	{
		// 起点度-1
		this->degrees_[starting_vertex_index]--;
		// 终点度-1
		this->degrees_[ending_vertex_index]--;
	}
	else // 有向图
	{
		// 终点入度-1
		this->in_degrees_[ending_vertex_index]--;
		// 起点出度-1
		this->out_degrees_[starting_vertex_index]--;
	}

	return true;
}

template<class TVertex, class TWeight>
inline int MatrixGraph<TVertex, TWeight>::getVertexIndex(const TVertex& vertex) const
{
	for (int i = 0; i < this->vertex_count_; i++)
	{
		if (this->vertices_[i] == vertex)
			return i;
	}
	return -1;
}

template<class TVertex, class TWeight>
inline void MatrixGraph<TVertex, TWeight>::printMatrix()
{
	for (int row_index = 0; row_index < this->vertex_count_; row_index++)
	{
		for (int col_index = 0; col_index < this->vertex_count_; col_index++)
			// setw()用于设置输出字段的宽度
			cout << setw(5) << this->adjacency_matrix_[row_index][col_index] << " ";
		cout << endl;
	}
}

template<class TVertex, class TWeight>
inline MatrixGraph<TVertex, TWeight>& MatrixGraph<TVertex, TWeight>::operator=(const MatrixGraph<TVertex, TWeight>& graph)
{
	this->max_vertex_count_ = graph.maxVertexCount();
	this->max_weight_ = graph.maxWeight();
	this->edge_count_ = graph.edgeCount();
	this->vertex_count_ = graph.vertexCount();
	this->type_ = graph.type();

	this->vertices_ = *(new vector<TVertex>(graph.vertices_));
	this->degrees_ = *(new vector<int>(graph.degrees_));
	this->in_degrees_ = *(new vector<int>(graph.in_degrees_));
	this->out_degrees_ = *(new vector<int>(graph.out_degrees_));
	this->edges_ = *(new vector<graph::Edge<TVertex, TWeight>>(graph.edges_));
	
	// 深复制（深拷贝）二维数组
	this->adjacency_matrix_ = new TWeight * [this->max_vertex_count_];
	if (!this->adjacency_matrix_)
		throw bad_alloc();

	for (int row_index = 0; row_index < this->max_vertex_count_; row_index++)
	{
		this->adjacency_matrix_[row_index] = new TWeight[this->max_vertex_count_];
		if (!this->adjacency_matrix_[row_index])
			throw bad_alloc();

		for (int col_index = 0; col_index < this->max_vertex_count_; col_index++)
		{
			if (col_index < this->vertex_count_)
				this->adjacency_matrix_[row_index][col_index] = graph.adjacency_matrix_[row_index][col_index];
			else
			{
				this->adjacency_matrix_[row_index][col_index] = TWeight();
			}
		}
	}

	return *this;
}