Fangorn 0.3.2

Nested Sets SQL Tree for Python

Fangorn

Nested Sets aka Modified Pre-order Tree Traversal (MPTT) SQL tree implemented in Python for MySQL and SQLite. Uses both traversal markup (left, right) and adjacency list parentId for more ad-hoc query flexibility.

Provides tree structure validation and “memorisation” via SQLite :memory: for quick reads.

Example

We want to achieve the following tree. Node is represented by name id → parentId (l, r). To output a tree this way fangorn.test.visualize function can be used.

R 1 → None (1, 18)
└─A1 2 → 1 (2, 5)
  └─B1 3 → 2 (3, 4)
└─A2 4 → 1 (6, 13)
  └─B2 5 → 4 (7, 8)
  └─B3 6 → 4 (9, 12)
    └─C1 7 → 6 (10, 11)
└─A3 8 → 1 (14, 17)
  └─B4 9 → 8 (15, 16)

First we need a table to represent the tree. And we want a tree node to have a name.

import MySQLdb as mysql
conn = mysql.connect(user = 'guest', db = 'test')
conn.query('''
  CREATE TABLE `node` (
    `node_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
    `parent_id` int(10) unsigned DEFAULT NULL,
    `l` int(10) unsigned NOT NULL,
    `r` int(10) unsigned NOT NULL,
    `name` varchar(8) NOT NULL,
    PRIMARY KEY (`node_id`),
    KEY `l` (`l`),
    KEY `r` (`r`),
    KEY `parent_id` (`parent_id`),
    CONSTRAINT `node_has_node` FOREIGN KEY (`parent_id`)
      REFERENCES `node` (`node_id`)
      ON DELETE CASCADE
      ON UPDATE CASCADE
  ) ENGINE=InnoDB;
''')

Now we can create tree instance. Note that DAO that the tree relies on is expected to support named DB-API paramstyle (i.e. WHERE node_id = :nodeId). Also transaction control methods are recommended to implement nested transaction support. However test suite requires nested transactions to run. For MySQLdb and sqlite3 there’re compatibility wrappers under fangorn.compat.

import fangorn
from fangorn.compat.mysqldb import Mysqldb as MysqldbWrapper
tree = fangorn.NestedSetsTree(MysqldbWrapper(conn), 'node', ('name',))

rId  = tree.add(dict(name = 'R'))
a1Id = tree.add(dict(name = 'A1'), parentId = rId)
tree.add(dict(name = 'B1'), parentId = a1Id)
a2Id = tree.add(dict(name = 'A2'), parentId = rId)
b2Id = tree.add(dict(name = 'B2'), parentId = a2Id)
b3Id = tree.add(dict(name = 'B3'), prevId = b2Id)
tree.add(dict(name = 'C1'), parentId = b3Id)
a3Id = tree.add(dict(name = 'A3'), parentId = rId)
tree.add(dict(name = 'B4'), parentId = a3Id)

tree.move(a1Id, rId)
tree.move(a3Id, prevId = a2Id)

Now we can play with the tree.

print(tree.isDescendantOf(a2Id, 4)) # False
print(tree.isDescendantOf(a2Id, 6)) # True
print(tree.isDescendantOf(a2Id, 7)) # True
print(tree.isDescendantOf(a2Id, 9)) # False

print([n['name'] for n in tree.getChildren(a2Id)])    # ['B2', 'B3']
print([n['name'] for n in tree.getDescendants(a2Id)]) # ['B2', 'B3', 'C1']
print([n['name'] for n in tree.getPath(7)])           # ['R', 'A2', 'B3', 'C1']

print(tree.getNode(8))   # {'left': 14L, 'right': 17L, 'nodeId': 8L, 'name': 'A3', 'parentId': 1L}
print(tree.getParent(8)) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}
print(tree.getRoot())    # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}

tree.edit(1, dict(name = 'RR'))
print(tree.getRoot()) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'RR', 'parentId': None}

print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2', 'B3', 'C1'])
tree.remove(b3Id)
print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2'])

For more usage examples look at project’s test suite.