search

a-maier / nauty-Traces-sys

Rust bindings for nauty and Traces
Other
5 stars 3 forks source link

Canonical orders returned by Traces inconsistent #8

Closed juliuskunze closed 12 months ago

juliuskunze commented 1 year ago

Hi @a-maier,

I wrote a test verifying that two small isomorphic node-labeled graphs give consistent canonical orders with Traces:

https://github.com/a-maier/nauty-Traces-sys/compare/master...juliuskunze:nauty-Traces-sys:traces-bug

Both graphs are isomorphic to the following structure consisting of two disconnected parts (colors highlight the node labels):

$${\color{red}0} - {\color{green}1} - {\color{green}1}$$

$${\color{red}0} - {\color{green}1} - {\color{green}1}$$

The test fails because the canonical orders are inconsistent and the canonicalized graphs are different.

Traces' canonical order is consistent for most of the ~200000 graphs I tested on but inconsistent for ~10 out of them. sparsenauty is prohibitively slow in many of these cases, so this issue is critical for my use case.

a-maier commented 1 year ago

Hi @juliuskunze,

Thanks for reporting this bug. I can also reproduce it without the bindings:

https://github.com/a-maier/traces-canon-issue/blob/main/traces_canon_issue.c

It looks like a genuine Traces issue to me. It's probably best if you get in touch with the authors.

juliuskunze commented 1 year ago

Thanks for reproducing this directly in C! I contacted the authors and will let you know here if there are any updates.

a-maier commented 12 months ago

This should now be fixed in version 0.7.0, bundling nauty & Traces 2.8.8.