Struct algorithms_edu::algo::graph::WeightedAdjacencyList

pub struct WeightedAdjacencyList { /* fields omitted */ }

A graph represented by a weighted adjacency list. Under the hood, a weighted adjacency list is a Vec of Vec of Edges. For an adjacency list g, g[i] is a Vec of edges pointing from i to other nodes (vertices). Thus, the number of nodes is implied by the len of the (outer) Vec. For each node i that do not have outgoing edges, g[i] is an empty vector.

Implementations

impl WeightedAdjacencyList

pub fn two_color(&self) -> Result<Vec<i8>, BipartiteCheckError>

impl WeightedAdjacencyList

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

Perform a depth first search on a graph with n nodes from a starting point to count the number of nodes in a given component.

In this particular implementation we just increment a counter each time we visit a new node. This, by itself, is not of much use, but you'll soon see that many other advanced algorithms are based on this DFS prototype.

impl WeightedAdjacencyList

pub fn kruskal(&self) -> Option<(f64, WeightedAdjacencyList)>

impl WeightedAdjacencyList

pub fn prim(&self) -> Option<(f64, WeightedAdjacencyList)>

impl WeightedAdjacencyList

pub fn bellman_ford(&self, start: usize) -> Vec<f64>

impl WeightedAdjacencyList

pub fn dijkstra(&self, start: usize, end: usize) -> Option<(f64, Vec<usize>)>

impl WeightedAdjacencyList

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

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

Imagine building a program with dependencies

pub fn dag_shortest_path(&self, start: usize) -> Vec<f64>

impl WeightedAdjacencyList

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

Is the graph devoid of vertices?

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

Add a directed edge from node u to node v with weight weight.

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

Add an undirected edge between nodes u and v.

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

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

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

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

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

Iterates over all edges in the gragh. Each item is a tuples of 3: (from, to, weight)

pub fn edge_count(&self) -> usize

Number of edges in the graph

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

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 Debug for WeightedAdjacencyList

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

Formats the value using the given formatter.

impl Display for WeightedAdjacencyList

Pretty-prints a small graph represented by a weighted adjacency list The graph is first converted to a WeightedAdjacencyMatrix before being printed

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

Formats the value using the given formatter.

impl From<WeightedAdjacencyList> for WeightedAdjacencyMatrix

For convinience

pub fn from(inp: WeightedAdjacencyList) -> Self

Performs the conversion.

impl From<WeightedAdjacencyList> for WeightedUndirectedAdjacencyMatrixCondensed

pub fn from(inp: WeightedAdjacencyList) -> Self

Performs the conversion.

impl Index<usize> for WeightedAdjacencyList

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

type Output = Vec<Edge>

The returned type after indexing.

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

Performs the indexing (container[index]) operation.