logo

1. 简介

Crates.io docs.rs MSRV Discord chat build_status

Rust中用于图数据结构处理的库,可以处理与图数据结构相关的各种算法。支持无/有向图稳定图带权图等。值得一提的是,Petgraph支持树,但是并没有单独设计树的数据结构。

2. 图的类型和简例

2.1 Graph通用图

图的基础结构体,其他部分结构体由Graph派生。Graph背后的内存模型是邻接表,其对节点和边的类型无任何限制。

其定义为:

1
2
3
4
5
pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> {  
nodes: Vec<Node<N, Ix>>,
edges: Vec<Edge<E, Ix>>,
ty: PhantomData<Ty>,
}

节点关联数据 N 和边关联数据 E,称为权重。关联数据可以是任意类型。

边类型 Ty,用于确定图边是有向图还是无向图。其中Directed为有向图,Undirected为无向图。

Ix为索引类型,默认u32

创建一个通用无向图:

1
let mut graph: Graph<&str, i32, Undirected> = Graph::new_undirected();

添加一些示范节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 添加12个节点  
let node_names: [&str; 12] = [
"Node1", "Node2", "Node3", "Node4", "Node5", "Node6",
"Node7", "Node8", "Node9", "Node10", "Node11", "Node12",
];

// 用一个向量来存储节点的索引
let mut nodes: Vec<NodeIndex<u32>> = Vec::new();

// 添加节点到图中
for &name in &node_names {
let node: NodeIndex<u32> = graph.add_node(name);
nodes.push(node);
}

在图中添加一些分支:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 定义边的连接信息和权重  
let edges: [(usize, usize, u32); 14] = [
(0, 1, 5),
(0, 2, 10),
(0, 3, 7),
(1, 4, 3),
(1, 5, 6),
(2, 6, 8),
(3, 7, 12),
(3, 8, 11),
(4, 9, 4),
(5, 10, 9),
(6, 11, 14),
(7, 8, 15),
(9, 10, 2),
(10, 11, 1),
];

// 从数组中加载边并添加到图中
for &(source, target, weight) in &edges {
graph.add_edge(nodes[source], nodes[target], weight as i32);
}

其结果如下图所示:

可以安装一个dot文件预览插件,可以帮助我们更好的处理图的结构。
使用下面的代码导出文件为dot文件

1
2
3
let dot_output = Dot::with_config(&graph, &[Config::EdgeIndexLabel]);  
let mut file1 = File::create("graph.dot").expect("Unable to create file");
write!(file1, "{:?}", dot_output).expect("Unable to write data");

完整代码如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
use std::fs::File;  
use petgraph::dot::{Config, Dot};
use petgraph::graph::{Graph, NodeIndex};
use petgraph::Undirected;
use std::io::Write;
fn main() {
// 创建一个通用的无向图
let mut graph: Graph<&str, i32, Undirected, u32> = Graph::new_undirected();

// 添加12个节点
let node_names: [&str; 12] = [
"Node1", "Node2", "Node3", "Node4", "Node5", "Node6",
"Node7", "Node8", "Node9", "Node10", "Node11", "Node12",
];

// 用一个向量来存储节点的索引
let mut nodes: Vec<NodeIndex<u32>> = Vec::new();

// 添加节点到图中
for &name in &node_names {
let node: NodeIndex<u32> = graph.add_node(name);
nodes.push(node);
}

// 定义边的连接信息和权重
let edges: [(usize, usize, u32); 14] = [
(0, 1, 5),
(0, 2, 10),
(0, 3, 7),
(1, 4, 3),
(1, 5, 6),
(2, 6, 8),
(3, 7, 12),
(3, 8, 11),
(4, 9, 4),
(5, 10, 9),
(6, 11, 14),
(7, 8, 15),
(9, 10, 2),
(10, 11, 1),
];

// 从数组中加载边并添加到图中
for &(source, target, weight) in &edges {
graph.add_edge(nodes[source], nodes[target], weight as i32);
}

let dot_output = Dot::with_config(&graph, &[Config::EdgeIndexLabel]);
let mut file1 = File::create("graph.dot").expect("Unable to create file");
write!(file1, "{:?}", dot_output).expect("Unable to write data");
}

2.2 DiGraph有向图

有向图DiGraph派生于Graph,与Graph大同小异,其定义如下:

