Re: [igraph] About bliss isomorphism testing and potential bug in igraph_isomorphic_bliss

[Tamas Nepusz]

> According to the documentation, igraph uses bliss 0.35
>
> http://igraph.org/c/doc/igraph-Isomorphism.html#idm470920858320
>
> * Is this accurate?
Probably yes - BLISS has been integrated a fairly long time ago into
igraph and we haven't been following the development since then.

> If yes, is there a specific reason why igraph doesn't upgrade to more
> recent bliss?
"If it ain't broke, don't fix it" :) More seriously, I think that no
one has asked for it so far, and the integration of an external tool
usually takes some time as we have to write the glue code that
converts between the internal format of the external tool and igraph's
format, plus we have to ensure that the external tool does not call
any routines that could interfere with igraph (e.g., calling abort()
in case of an error).

> The R/igraph documentation says that bliss doesn't support directed
> graphs: http://igraph.org/r/doc/isomorphic.html
This seems to be the case, judging from bliss_graph.cc. Also, some
BLISS-related functions in igraph (e.g., igraph_automorphisms) do
mention that directed graphs are treated as undirected. However, I
agree with you that there is a discrepancy between the C core and the
higher level interfaces re the handling of directed graphs and this
should be more consistent. Please file an issue for it on Github.

> All igraph_bliss functions return an igraph_bliss_info_t which has the
> group_size member.

> * Do I need to _always_ free(group_size), even if I ran some other
> function than igraph_automorphisms()?
igraph_canonical_permutations() also seems to fill it with something:

stats.group_size.tostring(&info->group_size)

Your safest bet is to set info->group_size to null before calling any
BLISS-related function, and then freeing it if it is non-NULL after
the BLISS-related function returned.

(Maybe we should have created an igraph_bliss_info_init() and an
igraph_bliss_info_destroy() function and then we could simply say that
these two functions have to be called no matter what).

> But igraph_isomorphic_bliss takes a _separate_ splitting heuristic
> argument for each of the two input graphs.  It would seem that setting
> different splitting heuristics may cause the function to return a
> wrong result.
Hmmm, maybe you are right here - I'm not that familiar with the
internals of the BLISS algorithm so I cannot judge this, but you seem
to be correct. Let's see what Gabor says.

T.