Struct sparse_graph::SparseGraph [−][src]
pub struct SparseGraph<'a> { /* fields omitted */ }
Expand description
A SparseGraph
represents an unweighted graph with V
nodes and E
edges using the
compressed sparse row format.
Implementations
Returns a sparse graph.
Arguments
idxptr
- Starting index inindices
for each vertex. These must be strictly non-decreasing and less thanindices.len
. The length defines the number of nodes in the graph,V
indices
- Values in the range0..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);
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
Auto Trait Implementations
impl<'a> RefUnwindSafe for SparseGraph<'a>
impl<'a> Send for SparseGraph<'a>
impl<'a> Sync for SparseGraph<'a>
impl<'a> Unpin for SparseGraph<'a>
impl<'a> UnwindSafe for SparseGraph<'a>