graaf 0.112.0

//! A distance matrix.
//!
//! A [`DistanceMatrix`] contains the distance between each vertex pair in a
//! digraph.
//!
//! # Examples
//!
//! ## A digraph
//!
//! A digraph of order `7` and size `15`.
//!
//! ![The digraph](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/distance_matrix_digraph_1-0.87.4.svg?)
//!
//! ### The distance matrix
//!
//! The corresponding [`DistanceMatrix`] by
//! [`FloydWarshall::distances`](crate::FloydWarshall::distances).
//!
//! ![The distance matrix](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/distance_matrix_matrix_1-0.87.4.svg?)
//!
//! ```
//! use graaf::{
//!     AddArcWeighted,
//!     AdjacencyListWeighted,
//!     DistanceMatrix,
//!     Empty,
//!     FloydWarshall,
//! };
//!
//! let mut digraph = AdjacencyListWeighted::<isize>::empty(7);
//!
//! digraph.add_arc_weighted(0, 1, 5);
//! digraph.add_arc_weighted(0, 2, 3);
//! digraph.add_arc_weighted(0, 3, 2);
//! digraph.add_arc_weighted(0, 4, 4);
//! digraph.add_arc_weighted(1, 0, 3);
//! digraph.add_arc_weighted(1, 3, 1);
//! digraph.add_arc_weighted(1, 4, 2);
//! digraph.add_arc_weighted(2, 6, 4);
//! digraph.add_arc_weighted(3, 4, 1);
//! digraph.add_arc_weighted(3, 5, 1);
//! digraph.add_arc_weighted(4, 2, 3);
//! digraph.add_arc_weighted(5, 6, 1);
//! digraph.add_arc_weighted(6, 0, 9);
//! digraph.add_arc_weighted(6, 1, 8);
//! digraph.add_arc_weighted(6, 2, 5);
//!
//! let mut floyd_warshall = FloydWarshall::new(&digraph);
//! let dist = floyd_warshall.distances();
//!
//! assert!(dist[0..7].eq(&[0, 5, 3, 2, 3, 3, 4]));
//! assert!(dist[7..14].eq(&[3, 0, 5, 1, 2, 2, 3]));
//! assert!(dist[14..21].eq(&[13, 12, 0, 13, 14, 14, 4]));
//! assert!(dist[21..28].eq(&[11, 10, 4, 0, 1, 1, 2]));
//! assert!(dist[28..35].eq(&[16, 15, 3, 16, 0, 17, 7]));
//! assert!(dist[35..42].eq(&[10, 9, 6, 10, 11, 0, 1]));
//! assert!(dist[42..49].eq(&[9, 8, 5, 9, 10, 10, 0]));
//! ```

use std::{
    cmp::Ordering::{
        Equal,
        Greater,
        Less,
    },
    ops::{
        Index,
        IndexMut,
        Range,
        RangeFull,
    },
    ptr::write,
};

