Directed graph implementations for Django

[Paul Dorman]

Hi all,

definite newbie here. I'd like to implement a category type system in Django. I've looked in the cookbook and Googled a bit, but to no avail. What I'm after should be pretty simple: a directed graph for categories, where objects and perhaps categories can be a member of one or more categories. For example, a 'server' is an 'infrastructure component' (for the techies), as well as an 'asset' (for the financial types). In my grand scheme when an object is associated with one or more categories (one is the minimum), the application will  execute method calls stored (with optional parameters) in the database (serialized as JSON or XML). With the 'server' example, it might be that being in the 'infrastructure component' category triggers an email to be sent to the system administrator, and the existence in the 'asset' category would trigger an automated update to the asset register. The methods are stored according to the standard CRUD set of operations, so that a user can create a new category in the view, and then specify actions which occur when an object is created, read, updated, or deleted (provided by the application itself). Actions are triggered for both objects (the things that are categorized) and for child categories (so for example it may be that a parent category can be locked in such a way as to prevent any more child categories from being added).

Note that categories are purely containers with generic actions (for crud operations on objects in the category) and distinct from objects, which I imagine would have a category_id FK. And note also that my objects are all using the same model, with the bulk of data serialized as XML.

Has anyone out there in Djangoland done something like this? The graph's the thing - I'm happy to deal with the CRUD triggers myself. If there's a model out there that would be a good starting point that would be great.

One additional thing I'm wondering about is how Django can work with stored procedures. For example, it might be more efficient if the application can ask the database for the methods to run  when an object is created,  and have the database return the methods for not only the object's bottom-level category, but for all parent categories as well.

P.S.

Congratulations on the great sprint!

P.P.S. I hope I haven't just embarrassed myself with my naïveté.

--
"Science fiction writers are the only ones who care about the future"
--  Kurt Vonnegut

[Julio César Carrascal Urquijo]

I'm a newbie on Django my self but maybe this is what you are looking
for:

class Category(models.Model):
code = models.CharField(maxlength=200, unique=True)
products = models.ManyToManyField('Product')

class Product(models.Model):
parent = models.ForeignKey('Post')
code = models.CharField(maxlength=200, unique=True)

I've also read that you can specify signals for most operations on a
model (Like when a model is inserted, updated or deleted from the
database) though I can't find the URL right now. There's some mention
of it here:

http://www.djangoproject.com/documentation/db-api/

[paul.dorman]

Thanks for your response Julio,

something similar yes. What I'm after is an Django implementation of
an directed acyclic graph. I understand there's some complexity
involved to ensure no cycles can be created (which I understand is the
graph equivalent of an endless loop). There's plenty of good examples
of DAG out there, but I'm not sure how to implement one that works
with RDMS (or Django for that matter!)

Paul

On Sep 17, 4:56 pm, Julio César Carrascal Urquijo

[vincent garonne]

Hello,

Does someone knows how to do a loop on a int inside template, e.g. :

<div align="left"><font size="-1">Result&nbsp;Page:&nbsp;</font>:
{% for p in pages %}
{% ifequal p page %}
<font color="brown"><strong> {{p}} </strong></font>
{% else %}
<a href="/page/{{p}}/" target="resultframe"> {{p}} </a>
{% endifequal %}
{% endfor %}
</div>

Where pages is an int. Do i have to use a special filter function ?

Cheers,
Vincent.

--
-----------------------<vincent...@cern.ch>------------------------
Vincent Garonne http://cern.ch/vincent.garonne
CERN PH, CH-1211, Geneva 23, Switzerland
Tel. +41 22 76 71181 Fax. +41 22 76 78350
----------------------------------=-------------------------------------

[doug.na...@gmail.com]

We use a Tree for the navigation bar (not a true DAG, but there are
circular checks):
https://pycon.coderanger.net/browser/django/trunk/pycon/navbar/models.py

There is a validator IsNotCircular, which does the obvious.

There is code to do serialization (currently just a pickle), but there
are plans to add json to communicate to the client.
The (poor) documentation on using the navbar is here:
https://pycon.coderanger.net/wiki/PyCon08/NavBar

