Repository: TheAlgorithms/Java
Pull request #5963 (2024-10-24 04:43:08)

refactor: Enhance docs, add more tests in `HamiltonianCycle`
<!--
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/5963?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 67.43%. Comparing base [(`be0b1d5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/be0b1d58d649dba9901214d23b0110d0ca1e9b56?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`26f51a8`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/26f51a8951c810a15bb645622683f5bd5e2e13e3?dropdown=coverage&el=desc&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    #5963   +/-   ##
=========================================
  Coverage     67.43%   67.43%           
+ Complexity     4578     4577    -1     
=========================================
  Files           620      620           
  Lines         17147    17147           
  Branches       3312     3310    -2     
=========================================
  Hits          11563    11563           
  Misses         5138     5138           
  Partials        446      446           
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5963?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/src/main/java/com/thealgorithms/datastructures/graphs/HamiltonianCycle.java b/src/main/java/com/thealgorithms/datastructures/graphs/HamiltonianCycle.java
index f12e3892..5c95850c 100644
--- a/src/main/java/com/thealgorithms/datastructures/graphs/HamiltonianCycle.java
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/HamiltonianCycle.java
@@ -1,8 +1,14 @@
 package com.thealgorithms.datastructures.graphs;
 
+import java.util.Arrays;
+
 /**
- * Java program for Hamiltonian Cycle
- * <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">wikipedia</a>
+ * Java program to find a Hamiltonian Cycle in a graph.
+ * A Hamiltonian Cycle is a cycle that visits every vertex exactly once
+ * and returns to the starting vertex.
+ *
+ * <p>For more details, see the
+ * <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Wikipedia article</a>.
  *
  * @author  <a href="https://github.com/itsAkshayDubey">Akshay Dubey</a>
  */
@@ -14,30 +20,30 @@ public class HamiltonianCycle {
     private int[][] graph;
 
     /**
-     * Find hamiltonian cycle for given graph G(V,E)
+     * Finds a Hamiltonian Cycle for the given graph.
      *
-     * @param graph Adjacency matrix of a graph G(V, E)
-     *              for which hamiltonian path is to be found
-     * @return Array containing hamiltonian cycle
-     *         else returns 1D array with value -1.
+     * @param graph Adjacency matrix representing the graph G(V, E), where V is
+     *              the set of vertices and E is the set of edges.
+     * @return An array representing the Hamiltonian cycle if found, otherwise an
+     *         array filled with -1 indicating no Hamiltonian cycle exists.
      */
     public int[] findHamiltonianCycle(int[][] graph) {
+        // Single vertex graph
+        if (graph.length == 1) {
+            return new int[] {0, 0};
+        }
+
         this.vertex = graph.length;
         this.cycle = new int[this.vertex + 1];
 
-        // Initialize path array with -1 value
-        for (int i = 0; i < this.cycle.length; i++) {
-            this.cycle[i] = -1;
-        }
+        // Initialize the cycle array with -1 to represent unvisited vertices
+        Arrays.fill(this.cycle, -1);
 
         this.graph = graph;
-
         this.cycle[0] = 0;
         this.pathCount = 1;
         if (!isPathFound(0)) {
-            for (int i = 0; i < this.cycle.length; i++) {
-                this.cycle[i] = -1;
-            }
+            Arrays.fill(this.cycle, -1);
         } else {
             this.cycle[this.cycle.length - 1] = this.cycle[0];
         }
@@ -46,11 +52,10 @@ public class HamiltonianCycle {
     }
 
     /**
-     * function to find paths recursively
-     * Find paths recursively from given vertex
+     * Recursively searches for a Hamiltonian cycle from the given vertex.
      *
-     * @param vertex Vertex from which path is to be found
-     * @returns true if path is found false otherwise
+     * @param vertex The current vertex from which to explore paths.
+     * @return {@code true} if a Hamiltonian cycle is found, otherwise {@code false}.
      */
     public boolean isPathFound(int vertex) {
         boolean isLastVertexConnectedToStart = this.graph[vertex][0] == 1 && this.pathCount == this.vertex;
@@ -58,31 +63,26 @@ public class HamiltonianCycle {
             return true;
         }
 
-        /* all vertices selected but last vertex not linked to 0 **/
+        // If all vertices are visited but the last vertex is not connected to the start
         if (this.pathCount == this.vertex) {
             return false;
         }
 
         for (int v = 0; v < this.vertex; v++) {
-            /* if connected **/
-            if (this.graph[vertex][v] == 1) {
-                /* add to path **/
-                this.cycle[this.pathCount++] = v;
-
-                /* remove connection **/
+            if (this.graph[vertex][v] == 1) { // Check if there is an edge
+                this.cycle[this.pathCount++] = v; // Add the vertex to the cycle
                 this.graph[vertex][v] = 0;
                 this.graph[v][vertex] = 0;
 
-                /* if vertex not already selected solve recursively **/
+                // Recursively attempt to complete the cycle
                 if (!isPresent(v)) {
                     return isPathFound(v);
                 }
 
-                /* restore connection **/
+                // Restore the edge if the path does not work
                 this.graph[vertex][v] = 1;
                 this.graph[v][vertex] = 1;
 
-                /* remove path **/
                 this.cycle[--this.pathCount] = -1;
             }
         }
@@ -90,10 +90,10 @@ public class HamiltonianCycle {
     }
 
     /**
-     * function to check if path is already selected
-     * Check if path is already selected
+     * Checks if a vertex is already part of the current Hamiltonian path.
      *
-     * @param vertex Starting vertex
+     * @param vertex The vertex to check.
+     * @return {@code true} if the vertex is already in the path, otherwise {@code false}.
      */
     public boolean isPresent(int vertex) {
         for (int i = 0; i < pathCount - 1; i++) {
@@ -101,7 +101,6 @@ public class HamiltonianCycle {
                 return true;
             }
         }
-
         return false;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java
index ed7c886d..4529606d 100644
--- a/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java
@@ -6,7 +6,7 @@ import org.junit.jupiter.api.Test;
 
 class HamiltonianCycleTest {
 
-    private HamiltonianCycle hamiltonianCycle = new HamiltonianCycle();
+    private final HamiltonianCycle hamiltonianCycle = new HamiltonianCycle();
 
     @Test
     void testFindHamiltonianCycleShouldReturnHamiltonianCycle() {
@@ -36,4 +36,63 @@ class HamiltonianCycleTest {
 
         assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
     }
+
+    @Test
+    void testSingleVertexGraph() {
+        int[] expectedArray = {0, 0};
+        int[][] inputArray = {{0}};
+
+        assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
+    }
+
+    @Test
+    void testDisconnectedGraphShouldReturnInfinityArray() {
+        int[] expectedArray = {-1, -1, -1, -1, -1};
+        int[][] inputArray = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
+
+        assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
+    }
+
+    @Test
+    void testCompleteGraphShouldReturnHamiltonianCycle() {
+        int[] expectedArray = {0, 1, 2, 3, 4, 0};
+        int[][] inputArray = {
+            {0, 1, 1, 1, 1},
+            {1, 0, 1, 1, 1},
+            {1, 1, 0, 1, 1},
+            {1, 1, 1, 0, 1},
+            {1, 1, 1, 1, 0},
+        };
+
+        assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
+    }
+
+    @Test
+    void testGraphWithNoEdgesShouldReturnInfinityArray() {
+        int[] expectedArray = {-1, -1, -1, -1, -1, -1};
+
+        int[][] inputArray = {
+            {0, 0, 0, 0, 0},
+            {0, 0, 0, 0, 0},
+            {0, 0, 0, 0, 0},
+            {0, 0, 0, 0, 0},
+            {0, 0, 0, 0, 0},
+        };
+
+        assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
+    }
+
+    @Test
+    void testLargeGraphWithHamiltonianCycle() {
+        int[] expectedArray = {0, 1, 2, 3, 4, 0};
+        int[][] inputArray = {
+            {0, 1, 0, 1, 1},
+            {1, 0, 1, 1, 0},
+            {0, 1, 0, 1, 1},
+            {1, 1, 1, 0, 1},
+            {1, 0, 1, 1, 0},
+        };
+
+        assertArrayEquals(expectedArray, hamiltonianCycle.findHamiltonianCycle(inputArray));
+    }
 }