/// A distance matrix
///
/// A [`DistanceMatrix`] contains the distance between each pair of vertices in
/// a digraph.
///
/// # Examples
///
/// A digraph of order `7` and size `15`.
///
/// ![A digraph of order `7` and size `15`](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/distance_matrix_digraph_1-0.87.4.svg?)
///
/// ### The distance matrix
///
/// The corresponding [`DistanceMatrix`] generated by
/// [`FloydWarshall::distances`](crate::FloydWarshall::distances).
///
/// ![The corresponding distance matrix generated by the Floyd-Warshall algorithm](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/distance_matrix_matrix_1-0.87.4.svg?)
///
/// ```
/// use graaf::{
///     AddArcWeighted,
///     AdjacencyListWeighted,
///     DistanceMatrix,
///     Empty,
///     FloydWarshall,
/// };
///
/// let mut digraph = AdjacencyListWeighted::<isize>::empty(7);
///
/// digraph.add_arc_weighted(0, 1, 5);
/// digraph.add_arc_weighted(0, 2, 3);
/// digraph.add_arc_weighted(0, 3, 2);
/// digraph.add_arc_weighted(0, 4, 4);
/// digraph.add_arc_weighted(1, 0, 3);
/// digraph.add_arc_weighted(1, 3, 1);
/// digraph.add_arc_weighted(1, 4, 2);
/// digraph.add_arc_weighted(2, 6, 4);
/// digraph.add_arc_weighted(3, 4, 1);
/// digraph.add_arc_weighted(3, 5, 1);
/// digraph.add_arc_weighted(4, 2, 3);
/// digraph.add_arc_weighted(5, 6, 1);
/// digraph.add_arc_weighted(6, 0, 9);
/// digraph.add_arc_weighted(6, 1, 8);
/// digraph.add_arc_weighted(6, 2, 5);
///
/// let mut floyd_warshall = FloydWarshall::new(&digraph);
/// let dist = floyd_warshall.distances();
///
/// assert!(dist[0..7].eq(&[0, 5, 3, 2, 3, 3, 4]));
/// assert!(dist[7..14].eq(&[3, 0, 5, 1, 2, 2, 3]));
/// assert!(dist[14..21].eq(&[13, 12, 0, 13, 14, 14, 4]));
/// assert!(dist[21..28].eq(&[11, 10, 4, 0, 1, 1, 2]));
/// assert!(dist[28..35].eq(&[16, 15, 3, 16, 0, 17, 7]));
/// assert!(dist[35..42].eq(&[10, 9, 6, 10, 11, 0, 1]));
/// assert!(dist[42..49].eq(&[9, 8, 5, 9, 10, 10, 0]));
/// ```
#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
#[non_exhaustive]
pub struct DistanceMatrix<W> {
    /// The distance matrix.
    pub dist: Vec<W>,
    /// The distance between unconnected vertices.
    pub infinity: W,
    /// The number of vertices.
    pub order: usize,
}

impl<W> DistanceMatrix<W> {
    /// Construct a new [`DistanceMatrix`].
    ///
    /// # Arguments
    ///
    /// * `order`: The number of vertices.
    /// * `infinity`: The distance between unconnected vertices.
    ///
    /// # Panics
    ///
    /// Panics if `order` is zero.
    ///
    /// # Examples
    ///
    /// ```
    /// use graaf::DistanceMatrix;
    ///
    /// let dist = DistanceMatrix::new(4, 0);
    ///
    /// assert_eq!(dist.infinity, 0);
    /// assert_eq!(dist[0..4], vec![0; 4]);
    /// assert_eq!(dist[4..8], vec![0; 4]);
    /// assert_eq!(dist[8..12], vec![0; 4]);
    /// assert_eq!(dist[12..16], vec![0; 4]);
    /// ```
    #[must_use]
    pub fn new(order: usize, infinity: W) -> Self
    where
        W: Copy,
    {
        assert!(order > 0, "a distance matrix has at least one vertex");

        let size = order
            .checked_mul(order)
            .expect("a matrix has at most `usize::MAX` elements");

        let mut dist = Vec::with_capacity(size);
        let dist_ptr: *mut W = dist.as_mut_ptr();

        unsafe {
            dist.set_len(size);

            for i in 0..size {
                write(dist_ptr.add(i), infinity);
            }
        }

        Self {
            dist,
            infinity,
            order,
        }
    }

