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 floyd_warshall;
use ;
use Graph;
let inf = f32INFINITY;
// Create a graph with `f32` edge weights.
let graph = from_edges;
// Calculate the distance matrix using the Floyd-Warshall algorithm.
assert_eq!;
// Calculate the radius and diameter of this graph,
// taking into account the weights of the edges.
assert_eq!;
assert_eq!;
If you have any comments or suggestions, or you suddenly found an error, please start a new issue or pool request.