I went ahead and coded something up, inspired by Massimo's Preorder Traversal example. I wouldn't be offended if people suggest how to make it better/faster, perhaps by combining stuff in the Link function into one query instead of many.
# Demonstrate closure tables. Deletion of nodes is left as an exercise to the reader. # See: http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html from gluon import DAL, Field db=DAL('sqlite://closure.db') db.define_table( 'thing', db.Field('name') ) db.thing.truncate() db.define_table( 'closure', db.Field('parent', type='reference thing'), db.Field('child', type='reference thing'), db.Field('depth', type='integer') ) db.closure.truncate() def link(parent_id,child_id): """ link(1,3) """ p = db.closure.with_alias('p') c = db.closure.with_alias('c') rows = db((p.child==parent_id) & (c.parent==child_id)).select( p.parent.with_alias('parent'), c.child.with_alias('child'), (p.depth+c.depth+1).with_alias('depth')) for row in rows: db.closure.insert(parent=row.parent, child=row.child, depth=row.depth) def add_node(name,parent_name): """ add_node('Fruit','Food') """ child_id=db.thing.insert(name=name) db.closure.insert(parent=child_id, child=child_id, depth=0) if parent_name is not None: parent_id=db(db.thing.name==parent_name).select().first().id link(parent_id, child_id) def ancestors(name): """ print ancestors('Red')""" node=db(db.thing.name==name).select().first() return db((db.closure.child==node.id) & (db.closure.parent != node.id)).select( db.thing.name, left=db.thing.on(db.thing.id==db.closure.parent), orderby=db.closure.depth) def descendants(name): """ print descendants('Fruit')""" node=db(db.thing.name==name).select().first() return db((db.closure.parent==node.id) & (db.closure.child != node.id)).select( db.thing.name, left=db.thing.on(db.thing.id==db.closure.child), orderby=db.closure.depth) def closure(): """ print closure() """ parent = db.thing.with_alias('parent') child = db.thing.with_alias('child') return db().select(db.closure.id, parent.name, child.name, db.closure.depth, left=(parent.on(parent.id == db.closure.parent), child.on(child.id == db.closure.child))) def test(): add_node('Food',None) db.commit() print closure() add_node('Vehicle',None) db.commit() print closure() add_node('Fruit','Food') db.commit() print closure() add_node('Meat','Food') db.commit() print closure() add_node('Red','Fruit') db.commit() print closure() add_node('Chevy','Vehicle') db.commit() print closure() print "descendants of 'Food'" print descendants('Food') print "ancestors of 'Red'" print ancestors('Red') test() On Tuesday, November 20, 2018 at 5:02:33 PM UTC-8, BigBaaadBob wrote: > > Has anyone implemented a closure table with triggers > <http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html> > approach > to hierarchy (specifically for a Bill of Materials (BOM) pattern) in > Web2Py's DAL? > > I've seen Massimo's implementation of Preorder Traversal which doesn't > work for BOM patterns where there are multiple roots. The Adjacency Table > method is slow for large trees. > > In a Bill of Materials situation > <http://www.vertabelo.com/blog/technical-articles/identifying-the-bill-of-materials-bom-structure-in-databases>, > > there are multiple roots in the main table, like this: > > db.define_table('item', > Field('name', type='string', length=128, label=T('Name'))) > > db.define_table('bill_of_materials', > Field('parent_item_id', type='reference item', notnull=True, > label=T('Parent Item')), > Field('child_item_id', type='reference item', notnull=True, > label=T('Child Item')), > Field('quantity', type='decimal(8,2)', default='1.0', > label=T('Quantity'))) > > > -- Resources: - http://web2py.com - http://web2py.com/book (Documentation) - http://github.com/web2py/web2py (Source code) - https://code.google.com/p/web2py/issues/list (Report Issues) --- You received this message because you are subscribed to the Google Groups "web2py-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to web2py+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
