Struct algorithms_edu::algo::graph::UnweightedAdjacencyList

pub struct UnweightedAdjacencyList { /* fields omitted */ }

An unweighted graph represented by an unweighted adjacency list. This is in principle the same as WeightedAdjacencyList, except that no weights are involved and thus a simple usize is able to represent an outgoing edge.

Implementations

impl UnweightedAdjacencyList

pub fn bfs(&self, start: usize) -> BfsResult

Perform a breadth first search on a graph a starting node start.

impl UnweightedAdjacencyList

pub fn dfs_recursive(&self, start: usize) -> usize

impl UnweightedAdjacencyList

pub fn eulerian_path(&self) -> Result<Vec<usize>, EulerianPathError>

Returns a list of edge_count + 1 node ids that give the Eulerian path or an EulerianPathError if no path exists or the graph is disconnected.

impl UnweightedAdjacencyList

pub fn scc(&self) -> SccResult

impl UnweightedAdjacencyList

pub fn center(&self) -> Center

Finds the center(s) of an undirected tree. The adjacency list must be build with undirected edges, and does not contain cycles, so that it qualifies the definition for a tree.

impl UnweightedAdjacencyList

pub fn is_isomorphic_with(&self, other: &UnweightedAdjacencyList) -> bool

impl UnweightedAdjacencyList

pub fn with_size(n: usize) -> Self

Initialize an empty adjacency list that can hold up to n nodes.

pub fn is_empty(&self) -> bool

pub fn add_directed_edge(&mut self, u: usize, v: usize)

Add a directed edge from node u to node v

pub fn add_undirected_edge(&mut self, u: usize, v: usize)

Add an undirected edge between nodes u and v.

pub fn new_directed(size: usize, edges: &[[usize; 2]]) -> Self

pub fn new_undirected(size: usize, edges: &[[usize; 2]]) -> Self

pub fn edges(&self) -> impl Iterator<Item = [usize; 2]> + '_

Iterates over all edges in the gragh. Each item is an array of length 2, showing the source and destination of this edge.

pub fn edge_count(&self) -> usize

Number of edges in the graph

pub fn nodes(&self) -> impl Iterator<Item = (usize, &Vec<usize>)>

Iterates over all nodes in the graph. Each item is a tuple of the node id and a Vec of all its outgoing edges

pub fn node_count(&self) -> usize

Number of nodes (vertices) in the graph

Trait Implementations

impl BfsReconstructPath for UnweightedAdjacencyList

pub fn bfs<T: Queue<usize>>(&self, start: usize) -> Vec<Option<usize>>

Perform a breadth first search on a graph a starting node start.

pub fn reconstruct_path<T: Queue<usize>>(
    &self,
    start: usize,
    end: usize
) -> Vec<usize>

impl Debug for UnweightedAdjacencyList

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

Formats the value using the given formatter.

impl Index<usize> for UnweightedAdjacencyList

Allows the outgoing edges of a node to be accessed easily.

type Output = Vec<usize>

The returned type after indexing.

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

Performs the indexing (container[index]) operation.