Graaf  

Rust 驱动的有向图。

目录

• 安装
• 有向图类型
• 创建有向图
• 操作
• 算法
  • Bellman-Ford-Moore
  • 广度优先搜索 (BFS)
  • 深度优先搜索 (DFS)
  • Dijkstra
  • Floyd-Warshall
  • Tarjan
  • 前驱树
  • 距离矩阵
• 命名约定
• 项目目标
• 变更日志
• 许可
• 联系
• 链接

安装

将以下内容添加到您的 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 通过谓词查找顶点。

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

• bfs_pred::Bfs::predecessors
• dijkstra_pred::Dijkstra::predecessors

距离矩阵

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

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

命名约定

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

项目目标

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

变更日志

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

许可

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

联系

随时提出问题或建议。

• 电子邮件
• GitHub

链接

• Coveralls
• Crates.io
• Docs.rs