9 releases
0.1.9 | Nov 5, 2024 |
---|---|
0.1.8 | Nov 5, 2024 |
0.1.5 | Oct 30, 2024 |
#244 in Algorithms
1,028 downloads per month
34KB
701 lines
Graph Algorithms
A collection of graph algorithms implemented in Rust. This repository aims to provide efficient and easy-to-understand implementations of various graph algorithms for educational purposes and practical use.
Contributions are welcome to expand the set of algorithms and improve existing implementations.
Reference implementation
Algorithm | Description | Example |
---|---|---|
Dijkstra's | Finds the shortest path from a starting node to all other nodes in a weighted graph. It uses a priority queue to efficiently select the next node with the smallest distance. | |
Bellman-Ford | Computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It can handle graphs with negative weight edges. | |
Floyd-Warshall | Finds shortest paths between all pairs of vertices in a weighted graph. It can handle graphs with negative weights but no negative weight cycles. |
A* Algorithm (TODO)
A* is a pathfinding and graph traversal algorithm that is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency.
Breadth-First Search (BFS) (TODO)
BFS explores the graph level by level, starting from a given node. It is used for finding the shortest path in an unweighted graph.
Depth-First Search (DFS) (TODO)
DFS explores as far as possible along each branch before backtracking. It is used for pathfinding and topological sorting.
Safety
This crate uses #![forbid(unsafe_code)]
to ensure everything is implemented in 100% safe Rust.
Usage
The examples
directory contains example implementations of various graph algorithms:
use graph_algorithms::{DijkstraAlgorithm, GraphAlgorithm};
Features
This crate provides optional features for different algorithms.
By default, all features are enabled. You can customize the features when adding the dependency in your Cargo.toml
:
[dependencies]
graph-algorithms-rs = { version = "x.x.x", default-features = false, features = ["dijkstra"] }
For a detailed list of available algorithms, refer to the Reference implementation section.
Contributing
Build the application:
cargo build
Test the application:
cargo test
Run clippy:
cargo clippy --all-targets --all-features --no-deps -- -D warnings
Run lint:
cargo fmt
Generate documentation in HTML format:
cargo doc --open