Utilities for implementing Modified Preorder Tree Traversal (MPTT) with your Django Model classes and working with trees of Model instances.

The latest version of this application's documentation, in reStructuredText format, is available in its docs directory. Note: this documentation is for the SVN trunk version of the application - it may differ from the documentation for the packaged release, which is available below.

The CHANGELOG is kept up to date with notable commits and development notes are taken when things just need a good old working out - have a look if you're interested in the thought process behind certain features or implementation details which needed a bit of thought.

What is Modified Preorder Tree Traversal?

MPTT is a technique for storing hierarchical data in a database in a manner which makes tree retrieval operations such as fetching complete trees, item ancestors and item descendants very efficient.

The trade-off for this efficiency is that performing inserts and moving items around is more involved, as there's some extra work required to keep the tree structure in a good state at all times.

Here are a couple of articles to whet your appetite:

• Storing Hierarchical Data in a Database
• Managing Hierarchical Data in MySQL

Version 0.2 Features

Version 0.2 was released on 16th January 2008, packaged from revision 88 in Subversion.

Version 0.2.1, a bugfix release, was released later on the same day - this fixes a bug with setup.py which prevented installation of the source distribution unless you had a DJANGO_SETTINGS_MODULE environment variable set up.

If you're upgrading from version 0.1, please see the BackwardsIncompatibleChanges wiki page - in particular, the mptt.models.treeify function has been replaced by mptt.register.

• Simple registration of Django model classes for MPTT - fields required specifically for the tree structure will be added dynamically if necessary.

In the simplest case, it's possible to use MPTT with your own models without adding a single line of MPTT-related code to them.

• The tree structure is automatically managed when you create or delete MPTT model instances. By default, new instances are added as the last child of their parent if they have one, otherwise they become the root of a new tree.

• The tree structure is automatically updated when you change a model instance's parent - by default, modified instances are moved so they are the last child of their new parent.

This allows basic management of the tree using the parent field available to you in the django.contrib.admin application and in newforms forms generated using the ModelForm class.

• To override the default insertion/reparenting positions mentioned above, you can specify that a particular field in your model is used for ordering when inserting or automatically reparenting model instances.

This allows you to have each level of the tree automatically sorted by a field of your choice.

• New methods are added model classes which are registered with MTTP, for changing their position in the tree, retrieving their ancestors, siblings and descendants, determining the number of descendants they have and other tree-related operations.

• A custom TreeManager manager is added to all MPTT model classes, providing tree management operations which, among other things, can be used to move any node in a tree (and its descendants) to an arbitrary point elsewhere in the tree, or to insert new nodes at any point in the tree.

• newforms components for working with trees in forms.

• Utility functions for working with trees of models.

• Template tags and filters for working with trees of models in templates.

Browse the version 0.2 HTML documentation online for more details.

Download and installation

Download the latest packaged version from http://code.google.com/p/django-mptt/ and unpack it. Inside is a script called setup.py. Enter this command:

python setup.py install

...and the package will install automatically.

A Windows installer is also available - just download and launch to install the application.

Alternatively, source code can be accessed by performing a Subversion checkout. For example, the following command will check the application's source code out to an mptt directory:

svn checkout http://django-mptt.googlecode.com/svn/trunk/ mptt

Add the resulting folder to your PYTHONPATH or symlink (junction, if you're on Windows) the mptt directory inside it into a directory which is on your PYTHONPATH, such as your Python installation's site-packages directory.

You can verify that the application is available on your PYTHONPATH by opening a Python interpreter and entering the following commands:

>>> import mptt
>>> mptt.VERSION
(0, 3, 'pre')

Keep in mind that the current code in SVN trunk may be different from the packaged release, and may contain bugs and backwards-incompatible changes, as well as new goodies to play with.

Running the tests

The mptt.tests package is set up as an application which holds a test settings module and defines models for use in testing MPTT. You can run the tests from the command-line using the django-admin.py script, specifying that the test settings module should be used:

django-admin.py test --settings=mptt.tests.settings

Django MPTT is tested with SQLite, MySQL 4.1 and PostgreSQL 8.1 on Windows.

Testimonials

"color me friggin amazed" -- Gulopine