## graph_builder

A building block for high-performant graph algorithms

### 6 releases(3 breaking)

 0.4.0 Nov 17, 2023 Feb 19, 2023 Nov 17, 2022 Oct 1, 2022 Jan 14, 2022

#793 in Algorithms

Used in 4 crates (via graph)

195KB
4K SLoC

# graph_builder

A library that can be used as a building block for high-performant graph algorithms.

Graph 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.

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 build a 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_builder::prelude::*;

let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
.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_builder::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]);
``````

Edges can have attached values to represent weighted graphs:

``````use graph_builder::prelude::*;

let graph: UndirectedCsrGraph<u32, (), f32> = GraphBuilder::new()
.csr_layout(CsrLayout::Sorted)
.edges_with_values(vec![(0, 1, 0.5), (0, 2, 0.7), (1, 2, 0.25), (1, 3, 1.0), (2, 3, 0.33)])
.build();

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.degree(1), 3);

assert_eq!(
graph.neighbors_with_values(1).as_slice(),
&[Target::new(0, 0.5), Target::new(2, 0.25), Target::new(3, 1.0)]
);
``````

It is also possible to create a graph from a specific input format. In the following example we use the `EdgeListInput` which is an input format where each line of a file contains an edge of the graph.

``````use std::path::PathBuf;

use graph_builder::prelude::*;

let path = [env!("CARGO_MANIFEST_DIR"), "resources", "example.el"]
.iter()
.collect::<PathBuf>();

let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
.csr_layout(CsrLayout::Sorted)
.file_format(EdgeListInput::default())
.path(path)
.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]);
``````

The `EdgeListInput` format also supports weighted edges. This can be controlled by a single type parameter on the graph type. Note, that the edge value type needs to implement `crate::input::ParseValue`.

``````use std::path::PathBuf;

use graph_builder::prelude::*;

let path = [env!("CARGO_MANIFEST_DIR"), "resources", "example.wel"]
.iter()
.collect::<PathBuf>();

let graph: DirectedCsrGraph<usize, (), f32> = GraphBuilder::new()
.csr_layout(CsrLayout::Sorted)
.file_format(EdgeListInput::default())
.path(path)
.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_with_values(1).as_slice(),
&[Target::new(2, 0.25), Target::new(3, 1.0)]
);
assert_eq!(
graph.in_neighbors_with_values(1).as_slice(),
&[Target::new(0, 0.5)]
);
``````

# Types of graphs

The crate currently ships with two graph implementations:

## Compressed Sparse Row (CSR)

CSR is a data structure used for representing a sparse matrix. Since graphs can be modelled as adjacency matrix and are typically very sparse, i.e., not all possible pairs of nodes are connected by an edge, the CSR representation is very well suited for representing a real-world graph topology.

In our current implementation, we use two arrays two model the edges. One array stores the adjacency lists for all nodes consecutively which requires `O(edge_count)` space. The other array stores the offset for each node in the first array where the corresponding adjacency list can be found which requires `O(node_count)` space. The degree of a node can be inferred from the offset array.

Our CSR implementation is immutable, i.e., once built, the topology of the graph cannot be altered as it would require inserting target ids and shifting all elements to the right which is expensive and invalidates all offsets coming afterwards. However, building the CSR data structure from a list of edges is implement very efficiently using multi-threading.

However, due to inlining the all adjacency lists in one `Vec`, access becomes very cache-friendly, as there is a chance that the adjacency list of the next node is already cached. Also, reading the graph from multiple threads is safe, as there will be never be a concurrent mutable access.

One can use `DirectedCsrGraph` or `UndirectedCsrGraph` to build a CSR-based graph:

``````use graph_builder::prelude::*;

let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
.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]);
``````

In the Adjacency List implementation, we essentially store the graph as `Vec<Vec<ID>>`. The outer `Vec` has a length of `node_count` and at each index, we store the neighbors for that particular node in its own, heap-allocated `Vec`.

The downside of that representation is that - compared to CSR - it is expected to be slower, both in building it and also in reading from it, as cache misses are becoming more likely due to the isolated heap allocations for individual neighbor lists.

However, in contrast to CSR, an adjacency list is mutable, i.e., it is possible to add edges to the graph even after it has been built. This makes the data structure interesting for more flexible graph construction frameworks or for algorithms that need to add new edges as part of the computation. Currently, adding edges is constrained by source and target node already existing in the graph.

Internally, the individual neighbor lists for each node are protected by a `Mutex` in order to support parallel read and write operations on the graph topology.

One can use `DirectedALGraph` or `UndirectedALGraph` to build a Adjacency-List-based graph:

``````use graph_builder::prelude::*;

let graph: DirectedALGraph<usize> = GraphBuilder::new()
.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]);

// Let's mutate the graph by adding another edge