c++ - Comparing two graphs -

i need compare many graphs(up few millions graph comparisons) , wonder fastest way that.

graphs' vertices can have 8 neighbours/edges , vertex can have value 0 or 1. rotated graph still same graph , every graph has identical number of vertices.

graph can this:

right i'm comparing graphs taking 1 vertex first graph , comparing every vertex second graph. if find identical vertex check if both vertices' neighbours identical , repeat until know if graphs identical or not.

this approach slow. without discarding graphs sure different, takes more 40 seconds compare several thousands graphs 1 hundred vertices.

i thinking calculating unique value every graph , compare values. tried this, managed come values if equal graphs may equal , if values different graphs different too.
if program compares these values, calculates in 2.5 second(which still slow).

and best/fastest way add vertex graph , update edges? right i'm storing graph in std::map< coord, vertex > because think searching vertex easier/faster way.
coord vertex position on game board(vertices' positions irrelevant in comparing graphs) , vertex is:

struct vertex {     player player; // player enum, first = 0, second = 1     vertex* neighbours[8]; }; 

and graph representing current board state of gomoku wrapping @ board edges , board size n*n n can 2^16.

i hope didn't made many errors while writing this. hope can me.

first need each graph consistent representation, natural way create ordered representation of graph.

the first level of ordering achieved grouping according number of neighbours.

each group of nodes same number of neighbours sorted mapping neighbours values (which 0 , 1) on binary number used enforce order amongst group nodes.

then can use hashing function iterates on each node of each group in ordered form. hashed value can used provide accelerated lookup