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

[Szabolcs Horvát]

It looks like bliss 0.73 was released since I posted this.  It also
looks like I was wrong when I said that 0.50 has things that 0.7x
doesn't.  It's just that doxygen didn't extract those classes in the
default configuration, so I thought they were not there.

On 31 August 2015 at 08:06, Szabolcs Horvát <address@hidden> wrote:
> 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