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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
//! A library that provides a collection of high-performant graph algorithms.
//! This crate builds on top of the [graph_builder](https://docs.rs/graph_builder/latest/)
//! crate, which can be used as a building block for custom graph algorithms.
//!
//! `graph_builder` provides implementations for directed and undirected graphs.
//! Graphs can be created programatically or read from custom input formats in a
//! type-safe way. The library uses [rayon](https://github.com/rayon-rs/rayon)
//! to parallelize all steps during graph creation. The implementation uses a
//! Compressed-Sparse-Row (CSR) data structure which is tailored for fast and
//! concurrent access to the graph topology.
//!
//! `graph` provides graph algorithms which take graphs created using `graph_builder`
//! as input. The algorithm implementations are designed to run efficiently on
//! large-scale graphs with billions of nodes and edges.
//!
//! **Note**: The development is mainly driven by
//! [Neo4j](https://github.com/neo4j/neo4j) developers. However, the library is
//! __not__ an official product of Neo4j.
//!
//! # What is a graph?
//!
//! A graph consists of nodes and edges where edges connect exactly two nodes. A
//! graph can be either directed, i.e., an edge has a source and a target node
//! or undirected where there is no such distinction.
//!
//! In a directed graph, each node `u` has outgoing and incoming neighbors. An
//! outgoing neighbor of node `u` is any node `v` for which an edge `(u, v)`
//! exists. An incoming neighbor of node `u` is any node `v` for which an edge
//! `(v, u)` exists.
//!
//! In an undirected graph there is no distinction between source and target
//! node. A neighbor of node `u` is any node `v` for which either an edge `(u,
//! v)` or `(v, u)` exists.
//!
//! # How to use graph?
//!
//! The library provides a builder that can be used to construct a graph from a
//! given list of edges.
//!
//! For example, to create a directed graph that uses `usize` as node
//! identifier, one can use the builder like so:
//!
//! ```
//! use graph::prelude::*;
//!
//! let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
//! .csr_layout(CsrLayout::Sorted)
//! .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
//! .build();
//!
//! assert_eq!(graph.node_count(), 4);
//! assert_eq!(graph.edge_count(), 5);
//!
//! assert_eq!(graph.out_degree(1), 2);
//! assert_eq!(graph.in_degree(1), 1);
//!
//! assert_eq!(graph.out_neighbors(1).as_slice(), &[2, 3]);
//! assert_eq!(graph.in_neighbors(1).as_slice(), &[0]);
//! ```
//!
//! To build an undirected graph using `u32` as node identifer, we only need to
//! change the expected types:
//!
//! ```
//! use graph::prelude::*;
//!
//! let graph: UndirectedCsrGraph<u32> = GraphBuilder::new()
//! .csr_layout(CsrLayout::Sorted)
//! .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
//! .build();
//!
//! assert_eq!(graph.node_count(), 4);
//! assert_eq!(graph.edge_count(), 5);
//!
//! assert_eq!(graph.degree(1), 3);
//!
//! assert_eq!(graph.neighbors(1).as_slice(), &[0, 2, 3]);
//! ```
//!
//! Check out the [graph_builder](https://docs.rs/graph_builder/latest/) crate for
//! for more examples on how to build graphs from various input formats.
//!
//! # How to run algorithms
//!
//! In the following we will demonstrate running [Page Rank](https://en.wikipedia.org/wiki/PageRank),
//! a graph algorithm to determine the importance of nodes in a graph based on the
//! number and quality of their incoming edges.
//!
//! Page Rank requires a directed graph and returns the rank value for each node.
//!
//! ```
//! use graph::prelude::*;
//!
//! // https://en.wikipedia.org/wiki/PageRank#/media/File:PageRanks-Example.svg
//! let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
//! .edges(vec![
//! (1,2), // B->C
//! (2,1), // C->B
//! (4,0), // D->A
//! (4,1), // D->B
//! (5,4), // E->D
//! (5,1), // E->B
//! (5,6), // E->F
//! (6,1), // F->B
//! (6,5), // F->E
//! (7,1), // G->B
//! (7,5), // F->E
//! (8,1), // G->B
//! (8,5), // G->E
//! (9,1), // H->B
//! (9,5), // H->E
//! (10,1), // I->B
//! (10,5), // I->E
//! (11,5), // J->B
//! (12,5), // K->B
//! ])
//! .build();
//!
//! let (ranks, iterations, _) = page_rank(&graph, PageRankConfig::new(10, 1E-4, 0.85));
//!
//! assert_eq!(iterations, 10);
//!
//! let expected = vec![
//! 0.024064068,
//! 0.3145448,
//! 0.27890152,
//! 0.01153846,
//! 0.029471997,
//! 0.06329483,
//! 0.029471997,
//! 0.01153846,
//! 0.01153846,
//! 0.01153846,
//! 0.01153846,
//! 0.01153846,
//! 0.01153846,
//! ];
//!
//! assert_eq!(ranks, expected);
//! ```
const DEFAULT_PARALLELISM: usize = 4;
// Related to https://github.com/rust-lang/rust/issues/72686
// `unused_crate_dependencies` does not differentiate between `dev-dependencies` and `dependencies`
// so we fake the usage by blank importing the dev0dependencies in test scope.
use env_logger as _;
use polars as _;