Update LAD

[gaborcsardi]

http://liris.cnrs.fr/csolnon/LAD.html

[gaborcsardi]

Or maybe we already have the latest version? Hmmm.....

[szhorvat]

I verified that as of today igraph has LAD v1. I contacted the LAD author to ask about the differences between LAD v1 and v2. She said that while both support either directed or undirected graphs, LAD v2 is going to perform better on directed ones.

[ntamas]

Thanks for the clarifications!

[szhorvat]

Version 3 is available since Dec 2015.

[szhorvat]

I see three difficulties with integrating LAD into igraph:

• it uses C99 variable length arrays, which igraph probably shouldn't use due to bad compiler support (MSVC still doesn't support it)
• it doesn't free any memory it allocates
• it ought to work on igraph graphs as directly as possible (to avoid graph format conversion overhead, though it's not clear to me to what extent this is possible)

Currently this was solved by modifying the LAD code significantly to use igraph data structures (igraph_vector_int_t) and memory management (IGRAPH_FINALLY, etc.). The disadvantage of this approach is that it is a lot of work (extensive modifications required), error prone, and hard to maintain (see bug #927).

I would like to propose an alternative approach if/when future LAD versions get integrated:

Use (very simple) C++ to provide array data structures that can be used (as much as possible) with the exact same syntax as C arrays. The goal is to keep modifications to the LAD source code as minimal as possible, thus reducing the change of mistakes, reducing the amount of work needed to integrate the code and increasing maintainability. Memory management would be done using RAII and interruptability by throwing exceptions (which are of course always caught by the outermost wrapper). In principle the only changes needed are to the initialization of arrays and converting the graph to use LAD data structures.

What do you think?

Note: I definitely won't have time to work on this for at least a couple of months, but I'd really like to see LAD updated. I would like to see igraph provide the best and most extensive isomorphism testing functionality of all packages.

---

Finally, I would also like to hear your opinion on whether the time limit functionality currently in igraph-LAD is really necessary. igraph functions are already interruptable. I think the high level interfaces (R, Python) could in principle provide time constraint functionality for any interruptable function (Mathematica does this).

[szhorvat]

So far this approach I proposed above works well.

Question: Do we really need to keep the time limit functionality? It would make things simpler if I could just leave it out.

Why I think timing is not necessary:

• igraph is mostly used through the high level interfaces, not through C. igraph functions are already interruptible. Time limits should use this interrupt functionality instead, and timing should be done fully within the high level language (e.g. setTimeLimit/evalWithTimeout in R, TimeConstrained in Mathematica, etc.)
• The current LAD port in igraph has separate code for interruption and time limits. This is suboptimal. Interruptions can happen at different points in the code for time limits and standard interruptions. Also, this functionality in LAD is not good enough at the moment: it can still get stuck running for a long time. It needs improvements which will be easier to do if there's only one way to interrupt.
• Ideally the function could still return results found so far if the time limit is reached. This is something that wouldn't be possible with a standard interruption. According to the documentation it doesn't do this currently, so we won't lose much by removing the time limit functionality. I tried to test this, but I couldn't get the time limit to work through the R interface ...

Note: Timing appears to have been included in the original LAD mainly for benchmarking and testing purposes.

[szhorvat]

I forgot to say that the API needs to be broken anyway if LAD is updated because later versions handle coloured graphs differently. There won't be a domains argument. Instead there will be separate vertex (and maybe edge) colours, like in the vf2 functions.

[szhorvat]

It would be good to get some feedback on this proposal before putting too much work into it. In particular on the following points: 1) breaking the API (this is simply necessary IMO) 2) remove time limit functionality 3) alternative LAD port using C++ (this is mostly done and it is much faster than the original LAD port in igraph due to using different memory management)

[ntamas]

I'm on the road at the moment - if @gaborcsardi could take a look at it in the next few days, that would be great. Otherwise, I'll try to do it early next week.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.