Graph Coloring: A Simple Implementation with JavaScript

Introduction

Graph coloring is a fundamental problem in computer science and graph theory, often used to solve various real-world problems such as scheduling tasks, register allocation in compilers, and solving map coloring puzzles. In this article, we will explore how to implement a simple graph coloring algorithm using JavaScript.

What is Graph Coloring?

Graph coloring involves assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. The goal is to use the minimum number of colors required to achieve this condition.

Example: Map Coloring

A classic example is map coloring, where countries (vertices) are colored so that no two adjacent countries have the same color. This ensures that maps can be visually distinguished and avoids confusion between neighboring regions.

Implementation in JavaScript

We will implement a graph coloring algorithm using JavaScript objects to represent the graph structure and perform depth-first search (DFS) for coloring.

Step-by-Step Guide

1. Graph Representation:
   • We will use an adjacency list representation of the graph.
2. Color Assignment:
   • We will use DFS to assign colors while ensuring no two adjacent vertices share the same color.
3. Conflict Detection:
   • We will detect conflicts and return false if a valid coloring cannot be achieved.

JavaScript Code

Here's the complete implementation:

// Function to perform the graph coloring using DFS
function dfs(graph, vertex, visited, colorMap) {
    // If the vertex is already colored, return true
    if (colorMap[vertex] !== undefined) return true;

    // Initialize with a default color
    colorMap[vertex] = 0;

    for (let neighbor of graph[vertex]) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            if (!dfs(graph, neighbor, visited, colorMap)) {
                return false; // Conflict found
            }
        } else if (colorMap[neighbor] === colorMap[vertex]) {
            return false; // Conflict found
        }
    }

    // Assign the next available color
    colorMap[vertex] = 1;

    return true;
}

// Function to perform graph coloring on the entire graph
function graphColoring(graph) {
    const visited = {};
    const colorMap = {};

    for (let vertex of Object.keys(graph)) {
        if (!visited[vertex]) {
            visited[vertex] = true;
            if (!dfs(graph, vertex, visited, colorMap)) {
                return false; // Conflict found
            }
        }
    }

    console.log("Coloring scheme:", colorMap);
    return true;
}

// Example usage:
const graph = {
    A: ['B', 'C'],
    B: ['A', 'D'],
    C: ['A', 'D', 'E'],
    D: ['B', 'C', 'E'],
    E: ['C', 'D']
};

if (graphColoring(graph)) {
    console.log("Graph is colored successfully!");
} else {
    console.log("Conflict found in graph coloring.");
}

Explanation

1. dfs Function:

   • This function performs a depth-first search to assign colors.
   • If the vertex has already been assigned a color, it returns true.
   • It initializes the color map for unvisited vertices and recursively assigns the next available color while checking for conflicts.

2. graphColoring Function:

   • Initializes visited and colorMap arrays.
   • Iterates over all vertices in the graph and calls dfs for unvisited vertices.
   • If a conflict is found during the DFS, it returns false; otherwise, it prints the color map.

Example Graph

Let's consider the example graph:

• Vertices: A, B, C, D, E
• Edges: A-B, A-C, B-D, C-D, C-E, D-E

The output will be a valid coloring scheme for this graph if one exists.

Conclusion

In this article, we explored how to implement a simple graph coloring algorithm using JavaScript. By representing the graph as an adjacency list and performing depth-first search, we can efficiently assign colors while ensuring no two adjacent vertices share the same color.