P86 - 图着色
Color a graph with the Welsh-Powell algorithm
官方模块：
Problems.P86核心函数：colorGraph
算法
Welsh-Powell 是贪心着色：按度数从高到低处理顶点，每个顶点选择尚未被邻居使用的最小正整数颜色。它保证合法，但不保证颜色数全局最少。
实现
方法一：Welsh-Powell 贪心
1import Data.List (sortOn)
2import Data.Ord (Down(..))
3
4colorGraph :: G -> [(Vertex, Int)]
5colorGraph graph = Map.toAscList (foldl color Map.empty order)
6 where
7 vs = Set.toList (fst (canonical graph))
8 order = sortOn (Down . Set.size . (`neighbors` graph)) vs
9
10 color assigned vertex = Map.insert vertex available assigned
11 where
12 used = Set.fromList
13 [c | neighbor <- Set.toList (neighbors vertex graph)
14 , Just c <- [Map.lookup neighbor assigned]]
15 available = head [c | c <- [1..], Set.notMember c used]
方法二：回溯求最少颜色
1colorGraphOptimal :: G -> [(Vertex, Int)]
2colorGraphOptimal graph = Map.toAscList $ head
3 [coloring
4 | colorCount <- [0..length vertices]
5 , Just coloring <- [assign colorCount vertices Map.empty]
6 ]
7 where
8 vertices = sortOn
9 (Down . Set.size . (`neighbors` graph))
10 (Set.toList (fst (canonical graph)))
11
12 assign _ [] coloring = Just coloring
13 assign colorCount (vertex:rest) coloring = firstJust
14 [assign colorCount rest (Map.insert vertex color coloring)
15 | color <- [1..colorCount]
16 , all (\neighbor -> Map.lookup neighbor coloring /= Just color)
17 (Set.toList (neighbors vertex graph))]
18
19 firstJust [] = Nothing
20 firstJust (Just value:_) = Just value
21 firstJust (Nothing:rest) = firstJust rest
从 0、1、2……种颜色依次尝试，找到的第一个完整着色必然使用最少颜色。高度数顶点优先可以提前制造冲突，但最坏情况仍是指数搜索。
方法对比
| 方法 | 保证 | 代价 |
|---|---|---|
| Welsh-Powell | 快速得到合法着色 | 不保证颜色数最少 |
| 回溯 | 得到最少颜色着色 | 指数级，只适合小图 |
测试
1>>> colorGraph (toG (Paths [[1,2,3,1]]))
2[(1,1),(2,2),(3,3)]
3>>> let graph = toG (Paths [[1,2,3,4],[1,4]])
4>>> let coloring = Map.fromList (colorGraph graph)
5>>> all (\(u,v) -> coloring Map.! u /= coloring Map.! v)
6... (Set.toList (snd (canonical graph)))
7True
8>>> maximum (map snd (colorGraphOptimal (toG (Paths [[1,2,3,1]]))))
93
在简单列表和集合实现下，复杂度约 。