对于以下型号:
class Entity(models.Model):
name = models.CharField(max_length=256)
class Entry(models.Model):
""" A <subj> has a <connection> to an <obj>
"""
subj = models.ForeignKey(Entity, related_name='subject')
connection = models.CharField(max_length=512)
obj = models.ForeignKey(Entity, related_name='object')
我存储了这种数据:
Z的作品
B在Z工作
B是C的兄弟
C住在D的隔壁
其中A,B,C,D和Z是实体实例
和“工作于”等内容存储在Entry模型的“ relation”字段中。
现在,考虑到所有实体之间存在许多联系,我该如何继续查找A和D之间的链接?我希望能够打印出类似以下内容:
A在第4度连接到D(并显示其步骤)。
我将其标记为Django问题,因为其目的是在基于Django的网站上使用它,但是我不知道Django的ORM是否可以在此提供帮助。
提前致谢!
最佳答案
这是一个图论问题。您的模型代表连接节点的边,并且您想查找节点之间的路径。有一些用于此类事情的python库,例如Boost库的python接口。
阅读图论,并检查相关的python软件包。您需要的搜索算法将是广度或深度优先搜索。