8 releases
0.1.1 | Feb 3, 2023 |
---|---|
0.1.0 | Oct 9, 2022 |
0.0.6 | Jun 10, 2021 |
0.0.5 | Mar 2, 2021 |
0.0.2 | Jan 23, 2021 |
#1439 in Algorithms
185KB
3.5K
SLoC
graphalgs
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
- 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.
- A* shortest path algorithm re-exported from petgraph.
- Bellman-Ford algorithm for computing shortest paths from source node to all other re-exported from petgraph.
- Dijkstra’s shortest path algorithm re-exported from petgraph.
- Floyd–Warshall algorithm for all pairs shortest path problem.
- Johnson algorithm for all pairs shortest path problem.
- Shortest Path Faster Algorithm Compute shortest distances from source node to all other.
- shortest_distances algorithm based on BFS.
- distance_map Convert distance matrix into hashmap.
- Floyd–Warshall from petgraph
Minimum spanning tree (MST) algorithms
- Borůvka’s algorithm
- Prim’s algorithm
- Kruskal’s algorithm re-exported from petgraph.
Metrics
Basic graph characteristics based on the concept of distance between vertices.
- Center and its weighted version.
- Diametr and its weighted version.
- Radius and its weighted version.
- Eccentricity of node and its weighted version.
- Peripheral graph vertices and its weighted version.
- Girth
Algorithms related to graph connectivity
- Articulation points
- Bridges
- Number of connected components re-exported from petgraph.
- Has path connecting re-exported from petgraph.
- Condensation Condense every strongly connected component into a single node and return the result (re-exported from petgraph).
- Kosaraju’s algorithm (re-exported from petgraph).
- Tarjan’s algorithm (re-exported from petgraph).
Generate
Generating various graphs.
- Complement
- Random directed graph
- Random directed weighted graph
- Random undirected graph
- Random undirected weighted graph
Tournament
Algorithms that simplify work with such type of graphs as a tournament.
Special algorithms that are difficult to categorize
- Check whether the sequence of numbers is graph-like
- Prufer encode
- Prufer decode
- Counting spanning trees
- Laplacian matrix
Circuits
Usage
As a library
use graphalgs::shortest_path::floyd_warshall;
use graphalgs::metrics::{ weighted_radius, weighted_diameter };
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.
assert_eq!(weighted_radius(&graph, |edge| *edge.weight()), Some(2.0));
assert_eq!(weighted_diameter(&graph, |edge| *edge.weight()), Some(inf));
If you have any comments or suggestions, or you suddenly found an error, please start a new issue or pool request.
Dependencies
~5.5MB
~93K SLoC