Repository: TheAlgorithms/Java
File: src/test/java/com/thealgorithms/datastructures/graphs/WelshPowellTest.java (Java)

Code before:
        assertTrue(isColoringValid(graph, colors));
        assertEquals(2, countDistinctColors(colors));
    }

    @Test
    void testDisconnectedGraph() {
        final var graph = WelshPowell.makeGraph(3, new int[][] {}); // No edges
        int[] colors = WelshPowell.findColoring(graph);
        assertTrue(isColoringValid(graph, colors));
        assertEquals(1, countDistinctColors(colors));
    }

    @Test
    void testCompleteGraph() {
        final var graph = WelshPowell.makeGraph(3, new int[][] {{0, 1}, {1, 2}, {2, 0}});
        int[] colors = WelshPowell.findColoring(graph);
        assertTrue(isColoringValid(graph, colors));
        assertEquals(3, countDistinctColors(colors));
    }

    @Test
    void testComplexGraph() {
        final var graph = WelshPowell.makeGraph(5, new int[][] {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}, {1, 3}});
        int[] colors = WelshPowell.findColoring(graph);
        assertTrue(isColoringValid(graph, colors));
        assertEquals(3, countDistinctColors(colors)); // Expect exactly 3 colors
    }

    @Test
    void testNegativeVertices() {
        assertThrows(IllegalArgumentException.class, () -> { WelshPowell.makeGraph(-1, new int[][] {}); }, "Number of vertices cannot be negative");
    }

    @Test
    void testSelfLoop() {
        assertThrows(IllegalArgumentException.class, () -> { WelshPowell.makeGraph(3, new int[][] {{0, 0}}); }, "Self-loops are not allowed");
    }

    @Test
    void testInvalidVertex() {
        assertThrows(IllegalArgumentException.class, () -> { WelshPowell.makeGraph(3, new int[][] {{0, 3}}); }, "Vertex out of bounds");
    }

    @Test
    void testInvalidEdgeArray() {
        assertThrows(IllegalArgumentException.class, () -> { WelshPowell.makeGraph(3, new int[][] {{0}}); }, "Edge array must have exactly two elements");
    }

    @Test
    void testWithPreColoredVertex() {
        final var graph = WelshPowell.makeGraph(4, new int[][] {{0, 1}, {1, 2}, {2, 3}});

Review comment (suggestion):
```suggestion
        assertEquals(3, countDistinctColors(colors));
```

Code after:
        final var graph = WelshPowell.makeGraph(4, new int[][] {{0, 1}, {1, 2}, {2, 3}});
        int[] colors = WelshPowell.findColoring(graph);
        assertTrue(isColoringValid(graph, colors));
        assertEquals(2, countDistinctColors(colors));
    }

    @Test
    void testDisconnectedGraph() {
        final var graph = WelshPowell.makeGraph(3, new int[][] {}); // No edges
        int[] colors = WelshPowell.findColoring(graph);
        assertTrue(isColoringValid(graph, colors));
        assertEquals(1, countDistinctColors(colors));
    }

    @Test
    void testCompleteGraph() {
        final var graph = WelshPowell.makeGraph(3, new int[][] {{0, 1}, {1, 2}, {2, 0}});
        int[] colors = WelshPowell.findColoring(graph);
        assertTrue(isColoringValid(graph, colors));
        assertEquals(3, countDistinctColors(colors));
    }

    // The following test originates from the following website : https://www.geeksforgeeks.org/welsh-powell-graph-colouring-algorithm/
    @Test
    void testComplexGraph() {
        int[][] edges = {
            {0, 7}, // A-H
            {0, 1}, // A-B
            {1, 3}, // B-D
            {2, 3}, // C-D
            {3, 8}, // D-I
            {3, 10}, // D-K
            {4, 10}, // E-K
            {4, 5}, // E-F
            {5, 6}, // F-G
            {6, 10}, // G-K
            {6, 7}, // G-H
            {7, 8}, // H-I
            {7, 9}, // H-J
            {7, 10}, // H-K
            {8, 9}, // I-J
            {9, 10}, // J-K
        };

        final var graph = WelshPowell.makeGraph(11, edges); // 11 vertices from A (0) to K (10)
        int[] colors = WelshPowell.findColoring(graph);

        assertTrue(isColoringValid(graph, colors), "The coloring should be valid with no adjacent vertices sharing the same color.");
        assertEquals(3, countDistinctColors(colors), "The chromatic number of the graph should be 3.");
    }