Nauty issues

[Ihromant]

Hi there.

I found your library when I was looking for Nauty alternative for Java. Without any offence, after adapting your code I was disappointed its issues and performance. Then I managed to write my own library according to https://arxiv.org/abs/1301.1493 and need of this adaptation disappeared.
Still, as a post mortem I am leaving this issue and probably you will fix and improve your library (I don't have plans to make my library public but your is available through public maven repository and is googlable).

So, found issues:

1. I used two of balanced incomplete block design BIBD(13,3,1) converted to point-line incidence matrices as an input and algorithm was not able to finish. I assume that there is a bug due to the fact that 13 > 10 and you are using string comparisons in your code (which don't correspond to natural integer ordering). Still, canonization worked for BIBD(7,3,1) (Fano plane) and for BIBD(9,3,1) (affine plane Z3xZ3).
2. This is actually the performance issue and the main problem of your code. On my computer canonization for BIBD(7,3,1) and BIBD(9,3,1) worked for seconds. This is unacceptable from performance standpoint and still corresponding graphs are only of size 14 and 21 correspondingly. I digged into this performance bottleneck. And found the reason. It's string concatenation/comparison (which are performed alot during search tree traversing). https://github.com/Data2Semantics/nodes/blob/master/nodes/src/main/java/org/nodes/algorithms/Nauty.java#L175 Here is the bottleneck. Firstly you're converting current search state to string (very costly operation) and then you compare two strings (second costly operation). This operations in general are applying 10k-100k times for graphs above (despite not very big size). And this leads to performance bottleneck.
   I can give you a hint how to perform comparison fast: https://github.com/Ihromant/math-utils/blob/master/src/main/java/ua/ihromant/mathutils/nauty/CanonicalConsumer.java I'm converting search state to FixBS (which is just fixed-size BitSet from common library). It can be just an array of longs (earlier it was like that) and this longs can be compared using simple machine instruction Long.compareUnsigned. If you want, you can adapt whole my algorithm to your library. But I gave you the hint how to fix performance (and probably algorithmic) issue. Still, in current state this library is not even close to nauty possibilities.

Sorry for a long message, but it would be great to have Java version of nauty publicly available. If I had more time in the future, I would make my library publicly available, but it requires extraction, refactoring and separation. For now I assume that you can fix issues in your repo.

Best regards,
Ivan Hetman

[pbloem]

Hi Ivan,

Thanks for the pointers, but this code is no longer maintained. I wrote it for my PhD, and optimized it to the point that its performance was no longer a bottleneck for me. It's not as fast as the real Nauty, but it was good enough for my use case. Note that if you expect to encounter general graphs, even the best implementation is still going to have exponential performance in the graph size, so optimizing things like string comparisons will only get you so far.

I haven't written any Java in almost a decade, so this library is unlikely to change. I'll leave this ticket up. Perhaps if somebody needs a Nauty implementation in the future, they can combine my code with your notes.