← Back to team overview

oqgraph-dev team mailing list archive

Re: Adding new algorithm to oqgraph

 

On Wednesday, 27 January 2016 16:00:29 CEST Arjen Lentz wrote:
> On 25/01/16 18:42, Heinz Wiesinger wrote:
> > 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.
> 
> Ah, thanks for that illustration. Indeed, that'd be new.
> 
> Well, my suggestion would be to take a peek at the code and see if you
> can make sense of it.
> I personally find C++ frustrating when it gets into the land of
> templates - Andrew of course is very good at that, and so is Antony.
> 
> Anyhow, the Boost Graph Library is C++/template based, and thus we have
> to deal with it for now.... on the good side, the BGL has heaps of
> interesting algorithms, so if someone is willing to put the few lines of
> template code in that's required to add a new algorithm, we can make
> lots of headway pretty fast!
> 
> Andrew will also be able to provide you with some guidance here. Just ask.

Hi all :)

I finally had the opportunity to look into this and managed to produce a first 
prototype, which works for me in preliminary tests. More testing to do 
obviously and rounding out the implementation also still needs to be done, but 
I would like to get some feedback on the change first, if possible :)

As an example, I created a large graph (~2M nodes) that exhibits the 
performance problem we experienced. Finding the leaf node from the root node 
with our current query takes around 45s, with the new "leaves" latch it takes 
around 7s.

The work on this can be found at https://github.com/pprkut/mariadb/commits/
oqgraph-leaves

Grs,
Heinz

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


References