@avantf/graph-recall

存储无关的关系图遍历库。

适配器把自己存储里的行映射成 GraphNode / GraphEdge，这个包负责走图——一跳、反向（"谁管理李娜"）、 两跳、AND（哪些事实同时提到多个实体）和邻居——返回的 RelationPath 同时带着走过的边和边背后的证据 id，所以每一条结果都能追回产生它的记录，而不是一段不可核查的文本。

零运行期依赖、零 peer 依赖：源码只 import 自己的文件，不碰 DSH、Cordis、SQLite 或 Node 内置模块。

安装

pnpm add @avantf/graph-recall     # 或 npm i @avantf/graph-recall

Node ≥ 22；纯 ESM；类型随包（lib/index.d.ts）。包里没有 lib/ 之外的运行期产物。

快速开始

import { InMemoryGraphReader, oneHop, reverse } from '@avantf/graph-recall'

const zhang = { id: 'zhang', label: '张伟' }
const li = { id: 'li', label: '李娜' }

const reader = new InMemoryGraphReader({
  nodes: [zhang, li],
  edges: [{ id: 'e1', subject: zhang, predicate: '管理', object: li, factId: 101, confidence: 0.9 }],
  nodeAliases: { 小李: 'li' },
  predicateAliases: { manages: '管理' },
})

oneHop(reader, zhang, 'manages').paths[0]!.evidence          // [101] —— 这条边背后的证据
reverse(reader, li, '管理').paths[0]!.nodes.map((n) => n.label) // ['张伟', '李娜'] —— 存的方向

接自己的存储就是实现下面的 GraphReader；InMemoryGraphReader 是参考适配器（fixture 与契约测试用）。

算子

import { InMemoryGraphReader, oneHop, reverse, twoHop, andPaths, neighbors, query } from '@avantf/graph-recall'

| 算子 | 回答的问题 | 返回的路径 | | --- | --- | --- | | oneHop(reader, start, predicate?, options?) | start --predicate--> ? | 一跳出边 | | reverse(reader, object, predicate?, options?) | ? --predicate--> object（"谁管理李娜"） | 一跳入边；答案是边的 subject | | twoHop(reader, start, predicate?, secondPredicate?, options?) | start --predicate--> mid --secondPredicate--> ? | 两跳；不给第二个谓词则第二跳不限 | | andPaths(reader, nodes, options?) | 哪些证据事实同时提到 nodes 里的至少 minSupport 个 | 每个合格事实的每条边（证据，见下） | | neighbors(reader, node, options?) | node 周围有什么（默认双向） | 每个邻居一条最优路径 | | query(reader, graphQuery) | 派发一个结构化 GraphQuery | 取决于 maxHops |

每个算子都返回同一个信封：

interface GraphResult {
  paths: RelationPath[]
  total: number       // 这次有界扫描找到的不同候选路径数
  truncated: boolean  // 候选比这一页多，或扫描碰到上限
}

query() 在给了 secondPredicate 时默认两跳，否则一跳；maxHops 只接受 1 | 2，其它值抛 RangeError。includeIncoming 只对一跳生效。query({ maxHops: 1, secondPredicate }) 同样抛错： 一跳没有第二跳，悄悄丢掉这个字段就会回答一个调用方没问的问题。

单跳算子的 options 是 { limit?, target? }（oneHop 另有 includeIncoming）；andPaths 是 { limit?, minSupport? }；neighbors 是 { limit?, predicate?, includeIncoming? }。

路径语义

path.nodes[i]   === path.edges[i].subject
path.nodes[i+1] === path.edges[i].object

• 方向永远是被存下来的方向，反向查询也一样（[subject, object]，不是 [object, subject]）。 要"答案节点"就读 edges[] 的端点。
• confidence 是各边置信度的乘积（缺失按 0.5，memory 那一列的默认值），保留 4 位小数： 0.9 × 0.8 = 0.72。所以两跳路径不可能显得比它最弱的证据更确定。
• evidence 是每边的 factId ?? edge.id，按 String(id) 去重且保序——7 和 "7" 在这里是同一条 证据，和 edgesForFact 用的是同一个身份。
• nodes / edges 是这条路径自己的数组，但里面的边对象是适配器的：库里只拷数组，不拷边。 这安全的前提是适配器不把可变内部状态交出去（见"适配器契约"）。

andPaths 返回的是事实证据，不是被查节点之间的路径

andPaths 把被查节点的关联边按 factId 分组，留下包含至少 minSupport（默认 2，低于 2 会被抬到 2） 个不同被查节点的事实，然后为留下的每个事实返回该事实的每条边。于是合格事实的边会全部返回， 包括：

• 从被查节点指向一个没被查的节点的边；
• 两端都没有同时被查的边。

所以它回答的是"哪些记录提到了这些实体"，而不是"它们之间怎么连"——后者用 twoHop。把这个结果 投影成答案时必须如实措辞（例如"提到这些实体的事实"），不能说成"它们之间的关系"。

排序、limit 与去重

• 排序：置信度 DESC → 跳数 ASC → 证据时间 DESC（GraphEdge.observedAt，ISO-8601 或 epoch 毫秒）→ 边 id 元组（保证确定性）。比较器导出为 compareRelationPaths，消费者自己合并多页时 用同一个，顺序才一致。
• limit 默认 10，夹到 [0, 100]（DEFAULT_LIMIT / MAX_LIMIT）。每次读适配器都会多取到 limit × 5，这样适配器返回顺序里的偏差藏不住更好的路径；total 是这次有界扫描找到的不同候选 数，不是全图计数。
• 去重：路径按有序边 id 元组。neighbors 按邻居 id 去重并保留该邻居的最优路径（邻居是一个节点， 两条事实连到它算一个答案）。
• target 过滤远端节点：oneHop / reverse 过滤"走到哪"，twoHop 过滤终点。
• 没有路径就是 { paths: [], total: 0, truncated: false }——是否退回模糊检索由调用方决定，这里不编造。

