Skip to content

Commit 1ef5208

Browse files
BamaCharanChhandogiBamaCharanChhandogisiriakDebasish Biswasgithub-actions
authored
Add M-coloring Problem (#4282)
Co-authored-by: BamaCharanChhandogi <b.c.chhandogi@gmailcom> Co-authored-by: Andrii Siriak <siryaka@gmail.com> Co-authored-by: Debasish Biswas <debasishbsws.abc@gmail.com> Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
1 parent c4a9ef1 commit 1ef5208

3 files changed

Lines changed: 132 additions & 1 deletion

File tree

‎DIRECTORY.md‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313
* [FloodFill](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/FloodFill.java)
1414
* [KnightsTour](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/KnightsTour.java)
1515
* [MazeRecursion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/MazeRecursion.java)
16+
* [MColoring](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/MColoring.java)
1617
* [NQueens](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/NQueens.java)
1718
* [Permutation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/Permutation.java)
1819
* [PowerSum](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/PowerSum.java)
@@ -181,7 +182,7 @@
181182
* [TrieImp](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TrieImp.java)
182183
* [VerticalOrderTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversal.java)
183184
* [ZigzagTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/ZigzagTraversal.java)
184-
* devutils
185+
* utils
185186
* entities
186187
* [ProcessDetails](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/devutils/entities/ProcessDetails.java)
187188
* nodes
@@ -522,6 +523,7 @@
522523
* [CombinationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/CombinationTest.java)
523524
* [FloodFillTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/FloodFillTest.java)
524525
* [MazeRecursionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/MazeRecursionTest.java)
526+
* [MColoringTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/MColoringTest.java)
525527
* [PermutationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/PermutationTest.java)
526528
* [PowerSumTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/PowerSumTest.java)
527529
* [WordSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/WordSearchTest.java)
@@ -645,6 +647,7 @@
645647
* [FrizzyNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FrizzyNumberTest.java)
646648
* [GaussianTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/GaussianTest.java)
647649
* [GCDTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/GCDTest.java)
650+
* [GenericRootTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/GenericRootTest.java)
648651
* [HarshadNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/HarshadNumberTest.java)
649652
* [HeronsFormulaTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/HeronsFormulaTest.java)
650653
* [JosephusProblemTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/JosephusProblemTest.java)
@@ -665,6 +668,7 @@
665668
* [PerfectSquareTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PerfectSquareTest.java)
666669
* [PerimeterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PerimeterTest.java)
667670
* [PollardRhoTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PollardRhoTest.java)
671+
* [PowerOfTwoOrNotTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PowerOfTwoOrNotTest.java)
668672
* [PrimeCheckTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PrimeCheckTest.java)
669673
* [PrimeFactorizationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PrimeFactorizationTest.java)
670674
* [PronicNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PronicNumberTest.java)

‎src/main/java/com/thealgorithms/backtracking/MColoring.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package com.thealgorithms.backtracking;
2+
3+
import java.io.*;
4+
import java.util.*;
5+
6+
/**
7+
* @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
8+
*/
9+
class Node {
10+
int color = 1;
11+
Set<Integer> edges = new HashSet<Integer>();
12+
}
13+
14+
public class MColoring {
15+
static int possiblePaint(ArrayList<Node> nodes, int n, int m) {
16+
17+
// Create a visited array of n nodes
18+
ArrayList<Integer> visited = new ArrayList<Integer>();
19+
for (int i = 0; i < n + 1; i++) {
20+
visited.add(0);
21+
}
22+
23+
// maxColors used till now are 1 as
24+
// all nodes are painted color 1
25+
int maxColors = 1;
26+
27+
for (int sv = 1; sv <= n; sv++) {
28+
if (visited.get(sv) > 0) {
29+
continue;
30+
}
31+
32+
// If the starting point is unvisited,
33+
// mark it visited and push it in queue
34+
visited.set(sv, 1);
35+
Queue<Integer> q = new LinkedList<>();
36+
q.add(sv);
37+
38+
// BFS
39+
while (q.size() != 0) {
40+
int top = q.peek();
41+
q.remove();
42+
43+
// Checking all adjacent nodes
44+
// to "top" edge in our queue
45+
for (int it : nodes.get(top).edges) {
46+
47+
// If the color of the
48+
// adjacent node is same, increase it by
49+
// 1
50+
if (nodes.get(top).color == nodes.get(it).color) {
51+
nodes.get(it).color += 1;
52+
}
53+
54+
// If number of colors used exceeds m,
55+
// return 0
56+
maxColors = Math.max(maxColors, Math.max(nodes.get(top).color, nodes.get(it).color));
57+
if (maxColors > m) return 0;
58+
59+
// If the adjacent node is not visited,
60+
// mark it visited and push it in queue
61+
if (visited.get(it) == 0) {
62+
visited.set(it, 1);
63+
q.add(it);
64+
}
65+
}
66+
}
67+
}
68+
return 1;
69+
}
70+
}

‎src/test/java/com/thealgorithms/backtracking/MColoringTest.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package com.thealgorithms.backtracking;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import java.util.*;
6+
import org.junit.jupiter.api.Test;
7+
8+
/**
9+
* @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
10+
*/
11+
class MColoringTest {
12+
13+
@Test
14+
void testGraphColoring1() {
15+
int n = 4;
16+
int[][] graph = {{0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}};
17+
int m = 3; // Number of colors
18+
19+
assertEquals(1, MColoring.possiblePaint(createGraph(graph), n, m));
20+
}
21+
22+
@Test
23+
void testGraphColoring2() {
24+
int n = 5;
25+
int[][] graph = {{0, 1, 1, 1, 0}, {1, 0, 0, 1, 0}, {1, 0, 0, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 1, 1, 0}};
26+
int m = 2; // Number of colors
27+
28+
assertEquals(0, MColoring.possiblePaint(createGraph(graph), n, m));
29+
}
30+
31+
@Test
32+
void testGraphColoring3() {
33+
int n = 3;
34+
int[][] graph = {{0, 1, 1}, {1, 0, 1}, {1, 1, 0}};
35+
int m = 2; // Number of colors
36+
37+
assertEquals(0, MColoring.possiblePaint(createGraph(graph), n, m));
38+
}
39+
40+
private ArrayList<Node> createGraph(int[][] graph) {
41+
int n = graph.length;
42+
ArrayList<Node> nodes = new ArrayList<>(n + 1);
43+
for (int i = 0; i <= n; i++) {
44+
nodes.add(new Node());
45+
}
46+
47+
for (int i = 0; i < n; i++) {
48+
for (int j = i + 1; j < n; j++) { // Use j = i + 1 to avoid setting edges twice
49+
if (graph[i][j] > 0) {
50+
nodes.get(i + 1).edges.add(j + 1);
51+
nodes.get(j + 1).edges.add(i + 1);
52+
}
53+
}
54+
}
55+
return nodes;
56+
}
57+
}

0 commit comments

Comments
 (0)