How can I uniquely identify a graph?

Question

I'm working on a puzzle game that deals with a lot of graph theory concepts that are way beyond me. In essence, I need to find a way to succinctly identify a particular non-directional graph where the vertices have numerical values, with the end result being that I can compare two graphs and determine if they're identical. For example, I want to be able to compare these two graphs and recognize that they're the same:

5 -- 8 -- 3        8 -- 2
|\                 |   /
| \         <==>   |  / 
|  \               | /   
2 -- 8             5 -- 8 -- 3

A kind of "ideal" identifier would be some type of string that summarizes the value of each vertex and what values/vertices they connect to, but I don't know if that would even work or if there's already some mathematical way to describe a graph this way.

Any help would be greatly appreciated.

Answer 1

There are two problems to solve : firstly writing out a graph as a string (not so hard) and secondly making that identifier unique (very hard!).

There are various 'line notations' used in chemistry that might be suitable to your graphs. You seem to have vertex colors (the numbers 2, 3, 5, 8 in your example) but not edge colors, so it's slightly simpler.

I'm not sure how readable they will be. That depends on how large the graphs are of course. For example, this is the 'signature' of a cage-like molecule:

[C]([C]([C,2]([C]([C,3][C,4]))[C]([C,5][C,3]([C,6]([C,1]))))[C]([C]([C,7][C]([C,1][C,8]))[C,5]([C,8]([C,6])))[C]([C,2][C,7]([C,4]([C,1]))))

Perhaps I chose a particularly complex example, but still.

The second part is harder, but the good news is that you could just use an existing library to do it. One algorithm to do what is often called 'canonical labelling' (see also this page ) is partition refinement, for which one major implementation is nAUTy/traces.

For partition refinement, the vertex colors form the initial partition of the vertices. This partition is then refined until each vertex has a different unique label. A much simpler algorithm that is kind of related (that only works for non-regular graphs) is Morgan numbering. Roughly it goes:

1. Label the vertices with a starting value
2. Iteratively update the labels based on the labels of the neighbours of each vertex
3. Stop when the set of different labels is stable

Hmmm. Actually reading this blogpost it looks like the algorithm is more complex than that. However, for your example, we get:

$$\begin{array}{c|c|c} & \text{L0} & \text{L1} & \text{L2} \\ \hline \text{Vertex 1} & 3 & 11 & 27 \\ \hline \text{Vertex 2} & 8 & 16 & 40 \\ \hline \text{Vertex 3} & 5 & 23 & 69 \\ \hline \text{Vertex 4} & 2 & 15 & 53 \\ \hline \text{Vertex 5} & 8 & 15 & 53 \\ \hline \end{array}$$

where you can see that vertices 4 and 5 (at the bottom of your diagram on the left) end up with the same value. Using these vertex equivalence classes, we can make a canonical labelling.

Answer 2

If you can give each node a fixed ID, I think you can use below 2 items to represent a graph of your game:

• An adjacency matrix to represent the graph.
• And an array to represent the node numbers.

Note that each graph must have the same ID for the same Node. And the matrix and array should follow the same node order.

Since the representation is unique for different graph, you can simply compare the matrix and array data to determine if 2 graphs are the same. A bitwise XOR operation should be fast enough.

This method doesn't involve any big theory. The problem with this method is, there can be many graph representations which are equivalent from the topology view.