On Wed, Jul 21, 2010 at 11:04 AM, Tim Gallagher <tgallag...@danati.com> wrote:
> I cannot be the only one that is having this problem, what are you using for 
> DAG (Direct Acrylic Graph)?  I need to have a mesh node edge graph and am 
> having trouble with this?  I see that Neo4j has a rest server and I can do 
> this in Java but I want to do it in PHP with a MYSQL or postgresql.  If you 
> are doing something like this, can you please tell me how you are doing this. 
>  I can do a relationship with a parent child or a nested tree, but I need to 
> do a DAG.
> Thanks for the help,
> timgerr

A basic approach would be to use two tables - one to store the nodes
and second table to store the edges between the nodes. As far as
traversing the graph, the best approach I have seen expands this a bit
to store the full transitive closure of the graph, rather than just
the direct edges:


It is written for SQL Server, but the idea works OK (and I
successfully tested it once) in MySQL. (I imagine the same would be
true for PostgreSQL.)

The idea is to store the transitive closure (every possible path) of
the entire graph. For instance, if you have a basic graph

A -> B -> C -> D

it stores these paths:

A -> B
B -> C
C -> D
A -> C
B -> D
A -> D

The obvious downside is that edge table can get incredibly large
depending on the nature of the graph you are modeling. (The article
provides much more detail.) I did, however, import a good chunk of an
Active Directory tree (just users and groups, not the full list of
attributes) into this pattern just to test the concept, and I found
that in that case the size of the transitive closure table did not get
out of hand.


PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Reply via email to