1
pub type DiGraph<N, E, Ix = DefaultIx> = Graph<N, E, Directed, Ix>;

具体有向图的创建不再赘述,只给出实例化代码:

1
let mut graph: DiGraph<&str, i32, u32> = DiGraph::new();

其结果输出为:

2.3 UnGraph无向图

同理,不在赘述。

2.4 StableGraph稳定图

Graph类似,StableGraph背后的内存模型也是邻接表。删除节点或者分支时,不会改变其他节点或者分支的索引。其特性更适合频繁增添/删除边的逻辑算法,例如:生成树的构建、割集的计算、基本回路的计算等等。

其定义如下:

1
2
3
4
5
6
pub struct StableGraph<N, E, Ty = Directed, Ix = DefaultIx> {  
g: Graph<Option<N>, Option<E>, Ty, Ix>,
node_count: usize,
edge_count: usize,
free_edge: EdgeIndex<Ix>,
}

同样,对于StableGraph,也有有向图和无向图的相应派生:

  • pub type StableDiGraph<N, E, Ix = DefaultIx> = StableGraph<N, E, Directed, Ix>;
  • pub type StableUnGraph<N, E, Ix = DefaultIx> = StableGraph<N, E, Undirected, Ix>;

3. 算法

3.1 最小生成树算法

1
2
3
4
5
pub fn min_spanning_tree<G>(g: G) -> MinSpanningTree<G>  
where
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
G: IntoNodeReferences + IntoEdgeReferences + NodeIndexable,

计算图的最小生成树。输入图被视为无向图。使用Kruskal算法。实际上返回的是最小生成森林,即图每个连通分量的一个最小生成树。

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let mst = min_spanning_tree(&graph);  
let mut tree: DiGraph<&str, i32, u32> = DiGraph::new();
for &name in &node_names {
tree.add_node(name);
}

for element in mst {
// 解构 Element::Edge
if let Element::Edge { source, target, weight } = element {
let source_index = NodeIndex::new(source);
let target_index = NodeIndex::new(target);
tree.add_edge(source_index, target_index, 0);
}
}

其输出结果如下:

输出结果不同?这是由于tree.add_node(name);添加节点时改变了节点索引。所以在进行最小生成树生成时最好对原图节点和分支进行clone,并使用StableGraph去掉连枝,以维持稳定性(如果需要的话)。也可以选择只clone节点,但是生成树的分支索引都是不可信的。

3.2 最短路径算法

Petgraph实现的最短路径算法有dijkstra算法、astar算法和BellmanFord算法等等。其中,dijkstra算法并不返回路径,而是返回一个Map,它包含了起始节点到每一个可达节点的最短路径成本。BellmanFord算法使dijkstra算法支持负权重。

我使用astar算法求解最短路径。

其实现代码如下:

1
2
3
4
5
6
7
8
9
let result = astar(  
&tree,
*source_index, // 起始节点
|finish| finish == *target_index, // 目标节点
|e| *e.weight(), // 边权重
|_| 0, // 启发函数,在此简单设置为 0
);
// 输出路径
if let Some((_cost, path)) = result { ... }

其路径path是路径节点的索引集合。

3.3 强连通分量

Petgraph使用Kosaraju算法计算强连通分量。对于无向图来说,计算的就是连通分量。通过迭代计算,对节点进行两次遍历。

其实现代码如下:

1
2
3
4
let scc = kosaraju_scc(&tree);  
for (i, group) in scc.iter().enumerate() {
println!("Group {} {:?}:", i, group);
}

其中,每一个Group都是一个连通分量,是连通分量节点的索引集合。

3.4 遍历算法

3.4.1 深度优先算法DFS

深度优先需要用到petgraph::visit::Dfs,其简单实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
use petgraph::visit::Dfs;

let mut dfs_graph = Graph::<(),(), petgraph::Undirected>::new_undirected();

// 0
// /|\
// 1 2 3
// |
// 4
dfs_graph.extend_with_edges(&[
(0, 1), (0, 2), (0, 3), (3, 4)
]);

for start in dfs_graph.node_indices() {
let mut dfs = Dfs::new(&dfs_graph, start);

print!("[{}] ", start.index());

while let Some(visited) = dfs.next(&dfs_graph) {
print!(" {}", visited.index());
}
println!();
};

输出结果为:

1
2
3
4
5
[0]  0 1 2 3 4
[1] 1 0 2 3 4
[2] 2 0 1 3 4
[3] 3 0 1 2 4
[4] 4 3 0 1 2

