How to test graph isomorphism with edge labels using IGraph?

Usage
1

Is it possible to check for isomorphism of undirected graphs with edge labels (no vertex label) in IGraph?
I have read the documentation on isomorphism in the package but haven’t figured out how to do it.
Here is an example with three graphs:

g1 = EdgeTaggedGraph[{UndirectedEdge[0, 1, a], 
    UndirectedEdge[0, 1, b], UndirectedEdge[0, 2, c], 
    UndirectedEdge[0, 2, e], UndirectedEdge[0, 3, d]}, 
   EdgeLabels -> "EdgeTag"];
g2 = EdgeTaggedGraph[{UndirectedEdge[0, 1, c], 
    UndirectedEdge[0, 1, e], UndirectedEdge[0, 2, a], 
    UndirectedEdge[0, 2, b], UndirectedEdge[0, 3, d]}, 
    EdgeLabels -> "EdgeTag"];

g3 = EdgeTaggedGraph[{UndirectedEdge[0, 1, d], 
    UndirectedEdge[0, 1, e], UndirectedEdge[0, 2, a], 
    UndirectedEdge[0, 2, b], UndirectedEdge[0, 3, c]}, 
    EdgeLabels -> "EdgeTag"];
{g1, g2, g3}

image
image1165×334 47.3 KB

g1 and g2 are isomorphic when considering edge labels.
g1 and g3, or g2 and g3, are not isomorphic when considering edge labels.

IGIsomorphicQ returns True for all of them, as it does not take edge labels into account.

2

IGraph/M’s isomorphism functions never take the EdgeLabel property (which is solely for display purposes) into account, but they do provide a way to supply “colours” for isomorphism algorithms. You will find examples in the documentation. Edge colours are only supported by the VF2 algorithm.

Provide edge colours in the order of the edge list:

In[266]:= IGVF2FindIsomorphisms[
 {CycleGraph[3], "EdgeColors" -> {1, 1, 2}},
 {CycleGraph[3], "EdgeColors" -> {1, 2, 1}}
 ]

Out[266]= {<|1 -> 2, 2 -> 1, 3 -> 3|>, <|1 -> 2, 2 -> 3, 3 -> 1|>}

Provide edge colours as associations. Some edges have no assigned colours:

In[268]:= IGVF2FindIsomorphisms[
 {CycleGraph[3], "EdgeColors" -> <|1 \[UndirectedEdge] 2 -> 1|>},
 {CycleGraph[3], "EdgeColors" -> <|2 \[UndirectedEdge] 3 -> 1|>}
 ]

Out[268]= {<|1 -> 2, 2 -> 3, 3 -> 1|>, <|1 -> 3, 2 -> 2, 3 -> 1|>}

Unfortunately, the graphs you show have multi-edges and our VF2 implementation does not support these. A workaround you can use is to somehow encode each set of parallel edges, with their associated colours, to a single edge with a new colour. I don’t have time to code this up this morning, but I hope the answer is useful.

3

Thanks for the information. Could you explain how to encode parallel edges? Simply treating all parallel edges as a single edge with the sum of their colors doesn’t always work.

4

No, you would need to produce a new unique colour ID for each colour combination that is found in the original two graphs. I would simply check what colour combinations are present, list them, and and assign a unique integer to each.

5

Here’s a sloppy example that assumes that:

  • There are no isolated vertices (since we build graphs from edges only)
  • The “edge colour” is the edge tag
simplifiedGraphs = Table[
  GroupBy[EdgeList[g], Sort@Drop[#, -1] & -> Last],
  {g, {g1, g2, g3}}
  ]

colorCombinations = Union@Catenate@simplifiedGraphs

asc = AssociationThread[colorCombinations, 
  Range@Length[colorCombinations]]

Graph[#, EdgeLabels -> "EdgeTag"] & /@ 
 KeyValueMap[Append[#1, asc[#2]] &] /@ simplifiedGraphs
1 Like
6

Thank you for the idea. I was considering the subdivision approach to convert it into a simple graph, but your method seems cleaner.

8

I’m sorry, I reverted the deletion of your last question because I do think it is related and relevant.

The answer is basically the same:

You can use the IGVF2...Subisomorphisms functions instead of the IGVF2...Isomorphisms to find a subgraph as part of a larger graph.

Currently, of the algorithms implemented in igraph, only VF2 supports edge colours, and it only handles simple graphs. So an encoding of multi edges similar to what I suggested above would be necessary.

Be aware that if you are requesting an exhaustive listing, all mappings will be returned. For example,

image
image720×360 2.99 KB

contains the triangle subgraph in 12 times, not just twice, according to these functions. This is because the a triangle maps to itself in 6 ways.

The same limitations apply as with the VF2 isomorphism functions.

9

Thanks again for the extra info!
I realized after posting that the answer was already in the docs, so I deleted it.