针对《寻找缺失的数据类型》一文，我收到了很多反馈。下面摘录了其中一些最有意思的回复。

博文回应

• “缺失”的图数据类型早已存在。它在 70 年代就被发明了，关于 datalog。

邮件与评论

引号内的内容均为原文照录。

GraphBLAS

我叫 Michel Pelletier，是 GraphBLAS API 标准及 Python 绑定的贡献者之一。

祝贺你的博客登上了 HN 首页。我在那边回复了一些信息，我觉得可能对你的问题有用，但淹没在了大量讨论中。我注意到你邀请读者给你发邮件，所以决定直接把这些信息发给你。

你所缺失的图数据类型，其实就是你已经提到过的——矩阵。你在博文中提到了邻接矩阵，但在你的语境里，它们只被当作一种存储格式，而非图本身。但图与矩阵在概念和代数上是同构的。所有图，因而所有复合数据结构，在数学上都是矩阵，反之亦然。超图和多重图则通过“关联矩阵”来表示，也就是用两个矩形矩阵来表示节点到边、边到节点的邻接关系。

由超级计算中心主任、MIT 林肯实验室的 Jeremy Kepner 博士牵头，一大批研究人员合写了一篇非常出色的入门论文：

https://arxiv.org/pdf/1606.05790.pdf

用矩阵的思维在计算机上处理图的问题在于，大多数图是稀疏的，而大多数矩阵库（如 numpy）是稠密的。这使得使用邻接矩阵的代价非常高，因为稠密矩阵中的大部分“空间”最终都是零。这极其低效，也无法有效利用冯·诺依曼架构典型的缓存层次。这两个世界尚未完全融合。

不过，围绕高效稀疏矩阵计算，进而围绕稀疏图分析，已经有了大量的研究与开发。虽然这两者看似不同，实则是一回事：矩阵乘法就是在图上的一步广度优先遍历。这正是二者同构性的体现。大量机器学习和人工智能研究同时涉及稀疏矩阵和图，而这些研究在提升两者性能的目标上是高度统一的。

关于这一点，我经常被问到的一个问题是“为什么”。为什么要用线性代数公式，而不是写一个遍历节点和边的函数？其中一个最重要的答案是在超大规模图上的并行化。当图变得非常非常大，拥有数十亿甚至数万亿条边时，你需要高效地划分算法的工作量。你打算怎么做？为每条边都 fork 一个任务？用线程池？如何高效地调度工作、划分图？现在再在 CUDA 上实现一遍……即便对最聪明的程序员来说，这个问题也几乎无解。

有了 GraphBLAS，图操作就是一个线性代数公式，会被分解成一系列矩阵乘法，你只需写出类似 Ax = b 这样的式子，底层库就会想办法在特定的目标架构上以最高效的方式完成计算。无论是在 Chromebook 上还是在超级计算机上运行，代码都不用变，变的只是机器能处理更大图的能力。你可以把 GraphBLAS 看作一种语言，它不仅能根据底层架构，还能根据你输入问题的形态和类型进行“即时编译”。由于线性代数是数学、科学和工程的通用语言，这项技术自然可以应用于大量现有工作中。

所以想把这些分享给你，祝你在这一主题上的进一步探索一切顺利。如果你想了解更多，我随时乐意交流，作为 C API 委员会的成员，推广这项技术是我的工作之一，我也很乐意介绍它。

谢谢！

Gremlin

在文章的早期草稿中，我曾谈到 Apache 的图计算框架 TinkerPop 及其查询语言 Gremlin。最终版本中我删掉了这部分，不少人注意到了这个缺失。下面是一条相关回复。

你提到了 Cypher，却没有谈 Gremlin，它是一种面向 Neo4j/TinkerPop 的、表达能力很强的图查询语言：

https://tinkerpop.apache.org/

它曾被用于驱动被 ShiftLeft 收购的 Joern SAST 工具，我想在金融领域也用得很多。

我上次用它来为 Maven 上的所有软件包及其相互依赖关系建了一个图。

它对编程语言的绑定做得很好——我用的是 Python Gremlin，这样就能用熟悉的脚本语言来驱动它，因为默认的 REPL/脚本语言是 Groovy，我用得不太顺手。

你可以在用 Gremlin 查询图和用 Python 进行“常规”命令式脚本编写之间来回切换，然后基于结果再做进一步查询。感觉非常自然。

我不太清楚它在全图算法方面的现状——我一直更关注基于遍历的查询，而不是像中心性这样的全图统计指标。

魔方

