5
$\begingroup$

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}

Mathematica graphics

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

Mathematica graphics

$\endgroup$
  • $\begingroup$ Possible duplicate: (22813) $\endgroup$ – Mr.Wizard Jul 20 '16 at 7:37
  • 1
    $\begingroup$ @Mr.Wizard It is in principle a duplicate, but I'm afraid that there is so much complexity in the constructions shown there that there's room for a separate question. That question is only about vertex colouring. This one is both about vertex and edge colouring. In principle isomorphism with edge colouring can be remapped into a problem dealing only with vertex colouring. Then we could use whuber's construction, but we must be very careful about the precise interpretation of the problem: his solution allows colour renaming, while most interpretations of this problem don't. $\endgroup$ – Szabolcs Jul 20 '16 at 8:01
  • $\begingroup$ I'll write a better answer here eventually, but not right now ... $\endgroup$ – Szabolcs Jul 20 '16 at 8:02
6
$\begingroup$

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:

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.

$\endgroup$
  • $\begingroup$ I see your point about the weights should be numbers, I just didn't know where else to put a per-edge and per-vertex property. In my application, I have vertex types (elements) and edge types (bonds), and I just need a way of comparing two graphs (molecules) to see if they are the same. I could easily map these types to integers though. $\endgroup$ – Jason B. Jul 19 '16 at 20:52
  • $\begingroup$ @JasonB There's a bug with simultaneously using vertex and edge colours. I'll release a fix on the weekend. After that you will be able to do IGVF2IsomorphicQ[{g1, "VertexColors" -> {1, 2, 3}, "EdgeColors" -> {1, 2, 3, 4, 5}}, {g2, "VertexColors" -> {1, 2, 3}, "EdgeColors" -> {1, 2, 3, 4, 5}}]. You can also specify colours as an association. For now, you can only use either vertex colours or edge colours, but not both. $\endgroup$ – Szabolcs Jul 19 '16 at 22:10
  • 1
    $\begingroup$ this is great, I made it work to show that g1 and g2 are not the same, but g3 and g1 are the same. I'm definitely a novice when it comes to graphs, so I may use the wrong nomenclature (perhaps isomorphic isn't the word I need) but I need some way to compare molecular graphs and detect whether two forms are the same, or are structural isomers. $\endgroup$ – Jason B. Jul 20 '16 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.