#include "function.h"
#include <queue>
#include <map>
using namespace std;


void Implement::addEdge(const int label_1, const int label_2 , const int weight)
{
	bool f1 = 0, f2 = 0;
	for (auto i = VertexArr.begin(); i != VertexArr.end(); i++) {
		if (i->label == label_1) {
			for (auto j : i->neighbors) {
				if (j.label == label_2)return;
			}
			i->neighbors.push_back(Neighbor(label_2, weight));
			f1 = 1;
		} else if (i->label == label_2) {
			for (auto j : i->neighbors) {
				if (j.label == label_1)return;
			}
			i->neighbors.push_back(Neighbor(label_1, weight));
			f2 = 1;
		}
	}
	if (!f1) {
		VertexArr.push_back(Vertex(label_1));
		if(label_1==label_2)return;
		VertexArr.back().neighbors.push_back(Neighbor(label_2, weight));
	}
	if (!f2) {
		VertexArr.push_back(Vertex(label_2));
		VertexArr.back().neighbors.push_back(Neighbor(label_1, weight));
	}
}
void Implement::deleteEdge(const int label_1, const int label_2)
{
	if(label_2==label_1)return;
	for (auto i = VertexArr.begin(); i != VertexArr.end(); i++) {
		if (i->label == label_1) {
			for (auto it = i->neighbors.begin(); it != i->neighbors.end(); it++) {
				if (it->label == label_2) {
					i->neighbors.erase(it);
					break;
				}
			}
		} else if (i->label == label_2) {
			for (auto it = i->neighbors.begin(); it != i->neighbors.end(); it++) {
				if (it->label == label_1) {
					i->neighbors.erase(it);
					break;
				}
			}
		}
	}
}
void Implement::deleteVertex(const int label)
{
	int length;
	map<int, bool> m;
	for (auto it = VertexArr.begin(); it != VertexArr.end(); it++) {
		if (it->label == label) {
			length = it->neighbors.size();
			for (auto i : it->neighbors)m[i.label] = 1;
			VertexArr.erase(it);
			break;
		}
	}
	for (auto i = VertexArr.begin(); i != VertexArr.end(); i++) {
		if (m[i->label]) {
			for (auto it = i->neighbors.begin(); it != i->neighbors.end(); it++) {
				if (it->label == label) {
					i->neighbors.erase(it);
					break;
				}
			}
		}
	}
}
int Implement::degree(const int label)
{
	for (auto v : VertexArr) {
		if (v.label == label) {
			return v.neighbors.size();
		}
	}
	return 0;
}
bool Implement::isExistPath(const int label_1, const int label_2)
{
	queue<int> s;
	map<int, bool> m;
	s.push(label_1);
	while (!s.empty()) {
		int a = s.front();
		s.pop();
		for (auto i : VertexArr) {
			if (i.label == a) {
				if (label_1 == label_2)return 1;
				for (auto j : i.neighbors) {
					if (j.label == label_2)return 1;
					else if (!m[j.label]) s.push(j.label), m[j.label] = 1;
				}
				break;
			}
		}
	}
	return 0;
}
void Implement::deleteGraph()
{
	VertexArr.clear();
}
int Implement::number_of_component()
{
	if (VertexArr.empty())return 0;
	map<int, bool> m;
	int total = 0;
	for (auto i : VertexArr) {
		if (!m[i.label]) {
			total++;
			m[i.label] = 1;
			queue<int> s;
			s.push(i.label);
			while (!s.empty()) {
				int a = s.front();
				s.pop();
				for (auto j : VertexArr) {
					if (j.label == a) {
						for (auto k : j.neighbors) {
							if (!m[k.label]) {
								m[k.label] = 1;
								s.push(k.label);
							}
						}
						break;
					}
				}
			}
		}
	}
	return total;
}