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

Check connectivity of the given matrix.

  • 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

Return type:



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.


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


>>> 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)
>>> T = np.array([[0.9, 0.1, 0.0], [0.5, 0.0, 0.5], [0.0, 0.1, 0.9]])
>>> is_connected(T)