### 19 releases

0.3.1 | Nov 20, 2023 |
---|---|

0.3.0 | Nov 17, 2022 |

0.2.1 | Oct 1, 2022 |

0.2.0 | Mar 13, 2022 |

0.0.2 | Mar 1, 2015 |

#**52** in Algorithms

**1,355** downloads per month

Used in **3** crates
(2 directly)

**MIT**license

250KB

5.5K
SLoC

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

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_builder`

provides graph algorithms which take graphs created using `graph`

as input. The algorithm implementations are designed to run efficiently on
large-scale graphs with billions of nodes and edges.`graph_builder`

**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

has outgoing and incoming neighbors. An
outgoing neighbor of node `u`

is any node `u`

for which an edge `v`

exists. An incoming neighbor of node `(`u`,` v`)`

is any node `u`

for which an edge
`v`

exists.`(`v`,` u`)`

In an undirected graph there is no distinction between source and target
node. A neighbor of node

is any node `u`

for which either an edge `v`

or `(`u`,` v`)`

exists.`(`v`,` u`)`

## 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

as node
identifier, one can use the builder like so:`usize`

`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

as node identifer, we only need to
change the expected types:`u32`

`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

#### Dependencies

~5–13MB

~118K SLoC