3
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ The most common data structures used for undirected graphs are probably adjacency lists and adjacency matrices, depending on your exact needs. If you were just using trees, you could use my favorite, Pruefer codes, but alas. $\endgroup$ Nov 6, 2019 at 0:43
  • $\begingroup$ Calculate the eigenvalues of the adjacency matrix of each graph. Just because two graphs have the same spectrum ... does not mean they are isomorphic! But this trick has work well for me in a similar situation. $\ddot \smile$ $\endgroup$ Nov 6, 2019 at 1:37
  • $\begingroup$ @DonaldSplutterwit Unfortunately I have no idea how to do any of that :/ I only took single-variable calc, and that was years ago. Does "isomorphic" mean the same thing as the way I use "identical"? $\endgroup$
    – Matt
    Nov 6, 2019 at 21:26
  • $\begingroup$ Yeah Isomorphic $=$ Identical $=$ the same as unlabelled graphs. The routines to calculate the eigenvalues of symmetric matrix are quite tough ... you can probably find them on the net somewhere ? $\endgroup$ Nov 6, 2019 at 21:40
  • $\begingroup$ @DonaldSplutterwit how do I get the adjacency/symmetric matrix of a graph? $\endgroup$
    – Matt
    Nov 7, 2019 at 19:03

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.