Module Avl_tarjan

module Avl_tarjan: sig  end

Tarjan's algorithm: calculating SCC of a graph in linear time.

This module provides an implementation of Tarjan's algorithm. This algorithm computes the strong connex composants of a directed graph (SCC). A SCC of a graph $G = (X, E)$ is a subset of $X$ such that for every pair of nodes $x_1$ and $x_2$ in $X$ there exists a path from the former to the latter in $G$. The SCCs of $G$ form a partition of $X$.

The Tarjan's algorithm has a time complexity in $O(n)$ (where $n$ is the number of nodes of the input graph).

Functions provided by this module are not reentering thread safe as long as at most one thread operates on the same graph at the same time.

module type GRAPH = sig  end

The client must provide an implementation of graphs which fullfills the signature GRAPH.

module Make: functor (X : GRAPH) -> sig  end