3 -- This is a generic graph coloring library, abstracted over the type of
4 -- the node keys, nodes and colors.
6 {-# OPTIONS -fno-warn-missing-signatures #-}
30 -- | Try to color a graph with this set of colors.
31 -- Uses Chaitin's algorithm to color the graph.
32 -- The graph is scanned for nodes which are deamed 'trivially colorable'. These nodes
33 -- are pushed onto a stack and removed from the graph.
34 -- Once this process is complete the graph can be colored by removing nodes from
35 -- the stack (ie in reverse order) and assigning them colors different to their neighbors.
38 :: ( Uniquable k, Uniquable cls, Uniquable color
39 , Eq color, Eq cls, Ord k
40 , Outputable k, Outputable cls, Outputable color)
41 => UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class).
42 -> Triv k cls color -- ^ fn to decide whether a node is trivially colorable.
43 -> (Graph k cls color -> k) -- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.
44 -> Graph k cls color -- ^ the graph to color.
46 -> ( Graph k cls color -- the colored graph.
47 , UniqSet k -- the set of nodes that we couldn't find a color for.
48 , UniqFM k ) -- map of regs (r1 -> r2) that were coaleced
49 -- r1 should be replaced by r2 in the source
51 colorGraph colors triv spill graph0
53 -- do aggressive coalesing on the graph
54 (graph_coalesced, rsCoalesce)
55 = coalesceGraph triv graph0
57 -- run the scanner to slurp out all the trivially colorable nodes
59 = colorScan triv spill graph_coalesced
61 -- color the trivially colorable nodes
62 -- as the keys were added to the front of the list while they were scanned,
63 -- this colors them in the reverse order they were found, as required by the algorithm.
64 (graph_triv, ksNoTriv)
65 = assignColors colors graph_coalesced ksTriv
67 -- try and color the problem nodes
68 (graph_prob, ksNoColor) = assignColors colors graph_triv ksProblems
70 -- if the trivially colorable nodes didn't color then something is wrong
71 -- with the provided triv function.
72 in if not $ null ksNoTriv
73 then pprPanic "colorGraph: trivially colorable nodes didn't color!" empty
75 $$ text "ksTriv = " <> ppr ksTriv
76 $$ text "ksNoTriv = " <> ppr ksNoTriv
78 $$ dotGraph (\x -> text "white") triv graph1) -}
82 , listToUFM rsCoalesce)
85 -- | Scan through the conflict graph separating out trivially colorable and
86 -- potentially uncolorable (problem) nodes.
88 -- Checking whether a node is trivially colorable or not is a resonably expensive operation,
89 -- so after a triv node is found and removed from the graph it's no good to return to the 'start'
90 -- of the graph and recheck a bunch of nodes that will probably still be non-trivially colorable.
92 -- To ward against this, during each pass through the graph we collect up a list of triv nodes
93 -- that were found, and only remove them once we've finished the pass. The more nodes we can delete
94 -- at once the more likely it is that nodes we've already checked will become trivially colorable
98 :: ( Uniquable k, Uniquable cls, Uniquable color)
99 => Triv k cls color -- ^ fn to decide whether a node is trivially colorable
100 -> (Graph k cls color -> k) -- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.
101 -> Graph k cls color -- ^ the graph to scan
102 -> ([k], [k]) -- triv colorable, problem nodes
105 colorScan triv spill graph
106 = colorScan' triv spill graph
109 (eltsUFM $ graphMap graph)
111 -- we've reached the end of the candidates list
112 colorScan' triv spill graph
117 -- if the graph is empty then we're done
118 | isNullUFM $ graphMap graph
119 = (ksTrivFound ++ ksTriv, ksSpill)
121 -- if we haven't found a trivially colorable node then we'll have to
122 -- choose a spill candidate and leave it uncolored
124 , kSpill <- spill graph -- choose a spill candiate
125 , graph' <- delNode kSpill graph -- remove it from the graph
126 , nsRest' <- eltsUFM $ graphMap graph' -- graph has changed, so get new node list
128 = colorScan' triv spill graph'
133 -- we're at the end of the candidates list but we've found some triv nodes
134 -- along the way. We can delete them from the graph and go back for more.
135 | graph' <- foldr delNode graph ksTrivFound
136 , nsRest' <- eltsUFM $ graphMap graph'
138 = colorScan' triv spill graph'
139 (ksTrivFound ++ ksTriv) []
143 -- check if the current node is triv colorable
144 colorScan' triv spill graph
149 -- node is trivially colorable
150 -- add it to the found nodes list and carry on.
152 , triv (nodeClass node) (nodeConflicts node) (nodeExclusions node)
154 = colorScan' triv spill graph
155 ksTriv (k : ksTrivFound)
159 -- node wasn't trivially colorable, skip over it and look in the rest of the list
161 = colorScan' triv spill graph
166 {- -- This is cute and easy to understand, but too slow.. BL 2007/09
168 colorScan colors triv spill safe prob graph
170 -- empty graphs are easy to color.
171 | isNullUFM $ graphMap graph
174 -- Try and find a trivially colorable node.
175 | Just node <- find (\node -> triv (nodeClass node)
177 (nodeExclusions node))
178 $ eltsUFM $ graphMap graph
180 = colorScan colors triv spill
181 (k : safe) prob (delNode k graph)
183 -- There was no trivially colorable node,
184 -- Choose one to potentially leave uncolored. We /might/ be able to find
185 -- a color for this later on, but no guarantees.
187 = colorScan colors triv spill
188 safe (addOneToUniqSet prob k) (delNode k graph)
192 -- | Try to assign a color to all these nodes.
195 :: ( Uniquable k, Uniquable cls, Uniquable color, Eq color )
196 => UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class).
197 -> Graph k cls color -- ^ the graph
198 -> [k] -- ^ nodes to assign a color to.
199 -> ( Graph k cls color -- the colored graph
200 , [k]) -- the nodes that didn't color.
202 assignColors colors graph ks
203 = assignColors' colors graph [] ks
205 where assignColors' _ graph prob []
208 assignColors' colors graph prob (k:ks)
209 = case assignColor colors k graph of
211 -- couldn't color this node
212 Nothing -> assignColors' colors graph (k : prob) ks
214 -- this node colored ok, so do the rest
215 Just graph' -> assignColors' colors graph' prob ks
218 assignColor colors u graph
219 | Just c <- selectColor colors graph u
220 = Just (setColor u c graph)
227 -- | Select a color for a certain node
228 -- taking into account preferences, neighbors and exclusions.
229 -- returns Nothing if no color can be assigned to this node.
232 :: ( Uniquable k, Uniquable cls, Uniquable color, Eq color)
233 => UniqFM (UniqSet color) -- ^ map of (node class -> set of colors available for this class).
234 -> Graph k cls color -- ^ the graph
235 -> k -- ^ key of the node to select a color for.
238 selectColor colors graph u
239 = let -- lookup the node
240 Just node = lookupNode graph u
242 -- lookup the available colors for the class of this node.
244 = lookupUFM colors (nodeClass node)
246 -- find colors we can't use because they're already being used
247 -- by a node that conflicts with this one.
250 $ map (lookupNode graph)
254 colors_conflict = mkUniqSet
256 $ map nodeColor nsConflicts
258 -- the prefs of our neighbors
259 colors_neighbor_prefs
261 $ concat $ map nodePreference nsConflicts
263 -- colors that are still valid for us
264 colors_ok_ex = minusUniqSet colors_avail (nodeExclusions node)
265 colors_ok = minusUniqSet colors_ok_ex colors_conflict
267 -- the colors that we prefer, and are still ok
268 colors_ok_pref = intersectUniqSets
269 (mkUniqSet $ nodePreference node) colors_ok
271 -- the colors that we could choose while being nice to our neighbors
272 colors_ok_nice = minusUniqSet
273 colors_ok colors_neighbor_prefs
275 -- the best of all possible worlds..
278 colors_ok_nice colors_ok_pref
283 -- everyone is happy, yay!
284 | not $ isEmptyUniqSet colors_ok_pref_nice
285 , c : _ <- filter (\x -> elementOfUniqSet x colors_ok_pref_nice)
286 (nodePreference node)
289 -- we've got one of our preferences
290 | not $ isEmptyUniqSet colors_ok_pref
291 , c : _ <- filter (\x -> elementOfUniqSet x colors_ok_pref)
292 (nodePreference node)
295 -- it wasn't a preference, but it was still ok
296 | not $ isEmptyUniqSet colors_ok
297 , c : _ <- uniqSetToList colors_ok
300 -- no colors were available for us this time.
301 -- looks like we're going around the loop again..