Struct algorithms_edu::algo::graph::WeightedUndirectedAdjacencyMatrixCondensed

pub struct WeightedUndirectedAdjacencyMatrixCondensed { /* fields omitted */ }

An adjacency matrix representing an undirected graph is symmetric with respect to the main diagonal, i.e. g[i][j] = g[j][i]. Thus, only half of the values in the matrix need to be stored. In addition, The assumption that g[i][i] = 0 works fine in most cases, so weights representing these self-pointing edges are also not stored.

Thus a condensed matrix stores only g[i][j] where i < j in a vector of length ${}^{n}C_{2} = \dfrac{n(n-1)}{2}$ (n-choose-2). For example, in a graph with 4 vertices, the 6 weights in the condensed vector represents g[0 -> 1], g[0 -> 2], g[0 -> 3], g[1 -> 2], g[1 -> 3], g[2 -> 3], respectively.

Implementations

impl WeightedUndirectedAdjacencyMatrixCondensed

pub fn new(node_count: usize) -> Self

pub fn from_adjacency_list(inp: &WeightedAdjacencyList) -> Self

Build a WeightedUndirectedAdjacencyMatrixCondensed from WeightedAdjacencyList. The graph must be undirected. Even if the WeightedAdjacencyList were build with directed edges, they are treated as undirected edges.

Panics

Panics if the WeightedAdjacencyList contains both g[i -> j] and g[j -> i] but their weights differ

pub fn from_slice(inp: &[f64]) -> Self

Builds a WeightedUndirectedAdjacencyMatrixCondensed from its inner representation.

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

Iterate over all pairs of nodes (i, j) where i < j with the weight associated with the pair. Each item is a tuple of 3: (i, j, weight). Note that only (i, j) but not (j, i) is outputted.

pub fn node_count(&self) -> usize

Number of nodes (vertices) in the graph

pub fn resized(&self, new_node_count: usize) -> Self

Trait Implementations

impl Debug for WeightedUndirectedAdjacencyMatrixCondensed

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

Formats the value using the given formatter.

impl Display for WeightedUndirectedAdjacencyMatrixCondensed

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

Formats the value using the given formatter.

impl From<WeightedAdjacencyList> for WeightedUndirectedAdjacencyMatrixCondensed

pub fn from(inp: WeightedAdjacencyList) -> Self

Performs the conversion.

impl Index<(usize, usize)> for WeightedUndirectedAdjacencyMatrixCondensed

This allows indexing into graphs represented by WeightedUndirectedAdjacencyMatrixCondensed easier. For example, for a graph g, either g[(i, j)] or g[(j, i)] will give the weight associated with node i and node j (remember the graph is undirected)

type Output = f64

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl IndexMut<(usize, usize)> for WeightedUndirectedAdjacencyMatrixCondensed

pub fn index_mut(&mut self, (i, j): (usize, usize)) -> &mut Self::Output

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