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 Edge<K, N, E> and Node<K, N, E>. These types work without any container type and implement method's for basic operations and traversal.

The Graph trait can be used to implement the graph on top of any kind of container. The crate provides generic Digraph and Ungraph types, but other types with different types of containers can be implemented easily just by implementing how nodes are accessed through the chosen container.

Traversal

When we traverse a graph we need to keep track of visited 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.

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 breadth_first and depth_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.

Performance

This repository contains benchmarks comparing the speed of sequential vs. parallel iteration. Thiose may be run using the cargo bench command. 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 rayon library to parallelize traversal loops.

!Continue