Switch to a functional approach instead of class-based.

vedas-dixit · vedas-dixit · commit 95cab089ab04 · 2023-10-23T10:38:29.000+05:30
Use proper JSDoc comments.
Refine the comments and remove redundancies.
diff --git a/Backtracking/MColoringProblem.js b/Backtracking/MColoringProblem.js
@@ -1,65 +1,49 @@
-/*
-  Problem: M Coloring Problem
-  Given a graph represented as an adjacency matrix and a number M (number of colors), 
-  determine if the graph can be colored with up to M colors such that no two adjacent 
-  vertices share the same color.
+//https://en.wikipedia.org/wiki/Edge_coloring
 
-  What is the M Coloring Problem?
-  - This problem is about coloring a graph's vertices with at most M different colors 
-    such that no two adjacent vertices have the same color.
+// M Coloring Problem
+// Given an adjacency matrix representation of a graph and a number M, 
+// determine if the graph can be colored with up to M colors such that 
+// no two adjacent vertices share the same color.
 
-  Example:
-  - Consider a triangle (3 nodes connected cyclically). We'd need 3 colors to color each vertex 
-    without adjacent vertices having the same color.
+function mColoring(graph, m) {
+  const colors = new Array(graph.length).fill(0);
 
-  Solution:
-  - We will be using backtracking to solve this question.
-  - Color a vertex, then move to an adjacent vertex and try all colors. If a color is valid, 
-    continue to the next vertex, else backtrack.
-*/
-
-class MColoring {
-    constructor(graph, m) {
-      this.graph = graph; // adjacency matrix representation
-      this.m = m; 
-      this.colors = new Array(graph.length).fill(0);
-    }
-  
-    isSafe(vertex, color) {
-      for (let i = 0; i < this.graph.length; i++) {
-        if (this.graph[vertex][i] && this.colors[i] === color) {
-          return false;
-        }
+  // 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) {
+        return false;
       }
+    }
+    return true;
+  }
+
+  // Use backtracking to try and color the graph.
+  function solveColoring(vertex = 0) {
+    if (vertex === graph.length) {
       return true;
     }
-  
-    solveColoring(vertex = 0) {
-      if (vertex === this.graph.length) {
-        return true;
-      }
-  
-      for (let color = 1; color <= this.m; color++) {
-        if (this.isSafe(vertex, color)) {
-          this.colors[vertex] = color;
-  
-          if (this.solveColoring(vertex + 1)) {
-            return true;
-          }
-  
-          this.colors[vertex] = 0; // backtrack
+
+    for (let color = 1; color <= m; color++) {
+      if (isSafe(vertex, color)) {
+        colors[vertex] = color;
+        
+        if (solveColoring(vertex + 1)) {
+          return true;
         }
+
+        // If no solution, backtrack.
+        colors[vertex] = 0;
       }
-      return false;
-    }
-  
-    getSolution() {
-      if (this.solveColoring()) {
-        return this.colors;
-      }
-      return [];
     }
+    return false;
   }
-  
-  export { MColoring }
-  
+
+  // If coloring is possible, return the colors.
+  if (solveColoring()) {
+    return colors;
+  }
+  return null;
+}
+
+export { mColoring };
diff --git a/Backtracking/tests/MColoringProblem.test.js b/Backtracking/tests/MColoringProblem.test.js
@@ -1,4 +1,4 @@
-import { MColoring } from '../MColoringProblem';
+import { mColoring } from '../MColoringProblem';
 
 describe('MColoringProblem', () => {
   it('should color a triangle with 3 colors', () => {
@@ -7,9 +7,8 @@ describe('MColoringProblem', () => {
       [1, 0, 1],
       [1, 1, 0]
     ];
-    const test1 = new MColoring(graph, 3);
-    const solution = test1.getSolution();
-    expect(solution).not.toEqual([]);
+    const solution = mColoring(graph, 3);
+    expect(solution).not.toBeNull();
   });
 
   it('should not color a triangle with 2 colors', () => {
@@ -18,8 +17,7 @@ describe('MColoringProblem', () => {
       [1, 0, 1],
       [1, 1, 0]
     ];
-    const test2 = new MColoring(graph, 2);
-    const solution = test2.getSolution();
-    expect(solution).toEqual([]);
+    const solution = mColoring(graph, 2);
+    expect(solution).toBeNull();
   });
-});
+});
