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

django_tree.png Введение

Для хранение древовидных структур в 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 кусок, который делает красиво :). Для этого:

  1. Содержимое feincms разворачиваем в корень проекта;
  2. Содержимое 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)

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

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

mptt_tree_admin.png

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

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

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

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 %}

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

mptt_tree.png

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

Цитата
Возможность упускается большинством людей, потому что она одета в обыкновенность и выглядит как работа.
-
Категории
Архив