### 4 releases

0.1.21 | Dec 16, 2021 |
---|---|

0.1.2 | Dec 16, 2021 |

0.1.1 | Dec 16, 2021 |

0.1.0 | Dec 13, 2021 |

#**1112** in Data structures

**MIT/Apache**

48KB

1K
SLoC

# Fastgraph

!!!Expect breaking changes

A graph API offering a powerful graph trait that allows for the construction of many types of graphs for different use-cases. Implements powerful parallel traversal algorithms offering speedups when traversing the graph.

# Example Usage

`use` `fastgraph``::``core``::``{`Empty`,` Traverse`}``;`
`use` `fastgraph``::``collections``::``*``;`
`fn` `main``(``)`` ``{`
`let` `mut` g `=` `Digraph``::``<``usize`, Empty, Empty`>``::`new`(``)``;`
g`.``add_node``(``1``,` Empty`)``;`
g`.``add_node``(``2``,` Empty`)``;`
g`.``add_node``(``3``,` Empty`)``;`
g`.``add_node``(``4``,` Empty`)``;`
g`.``add_node``(``5``,` Empty`)``;`
g`.``add_node``(``6``,` Empty`)``;`
g`.``add_edge``(``1``,` `2``,` Empty`)``;`
g`.``add_edge``(``1``,` `3``,` Empty`)``;`
g`.``add_edge``(``2``,` `1``,` Empty`)``;`
g`.``add_edge``(``2``,` `3``,` Empty`)``;`
g`.``add_edge``(``3``,` `1``,` Empty`)``;`
g`.``add_edge``(``3``,` `5``,` Empty`)``;`
g`.``add_edge``(``5``,` `2``,` Empty`)``;`
g`.``add_edge``(``5``,` `4``,` Empty`)``;`
g`.``add_edge``(``5``,` `1``,` Empty`)``;`
g`.``add_edge``(``4``,` `5``,` Empty`)``;`
g`.``add_edge``(``4``,` `3``,` Empty`)``;`
g`.``add_edge``(``4``,` `2``,` Empty`)``;`
g`.``add_edge``(``4``,` `6``,` Empty`)``;`
`let` sink `=` g`.``get_node``(``6``)``.``unwrap``(``)``;`
`let` shortest_tree `=` g`.``par_breadth_first``(``1``,`
`|``edge``|``{`
`if` edge`.``target``(``)` `==` sink `{`
`Traverse``::`Finish
`}` `else` `{`
`Traverse``::`Include
`}`
`}``)``.``unwrap``(``)``;`
`let` shortest_path `=` `fastgraph``::``core``::`backtrack_edges`(``&`shortest_tree`)``;`
`for` edge `in` shortest_path `{`
`println!``(``"``{}``"``,` edge`.``upgrade``(``)``.``unwrap``(``)``)`
`}`
`}`

`1` `->` `3`
`3` `->` `5`
`5` `->` `4`
`4` `->` `6`

# Implementation

Fastgraph is implemented ion a way as to allow for fast and concurrent processing of a graph. The underlying representation is basically an adjacency list, but both edges and nodes are implemented as their own structures and may contain arbitary data available atomically to each thread during traversal.

## Types

Fastgraph has

and `Edge <K, N, E>`

`Node``<`K, N, E`>`

. These types work without any
container type and implement method's for basic operations and traversal.The

trait can be used to implement the graph on top of any kind of
container. The crate provides generic `Graph`

and `Digraph`

types, but other
types with different types of containers can be implemented easily just by
implementing how nodes are accessed through the chosen container.`Ungraph`

## Traversal

When we traverse a graph we need to keep track of

nodes. This is often
done with some sort of a lookup such as a hash map or binary tree which we use
to check if a node has been visited or not. This is a very inefficient method
and when used in a multithreaded scenarion, would incur blocking when wiritng to
the datastructure from one thread.`visited`

In fastgraph each node itelf contains an atomic lock which we can toggle safely from any thread and thus block the node from traversal. When the traversal is finished, we open the locks again.

When we conduct a traversal we do create an additional data-structure, namely a
shortest path tree. This tree is then returned from the

and
`breadth_first`

(and their parallel counterparts). If we were looking for a
shortest path to a spesific node, that node will be the target node of the last
edge in the list and we can collect the shortest path by backtracking using the
shortest path tree.`depth_first`

# Performance

This repository contains benchmarks comparing the speed of sequential vs.
parallel iteration. Thiose may be run using the cargo

. In
detailed tests we observe a very nice performance gain in parallel iteration
over sequantial iteration as long as the graph's size is big enough to justify
the overhead. Under the hood fastgraph uses the `bench command`

library to parallelize
traversal loops.`rayon`

!Continue

#### Dependencies

~2.5MB

~44K SLoC