################################################################################
##  Function:     R <- warshall(R0)
##  Parameters:   n [number of observations/vertices]
##  Inputs:       R0 [(n by n) adjacency matrix/directed graph representing a
##                    (direct) revealed preference relation]
##  Outputs:      R [(n by n) matrix representing the transitive closure of the
##                   adjacency matrix/directed graph R0]
##  Libraries:    none
##  Calls:        none
##  Description:  returns a matrix representing the transitive closure of an
##                adjacency matrix/directed graph (Warshall's Algorithm)
################################################################################

warshall <- function(R0) {
  
  #  number of observations/vertices
  n <- dim(R0)[1]
  
  #  initialize transitive closure
  R <- R0
  
  #  compute transitive closure
  for (k in 1:n) {
    for (i in (1:n)[-k]) {
      if (R[i, k] == 1) {
        for (j in (1:n)[-k]) {
          if (R[i, j] == 0) {
            R[i, j] <- R[k, j]
          }
        }
      }
    }
  }
  
  #  clean and return result  
  result <- R
  remove(i, j, k, n, R, R0)
  return(result)
  
}