Struct prepona::storage::AdjMatrix

pub struct AdjMatrix<W, E: Edge<W>, Dir: EdgeDir = UndirectedEdge> { /* fields omitted */ }

AdjMatrix is a matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Note

From now on

• |V|: Means total number of vertices that are stored in the storage. Note that this is different from number of vertices that are present in the graph. Because even if you remove a vertex from storage, the allocated memory for that vertex will not get freed and will be reused again when adding a new vertex. You can retrieve the amount of |V| using total_vertex_count function(as opposed to number of vertices present in the graph which can be retrieved using vertex_count function). For more info and examples refer to total_vertex_count documentation.
• |E|: Means number of edges present in the graph.
• |E^out|: Means number of edges exiting a vertex(out degree of the vertex).
• |E_src->dst|: Means number of edges from vertex with id: src to vertex with id: dst.

Space complexity

Space complexity of AdjMatrix depends on wether Dir is Directed or Undirected.

• Directed: For directed graphs AdjMatrix stores matrix with |V|² + |E| elements.
• Undirected: For undirected graphs AdjMatrix stores a lower triangle matrix with (|V|² + |V|)/2 + |E| elements.

Generic Parameters

• W: Weight type associated with edges.
• E: Edge type that graph uses.
• Dir: Direction of edges: Directed or Undirected(default value).

Implementations

impl<W, E: Edge<W>, Dir: EdgeDir> AdjMatrix<W, E, Dir>

pub fn init() -> Self

Initializes an empty adjacency matrix.

AdjMatrix defines multiple types with different combination of values for generic parameters. These types are:

• Mat: An adjacency matrix that uses undirected default edges.
• DiMat: An adjacency matrix that uses directed default edges.
• FlowMat: An adjacency matrix that uses undirected flow edges.
• DiFlowMat: An adjacency matrix that uses directed flow edges.

Returns

An empty AdjMatrix.

Examples

use prepona::prelude::*;
use prepona::storage::{Mat, DiMat};

// To store an undirected graph with usize weights
let mat = Mat::<usize>::init();

// To store a directed graph with usize weights
let di_mat = DiMat::<usize>::init();

pub fn total_vertex_count(&self) -> usize

Returns

Total number of vertices in the storage(|V|).

Complexity

O(1)

Trait Implementations

impl<W: Any, E: Edge<W>, Dir: EdgeDir> GraphStorage<W, E, Dir> for AdjMatrix<W, E, Dir>

fn add_vertex(&mut self) -> usize

Adds a vertex to the graph.

Returns

Unique id of the newly added vertex.

Complexity

O(|V|)

fn remove_vertex_unchecked(&mut self, vertex_id: usize)

Removes the vertex with id: vertex_id from graph.

Arguments

vertex_id: Id of the vertex to be removed.

Complexity

O(|V|)

Panics

If vertex_id is not in range 0..|V|.

fn add_edge_unchecked(&mut self, src_id: usize, dst_id: usize, edge: E) -> usize

Adds edge from vertex with id :src_id to vertex with id: dst_id.

Arguments

• src_id: Id of the source vertex.
• dst_id: Id of the destination vertex.
• edge: Edge to be added from source to destination.

Returns

Unique id of the newly added edge.

Complexity

O(1)

Panics

If src_id or dst_id is not in 0..|V| range.

fn update_edge_unchecked(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize,
    edge: E
)

Replaces the edge with id: edge_id with edge.

Arguments

• src_id: Id of source vertex.
• dst_id: Id of destination vertex.
• edge_id: Id of the to be updated edge.
• edge: New edge to replace the old one.

Complexity

O(|E_src->dst|)

Panics

• If src_id or dst_id is not in range 0..|V|.

