Implementation of Seidel's algorithm

[starovoid]

Summary

This is the algorithm for solving the all-pairs-shortest-path problem for undirected, unweighted, connected graphs.

Motivation

I have just conducted a performance test in which a function using the Seidel algorithm outperformed a similar function with the Floyd-Warshall algorithm by about 1.8 times. And when generating a complete graph, the acceleration became already tenfold. The function consists of generating a random unweighted undirected graph of 1000 vertices and 249750 edges. This acceleration, as I think, is very good.

I attach a link to Wikipedia and recommend reading it before discussing further details. Seidel's algorithm

Details

In my implementation, I used the nalgebra crate version "0.25.1", here you can see my implementations of the Seidel and Floyd-Warshall algorithms.

I can't offer a full-fledged implementation plan for the Seidel algorithm, but I have a few thoughts about it:

1. If petgraph doesn't mind becoming dependent on nalgebra, you can take an existing implementation as a basis.
2. if using nalgebra is undesirable, I am ready to implement the necessary operations with matrices myself.

I am ready to implement this algorithm with all optimizations and requirements, but first I would like to hear the opinion of the maintainer.