Skip to content

Commit e493eb2

Browse files
TarunVishwakarma1TarunVishwakarma1
authored
Add Edmonds Blossom Algorithm (#5471)
1 parent 842ff52 commit e493eb2

File tree

3 files changed

+372
-0
lines changed

3 files changed

+372
-0
lines changed

‎DIRECTORY.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,7 @@
107107
* [ConnectedComponent](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/ConnectedComponent.java)
108108
* [Cycles](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/Cycles.java)
109109
* [DijkstraAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/DijkstraAlgorithm.java)
110+
* [EdmondsBlossomAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithm.java)
110111
* [FloydWarshall](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/FloydWarshall.java)
111112
* [FordFulkerson](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/FordFulkerson.java)
112113
* [Graphs](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/Graphs.java)
@@ -659,6 +660,7 @@
659660
* graphs
660661
* [BoruvkaAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithmTest.java)
661662
* [DijkstraAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/DijkstraAlgorithmTest.java)
663+
* [EdmondsBlossomAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithmTest.java)
662664
* [FordFulkersonTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/FordFulkersonTest.java)
663665
* [HamiltonianCycleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java)
664666
* [KosarajuTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KosarajuTest.java)

‎src/main/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithm.java

Lines changed: 251 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,251 @@
1+
package com.thealgorithms.datastructures.graphs;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
import java.util.Queue;
8+
9+
/**
10+
* The EdmondsBlossomAlgorithm class implements Edmonds' Blossom Algorithm
11+
* to find the maximum matching in a general graph. The algorithm efficiently
12+
* handles cases where the graph contains odd-length cycles by contracting
13+
* "blossoms" and finding augmenting paths.
14+
*<p>
15+
* <a href="https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf">Documentation of Algorithm (Stanford University)</a>
16+
* <p></p>
17+
* <a href="https://en.wikipedia.org/wiki/Blossom_algorithm">Wikipedia Documentation</a>
18+
*/
19+
public final class EdmondsBlossomAlgorithm {
20+
21+
private EdmondsBlossomAlgorithm() {
22+
}
23+
24+
private static final int UNMATCHED = -1; // Constant to represent unmatched vertices
25+
26+
/**
27+
* Finds the maximum matching in a general graph (Edmonds Blossom Algorithm).
28+
*
29+
* @param edges A list of edges in the graph.
30+
* @param vertexCount The number of vertices in the graph.
31+
* @return A list of matched pairs of vertices.
32+
*/
33+
public static List<int[]> maximumMatching(List<int[]> edges, int vertexCount) {
34+
List<List<Integer>> graph = new ArrayList<>(vertexCount);
35+
36+
// Initialize each vertex's adjacency list.
37+
for (int i = 0; i < vertexCount; i++) {
38+
graph.add(new ArrayList<>());
39+
}
40+
41+
// Populate the graph with the edges
42+
for (int[] edge : edges) {
43+
int u = edge[0];
44+
int v = edge[1];
45+
graph.get(u).add(v);
46+
graph.get(v).add(u);
47+
}
48+
49+
// Initial matching array and auxiliary data structures
50+
int[] match = new int[vertexCount];
51+
Arrays.fill(match, UNMATCHED); // All vertices are initially unmatched
52+
int[] parent = new int[vertexCount];
53+
int[] base = new int[vertexCount];
54+
boolean[] inBlossom = new boolean[vertexCount]; // Indicates if a vertex is part of a blossom
55+
boolean[] inQueue = new boolean[vertexCount]; // Tracks vertices in the BFS queue
56+
57+
// Main logic for finding maximum matching
58+
for (int u = 0; u < vertexCount; u++) {
59+
if (match[u] == UNMATCHED) {
60+
// BFS initialization
61+
Arrays.fill(parent, UNMATCHED);
62+
for (int i = 0; i < vertexCount; i++) {
63+
base[i] = i; // Each vertex is its own base initially
64+
}
65+
Arrays.fill(inBlossom, false);
66+
Arrays.fill(inQueue, false);
67+
68+
Queue<Integer> queue = new LinkedList<>();
69+
queue.add(u);
70+
inQueue[u] = true;
71+
72+
boolean augmentingPathFound = false;
73+
74+
// BFS to find augmenting paths
75+
while (!queue.isEmpty() && !augmentingPathFound) {
76+
int current = queue.poll(); // Use a different name for clarity
77+
for (int y : graph.get(current)) {
78+
// Skip if we are looking at the same edge as the current match
79+
if (match[current] == y) {
80+
continue;
81+
}
82+
83+
if (base[current] == base[y]) {
84+
continue; // Avoid self-loops
85+
}
86+
87+
if (parent[y] == UNMATCHED) {
88+
// Case 1: y is unmatched, we've found an augmenting path
89+
if (match[y] == UNMATCHED) {
90+
parent[y] = current;
91+
augmentingPathFound = true;
92+
updateMatching(match, parent, y); // Augment along this path
93+
break;
94+
}
95+
96+
// Case 2: y is matched, add y's match to the queue
97+
int z = match[y];
98+
parent[y] = current;
99+
parent[z] = y;
100+
if (!inQueue[z]) {
101+
queue.add(z);
102+
inQueue[z] = true;
103+
}
104+
} else {
105+
// Case 3: Both x and y have a parent; check for a cycle/blossom
106+
int baseU = findBase(base, parent, current, y);
107+
if (baseU != UNMATCHED) {
108+
contractBlossom(new BlossomData(new BlossomAuxData(queue, parent, base, inBlossom, match, inQueue), current, y, baseU));
109+
}
110+
}
111+
}
112+
}
113+
}
114+
}
115+
116+
// Create result list of matched pairs
117+
List<int[]> matchingResult = new ArrayList<>();
118+
for (int v = 0; v < vertexCount; v++) {
119+
if (match[v] != UNMATCHED && v < match[v]) {
120+
matchingResult.add(new int[] {v, match[v]});
121+
}
122+
}
123+
124+
return matchingResult;
125+
}
126+
127+
/**
128+
* Updates the matching along the augmenting path found.
129+
*
130+
* @param match The matching array.
131+
* @param parent The parent array used during the BFS.
132+
* @param u The starting node of the augmenting path.
133+
*/
134+
private static void updateMatching(int[] match, int[] parent, int u) {
135+
while (u != UNMATCHED) {
136+
int v = parent[u];
137+
int next = match[v];
138+
match[v] = u;
139+
match[u] = v;
140+
u = next;
141+
}
142+
}
143+
144+
/**
145+
* Finds the base of a node in the blossom.
146+
*
147+
* @param base The base array.
148+
* @param parent The parent array.
149+
* @param u One end of the edge.
150+
* @param v The other end of the edge.
151+
* @return The base of the node or UNMATCHED.
152+
*/
153+
private static int findBase(int[] base, int[] parent, int u, int v) {
154+
boolean[] visited = new boolean[base.length];
155+
156+
// Mark ancestors of u
157+
int currentU = u;
158+
while (true) {
159+
currentU = base[currentU]; // Move assignment out of the condition
160+
visited[currentU] = true;
161+
if (parent[currentU] == UNMATCHED) {
162+
break;
163+
}
164+
currentU = parent[currentU]; // Move assignment out of the condition
165+
}
166+
167+
// Find the common ancestor of v
168+
int currentV = v;
169+
while (true) {
170+
currentV = base[currentV]; // Move assignment out of the condition
171+
if (visited[currentV]) {
172+
return currentV;
173+
}
174+
currentV = parent[currentV]; // Move assignment out of the condition
175+
}
176+
}
177+
178+
/**
179+
* Contracts a blossom and updates the base array.
180+
*
181+
* @param blossomData The data containing the parameters related to the blossom contraction.
182+
*/
183+
private static void contractBlossom(BlossomData blossomData) {
184+
for (int x = blossomData.u; blossomData.auxData.base[x] != blossomData.lca; x = blossomData.auxData.parent[blossomData.auxData.match[x]]) {
185+
int baseX = blossomData.auxData.base[x];
186+
int matchBaseX = blossomData.auxData.base[blossomData.auxData.match[x]];
187+
188+
// Split the inner assignment into two separate assignments
189+
blossomData.auxData.inBlossom[baseX] = true;
190+
blossomData.auxData.inBlossom[matchBaseX] = true;
191+
}
192+
193+
for (int x = blossomData.v; blossomData.auxData.base[x] != blossomData.lca; x = blossomData.auxData.parent[blossomData.auxData.match[x]]) {
194+
int baseX = blossomData.auxData.base[x];
195+
int matchBaseX = blossomData.auxData.base[blossomData.auxData.match[x]];
196+
197+
// Split the inner assignment into two separate assignments
198+
blossomData.auxData.inBlossom[baseX] = true;
199+
blossomData.auxData.inBlossom[matchBaseX] = true;
200+
}
201+
202+
// Update the base for all marked vertices
203+
for (int i = 0; i < blossomData.auxData.base.length; i++) {
204+
if (blossomData.auxData.inBlossom[blossomData.auxData.base[i]]) {
205+
blossomData.auxData.base[i] = blossomData.lca; // Contract to the lowest common ancestor
206+
if (!blossomData.auxData.inQueue[i]) {
207+
blossomData.auxData.queue.add(i); // Add to queue if not already present
208+
blossomData.auxData.inQueue[i] = true;
209+
}
210+
}
211+
}
212+
}
213+
214+
/**
215+
* Auxiliary data class to encapsulate common parameters for the blossom operations.
216+
*/
217+
static class BlossomAuxData {
218+
Queue<Integer> queue; // Queue for BFS traversal
219+
int[] parent; // Parent array to store the paths
220+
int[] base; // Base array to track the base of each vertex
221+
boolean[] inBlossom; // Flags to indicate if a vertex is in a blossom
222+
int[] match; // Array to store matches for each vertex
223+
boolean[] inQueue; // Flags to track vertices in the BFS queue
224+
225+
BlossomAuxData(Queue<Integer> queue, int[] parent, int[] base, boolean[] inBlossom, int[] match, boolean[] inQueue) {
226+
this.queue = queue;
227+
this.parent = parent;
228+
this.base = base;
229+
this.inBlossom = inBlossom;
230+
this.match = match;
231+
this.inQueue = inQueue;
232+
}
233+
}
234+
235+
/**
236+
* BlossomData class with reduced parameters.
237+
*/
238+
static class BlossomData {
239+
BlossomAuxData auxData; // Use the auxiliary data class
240+
int u; // One vertex in the edge
241+
int v; // Another vertex in the edge
242+
int lca; // Lowest Common Ancestor
243+
244+
BlossomData(BlossomAuxData auxData, int u, int v, int lca) {
245+
this.auxData = auxData;
246+
this.u = u;
247+
this.v = v;
248+
this.lca = lca;
249+
}
250+
}
251+
}

‎src/test/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithmTest.java

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
package com.thealgorithms.datastructures.graphs;
2+
3+
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
4+
import static org.junit.jupiter.api.Assertions.assertEquals;
5+
import static org.junit.jupiter.api.Assertions.assertTrue;
6+
7+
import java.util.Arrays;
8+
import java.util.Collections;
9+
import java.util.List;
10+
import org.junit.jupiter.api.Test;
11+
12+
/**
13+
* Unit tests for the EdmondsBlossomAlgorithm class.
14+
*
15+
* These tests ensure that the Edmonds' Blossom Algorithm implementation
16+
* works as expected for various graph structures, returning the correct
17+
* maximum matching.
18+
*/
19+
public class EdmondsBlossomAlgorithmTest {
20+
21+
/**
22+
* Helper method to convert a list of matching pairs into a sorted 2D array.
23+
* Sorting ensures consistent ordering of pairs and vertices for easier comparison in tests.
24+
*
25+
* @param matching List of matched pairs returned by the algorithm.
26+
* @return A sorted 2D array of matching pairs.
27+
*/
28+
private int[][] convertMatchingToArray(List<int[]> matching) {
29+
// Convert the list of pairs into an array
30+
int[][] result = matching.toArray(new int[0][]);
31+
32+
// Sort each individual pair for consistency
33+
for (int[] pair : result) {
34+
Arrays.sort(pair);
35+
}
36+
37+
// Sort the array of pairs to ensure consistent order
38+
Arrays.sort(result, (a, b) -> Integer.compare(a[0], b[0]));
39+
return result;
40+
}
41+
42+
/**
43+
* Test Case 1: A triangle graph where vertices 0, 1, and 2 form a cycle.
44+
* The expected maximum matching is a single pair (0, 1) or any equivalent pair from the cycle.
45+
*/
46+
@Test
47+
public void testCase1() {
48+
List<int[]> edges = Arrays.asList(new int[] {0, 1}, new int[] {1, 2}, new int[] {2, 0});
49+
List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 3);
50+
51+
int[][] expected = new int[][] {{0, 1}};
52+
assertArrayEquals(expected, convertMatchingToArray(matching));
53+
}
54+
55+
/**
56+
* Test Case 2: A disconnected graph where vertices 0, 1, 2 form one component,
57+
* and vertices 3, 4 form another. The expected maximum matching is two pairs:
58+
* (0, 1) and (3, 4).
59+
*/
60+
@Test
61+
public void testCase2() {
62+
List<int[]> edges = Arrays.asList(new int[] {0, 1}, new int[] {1, 2}, new int[] {3, 4});
63+
List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 5);
64+
65+
int[][] expected = new int[][] {{0, 1}, {3, 4}};
66+
assertArrayEquals(expected, convertMatchingToArray(matching));
67+
}
68+
69+
/**
70+
* Test Case 3: A cycle graph involving vertices 0, 1, 2, 3 forming a cycle,
71+
* with an additional edge (4, 5) outside the cycle.
72+
* The expected maximum matching is (0, 1) and (4, 5).
73+
*/
74+
@Test
75+
public void testCase3() {
76+
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});
77+
List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 6);
78+
79+
// Updated expected output to include the maximum matching pairs
80+
int[][] expected = new int[][] {{0, 1}, {2, 3}, {4, 5}};
81+
assertArrayEquals(expected, convertMatchingToArray(matching));
82+
}
83+
84+
/**
85+
* Test Case 4: A graph with no edges.
86+
* Since there are no edges, the expected matching is an empty set.
87+
*/
88+
@Test
89+
public void testCaseNoMatching() {
90+
List<int[]> edges = Collections.emptyList(); // No edges
91+
List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 3);
92+
93+
int[][] expected = new int[][] {}; // No pairs expected
94+
assertArrayEquals(expected, convertMatchingToArray(matching));
95+
}
96+
97+
/**
98+
* Test Case 5: A more complex graph with multiple cycles and extra edges.
99+
* This tests the algorithm's ability to handle larger, more intricate graphs.
100+
* The expected matching is {{0, 1}, {2, 5}, {3, 4}}.
101+
*/
102+
@Test
103+
public void testCaseLargeGraph() {
104+
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});
105+
List<int[]> matching = EdmondsBlossomAlgorithm.maximumMatching(edges, 6);
106+
107+
// Check if the size of the matching is correct (i.e., 3 pairs)
108+
assertEquals(3, matching.size());
109+
110+
// Check that the result contains valid pairs (any order is fine)
111+
// Valid maximum matchings could be {{0, 1}, {2, 5}, {3, 4}} or {{0, 1}, {2, 3}, {4, 5}}, etc.
112+
int[][] possibleMatching1 = new int[][] {{0, 1}, {2, 5}, {3, 4}};
113+
int[][] possibleMatching2 = new int[][] {{0, 1}, {2, 3}, {4, 5}};
114+
int[][] result = convertMatchingToArray(matching);
115+
116+
// Assert that the result is one of the valid maximum matchings
117+
assertTrue(Arrays.deepEquals(result, possibleMatching1) || Arrays.deepEquals(result, possibleMatching2));
118+
}
119+
}

0 commit comments

Comments
 (0)