graph

图算法

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

图的表示

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] 显式指定权重。名称为大小写敏感字符串，允许空串和中文。 int/float 权重必须有限，内部为 float64，超大整数可能失去精度。

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

九项操作

函数	返回与语义
`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 接口与互操作

公共头 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。当前共享语言 string.byteLen 仍存在 NUL 截短缺陷，因而 XL 查询名应使用不含 NUL 的文本。独立失败用例保留，不用 C 侧通过替代语言侧验收。

双语范例与验证

发行目录运行 xl run examples/extlibs/graph_basic.xl。 C 对照为 extlibs/graph/examples/basic.c，须一同编译四个原生源文件；开发仓库可用 tools/run_extlib_c.ps1 -Package graph -Source release/extlibs/graph/examples/basic.c。两者覆盖全部九项 API，对照同一份 graph_basic.expected.txt。

门禁覆盖 128 组参照图、容量与错误、218 个分配失败点、独立线程、九个实际生成 C 原型、 Windows JIT/AOT 和 DLL 上下文复用。Linux 独立 C 使用 ASan/UBSan、泄漏检查与 LP64 原型验证。

不表示共享字符串缺陷、Linux xlang、32 位/ARM、TSan、同一可变输入并发或完整性能基准已经验收。工具为 tools/check_extlib_graph.ps1 与 .sh；构建或源码变化后须复验。