deeptime.markov.tools.estimation.connected_sets

deeptime.markov.tools.estimation.connected_sets(C, directed=True)

Compute connected sets of microstates.

Connected components for a directed graph with edge-weights given by the count matrix.

Parameters:

• C (scipy.sparse matrix) – Count matrix specifying edge weights.

• directed (bool, optional) – Whether to compute connected components for a directed or undirected graph. Default is True.

Returns:

cc – Each entry is an array containing all vertices (states) in the corresponding connected component. The list is sorted according to the size of the individual components. The largest connected set is the first entry in the list, lcc=cc[0].

Return type:

list of arrays of integers

Notes

Viewing the count matrix as the adjacency matrix of a (directed) graph the connected components are given by the connected components of that graph. Connected components of a graph can be efficiently computed using Tarjan’s algorithm [1].

References

[1]

Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146–160, 1972.

Examples

>>> import numpy as np
>>> from deeptime.markov.tools.estimation import connected_sets

>>> C = np.array([[10, 1, 0], [2, 0, 3], [0, 0, 4]])
>>> cc_directed = connected_sets(C)
>>> cc_directed
[array([0, 1]), array([2])]

>>> cc_undirected = connected_sets(C, directed=False)
>>> cc_undirected
[array([0, 1, 2])]