Repository: TheAlgorithms/Java
Pull request #5968 (2024-10-24 05:27:46)

refactor: Add tests, fix `removeEdge` bug in `MatrixGraphs`
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5968?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `92.30769%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 68.12%. Comparing base [(`1b51e3e`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/1b51e3e9886527e8be6d8a2bc968652744c42372?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`600fed9`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/600fed915a8594568cb6c07bcfd9123938a77d05?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 2 commits behind head on master.

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5968?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...algorithms/datastructures/graphs/MatrixGraphs.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5968?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fgraphs%2FMatrixGraphs.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9ncmFwaHMvTWF0cml4R3JhcGhzLmphdmE=) | 92.30% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5968?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5968      +/-   ##
============================================
+ Coverage     67.42%   68.12%   +0.70%     
+ Complexity     4577     4576       -1     
============================================
  Files           620      620              
  Lines         17147    17145       -2     
  Branches       3312     3311       -1     
============================================
+ Hits          11561    11680     +119     
+ Misses         5139     5014     -125     
- Partials        447      451       +4     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5968?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index f8bb3711..50f70abb 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -851,6 +851,7 @@
               * [KahnsAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KahnsAlgorithmTest.java)
               * [KosarajuTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KosarajuTest.java)
               * [KruskalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KruskalTest.java)
+              * [MatrixGraphsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/MatrixGraphsTest.java)
               * [TarjansAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/TarjansAlgorithmTest.java)
               * [WelshPowellTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/WelshPowellTest.java)
             * hashmap
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/MatrixGraphs.java b/src/main/java/com/thealgorithms/datastructures/graphs/MatrixGraphs.java
index 902553f9..c1d47df4 100644
--- a/src/main/java/com/thealgorithms/datastructures/graphs/MatrixGraphs.java
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/MatrixGraphs.java
@@ -102,7 +102,7 @@ class AdjacencyMatrixGraph {
     /**
      * Updates the number of edges in the graph
      *
-     * @param newNumberOfEdges
+     * @param newNumberOfEdges the new number of edges
      *
      */
     private void setNumberOfEdges(int newNumberOfEdges) {
@@ -202,7 +202,7 @@ class AdjacencyMatrixGraph {
      * exists and is removed
      */
     public boolean removeEdge(int from, int to) {
-        if (!this.vertexDoesExist(from) || !this.vertexDoesExist(to)) {
+        if (this.vertexDoesExist(from) && this.vertexDoesExist(to)) {
             if (this.adjacencyOfEdgeDoesExist(from, to)) {
                 this.adjacency()[from][to] = AdjacencyMatrixGraph.EDGE_NONE;
                 this.adjacency()[to][from] = AdjacencyMatrixGraph.EDGE_NONE;
@@ -223,14 +223,14 @@ class AdjacencyMatrixGraph {
     public List<Integer> depthFirstOrder(int startVertex) {
         // If the startVertex is invalid, return an empty list
         if (startVertex >= vertexCount || startVertex < 0) {
-            return new ArrayList<Integer>();
+            return new ArrayList<>();
         }
 
         // Create an array to track the visited vertices
         boolean[] visited = new boolean[vertexCount];
 
         // Create a list to keep track of the order of our traversal
-        ArrayList<Integer> orderList = new ArrayList<Integer>();
+        ArrayList<Integer> orderList = new ArrayList<>();
 
         // Perform our DFS algorithm
         depthFirstOrder(startVertex, visited, orderList);
@@ -278,18 +278,18 @@ class AdjacencyMatrixGraph {
     public List<Integer> breadthFirstOrder(int startVertex) {
         // If the specified startVertex is invalid, return an empty list
         if (startVertex >= vertexCount || startVertex < 0) {
-            return new ArrayList<Integer>();
+            return new ArrayList<>();
         }
 
         // Create an array to keep track of the visited vertices
         boolean[] visited = new boolean[vertexCount];
 
         // Create a list to keep track of the ordered vertices
-        ArrayList<Integer> orderList = new ArrayList<Integer>();
+        ArrayList<Integer> orderList = new ArrayList<>();
 
         // Create a queue for our BFS algorithm and add the startVertex
         // to the queue
-        Queue<Integer> queue = new LinkedList<Integer>();
+        Queue<Integer> queue = new LinkedList<>();
         queue.add(startVertex);
 
         // Continue until the queue is empty
@@ -327,19 +327,19 @@ class AdjacencyMatrixGraph {
      * @return returns a string describing this graph
      */
     public String toString() {
-        String s = "    ";
+        StringBuilder s = new StringBuilder("    ");
         for (int i = 0; i < this.numberOfVertices(); i++) {
-            s = s + i + " ";
+            s.append(i).append(" ");
         }
-        s = s + " \n";
+        s.append(" \n");
 
         for (int i = 0; i < this.numberOfVertices(); i++) {
-            s = s + i + " : ";
+            s.append(i).append(" : ");
             for (int j = 0; j < this.numberOfVertices(); j++) {
-                s = s + this.adjMatrix[i][j] + " ";
+                s.append(this.adjMatrix[i][j]).append(" ");
             }
-            s = s + "\n";
+            s.append("\n");
         }
-        return s;
+        return s.toString();
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/MatrixGraphsTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/MatrixGraphsTest.java
new file mode 100644
index 00000000..cc8a2df8
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/MatrixGraphsTest.java
@@ -0,0 +1,140 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.Arrays;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+class MatrixGraphsTest {
+
+    @Test
+    void testGraphConstruction() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);
+        assertEquals(5, graph.numberOfVertices());
+        assertEquals(0, graph.numberOfEdges());
+    }
+
+    @Test
+    void testAddEdge() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);
+        assertTrue(graph.addEdge(0, 1));
+        assertTrue(graph.edgeDoesExist(0, 1));
+        assertTrue(graph.edgeDoesExist(1, 0));
+        assertEquals(1, graph.numberOfEdges());
+
+        // Adding the same edge again should return false
+        assertFalse(graph.addEdge(0, 1));
+        assertFalse(graph.addEdge(5, 1));
+        assertFalse(graph.addEdge(-1, 1));
+    }
+
+    @Test
+    void testRemoveEdge() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);
+        graph.addEdge(0, 1);
+        graph.addEdge(1, 2);
+
+        assertTrue(graph.removeEdge(0, 1));
+        assertFalse(graph.edgeDoesExist(0, 1));
+        assertFalse(graph.edgeDoesExist(1, 0));
+        assertEquals(1, graph.numberOfEdges());
+
+        assertFalse(graph.removeEdge(0, 3));
+        assertFalse(graph.removeEdge(5, 1));
+        assertFalse(graph.removeEdge(-1, 1));
+    }
+
+    @Test
+    void testVertexDoesExist() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);
+        assertTrue(graph.vertexDoesExist(0));
+        assertTrue(graph.vertexDoesExist(4));
+        assertFalse(graph.vertexDoesExist(5));
+        assertFalse(graph.vertexDoesExist(-1));
+    }
+
+    @Test
+    void testDepthFirstOrder() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);
+        graph.addEdge(0, 1);
+        graph.addEdge(0, 2);
+        graph.addEdge(1, 3);
+        graph.addEdge(2, 4);
+
+        List<Integer> dfs = graph.depthFirstOrder(0);
+        assertEquals(5, dfs.size());
+        assertEquals(0, dfs.getFirst());
+
+        assertTrue(dfs.containsAll(Arrays.asList(0, 1, 2, 3, 4)));
+
+        List<Integer> emptyDfs = graph.depthFirstOrder(5);
+        assertTrue(emptyDfs.isEmpty());
+    }
+
+    @Test
+    void testBreadthFirstOrder() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);
+        graph.addEdge(0, 1);
+        graph.addEdge(0, 2);
+        graph.addEdge(1, 3);
+        graph.addEdge(2, 4);
+
+        List<Integer> bfs = graph.breadthFirstOrder(0);
+        assertEquals(5, bfs.size());
+        assertEquals(0, bfs.getFirst());
+
+        assertTrue(bfs.containsAll(Arrays.asList(0, 1, 2, 3, 4)));
+
+        List<Integer> emptyBfs = graph.breadthFirstOrder(5);
+        assertTrue(emptyBfs.isEmpty());
+    }
+
+    @Test
+    void testToString() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(3);
+        graph.addEdge(0, 1);
+        graph.addEdge(1, 2);
+
+        String expected = "    0 1 2  \n"
+            + "0 : 0 1 0 \n"
+            + "1 : 1 0 1 \n"
+            + "2 : 0 1 0 \n";
+
+        assertEquals(expected, graph.toString());
+    }
+
+    @Test
+    void testCyclicGraph() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(4);
+        graph.addEdge(0, 1);
+        graph.addEdge(1, 2);
+        graph.addEdge(2, 3);
+        graph.addEdge(3, 0);
+
+        List<Integer> dfs = graph.depthFirstOrder(0);
+        List<Integer> bfs = graph.breadthFirstOrder(0);
+
+        assertEquals(4, dfs.size());
+        assertEquals(4, bfs.size());
+        assertTrue(dfs.containsAll(Arrays.asList(0, 1, 2, 3)));
+        assertTrue(bfs.containsAll(Arrays.asList(0, 1, 2, 3)));
+    }
+
+    @Test
+    void testDisconnectedGraph() {
+        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);
+        graph.addEdge(0, 1);
+        graph.addEdge(2, 3);
+
+        List<Integer> dfs = graph.depthFirstOrder(0);
+        List<Integer> bfs = graph.breadthFirstOrder(0);
+
+        assertEquals(2, dfs.size());
+        assertEquals(2, bfs.size());
+        assertTrue(dfs.containsAll(Arrays.asList(0, 1)));
+        assertTrue(bfs.containsAll(Arrays.asList(0, 1)));
+    }
+}