graphalgs

• Documentation

• Crate

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

1. 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.
2. A* shortest path algorithm re-exported from petgraph.
3. Bellman-Ford algorithm for computing shortest paths from source node to all other re-exported from petgraph.
4. Dijkstra’s shortest path algorithm re-exported from petgraph.
5. Floyd–Warshall algorithm for all pairs shortest path problem.
6. Johnson algorithm for all pairs shortest path problem.
7. Shortest Path Faster Algorithm Compute shortest distances from source node to all other.
8. shortest_distances algorithm based on BFS.
9. distance_map Convert distance matrix into hashmap.
10. Floyd–Warshall from petgraph

Minimum spanning tree (MST) algorithms

1. Borůvka’s algorithm
2. Prim’s algorithm
3. Kruskal’s algorithm re-exported from petgraph.

Metrics

Basic graph characteristics based on the concept of distance between vertices.

1. Center and its weighted version.
2. Diametr and its weighted version.
3. Radius and its weighted version.
4. Eccentricity of node and its weighted version.
5. Peripheral graph vertices and its weighted version.
6. Girth

Algorithms related to graph connectivity

1. Articulation points
2. Bridges
3. Number of connected components re-exported from petgraph.
4. Has path connecting re-exported from petgraph.
5. Condensation Condense every strongly connected component into a single node and return the result (re-exported from petgraph).
6. Kosaraju’s algorithm (re-exported from petgraph).
7. Tarjan’s algorithm (re-exported from petgraph).

Generate

Generating various graphs.

1. Complement
2. Random directed graph
3. Random directed weighted graph
4. Random undirected graph
5. Random undirected weighted graph

Tournament

Algorithms that simplify work with such type of graphs as a tournament.

1. Is the graph a tournament?
2. Is the tournament transitive?
3. Generate random tournament

Special algorithms that are difficult to categorize

1. Check whether the sequence of numbers is graph-like
2. Prufer encode
3. Prufer decode
4. Counting spanning trees
5. Laplacian matrix

Circuits

1. Elementary 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.