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
signature.asc
Description: This is a digitally signed message part.
-- Mailing list: https://launchpad.net/~oqgraph-dev Post to : oqgraph-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~oqgraph-dev More help : https://help.launchpad.net/ListHelp
