algorithm - 如何根据顶点数据对每个顶点附加数据的无向图(可能是循环图)进行唯一排序

Question

我正在编写软件，根据图形拓扑结构和每个原子的化学元素来表征化学结构。需要对它们进行唯一排序，以评估两个键图是否相等。我用值数组和第一个数组中的索引对数组表示图形，例如

    vertices = {"C", "H", "H", "H", "H"};
    edges = {{0, 1}, {0, 2}, {0, 3}, {0, 4}};

首先对图进行排序 w.r.t.顶点值(在元素周期表中的位置)和第二个 w.r.t.边缘。每条边首先用较低值的索引表示，边根据 1) 左索引和 2) 右索引按字典顺序排序。因此，上述甲烷分子的有序形式为:

    vertices = {"H", "H", "H", "H", "C"};
    edges = {{0, 4}, {1, 4}, {2, 4}, {3, 4}};

它被排序是因为交换两个顶点，重新标记引用它们的边并重新排序这些边，要么保持表示不变，要么降低它的顺序。遵循这个约定，很容易小于比较图的两个排序来评估哪个更好，但是提出一个有效的排序算法比看起来更微妙，因为每个顶点交换都会导致边的重新标记，随后通过可能交换每个重新标记的边中的第一个和第二个元素以及对边列表进行排序。到目前为止，我一直使用蛮力方法遍历所有等值顶点的排列，但由于这与顶点类型数量的阶乘成比例，因此它已经为适度数量的相同类型的顶点撞上了计算砖墙。

在我看来，一定有人解决了这个问题，但在寻找解决方案时，我只能找到拓扑类型的 DAG，这是一个完全不同的问题，而且非常专业的基于有机化学的解决方案太重了对我的目的而言似乎不必要且无用的领域特定知识。

Answer 1

通过更多的研究，我发现这个问题被称为图规范化并且与图同构问题密切相关，它似乎是 NP 或 NP 完全，所以不幸的是并不像我希望的那么简单。

但是，存在一系列实用上成功的算法，其中 this recent paper是我找到的对当前知识的最好总结。该论文的作者还发布了一个开源现代 C++ 库，允许以模块化和可扩展的方式解决类似问题: https://github.com/jakobandersen/graph_canon .