Struct Graph

pub struct Graph {
    pub adjacency: Vec<Vec<PointId>>,
    pub degree: Vec<usize>,
    pub p_min_degree: usize,
    pub p_max_degree: usize,
    /* private fields */
}

Defines a graph structure to assist in renumbering a mesh

Fields

adjacency: Vec<Vec<PointId>>

Holds the adjacency (sparse) matrix (point connections)

Note: each row in this matrix is sorted in ascending order of degree, followed by id

degree: Vec<usize>

Holds all point degrees (the number of connections of a vertex)

p_min_degree: usize

Holds the id of the point with the minimum degree

p_max_degree: usize

Holds the id of the point with the maximum degree

Implementations

impl Graph

pub fn new(mesh: &Mesh, check_connectivity: bool) -> Result<Self, StrError>

Allocates a new instance

Input

• check_connectivity – checks if the graph is connected

pub fn cuthill_mckee( &mut self, start_point: Option<PointId>, ) -> Result<Vec<PointId>, StrError>

Computes the ordering array to renumber the vertices according to the (reverse) Cuthill-McKee algorithm

Note: All nodes must be reachable from the root; i.e., the corresponding graph must be connected.

Input

• start_point – (root) the first point id, which will not be renumbered. Should have a low degree. If None, a pseudo-peripheral point is determined and used as root.

Output

Returns the ordering array such that old = ordering[new] where old is the original point id and new is the new point id. See the function Graph::get_old_to_new_map

pub fn calc_distance(&mut self, root: usize) -> usize

Runs a BFS to compute the distances (levels) from every vertex to the root vertex

Input

• root – The root point

Output

Returns the max_distance

pub fn pseudo_peripheral(&mut self, start_point: Option<PointId>) -> usize

Finds a pseudo-peripheral point

Input

• start_point – (root) the first point id, which will not be renumbered. Should have a low degree. If None, a point with a minimum degree will be used.

pub fn calc_bandwidth(&self) -> usize

Calculates the (half) bandwidth (with diagonal) of the adjacency matrix

band = max{band_i, 0 ≤ n ≤ npoint-1}
band_i = max{|i - j| + 1, any j > i}

pub fn print_non_zero_pattern(&self)

Prints the non-zero pattern of the laplacian matrix

L = D - A

L: Laplacian matrix
A: Adjacency matrix
D: Diagonal matrix with the degrees

pub fn get_old_to_new_map(ordering: &[PointId]) -> Vec<PointId>

Converts the ordering array to the old_to_new map

old = ordering[new]
new = old_to_new[old]
Returns the ordering array such that `ordering[new_point_id] = old_point_id`

pub fn renumber_mesh( mesh: &mut Mesh, check_connectivity: bool, ) -> Result<(), StrError>

Renumbers a mesh using Cuthill-McKey algorithm with pseudo-peripheral starting point

Input

• check_connectivity – checks if the associated graph is connected