I have other examples of true DAG's in DB form, but they are very
domain specific and take advantage of the
limitations in the data. (like the divided room problem where a
conference room might have 3 parts which can
make a total of 6 'rooms', but have special meaning for room
scheduling). But the NavBar is closest to what
you are trying to do.

[Russell Keith-Magee]

On 9/18/07, vincent garonne <vincent...@cern.ch> wrote:
>
> Hello,
>
> Does someone knows how to do a loop on a int inside template, e.g. :

Well - looping in Django templates is quite similar to looping in
Python, so you can't 'loop on an int'. You can loop on a range, though
- so if you make pages = range(0,max_page), you will be able to use
the template you describe.

There was some talk over the sprint weekend about adding a 'repeat'
tag, or some equivalent syntax for 'iterate n times'; however, I'm not
sure how far that discussion went.

Yours,
Russ Magee %-)

[paul.dorman]

Thanks very much for your help Doug. Do you think there is value in
having a generic DAG implementation for Django? Seems to me like it
might be a useful addition, but I'm curious as to how useful it would
be given that most non-Django implementations I have come across are
as you describe 'very domain specific'.

I also wonder how much a DAG implementation should rely on RDMS
functions to minimize the chatter between the application and
database. For instance, it would be terrible to get a node from the
DB, determine it's parent(s), fetch each parent from the DB, determine
*its* parents, etc. etc. Now I could serialize the parents into the
node data, but don't know if that is going to be effective because if
the parent relationships change you're going to have a lot of
processing to update all your nodes.

I know that a DAG is a subset of a digraph, which is what an RDBMS is,
so I'm sure that there's a very elegant way of doing it. But the
problem for me is (a)determining how to do it from the database
perspective, and (b)how to do it in Django.

Cheers,
Paul

On Sep 18, 8:34 am, "doug.napole...@gmail.com"

<doug.napole...@gmail.com> wrote:
> We use a Tree for the navigation bar (not a true DAG, but there are
> circular checks):https://pycon.coderanger.net/browser/django/trunk/pycon/navbar/models.py
>
> There is a validator IsNotCircular, which does the obvious.
>
> There is code to do serialization (currently just a pickle), but there
> are plans to add json to communicate to the client.
> The (poor) documentation on using the navbar is here:https://pycon.coderanger.net/wiki/PyCon08/NavBar
>
> I have other examples of true DAG's in DB form, but they are very
> domain specific and take advantage of the
> limitations in the data. (like the divided room problem where a
> conference room might have 3 parts which can
> make a total of 6 'rooms', but have special meaning for room
> scheduling). But the NavBar is closest to what
> you are trying to do.
>
> On Sep 17, 4:08 pm, "paul.dorman" <paul.dor...@gmail.com> wrote:
>
> > Thanks for your response Julio,
>
> > something similar yes. What I'm after is an Django implementation of

> > andirectedacyclic graph. I understand there's some complexity

> > involved to ensure no cycles can be created (which I understand is the
> > graph equivalent of an endless loop). There's plenty of good examples
> > of DAG out there, but I'm not sure how to implement one that works
> > with RDMS (or Django for that matter!)
>
> > Paul
>
> > On Sep 17, 4:56 pm, Julio César Carrascal Urquijo
>
> > <jcarras...@gmail.com> wrote:
> > > I'm a newbie on Django my self but maybe this is what you are looking
> > > for:
>
> > > class Category(models.Model):
> > > code = models.CharField(maxlength=200, unique=True)
> > > products = models.ManyToManyField('Product')
>
> > > class Product(models.Model):
> > > parent = models.ForeignKey('Post')
> > > code = models.CharField(maxlength=200, unique=True)
>
> > > I've also read that you can specify signals for most operations on a
> > > model (Like when a model is inserted, updated or deleted from the
> > > database) though I can't find the URL right now. There's some mention
> > > of it here:
>
> > >http://www.djangoproject.com/documentation/db-api/
>
> > > On Sep 16, 9:54 pm, "Paul Dorman" <paul.dor...@gmail.com> wrote:
>
> > > > Hi all,
>
> > > > definite newbie here. I'd like to implement a category type system in
> > > > Django. I've looked in the cookbook and Googled a bit, but to no avail. What

> > > > I'm after should be pretty simple: adirectedgraph for categories, where