Struct toposort_scc::IndexGraph

pub struct IndexGraph { /* fields omitted */ }

An adjacency-list-based graph data structure

Stores graph vertices as lists of incoming and outgoing edges by their index in the graph. No additional data is stored per vertex.

Implementations

impl IndexGraph

pub fn with_vertices(len: usize) -> Self

Create a new graph with len vertices and no edges

pub fn from_graph<T, F>(g: &[T], f: F) -> Self where
    F: FnMut(IndexGraphBuilder, &T), 

Create a new graph from an existing graph-like data structure

The given closure will be called once for every element of g, with an IndexGraphBuilder instance so that edges can be easily added.

pub fn iter(&self) -> SliceIter<Vertex>

Returns an iterator over the contained vertices

pub fn add_edge(&mut self, from: usize, to: usize)

Add a new edge to the graph

This method does not check for duplicate edges.

pub fn transpose(&mut self)

Transpose the graph

Changes the direction of all edges in the graph

pub fn toposort_or_scc(self) -> Result<Vec<usize>, Vec<Vec<usize>>>

Perform topological sort or find strongly connected components

If the graph contains no cycles, finds the topological ordering of this graph using Kahn's algorithm and returns it as Ok(sorted).

If the graph contains cycles, finds the strongly connected components of this graph using Kosaraju's algorithm and returns them as Err(cycles).

Trait Implementations

impl Clone for IndexGraph

fn clone(&self) -> IndexGraph

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for IndexGraph

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

Formats the value using the given formatter.

impl Index<usize> for IndexGraph

type Output = Vertex

The returned type after indexing.

fn index(&self, index: usize) -> &Vertex

Performs the indexing (container[index]) operation.

impl<'g> IntoIterator for &'g IndexGraph

type Item = &'g Vertex

The type of the elements being iterated over.

type IntoIter = SliceIter<'g, Vertex>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl IntoIterator for IndexGraph

type Item = Vertex

The type of the elements being iterated over.

type IntoIter = VecIntoIter<Vertex>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.