oqgraph-dev team mailing list archive

[Heinz Wiesinger <HMWiesinger@xxxxxxxxxxx>]

On Monday 25 January 2016 13:07:30 Arjen Lentz wrote:
> Hi Heinz
> 
> On 22/01/16 21:48, Heinz Wiesinger wrote:
> > We recently had a situation in our backend system where we ended up with a
> > rather large graph (16000 edges for about 800 nodes). We found that a
> > particular query we run on our graph didn't perform very well, with
> > average
> > runtimes of 10s, tending upwards.
> > 
> > Our graph looks pretty much like a simple tree, and can probably be best
> > visualized similarly to a git commit graph. The query we run finds all
> > reachable leaf nodes for a given origid. Currently we do this by querying
> > all reachable nodes and then filtering the results with a "WHERE NOT IN
> > (SELECT origid FROM graph_table)" condition, which works reasonably fast
> > up until around 4000/5000 edges and then drastically slows down.
> > 
> > I was wondering if it might be an option to add an algorithm like that
> > directly in oqgraph itself, without the need to specify the extra WHERE
> > condition, in the hope that that would eliminate the slowdown on larger
> > graphs. Something like
> > 
> > SELECT * FROM graph_table WHERE latch="leafs" AND origid=356
> > 
> > I had a quick look at the code to get a grasp of the complexity of that,
> > and while I found the location where to put it, I also noticed I don't
> > understand much of the code present there currently :)
> > 
> > We (as in the company I work for) might be interested to implement this
> > feature, if feasible, but as a first step, I'd just like to hear some
> > opinions on this :)
> 
> I'm all for implementing new algorithms.
> 
> But in this case, it shouldn't be necessary.
> The current codebase already offers a query for finding all nodes below
> origid.

Ah, but I don't want *all* the nodes, just the ones that are only a destid, 
but not an origid, aka the leafs :)

Example:

A->B->C->D
 \--------------/

very simple graph with 4 edges:
A -> B
B -> C
C -> D
A -> D

I want a query that given origid A, *only* returns D.

Grs,
Heinz

Attachment: signature.asc
Description: This is a digitally signed message part.