#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<queue>
#include <time.h>
using namespace std;
const int maxpoint = 1e+7;
const int maxedge = 1e+6;
const int inf = 99999999;
struct e
{
int v, next;//无权值,指向的点,下一条边的地址
}edge[maxedge];
vector<int> pa;
string property[maxpoint];
bool isroot[maxpoint], visit[maxpoint];
int head[maxpoint], dep[maxpoint],chaxun[20];//查询数组
int hcnt,N;//N为查询属性的个数
vector<int> dis[maxpoint];
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;
memset(isroot,0, sizeof isroot);
memset(head, -1, sizeof head);
memset(dep, -1, sizeof dep);
memset(visit, -1, sizeof visit);
}
void addedge(int u,int v)
{
edge[hcnt].v = v;
edge[hcnt].next = head[u];
head[u] = hcnt++;
}
int isparent(int p1, int p2)
{
int t1 = 0, t2 = 0, equ = 0;
for (int i = 0; i < N; i++)
{
if (dis[p1][i] > dis[p2][i])
t1++;
if (dis[p1][i] > dis[p2][i])
t2++;
else {
equ++;
t1++;
t2++;
}
}
if (t1 == N && equ != N)
return 1;
if (t2 == N && equ != N)
return -1;
else return 0;
}
void bfs(int root) {
queue<int> Q;
Q.push(root);
visit[root] = 1;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
vector<int> prop = split(property[u],",");//进行分割
for(int j=0;j<N;j++)
for (int i = 0; i < prop.size(); i++)
if (prop[i]==chaxun[j]&&dep[u]<dis[root][j])
dis[root][j] = dep[u];
int flag = 0;
for (int i = 0; i < N; i++)//检测还有没有必要继续往深处走
if (dis[root][i] == inf)
flag = 1;
if (flag == 1)//如果需要往深处走
{
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if (visit[v]==0)
{
dep[v] = dep[u]+1;
Q.push(v);
visit[v] = 1;
}
}
}
}
}
void bfsentry() {
pa.clear();
for (int i = 0; i < maxpoint; i++)
{
if (isroot[i])
{
dis[i].resize(N);//建立dis数组
for (int j = 0; j < N; j++)
dis[i][j] = inf;
dep[i] = 0;
bfs(i);
int flag = 1;
for (int j = 0; j < N; j++)
if (dis[i][j] == inf)
{
flag = 0;
break;
}
if (flag == 1)
{
if (pa.size() == 0)
pa.push_back(i);
else {
int opflag = 0, firstflag = 1;
vector<int>::iterator it = pa.begin();
for (; it != pa.end(); it++)
{
int temp = isparent(i, *it);
if (temp == 1)
{
if (firstflag == 1)
{
*it = i;
opflag = 0;
}
else {
pa.erase(it);
it--;
}
opflag = 1;
}
else if (temp == -1)
{
opflag = 1;
break;
}
}
if (opflag == 0)//如果都没有支配或者被支配,加入新的祖宗集
pa.push_back(i);
}
}
dis[i].clear();
}
}
}
void processpoint(string o) {
int index = o.find_first_of(":");
int srcpoint = stoi(o.substr(0, index));
property[srcpoint] = 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]);
}
void getedge(string path) {
fstream file(path);//读取文件
if (file.is_open())
{
while (!file.eof())
{
string got;
getline(file, got);
if (!got.empty())
{
processedge(got);
}
}
}
}
void gettext(string path)
{
fstream file(path);//读取文件
if (file.is_open())
{
while (!file.eof())
{
string got;
getline(file, got);
if (!got.empty())
{
processpoint(got);
}
}
}
}
void getroot(string path)
{
fstream file(path);//读取文件
if (file.is_open())
{
while (!file.eof())
{
string got;
getline(file, got);
if (!got.empty())
{
processroot(got);
}
}
}
}
int main()
{
cout << "正在初始化" << endl;
init();
cout << "开始构造边" << endl;
clock_t t1 =clock();
getedge("G:/作业/算法设计作业/大作业/Yago/edge.txt");
cout << "开始构造属性" << endl;
gettext("G:/作业/算法设计作业/大作业/Yago/node_keywords.txt");
cout << "开始构造根节点数组" << endl;
getroot("G:/作业/算法设计作业/大作业/placeid2coordYagoVB.txt");
clock_t t2 = clock();
double time1 = (double)(t2 - t1)/ (CLOCKS_PER_SEC*20);
cout << "构造用时" << time1 << "ms" << endl;
cout << "请输入查询属性的个数(不大于20个):";
cin >> N;
cout << "请输入查询属性(数字),以空格分开(不大于20个):";
for (int i = 0; i < N; i++)
cin >> chaxun[i];
cout << "开始对每个根节点进行bfs并寻找skyline" << endl;
t1 = clock();
bfsentry();
t2 = clock();
time1 = (double)(t2 - t1) / (CLOCKS_PER_SEC * 20);
// cout << "语义地点构造完毕,开始在语义地点寻找skyline" << endl;
// findparent();
cout << "寻找完毕,用时"<<time1<<"ms,是skyline的点有"<<pa.size()<<"个,分别是:"<< endl;
for (int i = 0; i < pa.size(); i++)
cout << pa[i] << " ";
system("pause");
}