graph
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 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 *;
let graph: = new
.edges
.build;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
To build an undirected graph using u32
as node identifer, we only need to
change the expected types:
use *;
let graph: = new
.edges
.build;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
Edges can have values attached, this is useful to represent, for example, weighted graphs:
use *;
let graph: = new
.edges_with_values
.build;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
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 PathBuf;
use *;
let path =
.iter
.;
let graph: = new
.csr_layout
.file_format
.path
.build
.expect;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
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 PathBuf;
use *;
let path =
.iter
.;
let graph: = new
.csr_layout
.file_format
.path
.build
.expect;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
assert_eq!;
Examples?
Check the TriangleCount and PageRank implementations to see how the library is used to implement high-performant graph algorithms.
License: MIT