折腾了大半天我终于把那个依赖分析工具的核心数据结构从Graph换成AdjacencyMap又在另一边引入了Labelled Graph。回想起来这个选择过程比我预想的复杂得多——最开始我以为无非是“用哪种类型存图”的问题但在 Alga 里Graph、AdjacencyMap、Labelled Graph这三者的差异不只是“容器”的区别而是三种完全不同的建模思路。如果你也正在 Alga 类型的三种图之间犯迷糊这篇文章会把它们的内部逻辑、适用场景和迁移代价一次讲清楚。1. 一次依赖图建模引发的类型选择问题1.1 我最初想要的“图类型”是什么我的场景不算复杂要给一批内部组件建依赖关系每个组件是一个节点节点之间的连线表示“A 依赖 B”。我需要做这样几件事快速判断某个组件是否直接依赖另一个组件列出某个组件的所有反向依赖谁依赖它跑一遍拓扑排序找循环依赖最后把整张图导出成外部格式给别人看。当时我还处于“图 点 边”的惯性思维里觉得随便选一种图类型就行。但 Alga 给了我三个候选Graph、AdjacencyMap和Labelled Graph。它们的导出接口看起来高度相似都有vertex、overlay、connect、edge这类函数以至于我一度怀疑它们只是同一件事的三种写法。真正开始写代码以后我才意识到问题没那么简单。Graph是代数表达式式的图表示AdjacencyMap是邻接表式的规范表示Labelled Graph则允许给连接关系本身挂上额外信息。三种类型面对的操作难度完全不同构造一个图可能都很简单但查询、合并、比较、序列化的代价天差地别。1.2 为什么 Alga 的三种类型会让人纠结Alga 的核心卖点是用代数运算来描述图。它不像containers里的Map一样直接给你一个可读的内部结构而是用一组构造器把图“搭”出来。这在 Haskell 里很优雅但对刚上手的人来说很容易搞混到底什么时候该用Graph什么时候数据应该落在AdjacencyMap里如果边上有额外信息是不是一定要用到Labelled Graph从官方文档看Graph是基础类型AdjacencyMap可以看作它的“可执行版本”Labelled Graph则是给边加了标签的扩展。但文档不会直接告诉你Graph的随机查询性能在稠密图里可能会让你怀疑人生AdjacencyMap对顶点类型有Ord约束Labelled Graph一旦引入连“这两张图是否相等”这个问题都会变得更复杂。这些坑只有自己踩过一遍才会记住。2. Graph构造语义最纯粹但别拿它做随机查询2.1 四个构造器就是一套代数先看最基础的Graphdata Graph a Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)这个定义和普通的链表、树定义一样简单但它的含义是代数化的Empty表示空图里面没有任何顶点和边Vertex a表示只含有一个顶点a的图Overlay g1 g2表示把两幅图并排放在一起顶点集合取并集边集合也取并集Connect g1 g2表示把两幅图上下连接除了保留各自的内部边还从g1的每个顶点向g2的每个顶点连一条边。其中最关键的是Overlay和Connect两个运算。可以这样理解Overlay是普通的叠加Connect是“笛卡尔积式”的连接。用生活化的类比Overlay像是把两张透明胶片叠在一起两张胶片上的点都保留已有的连线也都能看见Connect则像是把左边一列按钮和右边一列按钮全部用线连起来形成的是完全二分关系。一个基础的边是这样构造出来的edge x y Connect (Vertex x) (Vertex y)节点之间的一条有向边本质就是“从单点 x 到单点 y 的连接”。三个以上的节点用Overlay组合即可。2.2 基于定律的变换与相等性Graph最有价值的地方是一组代数定律。比如Overlay x y Overlay y x -- 交换律 Overlay x (Overlay y z) Overlay (Overlay x y) z -- 结合律 Overlay x x x -- 幂等律 Connect x (Overlay y z) Overlay (Connect x y) (Connect x z)这些定律不是摆设它们让Graph的相等性建立在图论意义上的“同一张图”之上而不是语法上的“同一个表达式”。表达式Connect (Vertex 1) (Overlay (Vertex 2) (Vertex 3))和Overlay (Connect (Vertex 1) (Vertex 2)) (Connect (Vertex 1) (Vertex 3))写起来完全不同但表示的图是同一张。实际开发中这种“重写不改变语义”的能力非常好用。比如我要把一个复杂图结构拆成多个子图或者反过来把多个子图合并成一个大图在Graph层面可以直接依赖代数变换来保证结果正确。只要运算遵守这些定律重构时就不容易破坏图本身的意义。这也是Graph在形式化建模、验证场景下很难被替代的原因。2.3 随机查询是 Graph 的软肋但Graph的问题也很明显它本质是一棵表达式树不是索引结构。你要判断“1 到 2 之间有没有边”不能像查字典一样直接命中而是要递归遍历表达式遇到Connect再判断左右两边的顶点覆盖关系。这个过程在下面的例子里会非常难受bigGraph Connect (vertices [1..1000]) (vertices [1..1000])上面这个表达式用很短的代码就写完了但它在图论意义上包含的是 1000 个源顶点、1000 个目标顶点以及 100 万条边。如果我在这个Graph值上反复调用hasEdge或者枚举某个顶点的所有邻居指数级的重复遍历会立刻让程序变慢。问题不是 Alga 实现得不好而是Graph本来就不是为了“随机查询”而生的。所以我的建议是把Graph当作“结构表达式”来用。它擅长描述图怎么组合、怎么变换、怎么比较但如果你要把它当作常驻内存的查询结构尤其图很稠密或者查询次数很多时最好先把它转换到更合适的形式。3. AdjacencyMap把表达式编译成邻接表之后的收益3.1 邻接表表示与规范形AdjacencyMap的内部表示非常直白newtype AdjacencyMap a AdjacencyMap (Map a (Set a))它的意思就是对每个顶点用一个集合记录它能直接到达的邻居。这个表示有三个天然的好处查询某个顶点的所有邻居只需要一次Map查找然后拿到一个Set由于Set和Map本身会去重、排序同一张图只会对应一种AdjacencyMap表示不会出现 Graph 里那种“一个图有无数种表达式”的冗余判断两点之间是否有边本质就是在集合里做成员测试耗时远低于遍历表达式。Alga 把Graph转换成AdjacencyMap的过程本质上是对表达式做一次规约。Overlay合并两张邻接表Connect则是把所有左侧顶点的邻居集合都加上右侧顶点的全部顶点。这个过程会丢失“原始表达式长什么样”但换来的是一个干净、稳定、可以直接比较的图对象。3.2 查询、遍历、序列化都顺手了把图从Graph换成AdjacencyMap之后编程体验完全不一样。判断边、列举邻居、计算入度出度、做拓扑排序这些操作都变成了常规集合操作不需要在表达式树里做复杂的语义解释。我在那个依赖分析工具里写了这样的函数-- 伪代码风格示意查询反向依赖 reverseDeps :: Ord a a - AdjacencyMap a - Set a reverseDeps v g Set.filter (\u - hasEdge u v g) (vertexSet g)如果g是邻接表形式这个函数实现起来很直观如果g是Graph表达式每次hasEdge都可能要重新扫描整棵表达式树代码看起来一样背后性能差距却很大。在序列化方面AdjacencyMap也更好处理。要把邻接表转成 JSON、GraphML 或者自定义文本格式只需要遍历Map和Set天然适合外部系统交换数据。而Graph的表达式树虽然也能序列化但还原出来的仍然是一棵表达式树不一定是别人想要的“点边列表”。3.3 代价与约束不过AdjacencyMap不是免费的午餐。构造单个顶点的图需要往Map里插入键值构造一条边通常要更新两个方向的邻接关系所以它的插入和合并成本比Graph的常量时间构造要高。下面这张表反映的是我使用时的直观感受不同实现版本可能有细微差异但整体趋势是稳定的操作GraphAdjacencyMap构造edge x y常量时间只生成表达式多次Map/Set更新对数级成本合并两个图overlay常量时间构造树节点需要合并两个Map成本随规模增长判断两点是否相连遍历表达式可能重复计算Map查找加Set成员测试对数级枚举邻居需要从表达式中推导可能很慢直接取出Set线性于邻居数顶点类型必须有Ord实例是所有AdjacencyMap操作的前提。这一点很容易被忽略。如果你的顶点是自定义数据类型记得先派生出Ord否则代码会在类型检查阶段直接卡住。4. Labelled Graph当边也开始拥有信息时4.1 从一个带版本约束的依赖边说起在我们那个依赖分析工具里光是知道“组件 A 依赖组件 B”并不够。依赖通常是带版本约束的A 要求 B 的版本不小于某个值或者落在某个区间内。如果只用Graph或AdjacencyMap这条约束只能被“塞”到顶点或边的外部建模会很别扭。这时候Labelled Graph就有用了。Labelled Graph类型可以理解为在Graph的Connect上增加了一个标签参数data LabelledGraph e a Empty | Vertex a | Overlay (LabelledGraph e a) (LabelledGraph e a) | Connect e (LabelledGraph e a) (LabelledGraph e a)这里的e是每条连接上携带的标签。它可以是权重、颜色、版本区间也可以是表示“朋友”“关注”“拉黑”等语义的关系类型。于是依赖图变成了这样-- 示意代码用 Connect 构造带版本约束的依赖边 dependencyGraph Connect (VersionRange 2.0 3.0) (Vertex app) (Vertex lib)从结构上看Labelled Graph和Graph的区别只是Connect多了一个参数但正是这个参数让整个图的表达能力上了一个台阶。4.2 标签进入构造器之后的变化有了标签以后“存在一条边”这个命题本身变复杂了。在无标签图里Connect g1 g2表示所有左侧顶点都连到右侧所有顶点在带标签图里这个连接的每一条边都带着同一个标签e。如果你需要给不同边挂不同标签就不能只靠一个高层Connect还得用Overlay把单条带标签边组合起来。这一点直接影响相等性。两个带标签的图哪怕节点一样、边的连接端点一样只要边的标签不同它们就不是同一张图。在无标签的AdjacencyMap里两条平行的同向边会被Set自动折叠成一条但在Labelled Graph里如果两条边端点相同但标签不同它们是有可能同时存在的。这会带来两个结果建模能力更强多关系图、属性图都能表达算法更复杂很多原本简单的图算法都要把标签纳入考虑。比如“从 A 到 B 是否存在路径”要变成“是否存在满足某标签条件的路径”。4.3 带标签图的常见操作和坑我在实际使用中踩过的坑主要有三个。第一个坑是标签相等性。如果标签类型是自己定义的它必须有合理的Eq实例。否则两张“理应不同”的标签图可能会被判成相同或者相反。注意这里的相等是语义上的相等不是单纯构造器相同。第二个坑是顶点属性。Labelled Graph默认给边加标签并不直接给顶点加属性。如果还要给顶点挂额外信息我通常会把顶点类型改成一个包含 ID 和属性的记录类型data Package Package { packageId :: String, packageVersion :: Version }这样顶点本身变成一个大记录邻接关系和属性“长在一起”。好处是写起来自然坏处是查询某个 ID 对应的属性时还是要走一遍Map。图一旦变大顶点查重和属性更新都会比纯用 ID 当顶点更麻烦。第三个坑是标签与重边。使用带标签图时不要默认它会自动折叠重边。假设两条边都是a - b但一条权重是 1另一条权重是 2Alga 不会自作主张把它们合并成一条除非你在构造图之前就定义好标签的合并规则比如用加法处理权重。所以从无标签图迁移到带标签图时必须先想清楚“重边在我这个领域里是什么意思”。5. 三种图类型的能力边界与换算成本5.1 横向对比表把三种类型放在一起看能力边界会更清楚维度GraphAdjacencyMapLabelled Graph底层本质代数表达式树Map a (Set a)邻接表带标签的代数表达式树构造单条边成本常量时间对数级更新常量时间随机查询成本通常较高需要遍历/推导对数级查找通常比无标签版更高边标签支持不支持不支持原生支持相等性判断基于代数语义的公理推导直接比较规范邻接表需要考虑标签相等性顶点Ord约束构造时无要求查询/转换时有几乎所有操作都要求构造时无要求常用操作时有典型适用场景图结构设计、代数变换、验证算法、查询、序列化属性图、加权图、多关系图5.2 类型之间怎么转换Graph与AdjacencyMap之间可以互相转换。Graph转AdjacencyMap是一次规约把表达式变成邻接表AdjacencyMap转Graph则是把每一条邻接关系重新变成edge的组合。这两种转换都不是无代价的相当于对整张图做一次完整遍历所以不应该在热路径里频繁往返。Labelled Graph也可以丢掉标签得到一个普通图。反过来从普通图生成带标签图时标签必须由外部逻辑提供——Alga 不可能替你猜出每条边该挂什么信息。我的建议是在系统内部明确划分边界一个模块负责维护带标签的领域模型另一个模块负责把它投影成无标签邻接表再交给算法处理。这样既能享受标签的表达力又不至于让所有图算法都被标签处理拖累。5.3 选型决策清单经过这次重构我总结了一个简单的选型决策流程如果主要工作是构造图、合并图、比较图并且在思考“图应该怎么组合”而不是“怎么查得快”选Graph如果主要工作是判断边、找邻居、算度数、跑拓扑排序选AdjacencyMap如果边的类型/权重/关系种类本身就是领域模型的组成部分选Labelled Graph如果既要标签表达又需要高性能查询可以考虑把Labelled Graph作为模型层并在算法层投影到AdjacencyMap。不要一上来就选最强大的类型。表达力越强后续要承担的复杂度也越高。6. 迁移过程中的几个真实教训6.1 不要一上来就上 Labelled Graph我最初差点直接选用Labelled Graph因为觉得它“功能最全”反正版本约束迟早要加。但真写起来才发现带标签图让很多原本简单的操作都变重了判断两个节点是否有边要考虑标签合并两个图要考虑标签不同的边怎么处理打印图还要为标签设计文本格式。最后我不得不先把功能简化到无标签的AdjacencyMap上把算法跑通再在模型边界加上版本区间。先加标签再验证逻辑会平白多出很多调试成本。正确的路径是先确认“核心算法到底需要什么信息”不要为未来可能用到的东西提前引入复杂度。标签信息可以用一个单独的数据结构去维护把边和标签分开存放等确实需要整体建模时再迁移到Labelled Graph。6.2 把 Graph 当图纸把 AdjacencyMap 当台账我现在的工作习惯是把Graph当作“图纸”用来设计和检查图的结构关系把AdjacencyMap当作“台账”用来做查询、遍历和计算。具体来说当我要搭建一批节点和边时我会先写一个返回Graph的函数用vertex、overlay、connect把结构组合出来。这样做的好处是代码读起来像在描述关系而不是在操作集合。功能稳定之后再在算法入口处一次性把Graph转换成AdjacencyMap。这样两边的优势都能拿到结构表达靠代数性能计算靠邻接表。6.3 一个混合使用的习惯对于这个依赖分析工具我最终采用了混合方案。核心模型层保存Labelled Graph因为版本约束是领域的一部分图算法层接收AdjacencyMap因为需要快速查询和拓扑排序只在构造和测试阶段使用普通Graph表达式便于手工组装样例和验证不变式。三层之间用明确的转换函数衔接不让混乱的转换散落在业务逻辑里。我也养成了一个习惯不在一个函数里同时出现三种类型。一个函数只做一件事要么处理带标签的领域模型要么处理无标签的邻接表。这样既不会让 API 变得难以理解也方便以后替换内部实现。最后再分享一点个人体会。Alga 这套图类型系统与其说是在“存储图”不如说是在逼你想清楚一个图到底是怎么来的、要被怎么用。Graph是面向构造和变换的AdjacencyMap是面向查询和计算的Labelled Graph是面向领域语义的。搞清楚自己的真实需求再选类型很多后来的麻烦其实一开始就能避开。 
长河君 · 2026/10/24 4:54:24 · 阅读 1.2k Alga三种图类型选型指南：Graph、AdjacencyMap与Labelled Graph
折腾了大半天我终于把那个依赖分析工具的核心数据结构从Graph换成AdjacencyMap又在另一边引入了Labelled Graph。回想起来这个选择过程比我预想的复杂得多——最开始我以为无非是“用哪种类型存图”的问题但在 Alga 里Graph、AdjacencyMap、Labelled Graph这三者的差异不只是“容器”的区别而是三种完全不同的建模思路。如果你也正在 Alga 类型的三种图之间犯迷糊这篇文章会把它们的内部逻辑、适用场景和迁移代价一次讲清楚。1. 一次依赖图建模引发的类型选择问题1.1 我最初想要的“图类型”是什么我的场景不算复杂要给一批内部组件建依赖关系每个组件是一个节点节点之间的连线表示“A 依赖 B”。我需要做这样几件事快速判断某个组件是否直接依赖另一个组件列出某个组件的所有反向依赖谁依赖它跑一遍拓扑排序找循环依赖最后把整张图导出成外部格式给别人看。当时我还处于“图 点 边”的惯性思维里觉得随便选一种图类型就行。但 Alga 给了我三个候选Graph、AdjacencyMap和Labelled Graph。它们的导出接口看起来高度相似都有vertex、overlay、connect、edge这类函数以至于我一度怀疑它们只是同一件事的三种写法。真正开始写代码以后我才意识到问题没那么简单。Graph是代数表达式式的图表示AdjacencyMap是邻接表式的规范表示Labelled Graph则允许给连接关系本身挂上额外信息。三种类型面对的操作难度完全不同构造一个图可能都很简单但查询、合并、比较、序列化的代价天差地别。1.2 为什么 Alga 的三种类型会让人纠结Alga 的核心卖点是用代数运算来描述图。它不像containers里的Map一样直接给你一个可读的内部结构而是用一组构造器把图“搭”出来。这在 Haskell 里很优雅但对刚上手的人来说很容易搞混到底什么时候该用Graph什么时候数据应该落在AdjacencyMap里如果边上有额外信息是不是一定要用到Labelled Graph从官方文档看Graph是基础类型AdjacencyMap可以看作它的“可执行版本”Labelled Graph则是给边加了标签的扩展。但文档不会直接告诉你Graph的随机查询性能在稠密图里可能会让你怀疑人生AdjacencyMap对顶点类型有Ord约束Labelled Graph一旦引入连“这两张图是否相等”这个问题都会变得更复杂。这些坑只有自己踩过一遍才会记住。2. Graph构造语义最纯粹但别拿它做随机查询2.1 四个构造器就是一套代数先看最基础的Graphdata Graph a Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)这个定义和普通的链表、树定义一样简单但它的含义是代数化的Empty表示空图里面没有任何顶点和边Vertex a表示只含有一个顶点a的图Overlay g1 g2表示把两幅图并排放在一起顶点集合取并集边集合也取并集Connect g1 g2表示把两幅图上下连接除了保留各自的内部边还从g1的每个顶点向g2的每个顶点连一条边。其中最关键的是Overlay和Connect两个运算。可以这样理解Overlay是普通的叠加Connect是“笛卡尔积式”的连接。用生活化的类比Overlay像是把两张透明胶片叠在一起两张胶片上的点都保留已有的连线也都能看见Connect则像是把左边一列按钮和右边一列按钮全部用线连起来形成的是完全二分关系。一个基础的边是这样构造出来的edge x y Connect (Vertex x) (Vertex y)节点之间的一条有向边本质就是“从单点 x 到单点 y 的连接”。三个以上的节点用Overlay组合即可。2.2 基于定律的变换与相等性Graph最有价值的地方是一组代数定律。比如Overlay x y Overlay y x -- 交换律 Overlay x (Overlay y z) Overlay (Overlay x y) z -- 结合律 Overlay x x x -- 幂等律 Connect x (Overlay y z) Overlay (Connect x y) (Connect x z)这些定律不是摆设它们让Graph的相等性建立在图论意义上的“同一张图”之上而不是语法上的“同一个表达式”。表达式Connect (Vertex 1) (Overlay (Vertex 2) (Vertex 3))和Overlay (Connect (Vertex 1) (Vertex 2)) (Connect (Vertex 1) (Vertex 3))写起来完全不同但表示的图是同一张。实际开发中这种“重写不改变语义”的能力非常好用。比如我要把一个复杂图结构拆成多个子图或者反过来把多个子图合并成一个大图在Graph层面可以直接依赖代数变换来保证结果正确。只要运算遵守这些定律重构时就不容易破坏图本身的意义。这也是Graph在形式化建模、验证场景下很难被替代的原因。2.3 随机查询是 Graph 的软肋但Graph的问题也很明显它本质是一棵表达式树不是索引结构。你要判断“1 到 2 之间有没有边”不能像查字典一样直接命中而是要递归遍历表达式遇到Connect再判断左右两边的顶点覆盖关系。这个过程在下面的例子里会非常难受bigGraph Connect (vertices [1..1000]) (vertices [1..1000])上面这个表达式用很短的代码就写完了但它在图论意义上包含的是 1000 个源顶点、1000 个目标顶点以及 100 万条边。如果我在这个Graph值上反复调用hasEdge或者枚举某个顶点的所有邻居指数级的重复遍历会立刻让程序变慢。问题不是 Alga 实现得不好而是Graph本来就不是为了“随机查询”而生的。所以我的建议是把Graph当作“结构表达式”来用。它擅长描述图怎么组合、怎么变换、怎么比较但如果你要把它当作常驻内存的查询结构尤其图很稠密或者查询次数很多时最好先把它转换到更合适的形式。3. AdjacencyMap把表达式编译成邻接表之后的收益3.1 邻接表表示与规范形AdjacencyMap的内部表示非常直白newtype AdjacencyMap a AdjacencyMap (Map a (Set a))它的意思就是对每个顶点用一个集合记录它能直接到达的邻居。这个表示有三个天然的好处查询某个顶点的所有邻居只需要一次Map查找然后拿到一个Set由于Set和Map本身会去重、排序同一张图只会对应一种AdjacencyMap表示不会出现 Graph 里那种“一个图有无数种表达式”的冗余判断两点之间是否有边本质就是在集合里做成员测试耗时远低于遍历表达式。Alga 把Graph转换成AdjacencyMap的过程本质上是对表达式做一次规约。Overlay合并两张邻接表Connect则是把所有左侧顶点的邻居集合都加上右侧顶点的全部顶点。这个过程会丢失“原始表达式长什么样”但换来的是一个干净、稳定、可以直接比较的图对象。3.2 查询、遍历、序列化都顺手了把图从Graph换成AdjacencyMap之后编程体验完全不一样。判断边、列举邻居、计算入度出度、做拓扑排序这些操作都变成了常规集合操作不需要在表达式树里做复杂的语义解释。我在那个依赖分析工具里写了这样的函数-- 伪代码风格示意查询反向依赖 reverseDeps :: Ord a a - AdjacencyMap a - Set a reverseDeps v g Set.filter (\u - hasEdge u v g) (vertexSet g)如果g是邻接表形式这个函数实现起来很直观如果g是Graph表达式每次hasEdge都可能要重新扫描整棵表达式树代码看起来一样背后性能差距却很大。在序列化方面AdjacencyMap也更好处理。要把邻接表转成 JSON、GraphML 或者自定义文本格式只需要遍历Map和Set天然适合外部系统交换数据。而Graph的表达式树虽然也能序列化但还原出来的仍然是一棵表达式树不一定是别人想要的“点边列表”。3.3 代价与约束不过AdjacencyMap不是免费的午餐。构造单个顶点的图需要往Map里插入键值构造一条边通常要更新两个方向的邻接关系所以它的插入和合并成本比Graph的常量时间构造要高。下面这张表反映的是我使用时的直观感受不同实现版本可能有细微差异但整体趋势是稳定的操作GraphAdjacencyMap构造edge x y常量时间只生成表达式多次Map/Set更新对数级成本合并两个图overlay常量时间构造树节点需要合并两个Map成本随规模增长判断两点是否相连遍历表达式可能重复计算Map查找加Set成员测试对数级枚举邻居需要从表达式中推导可能很慢直接取出Set线性于邻居数顶点类型必须有Ord实例是所有AdjacencyMap操作的前提。这一点很容易被忽略。如果你的顶点是自定义数据类型记得先派生出Ord否则代码会在类型检查阶段直接卡住。4. Labelled Graph当边也开始拥有信息时4.1 从一个带版本约束的依赖边说起在我们那个依赖分析工具里光是知道“组件 A 依赖组件 B”并不够。依赖通常是带版本约束的A 要求 B 的版本不小于某个值或者落在某个区间内。如果只用Graph或AdjacencyMap这条约束只能被“塞”到顶点或边的外部建模会很别扭。这时候Labelled Graph就有用了。Labelled Graph类型可以理解为在Graph的Connect上增加了一个标签参数data LabelledGraph e a Empty | Vertex a | Overlay (LabelledGraph e a) (LabelledGraph e a) | Connect e (LabelledGraph e a) (LabelledGraph e a)这里的e是每条连接上携带的标签。它可以是权重、颜色、版本区间也可以是表示“朋友”“关注”“拉黑”等语义的关系类型。于是依赖图变成了这样-- 示意代码用 Connect 构造带版本约束的依赖边 dependencyGraph Connect (VersionRange 2.0 3.0) (Vertex app) (Vertex lib)从结构上看Labelled Graph和Graph的区别只是Connect多了一个参数但正是这个参数让整个图的表达能力上了一个台阶。4.2 标签进入构造器之后的变化有了标签以后“存在一条边”这个命题本身变复杂了。在无标签图里Connect g1 g2表示所有左侧顶点都连到右侧所有顶点在带标签图里这个连接的每一条边都带着同一个标签e。如果你需要给不同边挂不同标签就不能只靠一个高层Connect还得用Overlay把单条带标签边组合起来。这一点直接影响相等性。两个带标签的图哪怕节点一样、边的连接端点一样只要边的标签不同它们就不是同一张图。在无标签的AdjacencyMap里两条平行的同向边会被Set自动折叠成一条但在Labelled Graph里如果两条边端点相同但标签不同它们是有可能同时存在的。这会带来两个结果建模能力更强多关系图、属性图都能表达算法更复杂很多原本简单的图算法都要把标签纳入考虑。比如“从 A 到 B 是否存在路径”要变成“是否存在满足某标签条件的路径”。4.3 带标签图的常见操作和坑我在实际使用中踩过的坑主要有三个。第一个坑是标签相等性。如果标签类型是自己定义的它必须有合理的Eq实例。否则两张“理应不同”的标签图可能会被判成相同或者相反。注意这里的相等是语义上的相等不是单纯构造器相同。第二个坑是顶点属性。Labelled Graph默认给边加标签并不直接给顶点加属性。如果还要给顶点挂额外信息我通常会把顶点类型改成一个包含 ID 和属性的记录类型data Package Package { packageId :: String, packageVersion :: Version }这样顶点本身变成一个大记录邻接关系和属性“长在一起”。好处是写起来自然坏处是查询某个 ID 对应的属性时还是要走一遍Map。图一旦变大顶点查重和属性更新都会比纯用 ID 当顶点更麻烦。第三个坑是标签与重边。使用带标签图时不要默认它会自动折叠重边。假设两条边都是a - b但一条权重是 1另一条权重是 2Alga 不会自作主张把它们合并成一条除非你在构造图之前就定义好标签的合并规则比如用加法处理权重。所以从无标签图迁移到带标签图时必须先想清楚“重边在我这个领域里是什么意思”。5. 三种图类型的能力边界与换算成本5.1 横向对比表把三种类型放在一起看能力边界会更清楚维度GraphAdjacencyMapLabelled Graph底层本质代数表达式树Map a (Set a)邻接表带标签的代数表达式树构造单条边成本常量时间对数级更新常量时间随机查询成本通常较高需要遍历/推导对数级查找通常比无标签版更高边标签支持不支持不支持原生支持相等性判断基于代数语义的公理推导直接比较规范邻接表需要考虑标签相等性顶点Ord约束构造时无要求查询/转换时有几乎所有操作都要求构造时无要求常用操作时有典型适用场景图结构设计、代数变换、验证算法、查询、序列化属性图、加权图、多关系图5.2 类型之间怎么转换Graph与AdjacencyMap之间可以互相转换。Graph转AdjacencyMap是一次规约把表达式变成邻接表AdjacencyMap转Graph则是把每一条邻接关系重新变成edge的组合。这两种转换都不是无代价的相当于对整张图做一次完整遍历所以不应该在热路径里频繁往返。Labelled Graph也可以丢掉标签得到一个普通图。反过来从普通图生成带标签图时标签必须由外部逻辑提供——Alga 不可能替你猜出每条边该挂什么信息。我的建议是在系统内部明确划分边界一个模块负责维护带标签的领域模型另一个模块负责把它投影成无标签邻接表再交给算法处理。这样既能享受标签的表达力又不至于让所有图算法都被标签处理拖累。5.3 选型决策清单经过这次重构我总结了一个简单的选型决策流程如果主要工作是构造图、合并图、比较图并且在思考“图应该怎么组合”而不是“怎么查得快”选Graph如果主要工作是判断边、找邻居、算度数、跑拓扑排序选AdjacencyMap如果边的类型/权重/关系种类本身就是领域模型的组成部分选Labelled Graph如果既要标签表达又需要高性能查询可以考虑把Labelled Graph作为模型层并在算法层投影到AdjacencyMap。不要一上来就选最强大的类型。表达力越强后续要承担的复杂度也越高。6. 迁移过程中的几个真实教训6.1 不要一上来就上 Labelled Graph我最初差点直接选用Labelled Graph因为觉得它“功能最全”反正版本约束迟早要加。但真写起来才发现带标签图让很多原本简单的操作都变重了判断两个节点是否有边要考虑标签合并两个图要考虑标签不同的边怎么处理打印图还要为标签设计文本格式。最后我不得不先把功能简化到无标签的AdjacencyMap上把算法跑通再在模型边界加上版本区间。先加标签再验证逻辑会平白多出很多调试成本。正确的路径是先确认“核心算法到底需要什么信息”不要为未来可能用到的东西提前引入复杂度。标签信息可以用一个单独的数据结构去维护把边和标签分开存放等确实需要整体建模时再迁移到Labelled Graph。6.2 把 Graph 当图纸把 AdjacencyMap 当台账我现在的工作习惯是把Graph当作“图纸”用来设计和检查图的结构关系把AdjacencyMap当作“台账”用来做查询、遍历和计算。具体来说当我要搭建一批节点和边时我会先写一个返回Graph的函数用vertex、overlay、connect把结构组合出来。这样做的好处是代码读起来像在描述关系而不是在操作集合。功能稳定之后再在算法入口处一次性把Graph转换成AdjacencyMap。这样两边的优势都能拿到结构表达靠代数性能计算靠邻接表。6.3 一个混合使用的习惯对于这个依赖分析工具我最终采用了混合方案。核心模型层保存Labelled Graph因为版本约束是领域的一部分图算法层接收AdjacencyMap因为需要快速查询和拓扑排序只在构造和测试阶段使用普通Graph表达式便于手工组装样例和验证不变式。三层之间用明确的转换函数衔接不让混乱的转换散落在业务逻辑里。我也养成了一个习惯不在一个函数里同时出现三种类型。一个函数只做一件事要么处理带标签的领域模型要么处理无标签的邻接表。这样既不会让 API 变得难以理解也方便以后替换内部实现。最后再分享一点个人体会。Alga 这套图类型系统与其说是在“存储图”不如说是在逼你想清楚一个图到底是怎么来的、要被怎么用。Graph是面向构造和变换的AdjacencyMap是面向查询和计算的Labelled Graph是面向领域语义的。搞清楚自己的真实需求再选类型很多后来的麻烦其实一开始就能避开。