    /// Return a digraph's center.
    ///
    /// A digraph's center is the set of vertices with the smallest
    /// eccentricity. The center is also known as the Jordan center.
    ///
    /// # Examples
    ///
    /// The digraph's center is red.
    ///
    /// ![A digraph and its center](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/distance_matrix_center_1-0.87.4.svg?)
    ///
    /// ```
    /// use graaf::{
    ///     AddArcWeighted,
    ///     AdjacencyListWeighted,
    ///     DistanceMatrix,
    ///     Empty,
    ///     FloydWarshall,
    /// };
    ///
    /// let mut digraph = AdjacencyListWeighted::<isize>::empty(7);
    ///
    /// digraph.add_arc_weighted(0, 1, 5);
    /// digraph.add_arc_weighted(0, 2, 3);
    /// digraph.add_arc_weighted(0, 3, 2);
    /// digraph.add_arc_weighted(0, 4, 4);
    /// digraph.add_arc_weighted(1, 0, 3);
    /// digraph.add_arc_weighted(1, 3, 1);
    /// digraph.add_arc_weighted(1, 4, 2);
    /// digraph.add_arc_weighted(2, 6, 4);
    /// digraph.add_arc_weighted(3, 4, 1);
    /// digraph.add_arc_weighted(3, 5, 1);
    /// digraph.add_arc_weighted(4, 2, 3);
    /// digraph.add_arc_weighted(5, 6, 1);
    /// digraph.add_arc_weighted(6, 0, 9);
    /// digraph.add_arc_weighted(6, 1, 8);
    /// digraph.add_arc_weighted(6, 2, 5);
    ///
    /// assert!(
    ///     FloydWarshall::new(&digraph)
    ///         .distances()
    ///         .center()
    ///         .iter()
    ///         .eq(&[0, 1])
    /// );
    /// ```
    #[doc(alias = "centre")]
    #[doc(alias = "jordan_center")]
    #[doc(alias = "jordan_centre")]
    #[must_use]
    pub fn center(&self) -> Vec<usize>
    where
        W: Copy + Ord,
    {
        let ecc = self.eccentricities();
        let mut center = Vec::new();
        let mut min = self.infinity;

        for (i, &e) in ecc.enumerate() {
            match e.cmp(&min) {
                Less => {
                    center.clear();
                    center.push(i);
                    min = e;
                }
                Equal => center.push(i),
                Greater => (),
            }
        }

        center
    }

    /// Return a digraph's diameter.
    ///
    /// A digraph's diameter is its maximum eccentricity.
    ///
    /// # Examples
    ///
    /// The longest shortest path between vertices `4` and `5` is red.
    ///
    /// ![A digraph and its diameter](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/distance_matrix_diameter_1-0.87.4.svg?)
    ///
    /// ```
    /// use graaf::{
    ///     AddArcWeighted,
    ///     AdjacencyListWeighted,
    ///     DistanceMatrix,
    ///     Empty,
    ///     FloydWarshall,
    /// };
    ///
    /// let mut digraph = AdjacencyListWeighted::<isize>::empty(7);
    ///
    /// digraph.add_arc_weighted(0, 1, 5);
    /// digraph.add_arc_weighted(0, 2, 3);
    /// digraph.add_arc_weighted(0, 3, 2);
    /// digraph.add_arc_weighted(0, 4, 4);
    /// digraph.add_arc_weighted(1, 0, 3);
    /// digraph.add_arc_weighted(1, 3, 1);
    /// digraph.add_arc_weighted(1, 4, 2);
    /// digraph.add_arc_weighted(2, 6, 4);
    /// digraph.add_arc_weighted(3, 4, 1);
    /// digraph.add_arc_weighted(3, 5, 1);
    /// digraph.add_arc_weighted(4, 2, 3);
    /// digraph.add_arc_weighted(5, 6, 1);
    /// digraph.add_arc_weighted(6, 0, 9);
    /// digraph.add_arc_weighted(6, 1, 8);
    /// digraph.add_arc_weighted(6, 2, 5);
    ///
    /// assert_eq!(FloydWarshall::new(&digraph).distances().diameter(), &17);
    /// ```
    #[must_use]
    pub fn diameter(&self) -> &W
    where
        W: Copy + Ord,
    {
        self.eccentricities().max().unwrap_or(&self.infinity)
    }

