|
????????知识图谱是一种结构化的语义网络，用于描述物理世界中的概念及其实例的相关关系。可以把知识图谱看成是一种有向图，图中的点是概念或实例，图中的边是概念及其实例的相关关系。
现定义一种简单的知识图谱：
概念：包括父概念及其子概念，通过 subClasso关系关联，父子概念可以有多个层级；
实例：仅和概念之间通过 instanceOf关系关联；
关系：以三元组的形式表示，三元组是一个以空格为成员间分隔符的字符串。例如"student subClassof person"表示 student是person的子概念；apple instanceof fruit表示apple是fruit概念的实例。
给定一个知识图谱，请编写一个方法，可以根据一个概念查找其所有的实例。如果一个概念拥有子概念，那么返回的结果需要包含其所有子概念的实例；如果输入的概念没有实例，则返回字符串empty"(说明：输出字符串文本不需要包含引号)。
给定的图谱满足以下限制：
1、有向图中不存在环路；
2、所有点和关系的定义对大小写敏感；
解答要求
时间限制CC++1000ms，其他语言：2000ms
内存限制CC++32MB，其他语言：64MB
输入
输入第1行，表示图谱中关系的数量n，取值范围[1,10000]
从第2行到n+1行，表示图谱中的关系，每一行是一个关系三元组。
第n+2行，表示待查找的元节点,是关系三元组中存在的点。
每行字符的长度不超过100
输出
按字典序升序排列的字符串数组，其内容是概念及其子概念的所有实例。
注释：什么是字典序？在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。
样例1
输入：3
?student subClassOf person
?Tom instanceOf student
?Marry instanceOf person
?person
输出：Marry Tom
解释：studentperson是的子概念，Tom是 student的实例，Marryperson是的实例，Marry的字典序小于Tom，所以返回 Marry Tom
样例2
输入：1
?apple instanceOf fruit
?fruit
输出：apple
解释：applefruit是的唯一实例，所以返回 apple
# -*- coding: utf-8 -*-
n = int(input("图谱关系数n："))
keyWords = ['subClassOf','instanceOf']
class_dict = {}
instance_dict = {}
for i in range(n):
relation = input('关系三元组' + str(i) + '：')
relation_list = relation.split(' ') #关系拆分
son = relation_list[0]
key = relation_list[1]
parent = relation_list[2]
if key == 'subClassOf': #这是子概念
class_dict[i] = dict([(parent,son)])
elif key == 'instanceOf': #这是一个实例
instance_dict[i] = dict([(parent,son)])
else: #关键词错误
print('关键词错误！')
break
def f(dir_dict,key):
result = []
for tmp in dir_dict.keys(): #遍历实例字典
temp = dir_dict[tmp]
for tmp in temp.keys(): #查实例字典，找出实例
#遍历的所有实例字典中有多少个该子类的实例，存在instance中
if key == tmp:
result.append(temp[key])
return result #有可能为空，需要校验
node = input("待查询的概念：")
son = [node]
instance = []
for i in range(n): #遍历所有类字典，最多n轮，只可能更少
temp = f(class_dict,node) #所有的子类
if temp != []: #有子类，那么继续查这个子类还有没有子类，son返回所有该节点的子类
son.append(temp[0])
node = temp[0]
else:
break #无子类就退出
if son == []: # 无子类
instance = f(instance_dict,node) #没有子类，查有没有实例
if instance != []:
print('无子类，只有一个实例：',instance)
else:
print('既无子类，也无实例！')
else: # 有子类
for tmp in son: #遍历所有字典
instance.append(f(instance_dict,tmp)[0])
if instance != []:
instance.sort() #排序
for tmp in instance:
print(tmp,end=" ")
else:
print('empty')
print('有子类，无实例！')
|