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
#![warn(unused_crate_dependencies)]
//! 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);
//! ```
pub mod afforest;
pub mod dss;
pub mod page_rank;
pub mod prelude;
pub mod sssp;
pub mod triangle_count;
pub mod utils;
pub mod wcc;
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.
#[cfg(test)]
use env_logger as _;
#[cfg(test)]
use polars as _;