CODEWITHSUNDEEP
c++algorithmdata-structuresgraph
Michał Iwanicki
Michał Iwanicki

Reputation: 103

Comparing two graphs

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:

graph example

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.

Upvotes: 8

Views: 8832

Answers (4)

Tushar
Tushar

Reputation: 357

This is a possible suggestion for optimization.

I would recommend to try memoization (store all the vertex pairs that are found to be different), so that the next time those two vertices are compared you just do a simple lookup and reply. This may improve the performance (or worsen it), depending on the type of graphs you have.

Upvotes: 1

ipc
ipc

Reputation: 8143

You have found out yourself that checking isomorphism can be done by checking one bord with all the n*n shifts times 8 rotations of the other, thus having O(n^3) complexity.

This can be reduced to O(n^2). Let's shift only in one direction, say by moving the x axis. Then we only have to find the proper y-offset. For this, we concatenate the elements as follows for both graphs:

. . 1 .            0 . . 3
0 1 . .     =>     0 1 2 .     =>     0 3 0 1 2 0 2
. 0 . .            0 . 2 .
_______            
1 2 3 4            ^---- a 0 indicates start of a row

We get two arrays of size n and we have to check whether one is a cyclic permutation of the other. For this, we concatenate array a with itself and search for the other.

For example if the two arrays would be a=0301202 and b=0203012 we search for 0203012 in 03012020301202 using KMP or similar, which runs in O(n + 2n)=O(n) time (we can get rid of the whole preprocessing since the first array always is the same).

Combining this O(n) x-check with the n y-shifts and the 8 rotations gives O(n^2) overall complexity by using O(n) additional space.

Upvotes: 0

abeln
abeln

Reputation: 3759

The problem you're trying to solve is called graph isomorphism.

The problem is in NP (although it is not known whether it's NP-Complete) and no polynomial time algorithm for it has been found.

The algorithm you describe seems to take exponential time.

Upvotes: 3

Gearoid Murphy
Gearoid Murphy

Reputation: 12116

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

Upvotes: 5

Related Questions