effect Graph 新增 findCycle精确定位图中的环并返回节点与边见证【免费下载链接】effectBuild production-ready applications in TypeScript项目地址: https://gitcode.com/GitHub_Trending/ef/effect导读本文基于 effect 仓库中新增的变更集.changeset/pre/fresh-graphs-cycle.md展开该变更集为effect包的Graph模块引入Graph.findCycle用于在图中查找一个环并返回精确的节点路径与边序列见证witness。文章将从 API 语义、返回结构、底层算法到测试用例逐层剖析并对比isAcyclic等关联算法帮助你掌握在 effect 中做环检测与诊断的完整姿势。变更集说了什么.changeset/pre/fresh-graphs-cycle.md是一个标准的 changeset 变更记录声明内容如下--- effect: patch --- Add Graph.findCycle with exact node and edge witnesses.它传达了两个关键事实变更级别为patch这是向后兼容的新增能力不会破坏既有 API核心语义新增Graph.findCycle并且返回的环结果带精确的节点与边见证——也就是说调用方不仅能知道图中存在环还能拿到组成这个环的每一个节点索引和每一条边的索引直接用于诊断、上报或可视化。在源码层面该能力落在 packages/effect/src/Graph.ts 中与环检测相关的算法整体归入 Graph Structure Analysis Algorithms 区块。认识返回结构CycleResultGraph.findCycle的返回类型是OptionCycleResult其中CycleResult定义于 packages/effect/src/Graph.tsexport interface CycleResult { readonly path: ArrayNodeIndex readonly edges: ArrayEdgeIndex }path闭环的节点路径首尾节点重复起点在结尾再次出现因此edges.length恒等于path.length - 1edges沿path依次走过的边索引序列。NodeIndex与EdgeIndex都是普通number类型见 packages/effect/src/Graph.ts由addNode/addEdge分配且删除后的标识符不会复用因此见证中的索引在图的整个生命周期内是稳定的可以安全地用于后续getNode/getEdge查询或跨调用比较。返回值使用Option.Option包装当图中不存在环时返回Option.none()存在环时返回Option.some(cycle)——这符合 effect 一贯的用类型表达可选性的风格。精确见证的构造算法findCycle的实现位于 packages/effect/src/Graph.ts它采用经典的**三色深度优先搜索DFS**来检测回边并回溯构造见证colors用0 | 1 | 2标记节点状态0未访问、1在递归栈中灰、2已完全处理黑parentNodes/parentEdges记录 DFS 树中每个节点是从哪个节点、经由哪条边到达的当遍历到一条指向灰色节点的边时说明发现了环此时从当前节点沿parentEdges/parentNodes回溯到祖先节点即可构造出完整的节点路径和边序列。值得注意的实现细节无向图的去重当graph.type undirected时算法会跳过经由进入当前节点的同一条边返回父节点的情况parentEdges.get(frame.node) edgeIndex避免把一条无向边来回走一遍误判为环自环一条自环边会作为单边环被检测出来path形如[x, x]无向平行边两条连接同一对节点的平行边会构成双边环path形如[x, y, x]有向环尊重边方向只有顺着边的source - target方向能回到起点才算环。从代码结构看该实现直接基于内部impl的nodes/adjacency/edges结构进行遍历不依赖 CSR 缓存因此返回的见证与图中真实存在的节点、边索引一一对应保证精确。实战示例1. 有向图中的环检测import { Graph, Option } from effect // A - B - C - A 构成一个环 const graph Graph.directedstring, number((mutable) { const a Graph.addNode(mutable, A) const b Graph.addNode(mutable, B) const c Graph.addNode(mutable, C) Graph.addEdge(mutable, a, b, 1) // index 0 Graph.addEdge(mutable, b, c, 1) // index 1 Graph.addEdge(mutable, c, a, 1) // index 2 }) const result Graph.findCycle(graph) if (Option.isSome(result)) { console.log(result.value.path) // [0, 1, 2, 0] console.log(result.value.edges) // [0, 1, 2] }此时path首尾均为节点0Aedges恰好是按顺序走完这三条边回到起点的索引序列。2. 无环图返回 Noneimport { Graph, Option } from effect // A - B - C 是 DAG无环 const dag Graph.directedstring, string((mutable) { const a Graph.addNode(mutable, A) const b Graph.addNode(mutable, B) const c Graph.addNode(mutable, C) Graph.addEdge(mutable, a, b, A-B) Graph.addEdge(mutable, b, c, B-C) }) Graph.findCycle(dag) // Option.none()3. 自环与无向平行边在Graph.undirected中单节点的自环会作为{ path: [0, 0], edges: [0] }返回而两个节点之间两条平行边则返回{ path: [0, 1, 0], edges: [0, 1] }。这些行为均有测试用例覆盖详见下文。与 isAcyclic 的协同使用如果只需要是否有环的布尔判断而不需要见证Graph.isAcyclic是更轻量的选择定义于 packages/effect/src/Graph.ts。它与findCycle的定位差异如下场景推荐 API理由只需校验无环如拓扑排序前置检查isAcyclic返回布尔值语义直接需要定位环的位置用于诊断/上报findCycle返回精确的path与edges见证需要给 DAG 排序topo输出拓扑序见 packages/effect/src/Graph.ts两个 API 在源码中通过see相互引用findCycle的文档指向isAcyclicisAcyclic的文档回指findCycle形成一套完整的环分析组合拳。isAcyclic内部还会复用图中已有的 acyclic 缓存标记并在图发生变更时失效重建测试用例invalidates acyclic results after adding and removing a cycle edge验证了这一点。测试用例验证packages/effect/test/Graph.test.ts 中的cycles and connectivity描述块对findCycle与isAcyclic做了系统性验证可直接作为行为契约参考精确稀疏见证使用Graph.fromSnapshot构造索引不连续节点 2/5/9边 3/7/11的有向环断言结果为Option.some({ path: [2, 5, 9, 2], edges: [3, 7, 11] })——证明见证保留的是原始索引而非重排后的位置自环无向单节点自环返回{ path: [0, 0], edges: [0] }平行边无向双节点平行边返回{ path: [0, 1, 0], edges: [0, 1] }无环图有向链式图与反向存储的无向图均返回Option.none()可变图一致性beginMutation得到的可变图上加边后isAcyclic由true变false删边后恢复true验证了环检测在 scoped-mutable API 下同样正确。这些用例同时覆盖了directed/undirected两种图类型以及自环、平行边、反向存储等边界情况。使用前提与注意事项Graph.findCycle同时接受不可变Graph与MutableGraph签名见 packages/effect/src/Graph.ts在可变图上调用无需先endMutation返回的NodeIndex/EdgeIndex是稳定标识符而非数组下标删除过的索引不会复用见NodeIndex的 Gotchas 说明环见证的path一定首尾相同edges.length path.length - 1编写消费逻辑时可依赖这一不变式图数据结构、构造器directed/undirected、增删节点边的 API 均位于packages/effect/src/Graph.ts模块该模块自3.18.0起提供图模型findCycle与CycleResult的since标记为4.0.0。小结.changeset/pre/fresh-graphs-cycle.md以最精炼的变更声明引入了Graph.findCycle而其背后的能力却相当完整三色 DFS 保证检测正确性pathedges双序列给出可直接消费的精确见证Option类型让有环/无环两种结果都显式可处理。配合isAcyclic做布尔校验、topo做排序effect 的Graph模块已覆盖图分析中最常见的环相关诉求。若你的业务涉及依赖解析、任务调度 DAG 校验或网络拓扑诊断这一新增 API 值得直接上手。【免费下载链接】effectBuild production-ready applications in TypeScript项目地址: https://gitcode.com/GitHub_Trending/ef/effect创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 effect Graph 新增 findCycle：精确定位图中的环并返回节点与边见证
effect Graph 新增 findCycle精确定位图中的环并返回节点与边见证【免费下载链接】effectBuild production-ready applications in TypeScript项目地址: https://gitcode.com/GitHub_Trending/ef/effect导读本文基于 effect 仓库中新增的变更集.changeset/pre/fresh-graphs-cycle.md展开该变更集为effect包的Graph模块引入Graph.findCycle用于在图中查找一个环并返回精确的节点路径与边序列见证witness。文章将从 API 语义、返回结构、底层算法到测试用例逐层剖析并对比isAcyclic等关联算法帮助你掌握在 effect 中做环检测与诊断的完整姿势。变更集说了什么.changeset/pre/fresh-graphs-cycle.md是一个标准的 changeset 变更记录声明内容如下--- effect: patch --- Add Graph.findCycle with exact node and edge witnesses.它传达了两个关键事实变更级别为patch这是向后兼容的新增能力不会破坏既有 API核心语义新增Graph.findCycle并且返回的环结果带精确的节点与边见证——也就是说调用方不仅能知道图中存在环还能拿到组成这个环的每一个节点索引和每一条边的索引直接用于诊断、上报或可视化。在源码层面该能力落在 packages/effect/src/Graph.ts 中与环检测相关的算法整体归入 Graph Structure Analysis Algorithms 区块。认识返回结构CycleResultGraph.findCycle的返回类型是OptionCycleResult其中CycleResult定义于 packages/effect/src/Graph.tsexport interface CycleResult { readonly path: ArrayNodeIndex readonly edges: ArrayEdgeIndex }path闭环的节点路径首尾节点重复起点在结尾再次出现因此edges.length恒等于path.length - 1edges沿path依次走过的边索引序列。NodeIndex与EdgeIndex都是普通number类型见 packages/effect/src/Graph.ts由addNode/addEdge分配且删除后的标识符不会复用因此见证中的索引在图的整个生命周期内是稳定的可以安全地用于后续getNode/getEdge查询或跨调用比较。返回值使用Option.Option包装当图中不存在环时返回Option.none()存在环时返回Option.some(cycle)——这符合 effect 一贯的用类型表达可选性的风格。精确见证的构造算法findCycle的实现位于 packages/effect/src/Graph.ts它采用经典的**三色深度优先搜索DFS**来检测回边并回溯构造见证colors用0 | 1 | 2标记节点状态0未访问、1在递归栈中灰、2已完全处理黑parentNodes/parentEdges记录 DFS 树中每个节点是从哪个节点、经由哪条边到达的当遍历到一条指向灰色节点的边时说明发现了环此时从当前节点沿parentEdges/parentNodes回溯到祖先节点即可构造出完整的节点路径和边序列。值得注意的实现细节无向图的去重当graph.type undirected时算法会跳过经由进入当前节点的同一条边返回父节点的情况parentEdges.get(frame.node) edgeIndex避免把一条无向边来回走一遍误判为环自环一条自环边会作为单边环被检测出来path形如[x, x]无向平行边两条连接同一对节点的平行边会构成双边环path形如[x, y, x]有向环尊重边方向只有顺着边的source - target方向能回到起点才算环。从代码结构看该实现直接基于内部impl的nodes/adjacency/edges结构进行遍历不依赖 CSR 缓存因此返回的见证与图中真实存在的节点、边索引一一对应保证精确。实战示例1. 有向图中的环检测import { Graph, Option } from effect // A - B - C - A 构成一个环 const graph Graph.directedstring, number((mutable) { const a Graph.addNode(mutable, A) const b Graph.addNode(mutable, B) const c Graph.addNode(mutable, C) Graph.addEdge(mutable, a, b, 1) // index 0 Graph.addEdge(mutable, b, c, 1) // index 1 Graph.addEdge(mutable, c, a, 1) // index 2 }) const result Graph.findCycle(graph) if (Option.isSome(result)) { console.log(result.value.path) // [0, 1, 2, 0] console.log(result.value.edges) // [0, 1, 2] }此时path首尾均为节点0Aedges恰好是按顺序走完这三条边回到起点的索引序列。2. 无环图返回 Noneimport { Graph, Option } from effect // A - B - C 是 DAG无环 const dag Graph.directedstring, string((mutable) { const a Graph.addNode(mutable, A) const b Graph.addNode(mutable, B) const c Graph.addNode(mutable, C) Graph.addEdge(mutable, a, b, A-B) Graph.addEdge(mutable, b, c, B-C) }) Graph.findCycle(dag) // Option.none()3. 自环与无向平行边在Graph.undirected中单节点的自环会作为{ path: [0, 0], edges: [0] }返回而两个节点之间两条平行边则返回{ path: [0, 1, 0], edges: [0, 1] }。这些行为均有测试用例覆盖详见下文。与 isAcyclic 的协同使用如果只需要是否有环的布尔判断而不需要见证Graph.isAcyclic是更轻量的选择定义于 packages/effect/src/Graph.ts。它与findCycle的定位差异如下场景推荐 API理由只需校验无环如拓扑排序前置检查isAcyclic返回布尔值语义直接需要定位环的位置用于诊断/上报findCycle返回精确的path与edges见证需要给 DAG 排序topo输出拓扑序见 packages/effect/src/Graph.ts两个 API 在源码中通过see相互引用findCycle的文档指向isAcyclicisAcyclic的文档回指findCycle形成一套完整的环分析组合拳。isAcyclic内部还会复用图中已有的 acyclic 缓存标记并在图发生变更时失效重建测试用例invalidates acyclic results after adding and removing a cycle edge验证了这一点。测试用例验证packages/effect/test/Graph.test.ts 中的cycles and connectivity描述块对findCycle与isAcyclic做了系统性验证可直接作为行为契约参考精确稀疏见证使用Graph.fromSnapshot构造索引不连续节点 2/5/9边 3/7/11的有向环断言结果为Option.some({ path: [2, 5, 9, 2], edges: [3, 7, 11] })——证明见证保留的是原始索引而非重排后的位置自环无向单节点自环返回{ path: [0, 0], edges: [0] }平行边无向双节点平行边返回{ path: [0, 1, 0], edges: [0, 1] }无环图有向链式图与反向存储的无向图均返回Option.none()可变图一致性beginMutation得到的可变图上加边后isAcyclic由true变false删边后恢复true验证了环检测在 scoped-mutable API 下同样正确。这些用例同时覆盖了directed/undirected两种图类型以及自环、平行边、反向存储等边界情况。使用前提与注意事项Graph.findCycle同时接受不可变Graph与MutableGraph签名见 packages/effect/src/Graph.ts在可变图上调用无需先endMutation返回的NodeIndex/EdgeIndex是稳定标识符而非数组下标删除过的索引不会复用见NodeIndex的 Gotchas 说明环见证的path一定首尾相同edges.length path.length - 1编写消费逻辑时可依赖这一不变式图数据结构、构造器directed/undirected、增删节点边的 API 均位于packages/effect/src/Graph.ts模块该模块自3.18.0起提供图模型findCycle与CycleResult的since标记为4.0.0。小结.changeset/pre/fresh-graphs-cycle.md以最精炼的变更声明引入了Graph.findCycle而其背后的能力却相当完整三色 DFS 保证检测正确性pathedges双序列给出可直接消费的精确见证Option类型让有环/无环两种结果都显式可处理。配合isAcyclic做布尔校验、topo做排序effect 的Graph模块已覆盖图分析中最常见的环相关诉求。若你的业务涉及依赖解析、任务调度 DAG 校验或网络拓扑诊断这一新增 API 值得直接上手。【免费下载链接】effectBuild production-ready applications in TypeScript项目地址: https://gitcode.com/GitHub_Trending/ef/effect创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考