Repository: TheAlgorithms/Java
Pull request #5471 (2024-09-25 16:18:38)

Implemented Edmonds Blossom Algorithm
<!--
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
-->

Hey I've implemented Edmond's Blossom Algorithm in src/main/java/com.thealgorithms/datastructures/graphs/EdmondBlossomAlgorithm.java 
with the test class in the test package
for enhancement #5470 

This PR implements the Edmonds Blossom Algorithm, a well-known algorithm used to find maximum matchings in general graphs, including non-bipartite graphs. The algorithm is crucial in combinatorial optimization and graph theory.

Key Features:

Handles odd-length cycles (blossoms) by contracting them into single nodes, which allows the matching process to proceed in general graphs.
Finds the maximum cardinality matching in polynomial time.
Works efficiently for both directed and undirected graphs.
Algorithm Overview:

Initialization: Start with an empty matching and process the graph.
Augmenting Path Search: Search for augmenting paths using alternating paths (paths alternating between matched and unmatched edges).
Blossom Contraction: When an odd-length cycle (blossom) is encountered, it is temporarily contracted into a single node.
Expansion and Matching Update: Once an augmenting path is found, the blossoms are expanded, and the matching is updated.
Performance:

The time complexity is O(V^3), where V is the number of vertices in the graph.
This algorithm is especially useful in various applications such as network flow problems, stable marriages, and graph partitioning.

