fixed-length-search
| Crates.io | fixed-length-search |
| lib.rs | fixed-length-search |
| version | 0.1.0 |
| source | src |
| created_at | 2023-01-06 20:05:43.985189 |
| updated_at | 2023-01-06 20:05:43.985189 |
| description | The fastest algorithm for finding a path with a specific length in a graph |
| homepage | |
| repository | |
| max_upload_size | |
| id | 752565 |
| size | 16,500 |
Tiago Cavalcante Trindade (TiagoCavalcante)
documentation
README
fixed-length-search
The fastest algorithm for finding a path with a specific length in a graph
How to run?
$ cargo run --release
How fast is it?
Here is the output of the benchmark of the algorithm for a graph with 10 thousand vertices and density of 0.1:
Fill the graph - 250.07ms
Fixed length search - 19.52ms
The path is valid
Yep, that is milliseconds, not seconds.
You can find a better benchmark here.
How does it work?
This is a mix of the ideas used in meet-in-the-middle search and BFS, there are lots of comments in the code that explains each aspect of this algorithm. You can find an animation that may help you to understand this algorithm here.