CODEWITHSUNDEEP
pythondjango
Mathieu Dhondt
Mathieu Dhondt

Reputation: 8914

Finding connections between objects to the nth degree

For the following models:

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')

I have this kind of data stored:

A works at Z
B works at Z
B is the brother of C
C lives next door to D

where A, B, C, D and Z are Entity instances and "works at", etc are stored in the 'relation' field of the Entry model.

Now, how do I proceed to find a link between A and D, considering there are many connections between all of the Entities? I would like to be able to print out something like:

A is connected to D in the 4th degree (and show the steps in the meanwhile).

I've tagged this as a Django question as the intent is to use this on a Django-powered website, but I wonder whether Django's ORM can help here.

Thanks in advance!

Upvotes: 1

Views: 249

Answers (3)

Mathieu Dhondt
Mathieu Dhondt

Reputation: 8914

For those who happen to stumble on this questions: the essay at http://www.python.org/doc/essays/graphs/ has been very helpful. The dictionaries in the graph have Entities as keys, and lists of Entities as their paths.

With the find_all_paths function shown in the essay referenced above, I have been able to do exactly what I wanted. Thanks for the pointers, everyone.

Upvotes: 0

Spacedman
Spacedman

Reputation: 94202

This is a graph theory problem. Your model represents edges connecting nodes, and you want to find paths between nodes. There are python libs for this kind of thing, such as the python interface to the Boost library.

read up on graph theory, and check out relevant python packages. The search algorithm you need will be breadth or depth first search.

Upvotes: 1

Daniel Roseman
Daniel Roseman

Reputation: 599630

You need to look into an algorithm like Modified Pre-Order Tree Traversal, which allows you to store this kind of information in the database. There's a good Django implementation called django-mptt.

Upvotes: 0

Related Questions