我是因为 CodeProject 新闻通讯的链接才看到你那篇关于图缺失软件库的文章。文章写得非常精彩。我远不及你写作时咨询的那些人那般厉害，不过我还是想再举一个例子，说明为图创建通用软件库有多困难。具体来说，我是一个非常松散的小团体的一员，多年来我们一直在用计算机研究魔方的数学。

魔方背后的数学叫群论，而你能用群做的事之一，就是用一种叫凯莱图的图把它们描绘出来。那个无所不知的 Google 是这样描述的：“凯莱图常常被用来通过图的形式来呈现群的抽象结构，使其直观可见。当群 G 被呈现为凯莱图时，诸如其大小或生成元数量等性质就变得更容易考察。”具体来说，魔方的每一种可能状态都可以在凯莱图中表示为一个节点，而相邻节点就是只需一步就能到达的状态。你在文章中提到了 15 拼图。碰巧有一位魔方研究者为 15 拼图写了一个完整且非常快速的求解器。而事实证明，与魔方凯莱图的大小相比，15 拼图的规模简直是九牛一毛。

无论如何，我从 1985 年起就一直在写代码研究魔方。这不仅仅是为了“解”魔方，那其实相当容易。而是要为那近 10^20 种状态中的每一种，确定解开它所需的最少步数。这个问题至今仍未解决，仅仅是因为规模太大了。已经确定的是，任何状态都可以在 20 步或 26 步内解开，具体取决于你如何计算一步。但这与为每一种可能状态找到所需步数最少的最优解，并不是一回事。

无论如何，根据大量经验我知道，为了以任何切实可行的方式解决这个问题，我不得不开发非常特定于魔方的数据结构。关键问题在于（这里引用你文章中的话）“性能太重要了”。我找不到任何能满足我需求的库，所以只好自己造。

感谢你的精彩文章，

Jerry

我请他进一步解释“20 步或 26 步”是什么意思，以及能否多分享一些他使用的数据结构。他的回复是：

正如你猜到的，单次半圈旋转算作一步还是两步，是“什么算作一步”的主要例子。如果你只把四分之一圈旋转算作一步，那就叫四分之一转度量。在这种度量下，任何状态都可以在 26 步内解开。如果你把四分之一圈和半圈旋转都算作一步，那就叫面转动度量。在这种度量下，任何状态都可以在 20 步内解开。但对于什么算作一步，还有其他定义方式。魔方在任何方向上都有三层。通常你只把外层的转动算作一步，比如顶层和底层，而不算顶层与底层之间的中间层，或者右层和左层，而不算它们之间的中间层。但有时候把中间层的转动也算作一步也很有意思。另一种变体是“卡轴”问题，即假装其中一个轴被卡住了。例如，你不动顶面，只转动魔方另外五个面上的层。在这种变体下，你仍然可以到达所有可能的状态，但凯莱图不再具有轴都没卡住时的那种对称性。而且，用卡轴的方式解魔方，所需步数可能远多于标准的 20 步或 26 步。

我觉得魔方并没有什么标准数据结构。每个研究魔方的人都有自己的那一套，只不过显然，任何忠实表示魔方的数据结构，都必然在某种程度上与其他忠实表示魔方的数据结构同构。一个很大的区别在于，数据结构是只包含状态，还是同时包含状态和走法。例如，前面顺时针连续转两下四分之一圈，与前面逆时针连续转两下四分之一圈，会得到相同的位置。在凯莱图中，如果继续下去，这些走法序列会形成一个环。这个环是一个四步循环（4-环）。那么，你是同时存储走法和状态，还是只存储状态？

我真的不知道其他人的数据结构是如何处理这些问题的。就我自己而言，我并不显式地存储整个凯莱图。相反，我存储状态，并且为每个状态存储与每个可能走法对应的一个比特，用来指示该走法是让你离已解状态更远还是更近。在四分之一转度量下，每个状态有 12 个这样的比特，在面转动度量下则有 18 个。这些比特隐式地定义了一个凯莱图，但我并不显式地存储这个图。研究这个问题的其他人会谈到使用规范走法序列，例如你可以对前面连续做两次顺时针转动，但不能对前面连续做两次逆时针转动。我用我的比特做了类似但不完全相同的事情。

另一个问题是我需要一种树结构，而树可以被看作图的一种特例。也就是说，树就是指定一个节点为根节点且图中没有环的图。我不得不自己实现了一种树结构。我所需的树结构是这样产生的：标准魔方上有 54 个色块。在标准的数学模型中，每个面中心的色块不动，剩下 48 个会动的色块。在这 48 个中，24 个位于 3x3 方块的角上，24 个位于边上。角上的色块和边上的色块互不相交，所以我通过给每个角上的色块标上 A 到 X 的字母、给每个边上的色块也标上 A 到 X 的字母来表示一个魔方状态。于是每个状态就是一对有序的“单词”，每个单词由 24 个字母组成，且每个字母在每个单词中恰好出现一次。

