################################################################################
##  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)
  
}