Creating a Model That Has a Tree Structure

Creating a model that has a tree structure

What you're looking for is self joins. Check this section of the Rails guide out: http://guides.rubyonrails.org/association_basics.html#self-joins

class Category < ActiveRecord::Base
  has_many :children, class_name: "Category", foreign_key: "parent_id"
  belongs_to :parent, class_name: "Category"
end

Every Category will belong_to a parent, even your parent categories. You can create a single category parent that your highest level categories all belong to, then you can disregard that information in your application.

Making a tree structure in django models?

ManyToOneRel is an internal implementation class, it's not for use in your models.

But why do you think you need it anyway? As the documentation explains in detail, when you define a ForeignKey, you automatically get a reverse relation. So in your case, if you define parent then you automatically get self.foomodel_set already: and you can make it even more explicit by using the related_name parameter:

parent = models.ForeignKey('self', blank=True, null=True, related_name='children')

Note that if you're planning on doing complicated things with trees, you probably want to be using the django-mptt library.

How to efficiently build a tree from a flat structure?

Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly.

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}

---

Related Topics