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

Edges can then be added with the .add_edge() method.

Example

This example creates a graph with three vertices connected together in a cycle.

use toposort_scc::IndexGraph;

let mut g = IndexGraph::with_vertices(3);
g.add_edge(0, 1);
g.add_edge(1, 2);
g.add_edge(2, 0);

pub fn from_adjacency_list<S>(g: &[S]) -> Self where
    S: AsRef<[usize]>, 

Create a new graph from a list of adjacent vertices

The graph will contain outgoing edges from each vertex to the vertices in its adjacency list.

Example

This example creates an IndexGraph of the example graph from the Wikipedia page for Topological sorting.

use toposort_scc::IndexGraph;

let g = IndexGraph::from_adjacency_list(&vec![
    vec![3],
    vec![3, 4],
    vec![4, 7],
    vec![5, 6, 7],
    vec![6],
    vec![],
    vec![],
    vec![]
]);

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.

This method is useful for creating IndexGraphs from existing structures.

Example

This example creates a graph of dependencies in a hypothetical compiler or build tool, with edges from a dependency to the targets that use them.

use toposort_scc::IndexGraph;

// a target during compilation, having a name and dependencies
struct Target { name: &'static str, deps: Vec<usize> }
impl Target {
    fn new(name: &'static str, deps: Vec<usize>) -> Self {
        Target { name, deps }
    }
}

let targets = vec![
    Target::new("program", vec![1, 2, 4]),
    Target::new("main.c", vec![3]),
    Target::new("util.c", vec![3]),
    Target::new("util.h", vec![]),
    Target::new("libfoo.so", vec![])
];

let g = IndexGraph::from_graph(&targets, |mut builder, target| {
    for &dep in &target.deps {
        builder.add_in_edge(dep);
    }
});

To get a graph with edges in the other direction, use .add_out_edge() or the .transpose() method of the graph.

More complicated graph structures or structures that don't store edges as indices will need to first create a Map to look up indices in. Alternatively, the ArenaGraph type from the id-arena feature can be used.

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

Inverts the direction of all edges in the graph

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

Try to perform topological sort on the graph

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, returns the graph as Err(self).

For examples, see IndexGraph::toposort()

pub fn toposort(self) -> Option<Vec<usize>>

Perform topological sort on the graph

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

If the graph contains cycles, returns None.

Example

This example creates an IndexGraph of the example graph from the Wikipedia page for Topological sorting and performs a topological sort.

A copy of the graph with cycles in it is created to demonstrate failure.

use toposort_scc::IndexGraph;

let g = IndexGraph::from_adjacency_list(&vec![
    vec![3],
    vec![3, 4],
    vec![4, 7],
    vec![5, 6, 7],
    vec![6],
    vec![],
    vec![],
    vec![]
]);

let mut g2 = g.clone();
g2.add_edge(0, 0); // trivial cycle [0]
g2.add_edge(6, 2); // cycle [2, 4, 6]

assert_eq!(g.toposort(), Some(vec![0, 1, 2, 3, 4, 5, 7, 6]));
assert_eq!(g2.toposort(), None);

pub fn scc(self) -> Vec<Vec<usize>>

Find strongly connected components

Finds the strongly connected components of this graph using Kosaraju's algorithm and returns them.

Example

This examples creates an IndexGraph of the example graph from the Wikipedia page for Strongly connected compoents and finds the strongly connected components.

use toposort_scc::IndexGraph;

let g = IndexGraph::from_adjacency_list(&vec![
    vec![1],
    vec![2, 4, 5],
    vec![3, 6],
    vec![2, 7],
    vec![0, 5],
    vec![6],
    vec![5],
    vec![3, 6]
]);

assert_eq!(g.scc(), vec![vec![4, 1, 0], vec![3, 2, 7], vec![5, 6]]);

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).

Example

This example creates an IndexGraph of the example graph from the Wikipedia page for Topological sorting and performs a topological sort.

A copy of the graph with cycles in it is created to demonstrate finding of strongly connected components.

use toposort_scc::IndexGraph;

let g = IndexGraph::from_adjacency_list(&vec![
    vec![3],
    vec![3, 4],
    vec![4, 7],
    vec![5, 6, 7],
    vec![6],
    vec![],
    vec![],
    vec![]
]);

let mut g2 = g.clone();
g2.add_edge(0, 0); // trivial cycle [0]
g2.add_edge(6, 2); // cycle [2, 4, 6]

assert_eq!(g.toposort_or_scc(), Ok(vec![0, 1, 2, 3, 4, 5, 7, 6]));
assert_eq!(g2.toposort_or_scc(), Err(vec![vec![0], vec![4, 2, 6]]));

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.