Struct contest_algorithms::graph::connectivity::ConnectivityGraph

pub struct ConnectivityGraph<'a> {
    pub graph: &'a Graph,
    pub cc: Vec<usize>,
    pub vcc: Vec<usize>,
    pub num_cc: usize,
    pub num_vcc: usize,
}

Represents the decomposition of a graph into any of its constituent parts:

• Connected components (CC),
• Strongly connected components (SCC),
• 2-edge-connected components (2ECC),
• 2-vertex-connected components (2VCC)

Multiple-edges and self-loops are correctly handled.

Fields

graph: &'a Graph

cc: Vec<usize>

ID of a vertex's CC, SCC or 2ECC, whichever applies. Range 1 to num_cc.

vcc: Vec<usize>

ID of an edge's 2VCC, where applicable. Ranges from 1 to num_vcc.

num_cc: usize

Total number of CCs, SCCs or 2ECCs, whichever applies.

num_vcc: usize

Total number of 2VCCs, where applicable.

Implementations

impl<'a> ConnectivityGraph<'a>

pub fn new(graph: &'a Graph, is_directed: bool) -> Self

Computes CCs (connected components), SCCs (strongly connected components), 2ECCs (2-edge-connected components), and/or 2VCCs (2-vertex-connected components), depending on the parameter and graph:

• is_directed == true on directed graph: SCCs in rev-topological order
• is_directed == true on undirected graph: CCs
• is_directed == false on undirected graph: 2ECCs and 2VCCs
• is_directed == false on directed graph: undefined behavior

pub fn two_sat_assign(&self) -> Option<Vec<bool>>

From the directed implication graph corresponding to a 2-SAT clause, finds a satisfying assignment if it exists or returns None otherwise.

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

Gets the vertices of a graph according to a topological order of the strongly connected components. Most often used on DAGs.

pub fn is_cut_vertex(&self, u: usize) -> bool

In an undirected graph, determines whether u is an articulation vertex.

pub fn is_cut_edge(&self, e: usize) -> bool

In an undirected graph, determines whether e is a bridge