graph - 计算图的自同构组/检查两个图是否等距（DAG）

Question

这必须是一个经过充分研究的问题，但我正在努力研究它。

我从这里开始，但我正在寻找算法来研究和实现。 http://en.wikipedia.org/wiki/Graph_isomorphism_problem

例如，如果我有两个 DAG（有向无环图），我想标记/删除其中一个，因为它只是第一个的旋转/反射。在同一个自同构组中意味着它们可以被旋转/反射以具有完全相同的邻接矩阵，对吗？

Answer 1

你可以使用 nauty 或 saucy 算法来计算这个问题。

此链接可能对您有所帮助。:)

Nauty:
http://cs.anu.edu.au/~bdm/nauty/
http://cs.anu.edu.au/~bdm/nauty/

Saucy:
http://vlsicad.eecs.umich.edu/BK/SAUCY/

在 saucy 页面中还有一个可用的现成工具列表（尤其是基于 linux 的操作系统中的命令行）。