3
$\begingroup$

As the title says, we would like to compute the set of all isomorphisms between, possibly, non-simple directed multi-graphs.

A related question is How to compute the automorphisms of graphs with multiple edges?.

There, @Szabolcs gives a solution which apparently can solve the problem but gives error as with the following graph. The graph is the bouquet graph, and we want to compute $Aut(B_n)$.

B[n_] := Graph[Table[1 -> 1, n]];

Let's work with $n=3$.

asc1 = Counts[Sort /@ EdgeList[B[3]]];

IGVF2FindIsomorphisms[
 {Graph[VertexList[B[3]], Keys[asc1]], 
  "EdgeColors" -> asc1}, {Graph[VertexList[B[3]], Keys[asc1]], 
  "EdgeColors" -> asc1}
 ]

And then we get:

IGraphM::vf2nmg: VF2 does not support non-simple graphs. Consider using IGIsomorphicQ or IGColoredSimpleGraph.
$Failed

Any fix or any approach? we could do instead a conversion of the graphs into their simple version graph, by introducing new vertices for each loop edge or multiple, or something similar?

$\endgroup$
3
  • $\begingroup$ Do you want one isomorphism? Then use IGGetIsomorphism. Do you want the entire automorphism group? At this moment, IGraphM does not have a solution for this (though it would be nice to have it eventually). $\endgroup$
    – Szabolcs
    Aug 3 '20 at 19:17
  • $\begingroup$ The problem with the answer I gave in the other thread is that it does not take self-loops into account. To do that as well, we can "colour" each vertex with the multiplicity of the number of self-loops on it. This is what IGIsomorphicQ and IGGetIsomorphism does internally. The colouring can be done automatically with IGColoredSimpleGraph. $\endgroup$
    – Szabolcs
    Aug 3 '20 at 19:18
  • $\begingroup$ IGIsomorphicQ colours normal edges by their multiplicity and vertices by the multiplicity of their self-loops, then calls the VF2 algorithms. VF2 supports both edge and vertex colours, however, it can only list isomorphisms. It cannot compute a comact representation of the automorphism group. Currently, only Bliss can do that, but Bliss does not support edge colours. $\endgroup$
    – Szabolcs
    Aug 3 '20 at 19:21
3
$\begingroup$

As the title says, we would like to compute the set of all isomorphisms between, possibly, non-simple directed multi-graphs.

With the latest version of IGraph/M, we can do the following:

  1. Take the support graphs of the non-simple graphs
  2. Encode edge multiplicities into edge colours
  3. Encode self-loop multiplicities into vertex colours
  4. Use IGVF2FindIsomorphisms to find all isomorphism between these two coloured graphs

Steps 1-3 are accomplished directly by IGColoredSimpleGraph, which output a format that can be passed to IGVF2FindIsomorphisms without modifications.

Example:

SetOptions[IGShorthand, MultiEdges -> True, SelfLoops -> True];
g1 = IGShorthand["1-2-3-2-2"]
g2 = IGShorthand["1-2,1-2,1-3,1-1"]

enter image description here

As you noticed, IGVF2FindIsomorphisms does not support non-simple graphs. But the error message tells us what to do.

In[209]:= IGVF2FindIsomorphisms[g1, g2]

During evaluation of In[209]:= IGraphM::vf2nmg: VF2 does not support non-simple graphs. Consider using IGIsomorphicQ or IGColoredSimpleGraph.

Out[209]= $Failed

We can use IGColoredSimpleGraph to encode edge and loop multiplicities into colours:

In[212]:= IGColoredSimpleGraph[g1]
Out[212]= {-graph-, "VertexColors" -> {0, 1, 0}, "EdgeColors" -> {1, 2}}

This format is suitable for input to IGVF2FindIsomorphisms:

In[211]:= IGVF2FindIsomorphisms[IGColoredSimpleGraph[g1], IGColoredSimpleGraph[g2]]
Out[211]= {<|1 -> 3, 2 -> 1, 3 -> 2|>}

Note 1: Currently, of the isomorphism algorithms included in IGraph/M, only VF2 supports both edge and vertex colours, which are needed for this calculation.

Note 2: VF2 cannot give us merely the generators of the automorphism group, like Bliss can. Currently the only option is to get all isomorphisms. Alternatively, you could try to subdivide each edge in the support graph and encode edge multiplicities into colours of the subdividing vertices, then use Bliss, which supports only vertex colours. Doing this correctly may be a lot of work.

Note 3: If you only want to test isomorphism of non-simple graphs, you can use IGIsomorphicQ. If you only need one isomorphism (not all of them), you can use IGGetIsomorphism.

Note 4: Currently, IGColoredSimpleGraph does not retain vertex names. It changes vertex names to be consecutive integers. This is sufficiently inconvenient to be called a bug and I will fix it for IGraph/M 0.4.1.

Note 5: The method I described above only works for isomorphism tests, not for subisomorphism tests. This is because with subisomorphism tests, an edge of the subgraphs's support graph is allowed to to have smaller multiplicity than a matching edge of the big graph. However, IGSubisomorphicQ and IGGetSubisomorphism to handle this correctly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.