有界性：每个算子最多读多少

limit 只是页大小；真正的上界是固定的：每次读适配器最多 min(500, max(10, limit × 5)) 条边， 多读算子另有总量上限。

| 算子 | 适配器调用 | 收集上限 | | --- | --- | --- | | oneHop | 1（includeIncoming 时 2） | ≤ scan 条边（双向 ≤ 2 × scan） | | reverse | 1 | ≤ scan 条边 | | neighbors | 2（includeIncoming: false 时 1） | ≤ 2 × scan 条边，每个邻居一条路径 | | twoHop | 1 + scan（每条第一跳边走一次） | ≤ 500 条路径候选 | | andPaths | ≤ 2 × MAX_AND_NODES（每节点 2 次） | ≤ 500 条不同边 |

andPaths 接受至多 20 个不同被查节点（MAX_AND_NODES）；超了抛 RangeError 而不是截断——被 截断的 AND 会悄悄回答一个更弱的问题。碰到 500 条边上限时它停止读后续节点并报 truncated: true，因为 多出来的证据只会被分页翻掉。

"有界"在这里的意思是"固定倍数于 limit"，不是"与图规模成正比"。最大两跳，没有递归走、没有深度参数。

适配器契约

interface GraphReader {
  resolveNode(ref: string): GraphNode | null
  resolvePredicate(ref: string): string | null
  outgoing(node: GraphNode, predicate?: string, limit?: number): GraphEdge[]
  incoming(node: GraphNode, predicate?: string, limit?: number): GraphEdge[]
  edgesForFact(factId: string | number): GraphEdge[]
}

读的结果和节点对象都归适配器；适配器必须返回稳定顺序（插入序就行），并拥有所有过滤决定。走图的 一方会先用 resolvePredicate 把谓词归一（适配器没有词表时退回原始字符串），分页排序在库里做。

过滤不属于这个库：活跃事实、kind、source、时间窗、权限都是适配器的事。库也不抽取、不规划、不生成 答案。

四条义务，由 test/contract.ts 逐条检查：

1. resolveNode 是 alias-first：alias → label/name → node id。 显式别名压过节点 id、也压过 label，这样同一个查询在每个适配器里都落到同一个节点（memory 的顺序是 entity_aliases → entities.name → 数字 entity_id）。label 不唯一——适配器必须确定性地挑一个并一直挑同一个。 空白或不存在的引用返回 null。
2. 边 id 唯一。 路径去重定义在边 id 上，所以一个 id 只能指一条边；重复 id 要拒绝，而不是两条边 共用一个 id。
3. 读不暴露可变内部状态。 读拿到的边、端点节点、resolveNode 返回的节点，怎么改都不能改变图： 下一次读还是一样的值。InMemoryGraphReader 冻结自己的对象；每次读都新建值的适配器天然满足。
4. 证据可追溯。 factId 指向存下来的事实，edgesForFact 返回该事实产生的每条边（一个事实可能有 多条），factId 按 String(id) 比较——42 和 "42" 是同一份证据，在 reader 和 RelationPath.evidence 里都一样。

参考适配器

const reader = new InMemoryGraphReader({
  nodes: [zhang, li],
  edges: [{ id: 'e1', subject: zhang, predicate: '管理', object: li, factId: 101, confidence: 0.9 }],
  nodeAliases: { 小李: 'li' },
  predicateAliases: { manages: '管理' },
})
oneHop(reader, zhang, 'manages').paths[0]!.evidence // [101]

它是字面实现：读按插入序、谓词精确匹配、不推断边，别名只来自 fixture 显式声明的那两张表。重复边 id 会被拒绝；读结果是冻结的副本（改它抛 TypeError），你传进去的 fixture 对象不会被冻结——副本归 reader，原件归你。用新 label（或 kind）重新登记一个节点 id 会同时改写所有已索引到它的边，所以 resolveNode(id) 和边端点永远说同一个节点，旧 label 仍然解析到那个 id。

复用契约测试

test/contract.ts 导出 describeGraphReaderContract(name, create)，create() 返回的 fixture 还要提供 addDuplicateEdge（唯一性检查用的写路径）。每个适配器都该拿自己的 fixture 跑一遍。

test/ 目前不随包发布，所以跨仓消费者要自己复制这个文件（memory 的 packages/core/test/graph_reader.spec.ts 就是那份副本，四条义务它全 replay）。把契约套件做成可发布的 入口（子路径 + vitest peer）还在待办里。

已知边界

• 最多两跳，没有深度参数；query() 拒绝 maxHops: 3 而不是夹到 2。
• 不做过滤（活跃状态、kind、source、时间窗、权限）——那是适配器的事，库不猜。
• total 是有界扫描的计数，不是全图计数；truncated 在 andPaths 撞到 500 条边时也为真。
• 路径里的边对象归适配器，库只保证数组是自己的。

版本与兼容

• 语义化版本：破坏性变更进 major，兼容新增进 minor，修 bug 进 patch；候选版 X.Y.Z-rc.N。
• 变更记录在仓库的 CHANGELOG/<version>.md，一个版本一份。
• Node ≥ 22，纯 ESM，sideEffects: false。

许可

MIT。源码与问题跟踪：[email protected]:ffeng86/graph-recall.git。