Struct DistanceMatrix

#[non_exhaustive]
pub struct DistanceMatrix<W> {
    pub dist: Vec<W>,
    pub infinity: W,
    pub order: usize,
}

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.

The distance matrix

The corresponding DistanceMatrix generated by FloydWarshall::distances.

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]));

Fields (Non-exhaustive)

Non-exhaustive structs could have additional fields added in future. Therefore, non-exhaustive structs cannot be constructed in external crates using the traditional Struct { .. } syntax; cannot be matched against without a wildcard ..; and struct update syntax will not work.

dist: Vec<W>

The distance matrix.

infinity: W

The distance between unconnected vertices.

order: usize

The number of vertices.

Implementations

impl<W> DistanceMatrix<W>

pub fn new(order: usize, infinity: W) -> Self

where W: Copy,

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]);

pub fn center(&self) -> Vec<usize>

where W: Copy + Ord,

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.

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]));

pub fn diameter(&self) -> &W

where W: Copy + Ord,

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.

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);

pub fn eccentricities(&self) -> impl Iterator<Item = &W>

where W: Ord,

Return the digraph’s eccentricities.

A vertex’s eccentricity is the maximum distance to any other vertex.

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()
    .eccentricities()
    .eq(&[5, 5, 14, 11, 17, 11, 10]));

pub fn is_connected(&self) -> bool

where W: Ord,

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());

pub fn periphery(&self) -> impl Iterator<Item = usize> + '_

where W: Copy + Ord,

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]));

Trait Implementations

impl<W: Clone> Clone for DistanceMatrix<W>

fn clone(&self) -> DistanceMatrix<W>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<W: Debug> Debug for DistanceMatrix<W>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<W: Hash> Hash for DistanceMatrix<W>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<W> Index<(usize, usize)> for DistanceMatrix<W>

type Output = W

The returned type after indexing.

fn index(&self, index: (usize, usize)) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<W> Index<Range<usize>> for DistanceMatrix<W>

type Output = [W]

The returned type after indexing.

fn index(&self, index: Range<usize>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<W> Index<RangeFull> for DistanceMatrix<W>

type Output = [W]

The returned type after indexing.

fn index(&self, _: RangeFull) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<W> Index<usize> for DistanceMatrix<W>

type Output = W

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<W> IndexMut<(usize, usize)> for DistanceMatrix<W>

fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<W> IndexMut<Range<usize>> for DistanceMatrix<W>

fn index_mut(&mut self, index: Range<usize>) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<W> IndexMut<RangeFull> for DistanceMatrix<W>

fn index_mut(&mut self, _: RangeFull) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<W> IndexMut<usize> for DistanceMatrix<W>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<W: Ord> Ord for DistanceMatrix<W>

fn cmp(&self, other: &DistanceMatrix<W>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<W: PartialEq> PartialEq for DistanceMatrix<W>

fn eq(&self, other: &DistanceMatrix<W>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<W: PartialOrd> PartialOrd for DistanceMatrix<W>

fn partial_cmp(&self, other: &DistanceMatrix<W>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<W: Eq> Eq for DistanceMatrix<W>

impl<W> StructuralPartialEq for DistanceMatrix<W>