A library of high-performant graph algorithms.
Project description
graph
A library that provides a collection of high-performant graph algorithms. This crate builds on top of the graph_builder 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
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 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 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, 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);
License: MIT
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for graph_mate-0.0.2-cp38-abi3-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 259f178e72ff4af1b5a78f1005bc66cc9a7c116f6b25d89525fcec0583368fee |
|
MD5 | a4fdab5fcb2f8da9474fb6b3e0d17abe |
|
BLAKE2b-256 | ae0db4109d6cad7d853d52a053e3d55e2d523f044b0fa5d0c50e842f5ef01516 |
Hashes for graph_mate-0.0.2-cp38-abi3-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f52dbfb8418f8dcc45171079f5e42d96e0d419d5945ec38a24dd15befd6c9469 |
|
MD5 | 6e26b937b88fd7d772b6c73cf95dc1c9 |
|
BLAKE2b-256 | b31b4b84cf421c46f6e3f81dd8cd2e1dd7b67d926898cccd3b0f50a8d877bc2a |
Hashes for graph_mate-0.0.2-cp38-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 297e16373c98ab3f95f15357378e08a0e6ae51c75311b73748933da8bfd180b4 |
|
MD5 | 5a35cf04d03737b84d670dd7451113f1 |
|
BLAKE2b-256 | e99be0958cba53400350e758c2a30867b0acb7e7a46148482bc152b1d3cf0614 |
Hashes for graph_mate-0.0.2-cp38-abi3-manylinux_2_12_i686.manylinux2010_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 567e1e5e77ab4c5c4bc4bcb74df62c824ca8072d4c29252956a784f8063273f3 |
|
MD5 | c1b0f2b8c97cd1dace9dfc9fb1349a0e |
|
BLAKE2b-256 | 6c01972c78c07a0d8cc1a95614910c78fa6eb3558a92fd673738f8e9d1819473 |
Hashes for graph_mate-0.0.2-cp38-abi3-macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8b436bf6453ff3f03e9c561f2c7ccdfe3cc7e1cd8572f312d5a478098159f851 |
|
MD5 | 23eb1a8adf1b6272a20a8031246a0b2c |
|
BLAKE2b-256 | 454edd1c77d1f42bcee58e67222993c39b1e19ed24ca02a5f3b4d97fcbddad94 |
Hashes for graph_mate-0.0.2-cp38-abi3-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bde8038cfaeb53b5d58a7b2b6b7cbe90cbaf0bbe2c591830efbc9d0914b52372 |
|
MD5 | 1904535267d74176b7f1ddc7f4e7dd60 |
|
BLAKE2b-256 | 9afb586bbc5d3721d4b55d8283563b6de6d48e6714e5d1bde34909745f80389f |