stronglyconncomp.h File Reference

Strongly connected components of a directed graph, and which of them are recurrent (closed under the successor relation). More...

#include <algorithm>
#include <cstddef>
#include <numeric>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for stronglyconncomp.h:

Go to the source code of this file.

Classes
struct	line::mc::SccResult

Namespaces
namespace	line
namespace	line::mc

Functions
template<class T>
SccResult	line::mc::stronglyconncomp (const Matrix< T > &A)
	Strongly connected components of a directed graph, and which of them are recurrent (closed under the successor relation).

Detailed Description

Strongly connected components of a directed graph, and which of them are recurrent (closed under the successor relation).

Templated port of matlab/util/stronglyconncomp.m, the decomposition on which dtmc_solve_reducible, ctmc_solve_reducible and ctmc_solve_reducible_blkdecomp all rest. Tarjan's algorithm, with the components renumbered by decreasing size exactly as MATLAB does (a stable sort, so components of equal size keep their completion order), and a component declared recurrent when no state in it has a successor outside it.

Two details of the MATLAB version are reproduced deliberately. The depth first search follows the COLUMNS of the adjacency matrix, i.e. the reversed graph, while the recurrence test follows the ROWS; the component partition is the same for a graph and its reverse, so this only affects the discovery order, but reproducing it keeps the component numbering identical when sizes tie. The recursion of the MATLAB original is replaced by an explicit stack, which visits vertices in the same order and does not overflow on the tens of thousands of states a lumped generator can carry.

The computation is combinatorial: an entry only ever has its non-zero-ness tested, no arithmetic is performed, so it is exact at every number type.

Definition in file stronglyconncomp.h.