fn remove_edge_unchecked(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> E

Removes the edge with id: edge_id.

Arguments

• src_id: Id of source vertex.
• dst_id: Id of destination vertex.
• edge_id: Id of edge to be removed.

Returns

• Some: Containing the removed edge.
• None: If edge with edge_id does not exist in the graph.

Complexity

O(|E_src->dst|)

Panics

• If src_id or dst_id is not in range 0..|V|.
• If there is no edge with id: edge_id from src_id to dst_id.

fn vertex_count(&self) -> usize

Returns

Number of vertices in the graph.

Complexity

O(1)

fn edge_count(&self) -> usize

Returns

Number of edges in the graph.

Complexity:

O(1)

fn vertices(&self) -> Vec<usize>

Returns

Id of vertices that are present in the graph.

Complexity

O(|V|)

fn edges_from_unchecked(&self, src_id: usize) -> Vec<(usize, &E)>

Arguments

src_id: Id of the source vertex.

Returns

• All edges from the source vertex in the format of: (dst_id, edge)

Complexity

O(|E^*|)

Panics

If src_id is not in range 0..|V|.

fn neighbors_unchecked(&self, src_id: usize) -> Vec<usize>

Arguments:

src_id: Id of the source vertex.

Returns

Id of vertices accessible from source vertex using one edge.

Complexity O(|V|)

Panics

If src_id is not in range 0..|V|.

fn edges_between_unchecked(&self, src_id: usize, dst_id: usize) -> Vec<&E>

Arguments

• src_id: Id of source vertex.
• dst_id: Id of destination vertex.

Returns

Edges from source vertex to destination vertex.

Complexity

O(|E_src->dst|)

Panics

• If src_id or dst_id is not in range 0..|V|.

fn contains_vertex(&self, vertex_id: usize) -> bool

Arguments

vertex_id: Id of the vertex to search for its existence in the storage.

Returns

• true: If storage contains the vertex with id: vertex_id.
• false: Otherwise.

fn contains_edge(&self, edge_id: usize) -> bool

Arguments

edge_id: Id of the edge to search for its existence in the storage.

Returns

• true: If storage contains the edge with id: edge_id.
• false: Otherwise.

fn remove_vertex(&mut self, vertex_id: usize) -> Result<()>

Removes the vertex with id: vertex_id from storage.

fn add_edge(&mut self, src_id: usize, dst_id: usize, edge: E) -> Result<usize>

Adds edge from vertex with id src_id: to vertex with id: dst_id.

fn update_edge(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize,
    edge: E
) -> Result<()>

Replaces the edge with id: edge_id with edge.

fn remove_edge(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> Result<E>

Removes the edge with id: edge_id.

fn edges_between(&self, src_id: usize, dst_id: usize) -> Result<Vec<&E>>

Arguments

fn edge_between(
    &self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> Result<&E>

Arguments

fn edge_between_unchecked(
    &self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> &E

Arguments

fn edge(&self, edge_id: usize) -> Result<&E>

Note:

fn edge_unchecked(&self, edge_id: usize) -> &E

Note:

fn has_any_edge(&self, src_id: usize, dst_id: usize) -> Result<bool>

Arguments

fn has_any_edge_unchecked(&self, src_id: usize, dst_id: usize) -> bool

Arguments

fn edges(&self) -> Vec<(usize, usize, &E)>

Returns

fn as_directed_edges(&self) -> Vec<(usize, usize, &E)>

Difference between this function and edges is that this function treats each edge as a directed edge. For example consider storage: a — b If you call edges on this storage, you will get: (a, b, edge). But if you call as_directed_edges, you will get two elements: (a, b, edge) and (b, a, edge). It’s specifically useful in algorithms that are for directed graphs but can also be applied to undirected graphs if we treat the edges as directed. One example is BellmanFord algorithm.

fn edges_from(&self, src_id: usize) -> Result<Vec<(usize, &E)>>

Arguments

fn neighbors(&self, src_id: usize) -> Result<Vec<usize>>

Arguments:

fn is_directed(&self) -> bool

Returns

fn is_undirected(&self) -> bool

Returns

impl<W: Any, E: Edge<W>, Dir: EdgeDir> Index<(usize, usize)> for AdjMatrix<W, E, Dir>

type Output = Vec<E>

The returned type after indexing.

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

Arguments

• (src_id, dst_id): (Id of the source vertex, Id of the destination vertex).

Returns

Edges from vertex with id: src_id to vertex with id: dst_id.

Panics

• If src_id or dst_id is not in range 0..|V|.

impl<W: Any, E: Edge<W>, Dir: EdgeDir> IndexMut<(usize, usize)> for AdjMatrix<W, E, Dir>

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

Arguments

• (src_id, dst_id): (Id of the source vertex, Id of the destination vertex).

Returns

Edges from vertex with id: src_id to vertex with id: dst_id.

Panics

• If src_id or dst_id is not in range 0..|V|.