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

[Szabolcs Horvát]

On 1 September 2015 at 15:25, Tamas Nepusz <address@hidden> wrote:
>
>> 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.

Indeed it doesn't support directed graphs, i.e. it treats them as
undirected.  Perhaps a warning would be in order.  Here's a transcript
of a hopefully self-explanatory Mathematica session, which directly
corresponds to how the C code works, but it was easier to try.  I
didn't have this implemented yet when I asked the question yesterday.

In[2]:= << IGraphM`

In[3]:= g1 = Graph[{1, 2, 3}, {1 <-> 2, 2 <-> 3}]; (* undirected *)

In[4]:= g2 = Graph[{1, 2, 3}, {1 -> 2, 2 -> 3}]; (* directed *)

In[5]:= g3 = Graph[{1, 2, 3}, {1 -> 2, 3 -> 2}]; (* directed, but
different from g2 *)

It won't allow comparing directed with undirected:

In[6]:= IGBlissIsomorphic[g1, g2]

During evaluation of In[6]:= IGraphM`LTemplate`LTemplate::error:
Cannot compare directed and undirected graphs
During evaluation of In[6]:= IGraphM`LTemplate`LTemplate::error: Invalid value

Out[6]= LibraryFunctionError["LIBRARY_FUNCTION_ERROR", 6]

In[7]:= IGBlissIsomorphic[g2, g2]
Out[7]= True

It says that g2 and g3 are isomorphic when they really aren't.

In[8]:= IGBlissIsomorphic[g2, g3]
Out[8]= True

igraph_isomorphic() supports directed graphs:

In[9]:= IGIsomorphic[g2, g3]
Out[9]= False