IGraph/M 0.1.3 or later supports multigraph isomorphism testing directly. Note: Version 0.3.110 fixes important bugs in multigraph (sub-)isomorphism. Upgrade to this release or later.
<< IGraphM`
g1 = Graph[{1 -> 3, 1 -> 4, 1 -> 4, 2 -> 3, 2 -> 3, 2 -> 4}]
g2 = Graph[{1 -> 2, 1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4, 3 -> 4}]
As directed graphs they are not isomorphic:
IGIsomorphicQ[g1, g2]
(* False *)
As undirected ones they are:
g1 = Graph[{1 <-> 3, 1 <-> 4, 1 <-> 4, 2 <-> 3, 2 <-> 3, 2 <-> 4}]
g2 = Graph[{1 <-> 2, 1 <-> 2, 1 <-> 3, 2 <-> 4, 3 <-> 4, 3 <-> 4}]
IGIsomorphicQ[g1, g2]
(* True *)
We can get a specific mapping like so:
IGGetIsomorphism[g1, g2]
(* {<|1 -> 1, 3 -> 3, 4 -> 2, 2 -> 4|>} *)
The implementation is based on igraph's support for edge-colored graphs. Note that at the moment igraph itself (the library underlying IGraph/M) does not support multigraph isomorphism. It won't error on multigraphs, but it may not give correct results. It is important to be aware of this when using igraph from R/Python/C. IGraph/M, the Mathematica interface, does have checks for multigraphs, and can test for multigraph isomorphism by transforming them to edge-coloured simple graphs.
There's no builtin implementation for finding isomorphisms for multigraphs, but we can do the translation to edge-coloured graphs by hand:
asc1 = Counts[Sort /@ EdgeList[g1]]
(* <|1 <-> 3 -> 1, 1 <-> 4 -> 2, 2 <-> 3 -> 2, 2 <-> 4 -> 1|> *)
asc2 = Counts[Sort /@ EdgeList[g2]]
(* <|1 <-> 2 -> 2, 1 <-> 3 -> 1, 2 <-> 4 -> 1, 3 <-> 4 -> 2|> *)
IGVF2FindIsomorphisms[{Graph[VertexList[g1],Keys[asc1]], "EdgeColors" -> asc1}, {Graph[VertexList[g2],Keys[asc2]], "EdgeColors" -> asc2}]
(* {<|1 -> 1, 3 -> 3, 4 -> 2, 2 -> 4|>, <|1 -> 3, 3 -> 1, 4 -> 4, 2 -> 2|>,
<|1 -> 2, 3 -> 4, 4 -> 1, 2 -> 3|>, <|1 -> 4, 3 -> 2, 4 -> 3, 2 -> 1|>} *)