### 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 |

#**11** in #graph-algorithms

**51** downloads per month

**MIT**license

185KB

3.5K
SLoC

# graphalgs

# Description

Graph algorithms based on the Rust "petgraph" library.

# Relevance

is a great tool for working with graphs in `Petgraph`

, but not all algorithms make sense to put there, so the `Rust`

library will be a repository for a variety of algorithms implemented on the basis of `graphalgs`

.`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

~4.5MB

~92K SLoC