graphalgs

• 文档
• 包

描述

基于Rust "petgraph"库的图算法。

相关性

Petgraph是Rust中处理图的优秀工具，但并非所有算法都适合放在那里，因此graphalgs库将成为基于petgraph实现的多种算法的存储库。

主要功能

最短路径算法

1. APD (Seidel)算法用于在无权、无向、连通图中解决所有对最短路径问题。该算法由于使用矩阵乘法而表现出卓越的性能。
2. A*最短路径算法，从petgraph中重新导出。
3. Bellman-Ford算法，从petgraph中重新导出，用于计算从源节点到所有其他节点的最短路径。
4. Dijkstra的最短路径算法，从petgraph中重新导出。
5. Floyd-Warshall算法用于解决所有对最短路径问题。
6. Johnson算法用于解决所有对最短路径问题。
7. Shortest Path Faster Algorithm 计算源节点到所有其他节点的最短距离。
8. shortest_distances算法基于BFS。
9. distance_map 将距离矩阵转换为hashmap。
10. 从petgraph的Floyd-Warshall

最小生成树（MST）算法

1. Borůvka的算法
2. Prim的算法
3. Kruskal的算法从petgraph中重新导出。

度量

基于顶点之间距离概念的基本图特征。

1. Center及其加权版本。
2. 直径及其加权版本。
3. 半径及其加权版本。
4. 节点离心率及其加权版本。
5. 外围图顶点及其加权版本。
6. 圈长

与图连通性相关的算法

1. 割点
2. 桥
3. 连通分量数量（从petgraph导出）。
4. 是否有连接路径（从petgraph导出）。
5. 约简 将每个强连通分量压缩成一个节点并返回结果（从petgraph导出）。
6. Kosaraju算法（从petgraph导出）。
7. Tarjan算法（从petgraph导出）。

生成

生成各种图。

1. 补图
2. 随机有向图
3. 随机有向加权图
4. 随机无向图
5. 随机无向加权图

竞赛

简化处理类似竞赛这类图的算法。

1. 图是否是竞赛图？
2. 竞赛图是否是传递的？
3. 生成随机竞赛图

难以分类的特殊算法

1. 检查数字序列是否具有图样
2. Prufer编码
3. Prufer解码
4. 计数生成树
5. 拉普拉斯矩阵

回路

1. 基本回路

用途

作为库

use graphalgs::shortest_path::floyd_warshall;
use graphalgs::metrics::{ weighted_radius, weighted_diameter };
use petgraph::Graph;

let inf = f32::INFINITY;

// Create a graph with `f32` edge weights.
let graph = Graph::<(), f32>::from_edges(&[
    (0, 1, 2.0), (1, 2, 10.0), (1, 3, -5.0), 
    (3, 2, 2.0), (2, 3, 20.0),
]);

// Calculate the distance matrix using the Floyd-Warshall algorithm.
assert_eq!(
    floyd_warshall(&graph, |edge| *edge.weight()),
    Ok(vec![vec![0.0, 2.0, -1.0, -3.0],
            vec![inf, 0.0, -3.0, -5.0],
            vec![inf, inf,  0.0, 20.0],
            vec![inf, inf,  2.0,  0.0]])
);

// Calculate the radius and diameter of this graph, 
// taking into account the weights of the edges.
assert_eq!(weighted_radius(&graph, |edge| *edge.weight()), Some(2.0));
assert_eq!(weighted_diameter(&graph, |edge| *edge.weight()), Some(inf));

如果您有任何评论或建议，或者您突然发现了一个错误，请发起一个新的问题或请求。