1 use petgraph::{algo::page_rank, Graph};
2
3 #[cfg(feature = "rayon")]
4 use petgraph::algo::page_rank::parallel_page_rank;
5
graph_example() -> Graph<String, f32>6 fn graph_example() -> Graph<String, f32> {
7 // Taken and adapted from https://github.com/neo4j-labs/graph?tab=readme-ov-file#how-to-run-algorithms
8 let mut graph = Graph::<_, f32>::new();
9 graph.add_node("A".to_owned());
10 graph.add_node("B".to_owned());
11 graph.add_node("C".to_owned());
12 graph.add_node("D".to_owned());
13 graph.add_node("E".to_owned());
14 graph.add_node("F".to_owned());
15 graph.add_node("G".to_owned());
16 graph.add_node("H".to_owned());
17 graph.add_node("I".to_owned());
18 graph.add_node("J".to_owned());
19 graph.add_node("K".to_owned());
20 graph.add_node("L".to_owned());
21 graph.add_node("M".to_owned());
22 graph.extend_with_edges(&[
23 (1, 2), // B->C
24 (2, 1), // C->B
25 (4, 0), // D->A
26 (4, 1), // D->B
27 (5, 4), // E->D
28 (5, 1), // E->B
29 (5, 6), // E->F
30 (6, 1), // F->B
31 (6, 5), // F->E
32 (7, 1), // G->B
33 (7, 5), // F->E
34 (8, 1), // G->B
35 (8, 5), // G->E
36 (9, 1), // H->B
37 (9, 5), // H->E
38 (10, 1), // I->B
39 (10, 5), // I->E
40 (11, 5), // J->B
41 (12, 5), // K->B
42 ]);
43 graph
44 }
45
expected_ranks() -> Vec<f32>46 fn expected_ranks() -> Vec<f32> {
47 vec![
48 0.029228685,
49 0.38176042,
50 0.3410649,
51 0.014170233,
52 0.035662483,
53 0.077429585,
54 0.035662483,
55 0.014170233,
56 0.014170233,
57 0.014170233,
58 0.014170233,
59 0.014170233,
60 0.014170233,
61 ]
62 }
63
64 #[test]
test_page_rank()65 fn test_page_rank() {
66 let graph = graph_example();
67 let output_ranks = page_rank(&graph, 0.85_f32, 100);
68 assert_eq!(expected_ranks(), output_ranks);
69 }
70
71 #[test]
72 #[cfg(feature = "rayon")]
73
test_par_page_rank()74 fn test_par_page_rank() {
75 let graph = graph_example();
76 let output_ranks = parallel_page_rank(&graph, 0.85_f32, 100, Some(1e-12));
77 assert!(!expected_ranks()
78 .iter()
79 .zip(output_ranks)
80 .any(|(expected, computed)| ((expected - computed).abs() > 1e-6)
81 || computed.is_nan()
82 || expected.is_nan()));
83 }
84