R/coverGraph.R

In rankUncertainty: Methods for Working with Uncertainty in Rankings

#' Compute the cover graph of order generated by intervals
#'
#' The cover graph of the order generated by a set of intervals is the minimal
#' graph whose reachability relation is that order.
#'
#' See section 6 of Rising (2021).
#'
#' @param intervals data frame (see [rankUncertainty::generateIntervals] for
#' the required format)
#' @param names names of intervals (`1:nrow(intervals)` by default)
#'
#' @return A list of edges of the cover graph.
#' @export
#'
#' @references
#' Rising, Justin (2021).  _Uncertainty in Ranking_.  arXiv:2107.03459.
#'
#' @examples
#' left <- sort(c(1:3, 1:3 + 0.1))
#' right <- left + 0.7
#' intervals <- data.frame(left = left, right = right)
#' coverGraph(intervals)
#'
#' @importFrom magrittr %>%
coverGraph <- function(intervals, names = NULL)
{
  n <- nrow(intervals)

  if (is.null(names))
  {
    names <- 1:n %>% as.character()
  }
  else
  {
    if (length(names) != n)
    {
      stop('length(names) must match nrow(intervals)')
    }
  }

  l <- list()
  for (i in 1:n)
  {
    s <- c()
    idx <- which(intervals[i, 'right'] < intervals[, 'left'])
    for (j in idx)
    {
      idx1 <- which(intervals[idx, 'right'] < intervals[j, 'left'])
      if (length(idx1) == 0)
      {
        s <- c(s, j)
      }
    }
    if (length(s) > 0)
    {
      l[[names[i]]] <- names[s]
    }
  }
  l
}