    /// Return the digraph's eccentricities.
    ///
    /// A vertex's eccentricity is the maximum distance to any other vertex.
    ///
    /// # Examples
    ///
    /// ![A digraph and the vertices' eccentricities](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/distance_matrix_eccentricities_1-0.87.4.svg?)
    ///
    /// ```
    /// use graaf::{
    ///     AddArcWeighted,
    ///     AdjacencyListWeighted,
    ///     DistanceMatrix,
    ///     Empty,
    ///     FloydWarshall,
    /// };
    ///
    /// let mut digraph = AdjacencyListWeighted::<isize>::empty(7);
    ///
    /// digraph.add_arc_weighted(0, 1, 5);
    /// digraph.add_arc_weighted(0, 2, 3);
    /// digraph.add_arc_weighted(0, 3, 2);
    /// digraph.add_arc_weighted(0, 4, 4);
    /// digraph.add_arc_weighted(1, 0, 3);
    /// digraph.add_arc_weighted(1, 3, 1);
    /// digraph.add_arc_weighted(1, 4, 2);
    /// digraph.add_arc_weighted(2, 6, 4);
    /// digraph.add_arc_weighted(3, 4, 1);
    /// digraph.add_arc_weighted(3, 5, 1);
    /// digraph.add_arc_weighted(4, 2, 3);
    /// digraph.add_arc_weighted(5, 6, 1);
    /// digraph.add_arc_weighted(6, 0, 9);
    /// digraph.add_arc_weighted(6, 1, 8);
    /// digraph.add_arc_weighted(6, 2, 5);
    ///
    /// assert!(
    ///     FloydWarshall::new(&digraph)
    ///         .distances()
    ///         .eccentricities()
    ///         .eq(&[5, 5, 14, 11, 17, 11, 10])
    /// );
    /// ```
    pub fn eccentricities(&self) -> impl Iterator<Item = &'_ W>
    where
        W: Ord,
    {
        self.dist
            .chunks(self.order)
            .map(|row| row.iter().max().unwrap_or(&self.infinity))
    }

    /// Check whether the distance matrix is connected.
    ///
    /// A distance matrix is connected if the eccentricity of every vertex is
    /// finite.
    ///
    /// # Examples
    ///
    /// ```
    /// use graaf::{
    ///     AddArcWeighted,
    ///     AdjacencyListWeighted,
    ///     DistanceMatrix,
    ///     Empty,
    ///     FloydWarshall,
    /// };
    ///
    /// let mut digraph = AdjacencyListWeighted::<isize>::empty(7);
    ///
    /// digraph.add_arc_weighted(0, 1, 5);
    /// digraph.add_arc_weighted(0, 2, 3);
    /// digraph.add_arc_weighted(0, 3, 2);
    /// digraph.add_arc_weighted(0, 4, 4);
    /// digraph.add_arc_weighted(1, 0, 3);
    /// digraph.add_arc_weighted(1, 3, 1);
    /// digraph.add_arc_weighted(1, 4, 2);
    /// digraph.add_arc_weighted(2, 6, 4);
    /// digraph.add_arc_weighted(3, 4, 1);
    /// digraph.add_arc_weighted(3, 5, 1);
    /// digraph.add_arc_weighted(4, 2, 3);
    /// digraph.add_arc_weighted(5, 6, 1);
    /// digraph.add_arc_weighted(6, 0, 9);
    /// digraph.add_arc_weighted(6, 1, 8);
    /// digraph.add_arc_weighted(6, 2, 5);
    ///
    /// assert!(FloydWarshall::new(&digraph).distances().is_connected());
    /// ```
    #[must_use]
    pub fn is_connected(&self) -> bool
    where
        W: Ord,
    {
        self.eccentricities().all(|e| e != &self.infinity)
    }

    /// Return a digraph's periphery.
    ///
    /// A digraph's periphery is the set of vertices with an eccentricity equal
    /// to its diameter.
    ///
    /// # Examples
    ///
    /// ```
    /// use graaf::{
    ///     AddArcWeighted,
    ///     AdjacencyListWeighted,
    ///     DistanceMatrix,
    ///     Empty,
    ///     FloydWarshall,
    /// };
    ///
    /// let mut digraph = AdjacencyListWeighted::<isize>::empty(7);
    ///
    /// digraph.add_arc_weighted(0, 1, 5);
    /// digraph.add_arc_weighted(0, 2, 3);
    /// digraph.add_arc_weighted(0, 3, 2);
    /// digraph.add_arc_weighted(0, 4, 4);
    /// digraph.add_arc_weighted(1, 0, 3);
    /// digraph.add_arc_weighted(1, 3, 1);
    /// digraph.add_arc_weighted(1, 4, 2);
    /// digraph.add_arc_weighted(2, 6, 4);
    /// digraph.add_arc_weighted(3, 4, 1);
    /// digraph.add_arc_weighted(3, 5, 1);
    /// digraph.add_arc_weighted(4, 2, 3);
    /// digraph.add_arc_weighted(5, 6, 1);
    /// digraph.add_arc_weighted(6, 0, 9);
    /// digraph.add_arc_weighted(6, 1, 8);
    /// digraph.add_arc_weighted(6, 2, 5);
    ///
    /// assert!(FloydWarshall::new(&digraph).distances().periphery().eq([4]));
    /// ```
    pub fn periphery(&self) -> impl Iterator<Item = usize>
    where
        W: Copy + Ord,
    {
        let ecc = self.eccentricities();
        let diameter = self.diameter();

        ecc.enumerate()
            .filter_map(move |(i, e)| (e == diameter).then_some(i))
    }
}

