#include<iostream>
#include<vector>
#include<fstream>
#include<string>
using namespace std;
const int maxpoint = 1e+7;
const int maxedge = 1e+6;
struct pro
{
	int e;//文本属性个数
	string all;//存储文本属性用","来分隔
}property[maxpoint];
struct e
{
	int v, next;//无权值，指向的点，下一条边的地址
}edge[maxedge];
bool isroot[maxpoint];
int head[maxpoint];
int hcnt,rootnum;
vector<int> pa;
vector<int> split(const string& str, const string& pattern)
{
	vector<int> res;
	if (str == "")
		return res;
	//在字符串末尾也加入分隔符，方便截取最后一段
	string strs = str + pattern;
	size_t pos = strs.find(pattern);

	while (pos != strs.npos)
	{
		string temp = strs.substr(0, pos);
		if (temp == "")
			return res;
		res.push_back(stoi(temp));
		//去掉已分割的字符串,在剩下的字符串中进行分割
		strs = strs.substr(pos + 1, strs.size());
		pos = strs.find(pattern);
	}
	return res;
}//字符串分割所用到的
void init() {
	hcnt = 0;
	rootnum = 0;
	memset(isroot,0, maxpoint);
	memset(head, -1, maxpoint);
}
void addedge(int u,int v)
{
	edge[hcnt].v = v;
	edge[hcnt].next = head[u];
	head[u] = hcnt++;
}

/*
思路：比较

*/

int isparent(int p1, int p2)
{
	return 1;
	//返回1明p1支配p2
	//返回0说明互不支配
	//返回-1说明p2支配p1
}
int findparent(int n) {//n为目标集的点数量
	//遍历并查集的祖宗点
	//记录下支配的点
	//记录下被支配的点
	//将支配的点的祖宗都设为该点
	//初始化
	pa.clear();
	pa.push_back(1);//将第一个点加入并查集
	for (int i = 0; i < n; i++)//对点集进行遍历
	{
		int isop = 0;
		int isfirst = 1;
		vector<int>::iterator it = pa.begin();
		for (; it != pa.end();it++)
		{
			int temp = isparent(i, *it);
			if (temp == 1)
			{
				if (isfirst == 1)
				{
					*it = i;
					isfirst = 0;
				}
				else {
					pa.erase(it);
					it--;
				}
				isop = 1;
			}
			else if (temp == -1)
			{
				isop = 1;
				break;
			}
		}
		if (isop == 0)//如果都没有支配或者被支配，加入新的祖宗集
			pa.push_back(i);
	}
	return pa.size();
}
void processpoint(string o) {
	int index = o.find_first_of(":");
	int srcpoint = stoi(o.substr(0, index));
	property[srcpoint].all = o.substr(index + 1, o.length());
}
void processroot(string o) {
	int index = o.find_first_of(":");
	int srcpoint = stoi(o.substr(0, index));
	isroot[srcpoint]=true;
}
void processedge(string o)
{
	int index = o.find_first_of(" ");
	int srcpoint = stoi(o.substr(0, index));
	string edg = o.substr(index + 1, o.length());
	vector<int> pointto = split(edg, ",");
	for (int i = 0; i < pointto.size(); i++)
		addedge(srcpoint, pointto[i]);
}
int n;
void getedge(string path) {
	fstream file(path);//读取文件
	n = 1;
	if (file.is_open())
	{
		while (!file.eof())
		{
			string got;
			getline(file, got);
			if (!got.empty())
			{	cout << "正在读取第"<<n++ <<"行"<< endl;
				processedge(got);
			}
		}
	}
}
void gettext(string path)
{
	fstream file(path);//读取文件
	n = 1;
	if (file.is_open())
	{
		while (!file.eof())
		{
			string got;
			getline(file, got);
			if (!got.empty())
			{
				cout << "正在读取第" << n++ << "行" << endl;
				processpoint(got);
			}
		}
	}
}
void getroot(string path)
{
	fstream file(path);//读取文件
	n = 1;
	if (file.is_open())
	{
		while (!file.eof())
		{
			string got;
			getline(file, got);
			if (!got.empty())
			{
				cout << "正在读取第" << n++ << "行" << endl;
				processroot(got);
			}
		}
	}

}
int main()
{
	init();
	cout << "开始构造边" << endl;
	getedge("G:/作业/算法设计作业/大作业/Yago_small/edge.txt");
	cout << "开始构造属性" << endl;
	gettext("G:/作业/算法设计作业/大作业/Yago_small/node_keywords.txt");
	cout << "开始构造根节点数组" << endl;
	getroot("G:/作业/算法设计作业/大作业/placeid2coordYagoVB.txt");
	system("pause");
}