Constructing graph with ID that doesn't start at 1 can be very slow

[jeizenga]

The bottleneck appear to be this loop:
https://github.com/vgteam/odgi/blob/master/src/odgi.cpp#L432

I think it's hurting for a min ID offset to avoid this blow-up.

[ekg]

It's not just that. Also https://github.com/vgteam/odgi/blob/master/src/odgi.cpp#L429. There isn't an id/handle distinction in odgi. One can be added and optionally used when discontinuity is detected. A simple solution that works as long as the graph ID space is relatively dense is to find the min id of the input before starting construction.

…

On Wed, Jun 19, 2019, 23:12 Jordan Eizenga ***@***.***> wrote: The bottleneck appear to be this loop: https://github.com/vgteam/odgi/blob/master/src/odgi.cpp#L432 I think it's hurting for a min ID offset to avoid this blow-up. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#30>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AABDQEOPNEBC4V5RKHGWK3LP3KOMVANCNFSM4HZNMPOQ> .

[ekg]

OK, I'm back to this. Sorry for my earlier confusion.

I'm trying to figure out the best way to handle this. It may be impossible to avoid a translation layer of some kind.

[jeizenga]

Hey, if you're going to be developing on the ODGI graph, it might also be a good time to get it moved over to libbdsg. I have a port there, but I've never gotten it fully debugged. My handle evaluation crashes unless I use the odgi::graph_t.

[ekg]

I'm somewhat unsure about this. If graphs of this structure are common, we should just implement a GFA only tool that reduces a larger id space into a smaller one. I'm not sure it's good to implement that here. This tool might also do helpful things like converting back and forth between strings and numerical ids.

[ekg]

This has been resolved. The problem was graphs starting at a very high minimum node id. This is now supported.