对于以下型号:

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软件包。您需要的搜索算法将是广度或深度优先搜索。

10-06 09:02
查看更多