impl<W> Index<usize> for DistanceMatrix<W> {
    type Output = W;

    fn index(&self, index: usize) -> &Self::Output {
        &self.dist[index]
    }
}

impl<W> IndexMut<usize> for DistanceMatrix<W> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.dist[index]
    }
}

impl<W> Index<(usize, usize)> for DistanceMatrix<W> {
    type Output = W;

    fn index(&self, index: (usize, usize)) -> &Self::Output {
        &self.dist[index.0 * self.order + index.1]
    }
}

impl<W> IndexMut<(usize, usize)> for DistanceMatrix<W> {
    fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {
        &mut self.dist[index.0 * self.order + index.1]
    }
}

impl<W> Index<RangeFull> for DistanceMatrix<W> {
    type Output = [W];

    fn index(&self, _: RangeFull) -> &Self::Output {
        &self.dist
    }
}

impl<W> IndexMut<RangeFull> for DistanceMatrix<W> {
    fn index_mut(&mut self, _: RangeFull) -> &mut Self::Output {
        &mut self.dist
    }
}

impl<W> Index<Range<usize>> for DistanceMatrix<W> {
    type Output = [W];

    fn index(&self, index: Range<usize>) -> &Self::Output {
        &self.dist[index]
    }
}

impl<W> IndexMut<Range<usize>> for DistanceMatrix<W> {
    fn index_mut(&mut self, index: Range<usize>) -> &mut Self::Output {
        &mut self.dist[index]
    }
}

#[cfg(test)]
mod tests {
    use {
        super::*,
        crate::{
            AdjacencyListWeighted,
            Empty,
            FloydWarshall,
            RemoveArc,
            repr::adjacency_list_weighted::fixture::{
                kattis_bryr_1_isize,
                kattis_bryr_2_isize,
                kattis_bryr_3_isize,
                kattis_crosscountry_isize,
            },
        },
    };

