Древовидные структуры данных в Django

Древовидные структуры данных в Django Django 07.09.2010

Введение

Для хранение древовидных структур в Django чаще всего используются внешние ключи к родителю, без каких либо дополнительных ухищрений. Все хорошо когда надо добавить новый элемент или удалить листовой элемент. Но все усложняется когда надо построить дерево для какого-то элемента или удалить элемент, у которого есть потомки, немаловажной остается проблема и сортировки.

Одним из вариантов решений является алгоритм MPTT(Modified Preorder Tree Traversal) или еще называемый Nested Sets, который облегчает процесс выборки, построение пути, подсчет потомков, но усложняет процесс добавления нового элемента в дерево или удаления существующего (приходится пересчитывать используемые маркеры для каждого элемента дерева).

Подробнее про некоторые из способов хранение древовидных структур в реляционных БД можно почитать по следующим ссылкам:

В django для управления древовидными структурами существует два модуля django-mptt и django-treebeard.

Сравнение этих двух модулей есть в посте Representing hierarchical data with Django and MPTT

Установка и настройка

Устанавливаем последнюю версию django-mptt

git clone git://github.com/brosner/django-mptt.git
cd django-mptt
python setup install

Создаем тестовую модель. Обязательным условием является наличие поля parent и регистрация модели с помощью mptt.register.

# coding=utf-8
import mptt
from django.db import models

class Category(models.Model):
    title = models.CharField('Название', max_length=255)
    parent = models.ForeignKey('self', blank=True, null=True, verbose_name="Родитель", related_name='child')

    def __unicode__(self):
        return self.title
mptt.register(Category,)

Что-бы в админке дерево отображалось как настоящие дерево, с вложенной иерархией нам понадобится вырезать из feincms кусок, который делает красиво :). Для этого:

Содержимое feincms разворачиваем в корень проекта;
Содержимое feincms_static разворачиваем в директорию со статикой;

Содержимое settings.py получилось примерно такое:

import os
ROOT = os.path.abspath(os.path.dirname(__file__))
path = lambda *args: os.path.join(ROOT, *args)

...

MEDIA_ROOT = path('static/')
MEDIA_URL = '/static/'
ADMIN_MEDIA_PREFIX = '/media/'
FEINCMS_ADMIN_MEDIA = '/static/feincms/'
FEINCMS_ADMIN_MEDIA_LOCATION = path('static/feincms/')

...

TEMPLATE_DIRS = (
    path('templates'),
    path('feincms/templates'),
)

INSTALLED_APPS = (
    ...
    'mptt',
)

Файл admin.py выглядит так

from django.contrib import admin
from tree.models import Category
from feincms.admin import editor

class CategoryAdmin(editor.TreeEditor):
    list_display = ('title',)

admin.site.register(Category, CategoryAdmin)

т.е. мы меняем наследуемый админ-класс для нашей модели.

Теперь можно заходить в админку и начать заполнять модель, должно выглядеть примерно так:

Примеры использования

Моё тестовое дерево можно видеть выше.

Получаем всех родителей:

cat = Category.objects.get(id=4)
cat.get_ancestors()
[<Category: cat1>]

Получаем всех потомков:

cat = Category.objects.get(id=4)
cat.get_descendants()
[<Category: cat11>, <Category: cat12>]

Создадим новый элемент и назначим ему родителя

cat2 = Category.objects.get(id=2)
cat21 = Category(title="cat21")
cat21.save()
cat21.move_to(cat2)
cat2 = Category.objects.get(id=2)
cat2.get_descendants()
[<Category: cat21>]

Полный список методов можно посмотреть тут.

Разработчики также побеспокоились о отображении дерева в шаблонах. Ниже приведенный код отобразит дерево (в виде не сортированного списка) для нашей модели:

{% load mptt_tags %}

{% full_tree_for_model tree.Category as categories %}
{% for cat,structure in categories|tree_info %}
{% if structure.new_level %}{% else %}
{% endif %}
{{ cat.title }}
{% for level in structure.closed_levels %}{% endfor %}
{% endfor %}

На выходе получим

Дополнительное чтиво

Древовидные структуры данных в Django Django 07.09.2010

Цитата

Категории

Архив ↓