那么我为什么需要树呢？因为我需要能够非常快速地找到这些“单词”。这就像在拼写检查词典中快速查找单词一样。按理说，树中的每个节点需要有 24 个指向树中其他节点的指针。但与真实拼写检查词典中的真实单词不同，每个字母在每个单词中只能出现一次。所以当我越接近树的叶节点时，每个节点就会主要由空指针组成，这是对非常宝贵的内存的巨大浪费。因此，我不得不创建一种树结构来存储这些状态以便快速检索。没有任何标准库例程在速度上够快、在内存上够省。

所以本质上我有两层叠加的数据结构。其中一个用比特开关来定义魔方的凯莱图，另一个则用类似拼写检查词典的树来非常快速地定位特定状态。而树本身就只是图的特例。

不知道这是否回答了你的问题，希望对你有帮助。

Jerry

图与知识库

Hillel——感谢你分享对图表示的探索，并清晰地解释了为什么没有明显的胜出者。我在想，你提到的问题是否大到了以至于排除了可行的替代方案。

我首先是以 Smalltalk 程序员的身份，之后又以 Wiki 创造者的身份来思考这个问题。两者都具有一种由零碎部分组装而成、并在持续使用中保持持久化的类图结构。围绕我最新 wiki 实现的小社区非常积极地想在页面中加入图，就像加入段落、图片、大纲和表格一样。我们已经通过使用 Dot 作为标记语言的 Graphviz 部分地实现了这一点。但这并不能像 yaml 或 csv 文件那样便于计算和共享。

我们最近开始采用这样的做法（例如在 JavaScript 中）把图表示为一个包含节点和关系数组的对象。空图会是这样：

{nodes:[], rels:[]}

节点和关系本身也是对象，各有一个表示类型的字符串和一个表示属性的附加对象，以及一些将它们关联起来的受管索引。这样就能方便地序列化为（无环的）JSON，这是一种广泛使用、足以应对以 KB 计的图的格式。

这些图很容易转换成 Neo4j 对象，我们在这方面有相当多的经验。更常见的情况是，我们避免在 wiki 本身之外再维护一个数据库。虽然我们也构建了一个简易的 Cypher 解释器，但发现它并不太有用。我们有一个令人惊讶的发现：我们更倾向于把许多小图合并成一个能解决手头问题的图，而不是构建一个庞大的 Neo4j 图再查询出解决同一问题所需的子图。

最近，我们开始基于问题空间中的横切关注点，把问题拆分为“方面”。我们可能会有几十甚至几百个这样的图。我们像浏览 wiki 那样浏览它们，其中相当于 wiki 链接的东西，来自于识别出同一个节点出现在尚未纳入的图中。这是一个“推荐”过程，查询被对推荐的选取与取消所取代，而正在进行的工作会通过在浏览器中运行的 Graphviz 立即渲染出来。

我在这封邮件开头原本对我们的图抽象有更完整的描述，但又删去了，因为不确定你是否会对我们的经验感兴趣。我也可以描述一些它已证明有用的应用，通常都涉及社区内的协作问题。

如果你觉得我们有兴趣上的重叠，我很乐意继续交流。感谢并致以最诚挚的问候——Ward

他的相关代码可在这里找到，附有文档和示例。后续邮件：

Hillel——我们正在寻找代表更大问题的各个方面的那些小图。这里有一个例子：当被要求审阅一篇将投往欧洲模式大会的论文时，我选择非常仔细地阅读它，并把其中模式里每一个“关系型”句子都映射出来。下面这张图中，黄色的部分显示了方面之间意外的重叠。

这个特定的图查看器经历了颇为曲折的历程：起初是 wiki 页面上的脚本；后来被提取为基于 Croquet 的、用于在线协作的独立网页应用；然后又在这里作为单用户“solo”应用回归到 wiki 中。它目前还不是一看就懂。但你可以通过 wiki 页面最后一段中的“open”链接打开它，那是我与一位同样对这类探索感兴趣的共同审稿人协作的页面。http://ward.dojo.fed.wiki/aspects-of-pattern-relations.html

另外还有两个类似的项目，展示了“方面”的不同可能性：将一年的最近更改切分开来，以及，用节点-关系注释来标注搜索引擎源代码，并通过 GitHub Actions 将它们提取为图文件。