R/assert_dag.r

In giupo/GrafoDB: simple ETL for timeseries in R

#' assert that a network is a DAG
#'
#' @name assert_dag
#' @param network igraph instance
#' @note if dag has cicles, raises an Exception
#'
#' TODO: dovrebbe tornare una lista di cicli se trovati. con la nuova
#' versione di igraph non funziona.

assert_dag <- function(network) {
  if (!igraph::is.dag(network)) {
    cycles_vertex <- find_cycles(network)
    cycle_nodes <- igraph::V(network)[unlist(cycles_vertex)]$name
    stop("cycles found: ", paste(cycle_nodes, collapse = ", "))
  }
}


find_cycles <- function(g, l = 1) {
  cycles <- NULL
  for (v1 in igraph::V(g)) {
    if (igraph::degree(g, v1, mode = "in") == 0) next
    good_neighbors <- igraph::neighbors(g, v1, mode = "out")
    good_neighbors <- good_neighbors[good_neighbors > v1]
    for (v2 in good_neighbors) {
      temp_cycle <- lapply(igraph::all_simple_paths(g, v2, v1, mode="out"), function(p) c(v1,p)) # nolint
      temp_cycle <- temp_cycle[which(sapply(temp_cycle, length) > l)]
      temp_cycle <- temp_cycle[sapply(temp_cycle, min) == sapply(temp_cycle, `[`, 1)] # nolint
      cycles  <- c(cycles, temp_cycle)
    }
  }
  cycles
}