Computing the set of automorphisms of a non-simple AND multi-graph?

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"]

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.