Recently I discovered for myself IGraphM package and find it really great!
<< IGraphM`
I am still learning its basic functionality. I need to verify isomorphism of a large set of graphs. I have already simplified them to avoid directed edges as they possibly are harder to treat. However, they still possess 3 features:
- Colored vertices
- Colored edges
- There could be more than 1 edge connecting some of the vertices
Thus, they are colored multigraphs. In the manual to the IGVF2IsomorphicQ
function it is written that
VF2 supports vertex coloured and edge coloured graphs. A colour specification consists of one of more of the "VertexColors" and "EdgeColors" options.
In a different place it is also stated that
Additionally, IGIsomorphicQ[] and IGSubisomorphicQ[] try to select the best algorithm for the given graphs. For graphs without multiple edges, they use igraph's default algorithm selection. For multigraphs, they use VF2 after internally transforming the multigraphs to an edge coloured simple graph.
Thus, we seems to be on the safe side and can try one example
gr[1]={1 <-> 2, 3 <-> 8, 8 <-> 9, 9 <-> 4, 1 <-> 10, 10 <-> 11, 11 <-> 2, 5 <-> 5, 5 <-> 6, 3 <-> 6, 6 <-> 7, 4 <-> 7, 5 <-> 7}
vr[1]=<|8 -> 3, 10 -> 3, 9 -> 7, 11 -> 7|>
ed[1]=<|6 <-> 7 -> 10|>
gr[2]={1 <-> 2, 3 <-> 8, 8 <-> 9, 9 <-> 3, 4 <-> 10, 10 <-> 11, 11 <-> 2, 5 <-> 5, 3 <-> 3, 5 <-> 6, 5 <-> 6, 6 <-> 7, 1 <-> 7, 4 <-> 7}
vr[2]=<|8 -> 3, 10 -> 3, 9 -> 7, 11 -> 7|>
ed[2]=<|6 <-> 7 -> 10|>
Let us visualize them first:
decorateGraph[con_, vrts_, edgs_] := Module[{g, gv},
g = Graph[con];
gv = Fold[SetProperty[{#1, #2},
{VertexStyle -> ColorData[60, vrts[[Key[#2]]] ], VertexSize -> Medium}] &, g,
Keys[vrts]];
Fold[SetProperty[{#1, #2},
EdgeStyle -> {ColorData[60, edgs[[Key[#2]]]], Thick}] &, gv,
Keys[edgs]]
]
GraphicsRow[
{decorateGraph[Graph[gr[1]], vr[1], ed[1]],
decorateGraph[Graph[gr[2]], vr[2], ed[2]]},
Dividers -> Center, FrameStyle -> Directive[Dashed, Blue]]
Now we use IGVF2IsomorphicQ
to check the isomorphism
IGVF2IsomorphicQ[{Graph[gr[1]], "VertexColors" -> vr[1], "EdgeColors" -> ed[1]}, {Graph[gr[2]], "VertexColors" -> vr[2], "EdgeColors" -> ed[2]}]
But the result is not what I've expected:
IGraphM::vf2nmg: VF2 does not support multigraphs.
How to deal with this problem? Is it at all possible? I appreciate your help.
IGIsomorphicQ
. It is the only builtin function that supports multigraphs, but it does not support colours. $\endgroup$QuotientRemainder[newColour, n]
will be{multiplicity, oldColour}
. Of course, you would need to choosen
correctly based on the colour count of both graphs you are comparing. $\endgroup$