graphalgs

Graph algorithms based on the Rust 'petgraph' library

8 releases

 0.1.1 Feb 3, 2023 Oct 9, 2022 Jun 10, 2021 Mar 2, 2021 Jan 23, 2021

#11 in #graph-algorithms

185KB
3.5K SLoC

Description

Graph algorithms based on the Rust "petgraph" library.

Relevance

`Petgraph` is a great tool for working with graphs in `Rust`, but not all algorithms make sense to put there, so the `graphalgs` library will be a repository for a variety of algorithms implemented on the basis of `petgraph`.

Main features

Shortest path algorithms

1. APD (Seidel) algorithm for all pairs shortest path problem in unweighted, undirected, connected graph. This algorithm shows remarkable performance due to the use of matrix multiplication.
2. A* shortest path algorithm re-exported from petgraph.
3. Bellman-Ford algorithm for computing shortest paths from source node to all other re-exported from petgraph.
4. Dijkstra’s shortest path algorithm re-exported from petgraph.
5. Floyd–Warshall algorithm for all pairs shortest path problem.
6. Johnson algorithm for all pairs shortest path problem.
7. Shortest Path Faster Algorithm Compute shortest distances from source node to all other.
8. shortest_distances algorithm based on BFS.
9. distance_map Convert distance matrix into hashmap.
10. Floyd–Warshall from petgraph

Minimum spanning tree (MST) algorithms

1. Borůvka’s algorithm
2. Prim’s algorithm
3. Kruskal’s algorithm re-exported from petgraph.

Metrics

Basic graph characteristics based on the concept of distance between vertices.

1. Center and its weighted version.
2. Diametr and its weighted version.
3. Radius and its weighted version.
4. Eccentricity of node and its weighted version.
5. Peripheral graph vertices and its weighted version.
6. Girth
1. Articulation points
2. Bridges
3. Number of connected components re-exported from petgraph.
4. Has path connecting re-exported from petgraph.
5. Condensation Condense every strongly connected component into a single node and return the result (re-exported from petgraph).
6. Kosaraju’s algorithm (re-exported from petgraph).
7. Tarjan’s algorithm (re-exported from petgraph).

Generate

Generating various graphs.

Tournament

Algorithms that simplify work with such type of graphs as a tournament.

Usage

As a library

``````use graphalgs::shortest_path::floyd_warshall;
use petgraph::Graph;

let inf = f32::INFINITY;

// Create a graph with `f32` edge weights.
let graph = Graph::<(), f32>::from_edges(&[
(0, 1, 2.0), (1, 2, 10.0), (1, 3, -5.0),
(3, 2, 2.0), (2, 3, 20.0),
]);

// Calculate the distance matrix using the Floyd-Warshall algorithm.
assert_eq!(
floyd_warshall(&graph, |edge| *edge.weight()),
Ok(vec![vec![0.0, 2.0, -1.0, -3.0],
vec![inf, 0.0, -3.0, -5.0],
vec![inf, inf,  0.0, 20.0],
vec![inf, inf,  2.0,  0.0]])
);

// Calculate the radius and diameter of this graph,
// taking into account the weights of the edges.