Struct Graph 

pub struct Graph { /* private fields */ }

This struct represents a combinatorial undirected graph. It is used to generate the input for test cases and to check the output of solutions.

Implementations

impl Graph

pub fn new_empty(n: i32) -> Self

This function creates a new empty graph with n nodes and no edges.

pub fn new_full(n: i32) -> Self

This function creates a new full graph with n nodes and all possible edges.

pub fn new_random(n: i32, m: i32) -> Self

This function creates a new random graph with n nodes and m edges. The edges are chosen randomly.

pub fn new_random_tree(n: i32) -> Self

This function creates a new random tree with n nodes and n - 1 edges by the definition of a tree. The edges are chosen randomly.

pub fn new_random_connected(n: i32, m: i32) -> Self

This function creates a new random connected graph with n nodes and m edges. The edges are chosen randomly and the graph is guaranteed to be connected. If m <= n - 1, the graph will be a tree.

pub fn new_random_bipartite(n: i32, m: i32) -> Self

This function creates a new random bipartite graph with n nodes and m edges. The edges are chosen randomly and the graph is guaranteed to be bipartite.

pub fn new_from_input(input: &str) -> Option<Self>

This function creates a new graph from an input string. The input string should be formatted as follows: The first line should contain two integers n and m, the number of nodes and edges respectively. The next m lines should contain two integers u and v, representing an edge between nodes u and v. The nodes are 1-indexed.

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

This function returns true if there is an edge between nodes u and v. If u == v, this function will return false. Also for every pair of nodes u, v, the following holds: has_edge(u, v) == has_edge(v, u)

pub fn get_num_edges(&self) -> i32

This function returns the count of edges between nodes u and v.

pub const fn get_num_nodes(&self) -> i32

This function returns the count of nodes in the graph.

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

This function adds an edge between nodes u and v.

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

This function returns an iterator over the edges in the graph.

pub fn create_output(&self) -> String

This function converts the graph to an input string. The input string will be formatted as follows: The first line will contain two integers n and m, the number of nodes and edges respectively. The next m lines will contain two integers u and v, representing an edge between nodes u and v. The nodes are 1-indexed. The edges will be randomly shuffled and pair may be swapped.

pub fn create_output_edges(&self) -> String

This function only converts edges to an input string. The input string will be formatted as follows: M lines will contain two integers u and v, representing an edge between nodes u and v. The nodes are 1-indexed.

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

This function returns the array of connected components in the graph. Each connected component is represented by an array of node indices. The nodes are 0-indexed and the arrays are in undefined order.

pub fn is_connected(&self) -> bool

This function returns true if the graph is connected.

pub fn is_tree(&self) -> bool

This function returns true if the graph is a tree.

pub fn is_full(&self) -> bool

This function returns true if the graph has every possible edge.

pub fn is_bipartite(&self) -> bool

This function returns true if the graph is bipartite.