Can I make IsomorphicGraphQ consider other properties besides the EdgeRules?

Question

Consider two graphs, which are isomorphic to each other based on the vertices and edges,

g1 = Graph[{1, 2, 3}, {1 -> 2, 2 -> 3, 3 -> 2, 3 -> 1, 2 -> 1},
   VertexWeight -> {"A", "B", "C"},
   EdgeWeight -> {"a", "b", "c", "d", "e"},
   EdgeLabels -> "EdgeWeight", VertexLabels -> "VertexWeight"];
g2 = Graph[{1, 2, 3}, {2 -> 1, 1 -> 2, 1 -> 3, 3 -> 1, 3 -> 2},
   VertexWeight -> {"A", "B", "C"},
   EdgeWeight -> {"a", "b", "c", "d", "e"},
   EdgeLabels -> "EdgeWeight", VertexLabels -> "VertexWeight"];
{g1, g2}

I get the following result from IsomorphicGraphQ,

IsomorphicGraphQ[g1, g2]
(* True *)

But I would like it to return False in this case since the weights for the vertices and edges do not match after renaming the vertices according to

FindGraphIsomorphism[g1, g2]
(* {1 -> 2, 2 -> 1, 3 -> 3} *)

If you ignore the Weights then the two graphs are identical. How can I write a test, hopefully one as fast as IsomorphicGraphQ, that will consider these other properties?

For testing purposes, this is a Graph that should be considered isomorphic to g1 if weights are considered.

g3 = Graph[{1, 2, 3}, {2 -> 1, 1 -> 2, 1 -> 3, 3 -> 1, 3 -> 2}, 
  VertexWeight -> {"B", "A", "C"}, 
  EdgeWeight -> {"a", "e", "b", "c", "d"}, EdgeLabels -> "EdgeWeight",
   VertexLabels -> "VertexWeight"]

Answer 1

What you are looking for is called isomorphism for coloured graphs. Both vertices and edges may be "coloured" with colours chosen from a discrete set, and only those isomorphisms are admitted which map a vertex (or edge) into another one that has the same colour.

Using edge/vertex weights for this is not really appropriate. These properties are meant to be real numbers and are used for graph distance or flow calculations. They are not taken into account during isomorphism, not do I think this would be a good design.

Actually as of version 10.4, Mathematica does not support isomorphism for coloured graphs. But the good news is that with some effort the coloured graph isomorphism problem can be mapped back to "plain" isomorphism. We have a post discussing this for vertex colouring only:

• Determining whether two $k$-chromatic graphs are isomorphic (respecting vertex coloration)

While reading @whuber's answer in that thread, keep in mind that he discusses a slightly different problem than what you are asking for. In standard coloured graph isomorphism (and also in your question), a "red" vertex may only map into another "red" one. "Red" and "blue" are not interchangeable. In @whuber's answer it is allowed to first permute the colour names in some way, thus a solution where all red nodes map to blue, all blue ones to green and all green ones to red is accepted.

It is possible to modify his method to avoid this by making the special colour marker nodes distinguishable (e.g. by attaching further nodes to them).

Once we have isomorphism with vertex colouring, we can also handle edge colouring: just insert a specially coloured vertex into the middle of each coloured edge.

Doing all these problem remappings without making mistakes is however difficult. What I suggest instead is that you use the IGraph/M package, which includes several isomorphism algorithm that support colouring.

_{Note 1: I am the author of IGraph/M.
Note 2: Use IGraph/M 0.2.2 or later as earlier versions cannot handle vertex and edge colouring simultaneously due to a bug.}

As of version 0.2.2, IGraph/M includes these isomorphism algorithms with the following special features:

• Bliss: vertex colouring, automorphism group computations, canonicalization, very fast

• VF2: vertex colouring, edge colouring, subgraph isomoprhism

• LAD: vertex colouring, subgraph isomorphism, supports restricting matches to induced subgraphs

Since you want both edge and vertex colouring, use VF2.

You can do this:

IGVF2IsomorphicQ[
  {g1, "VertexColors" -> {1, 2, 3}, "EdgeColors" -> {1, 2, 3, 4, 5}}, 
  {g2, "VertexColors" -> {1, 2, 3}, "EdgeColors" -> {1, 2, 3, 4, 5}}]

"Colours" must be specified as integers, in the same order as vertices/edges appear in VertexList/EdgeList.

We can also use an association to specify colours:

IGVF2IsomorphicQ[{g1, "VertexColors" -> <|1 -> 1, 2 -> 2, 3 -> 3|>, 
  "EdgeColors" -> <|1 \[DirectedEdge] 2 -> 1, 
    2 \[DirectedEdge] 3 -> 2, 3 \[DirectedEdge] 2 -> 3, 
    3 \[DirectedEdge] 1 -> 4, 2 \[DirectedEdge] 1 -> 5|>}, {g2, 
  "VertexColors" -> <|1 -> 1, 2 -> 2, 3 -> 3|>, 
  "EdgeColors" -> <|2 \[DirectedEdge] 1 -> 1, 
    1 \[DirectedEdge] 2 -> 2, 1 \[DirectedEdge] 3 -> 3, 
    3 \[DirectedEdge] 1 -> 4, 3 \[DirectedEdge] 2 -> 5|>}]

In this case those vertices/edges for which no colour was given are assumed to have colour 0.

Details are given in the package documentation.

You might wonder why the function doesn't read colours from vertex/edge properties. Working with properties is still buggy and unreliable in v10.4.1. I am not willing to put up with the problems, so I'll wait until this area of functionality is cleaned up.