243 个版本 (82 个破坏性)

新 0.83.0	2024 年 8 月 23 日
0.81.0	2024 年 8 月 17 日
0.75.4	2024 年 7 月 30 日
0.2.3	2024 年 3 月 31 日

#155 在算法

3,171 每月下载

MIT/Apache

780KB
17K SLoC

Graaf

Rust 驱动的有向图。

安装

将以下内容添加到您的 Cargo.toml

[dependencies]
graaf = "0.83.0"

有向图类型

Graaf 提供有向图的表示。

adjacency_list 表示无权稀疏有向图。
adjacency_matrix 表示无权稠密有向图。
adjacency_list_weighted 表示弧加权稀疏有向图。

这些类型积极实现有向图的操作和算法。

创建有向图

gen 模块提供有向图生成器。

Biclique 生成完全二分图。
Circuit 生成电路图。
Complete 生成一个完整的有向图。
Cycle 生成一个双向电路。
Empty 生成一个没有弧的有向图。
ErdosRenyi 生成一个随机有向图。
Path 生成一个路径有向图。
RandomTournament 生成一个随机竞赛。
Star 生成一个星形有向图。

每个有向图的表示都可以通过op 模块中的操作来构建。

操作

op 模块提供了有向图操作特质。这些有向图类型实现了这些特质。可以为自定义有向图类型实现这些特质。操作是算法的基础。

AddArcWeighted 向一个带权弧有向图中添加一个弧。
AddArc 向一个无权有向图中添加一个弧。
ArcWeight 返回一个弧的权重。
ArcsWeighted 返回一个有向图的带权弧。
Arcs 返回一个有向图的弧。
Complement 返回一个有向图的补图。
Converse 返回一个有向图的逆图。
DegreeSequence 返回一个有向图的度序列。
Degree 返回一个顶点的度。
HasArc 检查一个有向图是否包含一个弧。
HasEdge 检查一个有向图是否包含一条边。
HasWalk 检查一个有向图是否包含一个遍历。
InNeighbors 返回一个顶点的入邻居。
IndegreeSequence 返回一个有向图的入度序列。
Indegree 返回一个顶点的入度。
IsBalanced 检查一个有向图是否是平衡的。
IsComplete 检查一个有向图是否是完整的。
IsIsolated 检查一个顶点是否是孤立的。
IsOriented 检查一个有向图是否为有向图。
IsPendant 检查一个顶点是否为悬挂顶点。
IsRegular 检查一个有向图是否为正则图。
IsSemicomplete 检查一个有向图是否为半完备图。
IsSimple 检查一个有向图是否为简单图。
IsSpanningSubdigraph 检查一个有向图是否为覆盖超图的子图。
IsSubdigraph 检查一个有向图是否为子图。
IsSuperdigraph 检查一个有向图是否为超图。
IsSymmetric 检查一个有向图是否为对称图。
IsTournament 检查一个有向图是否为竞赛图。
Order 返回有向图中顶点的数量。
OutNeighborsWeighted 返回一个顶点的加权出邻居。
OutNeighbors 返回一个顶点的出邻居。
OutdegreeSequence 返回有向图的出度序列。
Outdegree 返回一个顶点的出度。
RemoveArc 从有向图中移除一条弧。
SemidegreeSequence 返回有向图的半度序列。
Sinks 返回有向图的汇点。
Size 返回有向图中弧的数量。
Sources 返回有向图的源点。
Vertices 返回有向图中的顶点。

算法

模块 algo 提供有向图算法。

Bellman-Ford-Moore

Bellman-Ford-Moore 算法在具有负权重的弧权重有向图中找到最短路径。

single_source_distances 找到最短距离。

广度优先搜索 (BFS)

广度优先搜索按照顶点与源点的距离顺序探索无权有向图中的顶点。

bfs::Bfs 迭代顶点。
bfs_dist::Bfs 迭代顶点和它们从源点的距离。
bfs_successors::Bfs 迭代顶点和它们的后续顶点。
bfs_dist::Bfs::distances 寻找最短距离。
bfs_successors::Bfs::predecessors 寻找前驱节点。
bfs_successors::Bfs::shortest_path 寻找最短路径。

深度优先搜索 (DFS)

深度优先搜索按照从源点出发的深度顺序探索无权有向图中的顶点。

dfs::Dfs 遍历顶点。
dfs_dist::Dfs 遍历顶点和从源点到它们的距离。

Dijkstra

Dijkstra算法在弧加权有向图中找到最短路径。

dijkstra::Dijkstra 遍历顶点。
dijkstra_dist::Dijkstra 遍历顶点。
dijkstra_pred::Dijkstra 遍历顶点和它们的前驱节点。
dijkstra_dist::Dijkstra::distances 寻找最短距离。
dijkstra_pred::Dijkstra::predecessors 寻找前驱节点。
dijkstra_pred::Dijkstra::shortest_path 寻找最短路径。

Floyd-Warshall

Floyd-Warshall算法在弧加权有向图中找到所有顶点对之间的最短路径。

distances 寻找最短距离。

Tarjan

Tarjan算法在有向图中找到强连通分量。

strongly_connected_components 寻找强连通分量。

前驱树

一个 PredecessorTree 是广度优先搜索的结果。

search 通过值查找顶点。
search_by 通过谓词查找顶点。

这些函数生成一个前驱树。

距离矩阵

一个 DistanceMatrix 包含了有向图中所有顶点对之间的最短距离。

center 寻找有向图的核心。
diameter 找到有向图的直径。
eccentricities 返回顶点的离心率。
is_connected 检查有向图是否连通。
periphery 找到有向图的边缘。

命名约定

s 表示一个源顶点。
t 表示一个目标顶点。
u 表示一个尾顶点或作用域中的第一个顶点。
v 表示一个头顶点或作用域中的第二个顶点。
w 表示弧的权重。
x 表示一个尾顶点或作用域中的第三个顶点。
y 表示一个头顶点或作用域中的第四个顶点。

项目目标

灵活的有向图操作API
一套全面的算法
常见有向图的生成器
具有竞争力的性能
完整的文档
广泛的属性测试
完整的单元测试覆盖

变更日志

查看CHANGELOG.md以获取更改列表。

许可

根据您的选择，许可协议为Apache License, Version 2.0或MIT license。

联系

随时提出问题或建议。

graaf