比较两个图表

Question

我需要比较许多图表(高达数百万的图形比较),我想知道最快的方法是什么.

图形的顶点最多可以有8个邻居/边,顶点的值可以是0或1.旋转图仍然是相同的图,每个图都有相同数量的顶点.

图表可能如下所示:

现在我通过从第一个图形中取一个顶点并将它与第二个图形中的每个顶点进行比较来比较图形.如果我找到相同的顶点,那么我检查两个顶点的邻居是否相同,我重复这个,直到我知道图形是否相同.

这种方法太慢了.在不丢弃肯定不同的图形的情况下,将数千个图形与大约一百个顶点进行比较需要40多秒.

我在考虑为每个图计算唯一值,然后只比较值.我试图这样做,但我只设法得到的值如果相等则图表可能相等,如果值不同,那么图表也不同.
如果我的程序比较这些值,那么它会在大约2.5秒内计算所有内容(这仍然太慢).

将顶点添加到此图并更新边缘的最佳/最快方法是什么？现在我正在存储这个图,std::map< COORD, Vertex >因为我认为搜索顶点更容易/更快.
COORD是游戏板上的顶点位置(顶点的位置与比较图形无关),Vertex是:

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

此图表示Gomoku的当前电路板状态,板边缘和电路板尺寸为n*n,其中n可达2 ^ 16.

我希望在写这篇文章时我没有犯过太多错误.我希望有一个人可以帮助我.

Answer 1

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

第一级排序是通过根据邻居的数量进行分组来实现的。

然后通过将它们的邻居值（0 和 1）映射到一个二进制数来对具有相同邻居数的每组节点进行排序，然后使用二进制数来强制执行组节点之间的顺序。

然后你可以使用一个散列函数，它以有序的形式迭代每个组的每个节点。然后可以使用散列值来提供加速查找