A fast implementation of the greedy algorithm for the set cover problem using 'Rcpp'.
A fast implementation of the greedy algorithm for the set cover problem using 'Rcpp'.
You can install RcppGreedySetCover from github with:
devtools::install_github("matthiaskaeding/RcppGreedySetCover")
This is a basic example which shows you how to use the main function:
# Create some data.set.seed(333)X <- data.table::rbindlist(lapply(seq_len(1e4L),function(x) list(element=sample.int(n=1e3L,size=sample.int(50L,1L)))),idcol="set")# Input is in long format.head(X)#> set element#> 1: 1 85#> 2: 1 973#> 3: 1 571#> 4: 1 21#> 5: 1 721#> 6: 1 607# Run set coverres <- RcppGreedySetCover::greedySetCover(X,FALSE)#> 100% covered by 45 sets.# Result is in long format.head(res)#> set element#> 1 19 25#> 2 19 65#> 3 19 68#> 4 19 86#> 5 19 90#> 6 19 105# Check if all elements are covered.identical(sort(unique(res$element)),sort(unique(X$element)))#> [1] TRUE