2023-10-24 12:18:59 +05:30
|
|
|
/**
|
|
|
|
|
* Colors a graph using up to m colors such that no two adjacent vertices share the same color.
|
|
|
|
|
* @param {number[][]} graph - Adjacency matrix of the graph, using 0 for no edge.
|
|
|
|
|
* @param {number} m - The number of colors to use.
|
|
|
|
|
* @returns {?Array.<number>} A valid M-coloring of the graph using colors 1 to m, or null if none exists.
|
|
|
|
|
* @see https://en.wikipedia.org/wiki/Graph_coloring
|
|
|
|
|
*/
|
|
|
|
|
function mColoring(graph, m) {
|
2023-10-28 00:56:39 +02:00
|
|
|
const colors = new Array(graph.length).fill(0)
|
2023-10-24 12:18:59 +05:30
|
|
|
|
|
|
|
|
// Check if it's safe to color a vertex with a given color.
|
|
|
|
|
function isSafe(vertex, color) {
|
|
|
|
|
for (let i = 0; i < graph.length; i++) {
|
|
|
|
|
if (graph[vertex][i] && colors[i] === color) {
|
2023-10-28 00:56:39 +02:00
|
|
|
return false
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
|
|
|
|
}
|
2023-10-28 00:56:39 +02:00
|
|
|
return true
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Use backtracking to try and color the graph.
|
|
|
|
|
function solveColoring(vertex = 0) {
|
|
|
|
|
if (vertex === graph.length) {
|
2023-10-28 00:56:39 +02:00
|
|
|
return true
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (let color = 1; color <= m; color++) {
|
|
|
|
|
if (isSafe(vertex, color)) {
|
2023-10-28 00:56:39 +02:00
|
|
|
colors[vertex] = color
|
|
|
|
|
|
2023-10-24 12:18:59 +05:30
|
|
|
if (solveColoring(vertex + 1)) {
|
2023-10-28 00:56:39 +02:00
|
|
|
return true
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// If no solution, backtrack.
|
2023-10-28 00:56:39 +02:00
|
|
|
colors[vertex] = 0
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
|
|
|
|
}
|
2023-10-28 00:56:39 +02:00
|
|
|
return false
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// If coloring is possible, return the colors.
|
|
|
|
|
if (solveColoring()) {
|
2023-10-28 00:56:39 +02:00
|
|
|
return colors
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
2023-10-28 00:56:39 +02:00
|
|
|
return null
|
2023-10-24 12:18:59 +05:30
|
|
|
}
|
|
|
|
|
|
2023-10-28 00:56:39 +02:00
|
|
|
export { mColoring }
|
