Isomorphism of colored multigraphs

Question

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

They look quite different:

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.

Answer 1

One possible solution is to find an injective mapping from coloured multigraphs to coloured simple graphs. We then test the isomorphism of the transformed graphs with IGVF2IsomorphicQ.

My idea for such a mapping is the following:

1. Subdivide every edge a <-> b to a <-> x <-> b. This eliminates multi-edges between distinct vertices.

2. Subdivide self-loops a <-> a to a <-> x <-> y <-> a. This transforms self-loops to 3-cycles. A 3-cycle cannot be created with the type of subdivision in point 1. above, thus I believe that the injective property of the mapping stands.

The injective property, i.e. that non-isomorphic graphs map to non-isomoprhic ones, is critical. Therefore I encourage you to think through that the above approach is indeed valid.

---

To implement this, we start by introducing a new notation for coloured edges. col[a <-> b, c] represents an edge with colour c. Example:

edges = { col[1 <-> 2, 1], col[1 <-> 2, 2], 2 <-> 3 };

The following function brings edge representations to a canonical form. Uncoloured edges are assigned the colour 0.

normalizeEdges[edges_] :=
 Block[{TwoWayRule = UndirectedEdge},
  Replace[edges, e_UndirectedEdge -> col[e, 0], {1}]
 ]

This function creates a new symbol to be used as a node:

newNode[] := Unique[node]

Implement subdivision of normal edges and self-loops:

subdivide[col[UndirectedEdge[a_, a_], c_]] :=     
 With[{n1 = newNode[], n2 = newNode[]},
  Unevaluated@Sequence[
    col[UndirectedEdge[a, n1], c],
    col[UndirectedEdge[n1, n2], c],
    col[UndirectedEdge[n2, a], c]
    ]
  ]

subdivide[col[UndirectedEdge[a_, b_], c_]] :=
 With[{n1 = newNode[]},
  Unevaluated@Sequence[
    col[UndirectedEdge[a, n1], c],
    col[UndirectedEdge[n1, b], c]
    ]
  ]

Convert an edge list in the above format to a subdivided edge list in a format suitable for IGraph/M:

colouredSubdividedGraph[edges_] := 
 With[{newEdges = subdivide /@ normalizeEdges[edges]},
  {Graph[newEdges[[All, 1]]], "EdgeColors" -> newEdges[[All, 2]]}
 ]


colouredSubdividedGraph[edges]

Finally, use IGVF2IsomorphicQ to compare these transformed coloured graphs.

I won't address the visualization question as that in itself deserves a separate question and has been asked before.

• Color edges of a multigraph when there are parallel edges using Graph[] and EdgeStyle
• Graph: Coloring Edges individually

Unfortunately, Mathematica cannot properly deal with edge attributes of multigraphs, which makes visualization very messy. If you feel limited by this problem, I encourage you to report it to Wolfram.

Answer 2

Preamble

A few weeks ago I needed to find isomorphisms of colored multigraphs for my research, so I quickly wrote some ugly code that only worked if (a) none of the original colors were the same as the multi-edge counts used to color multi-edges; and (b) multi-edges were not originally colored. This sloppy 'solution' didn't sit well with me, so I decided to write an answer.

Disclaimers:

1. I haven't tested this terribly throroughly. Additional suggestions for test code is welcome -- I just don't currently have the willpower to invent exhaustive test cases (partialy because I wrote this code on an overnight flight). I did make some test cases, with an ad hoc series of assertions that I cooked up.
2. I didn't read the links in Szabolcs' comments. They might do things better than I do.

Answer

Full code

The full code is on github.

_{If you're really bored, you can look up my horrible original implementation in the earliest version(s).}

Warning -- It seems Mathematica 11.2 automatically replaces \[UndirectedEdge] with <-> in .m files, but only upon saving the file. I haven't investigated fully, but it seems that some edges are still \[UndirectedEdge]'s, while others are <->, and IGraphM distinguishes between them, so the tests break. As such, beware that this code will break if you open and save these .m files in MMA 11.2.

Overview

• first combine original colors (I refer to these as optsColors, as they are specified in an option-like way to the isomorphism function) with multicolors (computed in the standard way) into a two-element list
  • write these combined 'colors' in an association (associated by edges), in a similar form to the standard color specification
• map each color pair to an integer
  • this is done by adding each unique color pair as a key in a master association, with he nth unique color having value n.
  • this looks like, e.g., `<| {1,2} -> 1, {2,3} -> 2, ... |>

Note that the keys in this master association can be anything, not necessarily lists of integers

Colored (and multicolored) multi-edges:

(When I say 'multi-edge', I mean a graph which appears more than once in a multigraph. For now, I identify directed edges with their reverses. When I say a multi-edge is colored, I mean that different instances of that edge have different colors.)

If a multi-edge is given a color in the normal way, it is naturally assumed that every instance of that edge has that color. In order to give different instances of that edge distinct colors, one can specify, e.g., (1<->2) -> {2,3,4}, which gives one instance color 2, one color 3, and one color 4, with all others defaulting to zero.

It seems natural to identify different permutations of multi-edge colors -- e.g., (1<->2) -> {2,3,4} is identified with (1<->2) -> {3,2,4}. As such, all 'colors' which are lists will be assumed to refer to multi-edges, and will be sorted.

Further considerations

Things left to do

• Deal with directed graphs
• More exhaustive tests
• Figure out a way around the \[UndirectedEdge] vs <-> issue
• Consider type-checking color lists
• Make sure multicolored multi-edges aren't colored with more colors than their multiplicity

Minor notes

• I overloaded OP's decorateGraph function to work with IGVF2* color spec conventions. See the testing file.