如何用Dreadnaut/Auty判断p edge格式图同构？现有命令失效

问题原因 #

你之前的命令无法运行，是因为Dreadnaut默认是交互式环境，直接重定向输入时它不会自动完成操作并退出，需要明确的命令序列来驱动它完成图读取、规范形式生成和退出流程。

方法一：使用Dreadnaut生成规范形式并对比 #

步骤1：生成图的规范形式文件 #

通过管道传递命令序列给Dreadnaut，无需修改原输入文件：

# 生成graph1的规范形式
echo "read graph1.txt; can; write graph1.can; quit" | dreadnaut

# 生成graph2的规范形式
echo "read graph2.txt; can; write graph2.can; quit" | dreadnaut

命令解释：

• read graphX.txt：读取p edge格式的图文件
• can：计算图的规范形式（canonical form）
• write graphX.can：将规范形式写入文件
• quit：退出Dreadnaut

步骤2：对比规范形式文件 #

用diff命令检查两个规范形式文件是否完全一致：

diff graph1.can graph2.can

如果命令无输出，说明两个图的规范形式完全相同，即图同构；若有输出，则两图不同构。

方法二：使用Auty直接判断同构 #

Auty（autograph）工具支持直接读取p edge格式的文件并判断同构，步骤更简洁：

autograph -i edge graph1.txt graph2.txt

命令参数解释：

• -i edge：指定输入文件为p edge格式
• 后续两个参数为需要对比的图文件

执行后工具会直接输出结果：

• 显示Isomorphic则两图同构
• 显示Not isomorphic则两图不同构

内容的提问来源于stack exchange，提问作者ivoene