| Copyright | Copyright (C) 2021 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P86
Description
Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P86.
Synopsis
- colorGraph :: G -> [(Vertex, Int)]
Documentation
colorGraph :: G -> [(Vertex, Int)] Source #
Graph coloring assigns colors to each vertex in a way such that no adjacent vertexes have the same color.
Write a function to color a graph using Welch-Powell's algorithm. Use distinct integers to represent distinct colors, and return the association list between vertexes and their colors.
Examples
>>>colorGraph $ toG $ Paths [[1,2,3,4,5,10,8,6,9,7,2], [1,5], [1,6], [3,8], [4,9], [7,10]][(1,1),(2,2),(3,1),(4,2),(5,3),(6,2),(7,1),(8,3),(9,3),(10,2)]
Visualization with real colors
Hint
Write a function to sort vertexes in decreasing order of degree, i.e., the number of neighbors.
The function sortOn may be useful for this.