Safe Haskell  None 

Language  Haskell2010 
Types for the general graph colorer.
Synopsis
 type Triv k cls color = cls > UniqSet k > UniqSet color > Bool
 data Graph k cls color = Graph {}
 initGraph :: Graph k cls color
 graphMapModify :: (UniqFM (Node k cls color) > UniqFM (Node k cls color)) > Graph k cls color > Graph k cls color
 data Node k cls color = Node {
 nodeId :: k
 nodeClass :: cls
 nodeColor :: Maybe color
 nodeConflicts :: UniqSet k
 nodeExclusions :: UniqSet color
 nodePreference :: [color]
 nodeCoalesce :: UniqSet k
 newNode :: k > cls > Node k cls color
Documentation
type Triv k cls color = cls > UniqSet k > UniqSet color > Bool Source #
A fn to check if a node is trivially colorable For graphs who's color classes are disjoint then a node is 'trivially colorable' when it has less neighbors and exclusions than available colors for that node.
For graph's who's color classes overlap, ie some colors alias other colors, then this can be a bit more tricky. There is a general way to calculate this, but it's likely be too slow for use in the code. The coloring algorithm takes a canned function which can be optimised by the user to be specific to the specific graph being colored.
for details, see "A Generalised Algorithm for GraphColoring Register Allocation" Smith, Ramsey, Holloway  PLDI 2004.
data Graph k cls color Source #
The Interference graph. There used to be more fields, but they were turfed out in a previous revision. maybe we'll want more later..
graphMapModify :: (UniqFM (Node k cls color) > UniqFM (Node k cls color)) > Graph k cls color > Graph k cls color Source #
Modify the finite map holding the nodes in the graph.
data Node k cls color Source #
Graph nodes. Represents a thing that can conflict with another thing. For the register allocater the nodes represent registers.
Node  
