Function graphalgs::shortest_path::apd

pub fn apd<K>(A: DMatrix<K>) -> DMatrix<K>where
    K: Scalar + Copy + ClosedAdd + ClosedMul + Zero + One + PartialOrd + Sub<K, Output = K>,

APD algorithm for all pairs shortest path problem.

Compute the matrix of shortest distances of an unweighted, undirected, connected graph.

Unlike seidel, this function takes an adjacency matrix as input, which can be constructed, for example, using graphalgs::adj_matrix::unweighted. Use this algorithm if you need more control over data types or you already have an adjacency matrix.

Examples

use graphalgs::shortest_path::apd;
use graphalgs::adj_matrix;
use petgraph::Graph;
use nalgebra::Matrix6;

let mut graph: Graph<(), ()> = Graph::new();
let n0 = graph.add_node(()); // Node with no weight
let n1 = graph.add_node(());
let n2 = graph.add_node(());
let n3 = graph.add_node(());
let n4 = graph.add_node(());
let n5 = graph.add_node(());
graph.extend_with_edges(&[
    (0, 1), (1, 0),  // A pair of two directed edges forms one undirected edge
    (0, 3), (3, 0),
    (1, 2), (2, 1),
    (1, 5), (5, 1),
    (2, 4), (4, 2),
    (3, 4), (4, 3),
    (4, 5), (5, 4),
]);

// Graph representation
//
// (0)-----(1)-----(2)
//  |       |       |
// (3)     (5)      |
//  |       |       |
//  \------(4)------/

// Graph diameter is two, so we can use u8 to calculate the distances between the vertices.
let matrix = adj_matrix::unweighted(&graph, 1u8, 0u8);

// Graph distance matrix.
// At position (i, j) the length of the path from vertex i to vertex j.
assert_eq!(
    apd(matrix),
    Matrix6::new(
        0, 1, 2, 1, 2, 2,
        1, 0, 1, 2, 2, 1,
        2, 1, 0, 2, 1, 2,
        1, 2, 2, 0, 1, 2,
        2, 2, 1, 1, 0, 1,
        2, 1, 2, 2, 1, 0,
    )
);