工具与算法#
固定规则包括工具与算法两种。
只有在编译时启用了 graph-algo 选项时，以下叙述的算法规则才可用。目前除了浏览器 WASM 之外的所有预编译发布都启用了此选项。
如果你使用的是 Rust、Python 或 NodeJS 的 Cozo 库，或 Cozo 的独立可执行文件，你可以自定义规定规则。具体方法请参考相应的文档。
工具#
- Constant(data: [...])#
将传入的数组作为表输出。常量规则
?[] <- ...其实是?[] <~ Constant(data: ...)的语法糖。- 参数:
data – 一个元素为数组的数组，用来表示所需的表。
- ReorderSort(rel[...], out: [...], sort_by: [...], descending: false, break_ties: false, skip: 0, take: 0)#
将传入的规则
rel所代表的表排序，然后提取其一些列输出为新的表。- 参数:
out (required) – 一个由表达式元素组成的数组，每个元素会依次成为输出表的一列。表达式中的变量会绑定为
rel参数中给出的变量。sort_by – 一个由表达式组成的数组，使用这些表达式生成的值来对
rel中的行进行排序。表达式中的变量会绑定为rel参数中给出的变量。descending – 是否以倒序排序。默认否。
break_ties – 排序时同序的行是否给出不同的行号，即两行序列相同时，行号是
1和2还是1和1。默认否，即给出相同的行号。skip – 输出时跳过多少行。默认为 0.
take – 最多输出多少行。0 表示不做限制。默认为不限制。
- 返回:
返回表的列除了
out中声明的列之外，还会在前面添加序号列。序号从 1 开始。
小技巧
此工具与
:order、:limit、:offset查询选项功能有一定重合，但是这个工具可以运用于任意规则，而查询选项只能运用于入口规则。在应用于入口规则时，建议使用查询选项。
- CsvReader(url: ..., types: [...], delimiter: ',', prepend_index: false, has_headers: true)#
从文件或 GET HTTP 请求获取 CSV 格式的数据，并将其转化为表。
浏览器中的 WASM 实现中没有此工具。另外，如果编译时没有打开
requests选项，则不能从网络读取数据。- 参数:
url (required) – CSV 文件的 URL。本地文件请使用
file://<文件路径>格式的 URL。types (required) – 元素为字符串的数组，每个字符串表示一列的类型。与数据库中其它应用类型的地方不同，如果某一列类型为可空类型，而对文件中的数据应用对应的类型转换失败时，此工具会输出空值而不是报错。这么设计的原因是常见的生成 CSV 的程序输出的坏值太多了，如果碰到坏值就报错，那么这个工具其实就没多大作用了。
delimiter – CSV 文件中的分隔符。
prepend_index – 若为真，则输出的第一列为行号。
has_headers – CSV 文件的第一行是否是文件头。若为真，则程序直接跳过第一行，不会对其做任何解析。
- JsonReader(url: ..., fields: [...], json_lines: true, null_if_absent: false, prepend_index: false)#
从文件或 GET HTTP 请求获取 JSON 格式的数据，并将其转化为表。
浏览器中的 WASM 实现中没有此工具。另外，如果编译时没有打开
requests选项，则不能从网络读取数据。- 参数:
url (required) – JSON 文件的 URL。本地文件请使用
file://<文件路径>格式的 URL。fields (required) – 元素为字符串的数组，系统会将 JSON 对象中这些名称的字段提取为列。
json_lines – 若真，则文件应每行包含一个 JSON 对象，否则文件应包含一个大数组，数组中包含多个对象。
null_if_absent – 若真，则所需的字段不存在时默认使用空值，若假，则遇到这种情况时报错。
prepend_index – 若真，则输出的第一列为行号。
连通性算法#
- SCC(...)#
- MinimumSpanningForestKruskal(edges[from, to, weight?])#
在给出的边上运行 克鲁斯卡尔算法 来求 最小生成树 。边的权重可为负。
- 返回:
第一、二列表示一个边，第三列是从树根到第二列顶点的距离。具体哪个顶点会被选为根是不固定的。如果有多个根，则表明图不是连通的。
寻路算法#
- ShortestPathBFS(edges[from, to], starting[start_idx], goals[goal_idx])#
在所给出的边上进行宽度优先搜索，来找出
starting中的顶点与goals中的顶点的最短路径。给出的边是有向图的边，每个边的权重都为 1。若有多条最短路径，则返回任意一条。这是最简单的寻路算法：下面有更多的应用更广的寻路算法。- 返回:
第一列为起点，第二列为终点，第三列为最短路径。
- ShortestPathDijkstra(edges[from, to, weight?], starting[idx], goals[idx], undirected: false, keep_ties: false)#
在给出的边上运行 戴克斯特拉算法 ，以找出
starting中的节点与goals中的节点的最短路径。若给出了权重，则权重必须非负。- 参数:
undirected – 若真，则给出的边为无向图的边，否则为有向图的边。默认为有向图的边。
keep_ties – 当有多条最短路径时，是否返回所有的最短路径。默认为否，也就是仅返回其中某一条。
- 返回:
第一列为起点，第二列为终点，第三列为最短路径的总权重，第四列为最短路径。
- KShortestPathYen(edges[from, to, weight?], starting[idx], goals[idx], k: expr, undirected: false)#
在给出的边上运行 Yen 算法来找出连接每对
starting中的顶点与goals中的顶点的最短的 k 条路径。- 参数:
k (required) – 每对顶点返回多少条路径。
undirected – 若真，则给出的边为无向图的边，否则为有向图的边。默认为有向图的边。
- 返回:
第一列为起点，第二列为终点，第三列为最短路径的总权重，第四列为最短路径。
- BreadthFirstSearch(edges[from, to], nodes[idx, ...], starting?[idx], condition: expr, limit: 1)#
在所给的边上运行宽度优先搜索，从
starting中的顶点开始搜索。若starting未给出，则默认为边中所包含的所有顶点（计算量可能会非常大）。- 参数:
condition (required) – 表示停止搜索条件的表达式。表达式中的变量绑定为
nodes参数给出的变量。表达式的值应为布尔值，当值为真时表示找到了所需结果。limit – 找到多少个所需结果后停止搜索。默认为 1。
- 返回:
第一列为起点，第二列为终点，第三列为找到的路径。
- BFS(...)#
- DepthFirstSearch(edges[from, to], nodes[idx, ...], starting?[idx], condition: expr, limit: 1)#
在所给的边上运行深度优先搜索，从
starting中的顶点开始搜索。若starting未给出，则默认为边中所包含的所有顶点（计算量可能会非常大）。- 参数:
condition (required) – 表示停止搜索条件的表达式。表达式中的变量绑定为
nodes参数给出的变量。表达式的值应为布尔值，当值为真时表示找到了所需结果。limit – 找到多少个所需结果后停止搜索。默认为 1。
- 返回:
第一列为起点，第二列为终点，第三列为找到的路径。
- DFS(...)#
- ShortestPathAStar(edges[from, to, weight], nodes[idx, ...], starting[idx], goals[idx], heuristic: expr)#
在给出的边上执行 A* 算法 ，以找出
starting中每个顶点到goals中每个顶点的最短路径。给出的边edges必须是有向图的边，且每条边都有非负的权重值。- 参数:
heuristic (required) – 启发式的表达式。表达式中的变量将会绑定为
goals与nodes参数中给出的变量。启发式求值后应得到一个数值，这个数值应是当前顶点到当前终点的最短路径权重的一个下限。若启发式求值后的数值不是下限，则算法可能会返回错误的结果。- 返回:
第一列为起点，第二列为终点，第三列为最短路径的总权重，第四列为最短路径。
小技巧
A* 算法的性能受启发式的影响极大，好的启发式会大大提速算法。由于边的权重非负，
0是一个合法的启发式，但在这种情况下实际上应该使用戴克斯特拉算法。很多好的启发式实际上是由顶点所在空间的距离函数（度量）所决定的测地线长度，比如说球面上两个点之间的测度线， 在这时
Func.Math.haversine_deg_input函数可以用来表示启发式（但注意半径的单位一定要和数据中的单位匹配）。另一个例子是曼哈顿网格空间中的最短距离。虽然给出不满足条件的启发式可能会得出错误的结果，但误差的上限决定于启发式对于实际最短距离高估的值。如果这个值不大的话，在一些场景下错误的结果也是可以用的。
社区发现算法#
- ClusteringCoefficients(edges[from, to, weight?])#
根据所给出的边，计算其中所含每个顶点的聚合系数。
- 返回:
第一列为顶点，第二列为聚合系数，第三列为包含此顶点的三角形的数量，第四列为包含该顶点的边的数量。
- CommunityDetectionLouvain(edges[from, to, weight?], undirected: false, max_iter: 10, delta: 0.0001, keep_depth?: depth)#
在给出的边上运行 Louvain 算法找出社区结构。
- 参数:
undirected – 图是否是无向图。默认为否，即有向图。
max_iter – 在算法的每个纪元内运行的最大迭代次数。默认为 10。
delta – 模块性变更多少以上才认为其代表了有效的社区效应。
keep_depth – 返回多少层社区。默认返回所有层级。
- 返回:
第一列是表示社区的一个数组，第二列是包含在这个社区中的一个顶点。数组的长度小于等于要求输出的社区层数，其结构表示社区与子社区的内部结构。
中心度量算法#
- DegreeCentrality(edges[from, to])#
使用给出的边计算其中所含顶点的度中心性。这个没有任何复杂计算，因此非常快，在拿到新图想要了解其结构时第一个运行的应该就是此算法。
- 返回:
第一列是顶点，第二列是包含此顶点的边的数量，第三列是由此顶点出发的边的数量，第四列是到达此顶点的边的数量。
- PageRank(edges[from, to, weight?], undirected: false, theta: 0.85, epsilon: 0.0001, iterations: 10)#
在所给的边上运行 佩奇排名 算法。
- 参数:
undirected – 图是否是无向图。默认为否，即有向图。
theta – 0 与 1 之间的一个小数，表示显性给出的边在（假设的）所有边中的比例。默认为 0.8。为 1 时表明严格意义上网络中不存在未发现、未给出的隐藏边。
epsilon – 迭代中最小变化阈值。Pagerank 值的提升如果低于这个阈值，则认为迭代已经收敛。默认为 0.05。
iterations – 最大迭代次数。若提前收敛，则在此次数到达前返回结果。默认为 20。
- 返回:
第一列为顶点，第二列为佩奇排名的值。
- ClosenessCentrality(edges[from, to, weight?], undirected: false)#
使用给出的边计算其中所含顶点的临近中心性。边可以同时给出权重。
- 参数:
undirected – 图是否是无向图。默认为否，即有向图。
- 返回:
第一列为顶点，第二列为临近中心性。
- BetweennessCentrality(edges[from, to, weight?], undirected: false)#
使用给出的边计算其中所含顶点的介中心性。边可以同时给出权重。
- 参数:
undirected – 图是否是无向图。默认为否，即有向图。
- 返回:
第一列为顶点，第二列为介中心性。
警告
此算法复杂度非常高，因此无法在大中型网络上运行。对于大中型网络，建议先使用社区发现算法将其聚合为中小型的超级网络，再运行此算法。
杂项#
- RandomWalk(edges[from, to, ...], nodes[idx, ...], starting[idx], steps: 10, weight?: expr, iterations: 1)#
在给出的边上进行随机游走，起点为
starting中的顶点。- 参数:
steps (required) – 游走步数。若走入了死胡同，则实际返回的步数可能会比这个值短。
weight – 表达式，其中变量绑定为
nodes与edges参数中给出的变量，每次执行时分别代表了当前所在顶点与下一步可选的边。应返回非负浮点数，代表这条边的权重，权重越大选择这条边的几率越大。若未给出此选项，则每步都对所有可选边均匀抽样。iterations – 由
starting中的每个顶点开始随机游走的次数。
- 返回:
第一列是序号，第二列是开始的节点，第三列是游走的路线（表示为包含节点的一个数组）。