    #[test]
    fn center_kattis_bryr_1() {
        let digraph = kattis_bryr_1_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.center().iter().eq(&[0, 1, 2]));
    }

    #[test]
    fn center_kattis_bryr_2() {
        let digraph = kattis_bryr_2_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.center().iter().eq(&[3]));
    }

    #[test]
    fn center_kattis_bryr_3() {
        let digraph = kattis_bryr_3_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.center().iter().eq(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
    }

    #[test]
    fn center_kattis_crosscountry() {
        let digraph = kattis_crosscountry_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.center().iter().eq(&[3]));
    }

    #[test]
    fn center_trivial() {
        let digraph = AdjacencyListWeighted::<isize>::trivial();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.center().iter().eq(&[0]));
    }

    #[test]
    fn diameter_kattis_bryr_1() {
        let digraph = kattis_bryr_1_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert_eq!(dist.diameter(), &1);
    }

    #[test]
    fn diameter_kattis_bryr_2() {
        let digraph = kattis_bryr_2_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert_eq!(dist.diameter(), &4);
    }

    #[test]
    fn diameter_kattis_bryr_3() {
        let digraph = kattis_bryr_3_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert_eq!(dist.diameter(), &1);
    }

    #[test]
    fn diameter_kattis_crosscountry() {
        let digraph = kattis_crosscountry_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert_eq!(dist.diameter(), &11);
    }

    #[test]
    fn diameter_trivial() {
        let digraph = AdjacencyListWeighted::<isize>::trivial();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert_eq!(dist.diameter(), &0);
    }

    #[test]
    fn eccentricities_kattis_bryr_1() {
        let digraph = kattis_bryr_1_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.eccentricities().eq(&[1, 1, 1]));
    }

    #[test]
    fn eccentricities_kattis_bryr_2() {
        let digraph = kattis_bryr_2_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.eccentricities().eq(&[3, 4, 3, 2, 3, 4]));
    }

    #[test]
    fn eccentricities_kattis_bryr_3() {
        let digraph = kattis_bryr_3_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.eccentricities().eq(&[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]));
    }

    #[test]
    fn eccentricities_kattis_crosscountry() {
        let digraph = kattis_crosscountry_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.eccentricities().eq(&[10, 11, 7, 6]));
    }

    #[test]
    fn eccentricities_trivial() {
        let digraph = AdjacencyListWeighted::<isize>::trivial();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.eccentricities().eq(&[0]));
    }

    #[test]
    fn index_usize() {
        let dist = DistanceMatrix::new(4, isize::MAX);

        assert_eq!(dist[0], isize::MAX);
        assert_eq!(dist[1], isize::MAX);
        assert_eq!(dist[2], isize::MAX);
        assert_eq!(dist[3], isize::MAX);
    }

    #[test]
    fn index_mut_usize() {
        let mut dist = DistanceMatrix::new(4, isize::MAX);

        dist[0] = 1;
        dist[1] = 2;
        dist[2] = 3;
        dist[3] = 4;

        assert!(dist[0..4].iter().eq(&[1, 2, 3, 4]));
    }

    #[test]
    fn index_tuple() {
        let dist = DistanceMatrix::new(4, isize::MAX);

        assert_eq!(dist[(0, 0)], isize::MAX);
        assert_eq!(dist[(0, 1)], isize::MAX);
        assert_eq!(dist[(0, 2)], isize::MAX);
        assert_eq!(dist[(0, 3)], isize::MAX);
        assert_eq!(dist[(1, 0)], isize::MAX);
        assert_eq!(dist[(1, 1)], isize::MAX);
        assert_eq!(dist[(1, 2)], isize::MAX);
        assert_eq!(dist[(1, 3)], isize::MAX);
        assert_eq!(dist[(2, 0)], isize::MAX);
        assert_eq!(dist[(2, 1)], isize::MAX);
        assert_eq!(dist[(2, 2)], isize::MAX);
        assert_eq!(dist[(2, 3)], isize::MAX);
        assert_eq!(dist[(3, 0)], isize::MAX);
        assert_eq!(dist[(3, 1)], isize::MAX);
        assert_eq!(dist[(3, 2)], isize::MAX);
        assert_eq!(dist[(3, 3)], isize::MAX);
    }

    #[test]
    fn index_mut_tuple() {
        let mut dist = DistanceMatrix::new(4, isize::MAX);

        dist[(0, 0)] = 1;
        dist[(0, 1)] = 2;
        dist[(0, 2)] = 3;
        dist[(0, 3)] = 4;
        dist[(1, 0)] = 5;
        dist[(1, 1)] = 6;
        dist[(1, 2)] = 7;
        dist[(1, 3)] = 8;
        dist[(2, 0)] = 9;
        dist[(2, 1)] = 10;
        dist[(2, 2)] = 11;
        dist[(2, 3)] = 12;
        dist[(3, 0)] = 13;
        dist[(3, 1)] = 14;
        dist[(3, 2)] = 15;
        dist[(3, 3)] = 16;

        assert!(dist[0..4].iter().eq(&[1, 2, 3, 4]));
        assert!(dist[4..8].iter().eq(&[5, 6, 7, 8]));
        assert!(dist[8..12].iter().eq(&[9, 10, 11, 12]));
        assert!(dist[12..16].iter().eq(&[13, 14, 15, 16]));
    }

    #[test]
    fn index_range_full() {
        let dist = DistanceMatrix::new(4, isize::MAX);

        assert!(dist[..].iter().eq(&[isize::MAX; 16]));
    }

    #[test]
    fn index_mut_range_full() {
        let mut dist = DistanceMatrix::new(4, isize::MAX);

        dist[..].iter_mut().for_each(|d| *d = 1);

        assert!(dist[0..4].iter().eq(&[1; 4]));
        assert!(dist[4..8].iter().eq(&[1; 4]));
        assert!(dist[8..12].iter().eq(&[1; 4]));
        assert!(dist[12..16].iter().eq(&[1; 4]));
    }

    #[test]
    fn index_range() {
        let dist = DistanceMatrix::new(4, isize::MAX);

        assert!(dist[0..4].iter().eq(&[isize::MAX; 4]));
        assert!(dist[4..8].iter().eq(&[isize::MAX; 4]));
        assert!(dist[8..12].iter().eq(&[isize::MAX; 4]));
        assert!(dist[12..16].iter().eq(&[isize::MAX; 4]));
    }

    #[test]
    fn index_mut_range() {
        let mut dist = DistanceMatrix::new(4, isize::MAX);

        dist[0..4].iter_mut().for_each(|d| *d = 1);
        dist[4..8].iter_mut().for_each(|d| *d = 2);
        dist[8..12].iter_mut().for_each(|d| *d = 3);
        dist[12..16].iter_mut().for_each(|d| *d = 4);

        assert!(dist[0..4].iter().eq(&[1; 4]));
        assert!(dist[4..8].iter().eq(&[2; 4]));
        assert!(dist[8..12].iter().eq(&[3; 4]));
        assert!(dist[12..16].iter().eq(&[4; 4]));
    }

    #[test]
    fn is_connected_kattis_bryr_1() {
        let mut digraph = kattis_bryr_1_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.is_connected());
        assert!(digraph.remove_arc(1, 0));
        assert!(digraph.remove_arc(2, 0));

        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(!dist.is_connected());
    }

    #[test]
    fn is_connected_kattis_bryr_2() {
        let mut digraph = kattis_bryr_2_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.is_connected());
        assert!(digraph.remove_arc(3, 4));

        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(!dist.is_connected());
    }

    #[test]
    fn is_connected_kattis_bryr_3() {
        let mut digraph = kattis_bryr_3_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.is_connected());
        assert!(digraph.remove_arc(0, 3));
        assert!(digraph.remove_arc(3, 0));

        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(!dist.is_connected());
    }

    #[test]
    fn is_connected_kattis_crosscountry() {
        let mut digraph = kattis_crosscountry_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.is_connected());
        assert!(digraph.remove_arc(0, 1));
        assert!(digraph.remove_arc(2, 1));
        assert!(digraph.remove_arc(3, 1));

        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(!dist.is_connected());
    }

    #[test]
    fn is_connected_trivial() {
        let digraph = AdjacencyListWeighted::<isize>::trivial();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.is_connected());
    }

    #[test]
    fn new() {
        let dist = DistanceMatrix::new(4, isize::MAX);

        assert_eq!(dist.infinity, isize::MAX);
        assert!(dist[0..4].iter().eq(&[isize::MAX; 4]));
        assert!(dist[4..8].iter().eq(&[isize::MAX; 4]));
        assert!(dist[8..12].iter().eq(&[isize::MAX; 4]));
        assert!(dist[12..16].iter().eq(&[isize::MAX; 4]));
    }

    #[test]
    #[should_panic(expected = "a distance matrix has at least one vertex")]
    fn new_0() {
        drop(DistanceMatrix::new(0, isize::MAX));
    }

    #[test]
    fn periphery_kattis_bryr_1() {
        let digraph = kattis_bryr_1_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.periphery().eq([0, 1, 2]));
    }

    #[test]
    fn periphery_kattis_bryr_2() {
        let digraph = kattis_bryr_2_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.periphery().eq([1, 5]));
    }

    #[test]
    fn periphery_kattis_bryr_3() {
        let digraph = kattis_bryr_3_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.periphery().eq([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
    }

    #[test]
    fn periphery_kattis_crosscountry() {
        let digraph = kattis_crosscountry_isize();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.periphery().eq([1]));
    }

    #[test]
    fn periphery_trivial() {
        let digraph = AdjacencyListWeighted::<isize>::trivial();
        let mut floyd_warshall = FloydWarshall::new(&digraph);
        let dist = floyd_warshall.distances();

        assert!(dist.periphery().eq([0]));
    }
}