HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

Moduleghc-9.10.3GHC2021

GHC.Data.Graph.Color

Graph Coloring. This is a generic graph coloring library, abstracted over the type of the node keys, nodes and colors.

  • 1 value
  • Packageghc-9.10.3
  • Exports1
  • LanguageGHC2021
  • LicenceBSD-3-Clause
  • SourceColor.hs

module GHC.Data.Graph.Base

module GHC.Data.Graph.Ops

module GHC.Data.Graph.Ppr

valuecolorGraph
  1. :: (Uniquable k, Uniquable cls, Uniquable color, Eq cls, Ord k, Outputable k, Outputable cls, Outputable color)
  2. => Bool

    whether to do iterative coalescing

  3. -> Int

    how many times we've tried to color this graph so far.

  4. -> UniqFM cls (UniqSet color)

    map of (node class -> set of colors available for this class).

  5. -> Triv k cls color

    fn to decide whether a node is trivially colorable.

  6. -> (Graph k cls color -> k)

    fn to choose a node to potentially leave uncolored if nothing is trivially colorable.

  7. -> Graph k cls color

    the graph to color.

  8. -> (Graph k cls color, UniqSet k, UniqFM k k)
#

Try to color a graph with this set of colors. Uses Chaitin's algorithm to color the graph. The graph is scanned for nodes which are deamed 'trivially colorable'. These nodes are pushed onto a stack and removed from the graph. Once this process is complete the graph can be colored by removing nodes from the stack (ie in reverse order) and assigning them colors different to their neighbors.