Implement better coloring of adjacent clusters on large embeddings

[VPetukhov]

It should be possible to solve using graph coloring algorithms. For example, MapColor is a package, which does it for polygon maps (probably there is something better for our case). And here is an article on how to use it.

[VPetukhov]

graph_cl <- sccore::getClusterGraph(con_v1$graph, groups=ann_by_level$annotation$l6, method="paga")
nns_per_clust <- as.matrix(graph_cl) %>% apply(1, order, decreasing=T) #%>% .[1:2,]
sims_per_clust <- 1:ncol(nns_per_clust) %>% lapply(function(i) graph_cl[nns_per_clust[, i], i]) %>% 
  setNames(colnames(nns_per_clust)) %>% lapply(function(x) x[x > 0])

color_set <- (RColorBrewer::brewer.pal(9, "Set1") %>% colorRampPalette())(100)
color_set_dists <- col2rgb(color_set) %>% apply(2, convertColor, "sRGB", "Lab") %>% t() %>%
  dist(method="minkowski", p=1) %>% as.matrix() %>% set_rownames(color_set) %>% set_colnames(color_set)

cl_colors <- rep(NA, length(sims_per_clust)) %>% setNames(names(sims_per_clust)) %>% 
  factor(levels=color_set)

col_queue <- names(cl_colors)[1]
while(length(col_queue) > 0) {
  n <- col_queue[1]
  # n
  cur.sims <- sims_per_clust[[n]]
  cur.neighbs <- names(cur.sims)
  col_queue <- c(col_queue[-1], cur.neighbs[is.na(cl_colors[cur.neighbs])] %>% .[!(.%in% col_queue[-1])])

  if (all(is.na(cl_colors[cur.neighbs]))) {
    cl_colors[[n]] <- table(cl_colors) %>% which.max() %>% names()
    next
  }
  cur.assigned.neighbs <- cl_colors[cur.neighbs] %>% .[!is.na(.)]
  cl_colors[[n]] <- apply(color_set_dists[cur.assigned.neighbs,,drop=F] * cur.sims[names(cur.assigned.neighbs)], 2, median) %>% 
    which.max() %>% names()
}

cl_colors %<>% as.character() %>% setNames(names(cl_colors))

Works somehow, but needs penalty for assigning distant clusters to exactly the same color

[VPetukhov]

Just found that it was implemented in Palo