oqgraph-dev team mailing list archive
-
oqgraph-dev team
-
Mailing list archive
-
Message #00318
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