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

[Szabolcs Horvát]

Dear All,

I have a few questions about C/igraph and isomorphism testing using bliss.

According to the documentation, igraph uses bliss 0.35

http://igraph.org/c/doc/igraph-Isomorphism.html#idm470920858320

* Is this accurate?

If yes, is there a specific reason why igraph doesn't upgrade to more
recent bliss?  Currently 0.50 and 0.72 are available.  0.50 seems to
have functionality that 0.72 doesn't.  Maybe the same is the case with
0.35?

The R/igraph documentation says that bliss doesn't support directed
graphs: http://igraph.org/r/doc/isomorphic.html  The C/igraph
documentation makes no such mention and the canonical_permutation
function does return a result for directed graphs.

* Does bliss support directed graphs in igraph?

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()?

Finally, the bliss documentation says:

http://www.tcs.hut.fi/Software/bliss/doxy/classbliss_1_1Graph.html#08da370e34106cd7db479eca7c7375cc

"The selected splitting heuristics affects the computed canonical
labelings; therefore, if you want to compare whether two graphs are
isomorphic by computing and comparing (for equality) their canonical
versions, be sure to use the same splitting heuristics for both
graphs."

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.

 * Is it a bug that different splitting heuristics are allowed?  Or is
it done intentionally?

Szabolcs