# msmtools.analysis.is_connected¶

msmtools.analysis.is_connected(T, directed=True)

Check connectivity of the given matrix.

Parameters: T ((M, M) ndarray or scipy.sparse matrix) – Matrix to check directed (bool (optional)) – If True respect direction of transitions, if False do not distinguish between forward and backward transitions is_connected – True, if T is connected, False otherwise bool

Notes

A transition matrix $$T=(t_{ij})$$ is connected if for any pair of states $$(i, j)$$ one can reach state $$j$$ from state $$i$$ in a finite number of steps.

In more precise terms: For any pair of states $$(i, j)$$ there exists a number $$N=N(i, j)$$, so that the probability of going from state $$i$$ to state $$j$$ in $$N$$ steps is positive, $$\mathbb{P}(X_{N}=j|X_{0}=i)>0$$.

A transition matrix with this property is also called irreducible.

Viewing the transition matrix as the adjency matrix of a (directed) graph the transition matrix is irreducible if and only if the corresponding graph has a single connected component. Connectivity of a graph can be efficiently checked using Tarjan’s algorithm.

References

 [1] Hoel, P G and S C Port and C J Stone. 1972. Introduction to Stochastic Processes.
 [2] Tarjan, R E. 1972. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1 (2): 146-160.

Examples

>>> import numpy as np
>>> from msmtools.analysis import is_connected

>>> A = np.array([[0.9, 0.1, 0.0], [0.5, 0.0, 0.5], [0.0, 0.0, 1.0]])
>>> is_connected(A)
False

>>> T = np.array([[0.9, 0.1, 0.0], [0.5, 0.0, 0.5], [0.0, 0.1, 0.9]])
>>> is_connected(T)
True