Struct contest_algorithms::graph::Graph

pub struct Graph { /* fields omitted */ }

A compact graph representation. Edges are numbered in order of insertion. Each adjacency list consists of all edges pointing out from a given vertex.

Implementations

impl Graph

pub fn euler_path(&self, u: usize) -> Vec<usize>

Finds the sequence of edges in an Euler path starting from u, assuming it exists and that the graph is directed. Undefined behavior if this precondition is violated. To extend this to undirected graphs, maintain a visited array to skip the reverse edge.

pub fn min_spanning_tree(&self, weights: &[i64]) -> Vec<usize>

Kruskal's minimum spanning tree algorithm on an undirected graph.

pub fn dijkstra(&self, weights: &[u64], u: usize) -> Vec<u64>

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

impl Graph

pub fn new(vmax: usize, emax_hint: usize) -> Self

Initializes a graph with vmax vertices and no edges. To reduce unnecessary allocations, emax_hint should be close to the number of edges that will be inserted.

pub fn num_v(&self) -> usize

Returns the number of vertices.

pub fn num_e(&self) -> usize

Returns the number of edges, double-counting undirected edges.

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

Adds a directed edge from u to v.

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

An undirected edge is two directed edges. If edges are added only via this funcion, the reverse of any edge e can be found at e^1.

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

If we think of each even-numbered vertex as a variable, and its odd-numbered successor as its negation, then we can build the implication graph corresponding to any 2-CNF formula. Note that u||v == !u -> v == !v -> u.

pub fn adj_list(&self, u: usize) -> AdjListIteratorⓘ

Important traits for AdjListIterator<'a>

impl<'a> Iterator for AdjListIterator<'a> type Item = (usize, usize);

Gets vertex u's adjacency list.