<!-- 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/5471?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 `80.32787%` with `24 lines` in your changes missing coverage. Please review.
> Project coverage is 52.51%. Comparing base [(`27343e7`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/27343e7aa874343cf084f767b1aaa71e9134bc5e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`14826e8`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/14826e89702752770db87c262d198502f3bade40?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5471?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...datastructures/graphs/EdmondsBlossomAlgorithm.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5471?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fgraphs%2FEdmondsBlossomAlgorithm.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9ncmFwaHMvRWRtb25kc0Jsb3Nzb21BbGdvcml0aG0uamF2YQ==) | 80.32% | [20 Missing and 4 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5471?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    #5471      +/-   ##
============================================
+ Coverage     52.28%   52.51%   +0.23%     
- Complexity     3255     3281      +26     
============================================
  Files           525      526       +1     
  Lines         15184    15306     +122     
  Branches       2887     2910      +23     
============================================
+ Hits           7939     8038      +99     
- Misses         6920     6940      +20     
- Partials        325      328       +3     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5471?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).

TarunVishwakarma1: I apologize for so many file changes but there were too many issue to fix one by one. Thankfully it all works now. 😄
If its in scope of merging to the repo, may I ask that you do it in October,  I've signed up for the hacktoberfest and it will be great if I got a merge at that time.

Thank you for understanding😄😄. 
TarunVishwakarma1: Sure will do 

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index ee09790e..6f63a88b 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -107,6 +107,7 @@
               * [ConnectedComponent](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/ConnectedComponent.java)
               * [Cycles](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/Cycles.java)
               * [DijkstraAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/DijkstraAlgorithm.java)
+              * [EdmondsBlossomAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithm.java)
               * [FloydWarshall](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/FloydWarshall.java)
               * [FordFulkerson](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/FordFulkerson.java)
               * [Graphs](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/Graphs.java)
@@ -659,6 +660,7 @@
             * graphs
               * [BoruvkaAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithmTest.java)
               * [DijkstraAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/DijkstraAlgorithmTest.java)
+              * [EdmondsBlossomAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithmTest.java)
               * [FordFulkersonTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/FordFulkersonTest.java)
               * [HamiltonianCycleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java)
               * [KosarajuTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KosarajuTest.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithm.java b/src/main/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithm.java
new file mode 100644
index 00000000..27ad96d7
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithm.java
@@ -0,0 +1,251 @@
+package com.thealgorithms.datastructures.graphs;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+
+/**
+ * The EdmondsBlossomAlgorithm class implements Edmonds' Blossom Algorithm
+ * to find the maximum matching in a general graph. The algorithm efficiently
+ * handles cases where the graph contains odd-length cycles by contracting
+ * "blossoms" and finding augmenting paths.
+ *<p>
+ * <a href="https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf">Documentation of Algorithm (Stanford University)</a>
+ * <p></p>
+ * <a href="https://en.wikipedia.org/wiki/Blossom_algorithm">Wikipedia Documentation</a>
+ */
+public final class EdmondsBlossomAlgorithm {
+
+    private EdmondsBlossomAlgorithm() {
+    }
+
+    private static final int UNMATCHED = -1; // Constant to represent unmatched vertices
+
+    /**
+     * Finds the maximum matching in a general graph (Edmonds Blossom Algorithm).
+     *
+     * @param edges A list of edges in the graph.
+     * @param vertexCount The number of vertices in the graph.
+     * @return A list of matched pairs of vertices.
+     */
+    public static List<int[]> maximumMatching(List<int[]> edges, int vertexCount) {
+        List<List<Integer>> graph = new ArrayList<>(vertexCount);
+
+        // Initialize each vertex's adjacency list.
+        for (int i = 0; i < vertexCount; i++) {
+            graph.add(new ArrayList<>());
+        }
+
+        // Populate the graph with the edges
+        for (int[] edge : edges) {
+            int u = edge[0];
+            int v = edge[1];
+            graph.get(u).add(v);
+            graph.get(v).add(u);
+        }
+
+        // Initial matching array and auxiliary data structures
+        int[] match = new int[vertexCount];
+        Arrays.fill(match, UNMATCHED); // All vertices are initially unmatched
+        int[] parent = new int[vertexCount];
+        int[] base = new int[vertexCount];
+        boolean[] inBlossom = new boolean[vertexCount]; // Indicates if a vertex is part of a blossom
+        boolean[] inQueue = new boolean[vertexCount]; // Tracks vertices in the BFS queue
+
+        // Main logic for finding maximum matching
+        for (int u = 0; u < vertexCount; u++) {
+            if (match[u] == UNMATCHED) {
+                // BFS initialization
+                Arrays.fill(parent, UNMATCHED);
+                for (int i = 0; i < vertexCount; i++) {
+                    base[i] = i; // Each vertex is its own base initially
+                }
+                Arrays.fill(inBlossom, false);
+                Arrays.fill(inQueue, false);
+
+                Queue<Integer> queue = new LinkedList<>();
+                queue.add(u);
+                inQueue[u] = true;
+
+                boolean augmentingPathFound = false;
+
+                // BFS to find augmenting paths
+                while (!queue.isEmpty() && !augmentingPathFound) {
+                    int current = queue.poll(); // Use a different name for clarity
+                    for (int y : graph.get(current)) {
+                        // Skip if we are looking at the same edge as the current match
+                        if (match[current] == y) {
+                            continue;
+                        }
+
+                        if (base[current] == base[y]) {
+                            continue; // Avoid self-loops
+                        }
+
+                        if (parent[y] == UNMATCHED) {
+                            // Case 1: y is unmatched, we've found an augmenting path
+                            if (match[y] == UNMATCHED) {
+                                parent[y] = current;
+                                augmentingPathFound = true;
+                                updateMatching(match, parent, y); // Augment along this path
+                                break;
+                            }
+
+                            // Case 2: y is matched, add y's match to the queue
+                            int z = match[y];
+                            parent[y] = current;
+                            parent[z] = y;
+                            if (!inQueue[z]) {
+                                queue.add(z);
+                                inQueue[z] = true;
+                            }
+                        } else {
+                            // Case 3: Both x and y have a parent; check for a cycle/blossom
+                            int baseU = findBase(base, parent, current, y);
+                            if (baseU != UNMATCHED) {
+                                contractBlossom(new BlossomData(new BlossomAuxData(queue, parent, base, inBlossom, match, inQueue), current, y, baseU));
+                            }
+                        }
+                    }
+                }
+            }
+        }
+
+        // Create result list of matched pairs
+        List<int[]> matchingResult = new ArrayList<>();
+        for (int v = 0; v < vertexCount; v++) {
+            if (match[v] != UNMATCHED && v < match[v]) {
+                matchingResult.add(new int[] {v, match[v]});
+            }
+        }
+
+        return matchingResult;
+    }
+
+    /**
+     * Updates the matching along the augmenting path found.
+     *
+     * @param match The matching array.
+     * @param parent The parent array used during the BFS.
+     * @param u The starting node of the augmenting path.
+     */
+    private static void updateMatching(int[] match, int[] parent, int u) {
+        while (u != UNMATCHED) {
+            int v = parent[u];
+            int next = match[v];
+            match[v] = u;
+            match[u] = v;
+            u = next;
+        }
+    }
+
+    /**
+     * Finds the base of a node in the blossom.
+     *
+     * @param base The base array.
+     * @param parent The parent array.
+     * @param u One end of the edge.
+     * @param v The other end of the edge.
+     * @return The base of the node or UNMATCHED.
+     */
+    private static int findBase(int[] base, int[] parent, int u, int v) {
+        boolean[] visited = new boolean[base.length];
+
+        // Mark ancestors of u
+        int currentU = u;
+        while (true) {
+            currentU = base[currentU]; // Move assignment out of the condition
+            visited[currentU] = true;
+            if (parent[currentU] == UNMATCHED) {
+                break;
+            }
+            currentU = parent[currentU]; // Move assignment out of the condition
+        }
+
+        // Find the common ancestor of v
+        int currentV = v;
+        while (true) {
+            currentV = base[currentV]; // Move assignment out of the condition
+            if (visited[currentV]) {
+                return currentV;
+            }
+            currentV = parent[currentV]; // Move assignment out of the condition
+        }
+    }
+
+    /**
+     * Contracts a blossom and updates the base array.
+     *
+     * @param blossomData The data containing the parameters related to the blossom contraction.
+     */
+    private static void contractBlossom(BlossomData blossomData) {
+        for (int x = blossomData.u; blossomData.auxData.base[x] != blossomData.lca; x = blossomData.auxData.parent[blossomData.auxData.match[x]]) {
+            int baseX = blossomData.auxData.base[x];
+            int matchBaseX = blossomData.auxData.base[blossomData.auxData.match[x]];
+
+            // Split the inner assignment into two separate assignments
+            blossomData.auxData.inBlossom[baseX] = true;
+            blossomData.auxData.inBlossom[matchBaseX] = true;
+        }
+
+        for (int x = blossomData.v; blossomData.auxData.base[x] != blossomData.lca; x = blossomData.auxData.parent[blossomData.auxData.match[x]]) {
+            int baseX = blossomData.auxData.base[x];
+            int matchBaseX = blossomData.auxData.base[blossomData.auxData.match[x]];
+
+            // Split the inner assignment into two separate assignments
+            blossomData.auxData.inBlossom[baseX] = true;
+            blossomData.auxData.inBlossom[matchBaseX] = true;
+        }
+
+        // Update the base for all marked vertices
+        for (int i = 0; i < blossomData.auxData.base.length; i++) {
+            if (blossomData.auxData.inBlossom[blossomData.auxData.base[i]]) {
+                blossomData.auxData.base[i] = blossomData.lca; // Contract to the lowest common ancestor
+                if (!blossomData.auxData.inQueue[i]) {
+                    blossomData.auxData.queue.add(i); // Add to queue if not already present
+                    blossomData.auxData.inQueue[i] = true;
+                }
+            }
+        }
+    }
+
+    /**
+     * Auxiliary data class to encapsulate common parameters for the blossom operations.
+     */
+    static class BlossomAuxData {
+        Queue<Integer> queue; // Queue for BFS traversal
+        int[] parent; // Parent array to store the paths
+        int[] base; // Base array to track the base of each vertex
+        boolean[] inBlossom; // Flags to indicate if a vertex is in a blossom
+        int[] match; // Array to store matches for each vertex
+        boolean[] inQueue; // Flags to track vertices in the BFS queue
+
+        BlossomAuxData(Queue<Integer> queue, int[] parent, int[] base, boolean[] inBlossom, int[] match, boolean[] inQueue) {
+            this.queue = queue;
+            this.parent = parent;
+            this.base = base;
+            this.inBlossom = inBlossom;
+            this.match = match;
+            this.inQueue = inQueue;
+        }
+    }
+
+    /**
+     * BlossomData class with reduced parameters.
+     */
+    static class BlossomData {
+        BlossomAuxData auxData; // Use the auxiliary data class
+        int u; // One vertex in the edge
+        int v; // Another vertex in the edge
+        int lca; // Lowest Common Ancestor
+
+        BlossomData(BlossomAuxData auxData, int u, int v, int lca) {
+            this.auxData = auxData;
+            this.u = u;
+            this.v = v;
+            this.lca = lca;
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithmTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithmTest.java
new file mode 100644
index 00000000..4a723244
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithmTest.java
@@ -0,0 +1,119 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Unit tests for the EdmondsBlossomAlgorithm class.
+ *
+ * These tests ensure that the Edmonds' Blossom Algorithm implementation
+ * works as expected for various graph structures, returning the correct
+ * maximum matching.
+ */
+public class EdmondsBlossomAlgorithmTest {
+
+    /**
+     * Helper method to convert a list of matching pairs into a sorted 2D array.
+     * Sorting ensures consistent ordering of pairs and vertices for easier comparison in tests.
+     *
+     * @param matching List of matched pairs returned by the algorithm.
+     * @return A sorted 2D array of matching pairs.
+     */
+    private int[][] convertMatchingToArray(List<int[]> matching) {
+        // Convert the list of pairs into an array
+        int[][] result = matching.toArray(new int[0][]);
+
+        // Sort each individual pair for consistency
+        for (int[] pair : result) {
+            Arrays.sort(pair);
+        }
+
+        // Sort the array of pairs to ensure consistent order
+        Arrays.sort(result, (a, b) -> Integer.compare(a[0], b[0]));
+        return result;
+    }
+
+    /**
+     * Test Case 1: A triangle graph where vertices 0, 1, and 2 form a cycle.
+     * The expected maximum matching is a single pair (0, 1) or any equivalent pair from the cycle.
+     */
+    @Test
+    public void testCase1() {
+        List<int[]> edges = Arrays.asList(new int[] {0, 1}, new int[] {1, 2}, new int[] {2, 0});
+        List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 3);
+
+        int[][] expected = new int[][] {{0, 1}};
+        assertArrayEquals(expected, convertMatchingToArray(matching));
+    }
+
+    /**
+     * Test Case 2: A disconnected graph where vertices 0, 1, 2 form one component,
+     * and vertices 3, 4 form another. The expected maximum matching is two pairs:
+     * (0, 1) and (3, 4).
+     */
+    @Test
+    public void testCase2() {
+        List<int[]> edges = Arrays.asList(new int[] {0, 1}, new int[] {1, 2}, new int[] {3, 4});
+        List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 5);
+
+        int[][] expected = new int[][] {{0, 1}, {3, 4}};
+        assertArrayEquals(expected, convertMatchingToArray(matching));
+    }
+
+    /**
+     * Test Case 3: A cycle graph involving vertices 0, 1, 2, 3 forming a cycle,
+     * with an additional edge (4, 5) outside the cycle.
+     * The expected maximum matching is (0, 1) and (4, 5).
+     */
+    @Test
+    public void testCase3() {
+        List<int[]> edges = Arrays.asList(new int[] {0, 1}, new int[] {1, 2}, new int[] {2, 3}, new int[] {3, 0}, new int[] {4, 5});
+        List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 6);
+
+        // Updated expected output to include the maximum matching pairs
+        int[][] expected = new int[][] {{0, 1}, {2, 3}, {4, 5}};
+        assertArrayEquals(expected, convertMatchingToArray(matching));
+    }
+
+    /**
+     * Test Case 4: A graph with no edges.
+     * Since there are no edges, the expected matching is an empty set.
+     */
+    @Test
+    public void testCaseNoMatching() {
+        List<int[]> edges = Collections.emptyList(); // No edges
+        List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 3);
+
+        int[][] expected = new int[][] {}; // No pairs expected
+        assertArrayEquals(expected, convertMatchingToArray(matching));
+    }
+
+    /**
+     * Test Case 5: A more complex graph with multiple cycles and extra edges.
+     * This tests the algorithm's ability to handle larger, more intricate graphs.
+     * The expected matching is {{0, 1}, {2, 5}, {3, 4}}.
+     */
+    @Test
+    public void testCaseLargeGraph() {
+        List<int[]> edges = Arrays.asList(new int[] {0, 1}, new int[] {1, 2}, new int[] {2, 3}, new int[] {3, 4}, new int[] {4, 5}, new int[] {5, 0}, new int[] {1, 4}, new int[] {2, 5});
+        List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 6);
+
+        // Check if the size of the matching is correct (i.e., 3 pairs)
+        assertEquals(3, matching.size());
+
+        // Check that the result contains valid pairs (any order is fine)
+        // Valid maximum matchings could be {{0, 1}, {2, 5}, {3, 4}} or {{0, 1}, {2, 3}, {4, 5}}, etc.
+        int[][] possibleMatching1 = new int[][] {{0, 1}, {2, 5}, {3, 4}};
+        int[][] possibleMatching2 = new int[][] {{0, 1}, {2, 3}, {4, 5}};
+        int[][] result = convertMatchingToArray(matching);
+
+        // Assert that the result is one of the valid maximum matchings
+        assertTrue(Arrays.deepEquals(result, possibleMatching1) || Arrays.deepEquals(result, possibleMatching2));
+    }
+}