Comparing two graphs

Question

I need to compare many graphs(up to a few millions graph comparisons) and I wonder what is the fastest way to do that.

Graphs' vertices can have up to 8 neighbours/edges and vertex can have value 0 or 1. Rotated graph is still the same graph and every graph has identical number of vertices.

Graph can look like this:

Right now I'm comparing graphs by taking one vertex from first graph and comparing it with every vertex from second graph. If I find identical vertex then I check if both vertices' neighbours are identical and I repeat this until I know if graphs are identical or not.

This approach is too slow. Without discarding graphs that are for sure different, it takes more than 40 seconds to compare several thousands graphs with about one hundred vertices.

I was thinking about calculating unique value for every graph and then only compare values. I tried to do this, but I only managed to come up with values that if are equal then graphs may be equal and if values are different then graphs are different too.
If my program compares these values, then it calculates everything in about 2.5 second(which is still too slow).

And what is the best/fastest way to add vertex to this graph and update edges? Right now I'm storing this graph in std::map< COORD, Vertex > because I think searching for vertex is easier/faster that way.
COORD is vertex position on game board(vertices' positions are irrelevant in comparing graphs) and Vertex is:

struct Vertex
{
    Player player; // Player is enum, FIRST = 0, SECOND = 1
    Vertex* neighbours[8];
};

And this graph is representing current board state of Gomoku with wrapping at board edges and board size n*n where n can be up to 2^16.

I hope I didn't made too many errors while writing this. I hope someone can help me.

Answer 1

First you need to get each graph into a consistent representation, the natural way to do this is to create an ordered representation of the graph.

The first level of ordering is achieved by grouping according to the number of neighbours.

Each group of nodes with the same number of neighbours is then sorted by mapping their neighbours values (which are 0 and 1) on a binary number which is then used to enforce an order amongst the group nodes.

Then you can use a hashing function which iterates over each node of each group in the ordered form. The hashed value can then be used to provide an accelerated lookup