compute_reachability: Compute Reachability Matrix

In ISMtools: Interpretive Structural Modelling Analysis Tools

Compute Reachability Matrix

Description

Calculates the reachability matrix from an adjacency matrix using Warshall's algorithm. The reachability matrix shows all direct and indirect relationships between elements in a system.

Usage

compute_reachability(adj_matrix, include_self = TRUE)

Arguments

adj_matrix	A square adjacency matrix (n x n) containing only 0s and 1s. A value of 1 at position (i,j) indicates that element i directly influences element j.
include_self	Logical. If TRUE (default), the diagonal elements are set to 1, indicating that each element can reach itself (self-reachability). This is the standard ISM convention.

Details

The function implements Warshall's algorithm for computing the transitive closure of a directed graph. The time complexity is O(n^3) where n is the number of elements.

In standard ISM methodology, the reachability matrix is defined as:

R = (A + I)^k

where A is the adjacency matrix, I is the identity matrix, and k is the smallest integer such that (A + I)^k = (A + I)^{k+1}.

The diagonal elements being 1 (self-reachability) is essential for correct level partitioning in ISM analysis.

Value

A reachability matrix of the same dimension as the input.

• A value of 1 at position (i,j) indicates that element i can reach element j either directly or through intermediate elements.

• When include_self = TRUE, diagonal elements are always 1.

References

Warfield, J. N. (1974). Developing interconnection matrices in structural modeling. IEEE Transactions on Systems, Man, and Cybernetics, SMC-4(1), 81-87. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1109/TSMC.1974.5408524")}

See Also

create_relation_matrix for creating adjacency matrices, level_partitioning for hierarchical decomposition, plot_ism for visualization.

Examples

# Create a 4x4 adjacency matrix
adj_matrix <- matrix(c(0, 1, 0, 0,
                       0, 0, 1, 1,
                       0, 0, 0, 0,
                       0, 0, 0, 0),
                     nrow = 4, byrow = TRUE)

# Compute reachability matrix (with self-reachability)
reach_matrix <- compute_reachability(adj_matrix)
print(reach_matrix)

# Note: diagonal elements are 1 (self-reachability)
diag(reach_matrix)

# With named elements
rownames(adj_matrix) <- colnames(adj_matrix) <- c("A", "B", "C", "D")
reach_matrix <- compute_reachability(adj_matrix)
print(reach_matrix)

ISMtools documentation built on March 13, 2026, 1:06 a.m.