I managed to design a directed graph model in Django. But now I’m trying to figure out how to traverse between vertices of this graph. Can anybody help?
Is this a general graph (possible loops or connections between branches), or is this a strict hierarchical model?
I think it is more of a hierarchical model. This representation fits if the dirrection of arrows is reversed.
If it’s a true hierarchy, then you probably want to implement it as such using treebeard (or one of the other hierarchical model packages). We use treebeard and are quite happy with it.
A pure hierarchy (one relying upon just the FK relationships) is probably the least efficient mechanism for storing a hierarchical structure in a relational database. Choosing which of the alternative models depends upon which operations you wish to optimize.
What if it’s not a pure hierarchy? I would like to implement the possibility of inheriting from two or more parents.
The “standard” way to address that in a relational DB is to have two tables, Vertex and Edge. In Django terms, Edge would be a ManyToMany Through table consisting of two FKs to Vertex (ancestor, descendant) and whatever additional information is needed to properly describe that Edge.
However, this is not an efficient data structure for general querying of that data. Depending upon the size, frequency of change, and your precise requirements for querying that data, I’d consider a true graph database or some type of denormalized structure to optimize those queries. It’s one of those situations where a general solution isn’t going to be optimal and you need to define your data structures in terms of desired use.
1 Like