比较两张图 [英] 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.

图形顶点可以最多8个邻居/边缘和顶点可以具有0或1.旋转图仍然是相同的图形，每个图形具有相同数量的顶点。

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.

这种方法太慢了。在不丢弃确实不同的图形的情况下，需要40多秒的时间来比较几百个图形，其中约有100个顶点。

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.

我正在考虑为每个图形计算唯一的值图然后只比较值。我试图做到这一点，但是我只是设法得出值，如果相等，那么图可能是相等的，如果值不同，那么图也不同。

如果我的程序比较这些值，那么它计算大约2.5秒的时间（这仍然太慢）。

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).

什么是最佳/最快的方法来添加顶点到这个图表和更新边缘？现在我将这个图存储在 std :: map< COORD，Vertex> 因为我认为搜索顶点更容易/更快。

COORD是游戏板上的顶点位置（顶点的位置在比较图中无关）和顶点是：

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];
};

此图表示Gomoku的当前板状态，包含板边缘和板尺寸n * n其中n可以达到2 ^ 16。

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.

推荐答案

首先，你需要让每个图形成一个一致的表示，这样做的自然方法是创建图的有序表示。

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.

然后通过将其邻居值（其为0和1）映射到二进制数然后用于执行的每个具有相同数量的邻居的每个节点组在组节点之间的顺序。

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

这篇关于比较两张图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！