能否为任意顶点边标记图构造规范SMILES字符串？

结论 #

存在可证明满足要求的算法，这类算法的核心本质是将通用带标记图的规范标号（Canonical Labeling）能力与SMILES字符串的生成规则结合。

具体原理 #

• 你描述的带顶点、边标记的有向图的规范映射需求，本质是经典的带标记图同构的衍生问题：只要能找到一套规则，给所有同构的图输出唯一的顶点排序，再基于这个固定排序做SMILES的深度优先遍历生成字符串，就能保证同构图的输出完全一致。
• 现有化学领域常用的规范SMILES算法，其实就是这套逻辑针对分子图（顶点为原子类型、边为键级，附带电荷、手性等顶点扩展标记）的特化实现，只是默认加入了很多化学领域的先验约束，不支持通用图场景。

可行的实现路径 #

1. 首先调用成熟的通用带标记图规范标号算法获取全局唯一的顶点顺序
   • 普通实用场景下直接用1阶Weisfeiler-Lehman（WL）测试即可，它可以对绝大多数非人工构造的图输出可证明同构一致的顶点排序，计算效率很高
   • 如果需要覆盖所有理论场景的正确性，可以用NAUTY、BLISS这类精确图同构求解工具的规范标号输出，这类工具的结果是严格可证明同构图输出完全一致的，只是在处理超大图时计算复杂度更高
2. 基于得到的规范顶点顺序，按照标准SMILES的遍历规则生成字符串即可：
   • 固定从排序最靠前的顶点开始深度优先遍历
   • 边的方向和边标记可以自定义统一的编码规则写入字符串（比如有向边用>标记、不同边类型加对应的单字符前缀），只要规则固定，同构的图生成的字符串必然完全相同

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