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.

Reply via email to