Struct SparseGraph

pub struct SparseGraph<'a> { /* private fields */ }

A SparseGraph represents an unweighted graph with V nodes and E edges using the compressed sparse row format.

Implementations

impl SparseGraph<'_>

pub fn new<'a>(idxptr: &'a [usize], indices: &'a [usize]) -> SparseGraph<'a>

Returns a sparse graph.

Arguments

• idxptr - Starting index in indices for each vertex. These must be strictly non-decreasing and less than indices.len. The length defines the number of nodes in the graph, V
• indices - Values in the range 0..V-1 indicating which nodes each vertex is linked to. The length defines the number edges in the graph, E.

Panics

Example

use sparse_graph::SparseGraph;

let (idxptr, indices) = (vec![0, 1, 3, 4, 5, 6], vec![1, 2, 3, 0, 4, 5, 3]);
let g = SparseGraph::new(&idxptr, &indices);

pub fn scc(&self) -> ConnectedComponents<'_>

Computes the strongly connected components using a memory optimised version of Tarjan’s algorithm.

See http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1707.

Returns

Example

use sparse_graph::{SparseGraph, ConnectedComponents};

// Create a graph with two strongly connect components
let (idxptr, indices) = (vec![0, 1, 3, 4, 5, 6], vec![1, 2, 3, 0, 4, 5, 3]);
let g = SparseGraph::new(&idxptr, &indices);
let ConnectedComponents { n, labels, sparse_graph } = g.scc();
assert_eq!(n, 2);
assert_eq!(labels, [1, 1, 1, 0, 0, 0]);
assert!(std::ptr::eq(sparse_graph, &g))

Trait Implementations

impl<'a> Debug for SparseGraph<'a>

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

Formats the value using the given formatter.

impl Display for SparseGraph<'_>

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

Formats the value using the given formatter.