3.4.2 广度优先算法BFS

广度优先需要用到petgraph::visit::Bfs,用法跟广度优先一样,只需要将Dfs替换成Bfs即可,其实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
use petgraph::visit::Bfs;

let mut bfs_graph = Graph::<(),(), petgraph::Undirected>::new_undirected();

// 0
// /|\
// 1 2 3
// |
// 4
bfs_graph.extend_with_edges(&[
(0, 1), (0, 2), (0, 3), (3, 4)
]);


for start in bfs_graph.node_indices() {
let mut bfs = Bfs::new(&bfs_graph, start);

print!("[{}] ", start.index());

while let Some(visited) = bfs.next(&bfs_graph) {
print!(" {}", visited.index());
}

println!();
};

输出结果为:

1
2
3
4
5
[0]  0 3 2 1 4
[1] 1 0 3 2 4
[2] 2 0 3 1 4
[3] 3 4 0 2 1
[4] 4 3 0 2 1

3.4.3 后序深度优先算法DfsPostOrder

有时我们可能需要先迭代节点的邻居,然后是节点本身。petgraph为这种遍历顺序提供了DfsPostOrder。使用方式与深度遍历相同:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
use petgraph::visit::DfsPostOrder;

let mut dfs_graph = Graph::<(),(), petgraph::Undirected>::new_undirected();

// 0
// /|\
// 1 2 3
// |
// 4
dfs_graph.extend_with_edges(&[
(0, 1), (0, 2), (0, 3), (3, 4)
]);


for start in dfs_graph.node_indices() {
let mut dfs = DfsPostOrder::new(&dfs_graph, start);

print!("[{}] ", start.index());

while let Some(visited) = dfs.next(&dfs_graph) {
print!(" {}", visited.index());
}

println!();
};

输出结果为:

1
2
3
4
5
[0]  1 2 4 3 0
[1] 2 4 3 0 1
[2] 1 4 3 0 2
[3] 1 2 0 4 3
[4] 1 2 0 3 4

3.5 其他算法

除了寻路算法,petgraph还有很多其他算法,这里简单列举一些常用的算法:

  • all_simple_paths: 返回给定节点上所有路径的迭代器。
  • condensation: 将每个强连接节点归并到一个节点。
  • connected_components:返回连通节点数。
  • has_path_connecting:如果两个节点间存在连通路径则返回True。
  • is_cyclic_directed:如果图中包含至少一个有向环则返回True。
  • is_cyclic_undirected: 如果图中包含至少一个环则返回。
  • tarjan_scc:用 Tarjan 算法返回强连通分量向量。
  • dominators:实现支配节点算法,用于计算图中某个节点的支配节点,通常应用于编译器分析和控制流图。
  • feedback_arc_set:实现反馈弧集算法,用于找到并移除最少数量的边,使得图中没有循环(在有向图中应用)。
  • floyd_warshall:实现Floyd-Warshall算法,用于计算图中所有节点对的最短路径,适用于稠密图(即边数量较多的图)。
  • ford_fulkerson:实现Ford-Fulkerson算法,用于解决最大流问题,通过增广路径寻找图中的最大流量。
  • isomorphism:实现同构算法,用于检测两个图是否是同构的(即结构上相同)。
  • k_shortest_path:实现K-最短路径算法,用于寻找图中从源节点到目标节点的K条最短路径。
  • matching:实现匹配算法,用于在图中寻找最大匹配或完美匹配,广泛应用于图的二分图匹配问题。
  • page_rank:实现PageRank算法,用于对图中的节点进行排序,最初由谷歌提出,用于网页排名。
  • simple_paths:提供与简单路径相关的算法,例如寻找图中两点之间的所有简单路径(不重复经过同一个节点的路径)。
  • tred:实现拓扑排序算法,用于对有向无环图(DAG)中的节点进行线性排序,广泛用于依赖关系解析、任务调度等场景。

petgraph并没有实现寻找回路的算法,可以拆解为寻找路径的算法曲线实现。

4. 参考文献

[1] Jarodyv. (2023, February 21). Rust机器学习之petgraph. CSDN. https://blog.csdn.net/jarodyv/article/details/128796914
[2] Petgraph Developers. (2024). Petgraph library for Rust. GitHub. https://github.com/petgraph/petgraph