Futhark.Optimise.ReuseAllocations.GreedyColoring

Provides a greedy graph-coloring algorithm.

Documentation

colorGraph :: (Ord a, Ord space) => Map a space -> Graph a -> (Map Int space, Coloring a)

Graph coloring that takes into account the space of values. Two values can only share the same color if they live in the same space. The result is map from each color to a space and a map from each value in the input graph to it's new color.

type Coloring a = Map a Int

A map of values to their color, identified by an integer.