################################################################################ ## Function: R <- warshall (R0) ## Inputs: R0 >= 0 is a (t by t) adjacency matrix (directed graph) representing ## a (direct) revealed preference relation, t >= 1 is the number of ## observations (vertices in the directed graph) ## Outputs: R >= 0 is a matrix representing the transitive closure of R0 ## Description: returns a matrix R which is the transitive closure of the ## adjacency matrix R0 by applying Warshall's Algorithm ################################################################################ warshall <- function (R0) { # number of observations t <- dim (R0)[1] # initialize transitive closure R <- R0 # compute transitive closure for (k in 1 : t) { for (i in (1 : t)[-k]) { if (R[i, k] == 1) { for (j in (1 : t)[-k]) { if (R[i, j] == 0) { R[i, j] <- R[k, j] } } } } } # clean and return result result <- R remove (i, j, k, R, R0, t) return (result) }