Greedy Map Coloring

greedy-map-coloring.md

require 'viewmat plot'
colorxy =: colorxy_jzplot_

dm =. ,~ 200                    NB. dimensions
np =. 50                        NB. number of points
ps =. ? np $ ,: dm              NB. points

NB. Voronoi tesselation
Dist =: +/"1@(*:@-"1/)
map =: (i. <./)"1 ((#: i.) dm) Dist ps

NB. Adjacency map
Shift4 =: ((, -) =/~ i. 2)&(|.!.0)
AdjMap =: [ e."1 ([ -.~ ] ~.@#&,~ +./@Shift4@:=)"0 _
NB. Need to avoid 0 when building adjacency map
nodes =. /:~ ~. , map
adj =. nodes AdjMap&:>: nodes i. map

ord =. \: +/"1 adj              NB. degree order
col =. (# nodes) $ < i. 8       NB. possible colors

Prune =: {{ (I. x { m) (-.&({. x {:: y))&.>@:{`[`]} y }}
col =. col ]F..(adj Prune) ord
echo ' colors',~ ": # ~. {.@> col

pal =. 10 colorxy 0.9 0.9 0.1,0.1 0.5 0.5,:0.2 0.0 0.3
pal viewmat (nodes i. map) { {.@> col