graph

图算法

用边数组表示依赖、流程和连接关系。提供拓扑排序、遍历、强弱连通分量及距离计算，C 与 xlang 使用同一套 XRT 存储和算法。

当前发布版中，合法的 XLang var 边数组传给原生图函数仍可能被误判为非数组；已登记最小复现并等待共享容器投影修复。C 原生算法测试通过不代表语言入口已签收发布级。

2026-10-30：未确认新的算法错误，四个算法单元不改。新增3072条float64加权记录，以独立Bellman-Ford逐边松弛及独立可达性核对，123条RangeError；包含次正规数、负零、极大值、整数转换、堆降距与溢出后的有限替代路径，不是任意精度距离认证。

图的表示

import graph

var jobs = [["parse", "check", 2], ["check", "emit", 3], ["parse", "emit", 9], ["docs"]]
println(graph.isDag(jobs))                 // true
println(graph.shortestPath(jobs, "parse", "emit").length)  // 2
println(int(graph.dijkstra(jobs, "parse")["emit"]))        // 5

[name] 声明孤立点；[from, to] 声明权重 1 的有向边； [from, to, weight] 显式指定权重。名称为大小写敏感字符串，允许空串和中文。有符号/无符号整数或 float 权重必须有限，内部为 float64，超大整数可能失去精度。

重复边和自环允许，重复节点声明不增加节点数。上限为 4096 个不同节点、32768 条边；不预留上限大小的全局数组。此限额不等于名称总字节数或执行时间预算。

新增 examples/from_json.xl 从标准JSON配置读取图，与现有 examples/basic.c 对照全部九项API和同一十行黄金输出。正常JSON输入成功不能关闭语言字面量的M1；没有新增原生工厂或先序列化字面量来绕行。

九项操作

函数	返回与语义
`isDag(edges) as bool`	有环为 false；空图为 true。错误仍抛异常。
`topoSort(edges) as array`	拓扑序，有环抛 ValueError，空图为 []。
`bfs(edges, start) as array`	沿出边广度优先遍历，包含起点，每个节点最多一次。
`shortestPath(edges, start, target) as array`	最少边数路径，包含两端，忽略权重；不可达抛 ValueError。
`dijkstra(edges, start) as dict`	最小权重和，值为 float64；起点为 0，不可达节点没有键。要求全图非负权。
`components(edges) as array`	忽略方向的弱连通分量，每项为节点数组。
`scc(edges) as array`	强连通分量，每项为节点数组。
`nodes(edges) as array`	去重后按原始字节字典序排列的节点，不是区域化排序。
`neighbors(edges, node) as array`	出邻居，依边出现顺序去重，自环可包含自身。

查询名必须已声明，缺少起点、终点或节点均抛 ValueError。起终点相同时 shortestPath 返回单节点数组。所有行先完整校验；非加权算法也要求权重类型正确且有限，但允许有限负权。

分量与环

import graph

var edges = [["a", "b"], ["b", "a"], ["b", "c"], ["alone"]]
println(graph.components(edges).length)    // 2
println(graph.scc(edges).length)           // 3
try
    graph.topoSort(edges)
catch ValueError error
    println("cycle")
end

分量及内部节点按输入节点首次出现的顺序输出。拓扑队列按节点首次出现顺序初始化，之后按出边顺序入队； BFS 和最少边数路径也依出边顺序处理同层候选，不承诺字母序。

资源与性能

每次调用独立构建图模型，没有隐式全局缓存。相同大图多次查询会重复建模，成本还包括读取、散列和复制名称字节。不计建模及输出，遍历、拓扑和分量为 O(V+E)，Dijkstra 的索引堆为 O((V+E) log V)，节点排序为 O(V log V) 次字符串比较。

SCC 使用显式栈，不依赖递归深度。结果独立拥有容器和名称，后续调用或输入更新不破坏已有结果。独立调用可并发，调用期间不得并发修改输入。非法输入、环和缺失路径为 ValueError；容量超限以及可达节点最终没有可表示的有限最短距离时为 RangeError；单条溢出候选不会遮蔽其他有限路径。分配失败为 MemoryError，不返回截断结果。

C 接口与互操作

当前Windows预验包括三模块独立运行库、九条实际生成原型、原C/Floyd/OOM/四线程及三条独立程序；xl.dll/xlc.dll各以同一上下文顺序运行新例三轮，30行黄金输出一致，不外推跨线程上下文。最终双平台证据见仓库验收矩阵；默认门禁仍在最后原字面量入口M1处失败，整包不签收。

从仓库根运行 powershell -NoProfile -ExecutionPolicy Bypass -File tools/check_extlib_graph.ps1 或 bash release/extlibs/graph/test/check.sh。需要GCC/Python3，可用CC/PYTHON指定。逐进程限时、输入前后指纹、失败日志保留；不需要第三方Python包。详情页源已更新，外部官网未部署。

公共头 extlibs/graph/include/graph.h 提供 xg_is_dag、xg_topo_sort、xg_bfs、xg_shortest_path、 xg_dijkstra、xg_components、xg_scc、xg_nodes、xg_neighbors。输入为借用 xvalue*，查询名为 const char* 与 size_t；结果由调用方 xrtValueRelease。

失败返回 NULL 并设置 XRT error；isDag 的 false 也可能是正常有环，C 调用者检查 xrtGetError()。每个入口清除旧错误。依赖 VALUE_CONTAINER、ARRAY、MAP 模块，四个 C 编译单元由 manifest 统一声明。

C 名称接口按完整字节处理，支持内嵌 NUL。XLang 边界用例同样验证完整名称可查询，且不会误匹配其 NUL 前缀。

双语范例与验证

发行目录运行 xl run examples/extlibs/graph_basic.xl。 C 对照为 extlibs/graph/examples/basic.c，已显式包含四个原生源文件，可直接使用 xl run release/extlibs/graph/examples/basic.c；正式扩展包仍分别编译。两者覆盖全部九项 API，对照同一份 graph_basic.expected.txt。

门禁覆盖 128 组参照图、容量与错误、218 个分配失败点、独立线程、九个实际生成 C 原型、 Windows JIT/AOT 和 DLL 上下文复用。Linux 包级脚本先运行 C ASan/UBSan 与泄漏检查，再运行 XLang 边界和范例，并与 C 范例黄金输出逐字节比较；LP64 原型可单独验证。

不表示 32 位/ARM、TSan、同一可变输入并发或完整性能基准已经验收。工具为 tools/check_extlib_graph.ps1 与 release/extlibs/graph/test/check.sh；构建或源码变化后须复验。当前旧版 xl.dll 宿主运行集合结果的 .length 路径时缺少内置头文件， xlc.dll 对照通过；Windows 完整门禁仍待发布 DLL 重建后复验。