Repository: TheAlgorithms/Java
Pull request #6184 (2025-02-28 22:51:18)

Add Maximum Weighted Matching Algorithm for Trees
This PR adds an algorithm for solving the **Maximum Weighted Matching in Trees** problem. The tree is represented as an undirected graph with weighted edges. The goal is to find a matching in the tree such that no two edges in the matching share a common vertex, while maximizing the sum of the edge weights.

#### Problem Description:
Given an undirected tree **G = (V, E)** with edge weights **γ: E → N** and a root **r ∈ V**, the algorithm computes a maximum weight matching **M ⊆ E** where no two edges share a common vertex. The sum of the weights of the edges in the matching, **∑ e∈M γ(e)**, should be maximized.

The solution utilizes dynamic programming to efficiently compute the optimal matching in the tree while ensuring that no vertices are repeated in the matching.

For more details on matching theory, refer to the [Matching (graph theory)](https://en.wikipedia.org/wiki/Matching_(graph_theory)) page.

- [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/6184?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 `85.00000%` with `6 lines` in your changes missing coverage. Please review.
> Project coverage is 74.15%. Comparing base [(`849ab91`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/849ab913c0d22c7d1df967b6e46eea849f3dab42?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`02d4cb0`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/02d4cb0dc6f196ef484d9f7cd19db4304b24e3ae?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/6184?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...tructures/graphs/UndirectedAdjacencyListGraph.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6184?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fgraphs%2FUndirectedAdjacencyListGraph.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9ncmFwaHMvVW5kaXJlY3RlZEFkamFjZW5jeUxpc3RHcmFwaC5qYXZh) | 73.33% | [2 Missing and 2 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6184?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |
| [...thealgorithms/dynamicprogramming/TreeMatching.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6184?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdynamicprogramming%2FTreeMatching.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9keW5hbWljcHJvZ3JhbW1pbmcvVHJlZU1hdGNoaW5nLmphdmE=) | 92.00% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6184?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    #6184      +/-   ##
============================================
+ Coverage     74.13%   74.15%   +0.01%     
- Complexity     5195     5207      +12     
============================================
  Files           663      665       +2     
  Lines         17778    17818      +40     
  Branches       3423     3429       +6     
============================================
+ Hits          13180    13213      +33     
- Misses         4096     4099       +3     
- Partials        502      506       +4     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6184?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/UndirectedAdjacencyListGraph.java b/src/main/java/com/thealgorithms/datastructures/graphs/UndirectedAdjacencyListGraph.java
new file mode 100644
index 00000000..8aafc1ef
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/UndirectedAdjacencyListGraph.java
@@ -0,0 +1,69 @@
+package com.thealgorithms.datastructures.graphs;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+
+public class UndirectedAdjacencyListGraph {
+    private ArrayList<HashMap<Integer, Integer>> adjacencyList = new ArrayList<>();
+
+    /**
+     * Adds a new node to the graph by adding an empty HashMap for its neighbors.
+     * @return the index of the newly added node in the adjacency list
+     */
+    public int addNode() {
+        adjacencyList.add(new HashMap<>());
+        return adjacencyList.size() - 1;
+    }
+
+    /**
+     * Adds an undirected edge between the origin node (@orig) and the destination node (@dest) with the specified weight.
+     * If the edge already exists, no changes are made.
+     * @param orig the index of the origin node
+     * @param dest the index of the destination node
+     * @param weight the weight of the edge between @orig and @dest
+     * @return true if the edge was successfully added, false if the edge already exists or if any node index is invalid
+     */
+    public boolean addEdge(int orig, int dest, int weight) {
+        int numNodes = adjacencyList.size();
+        if (orig >= numNodes || dest >= numNodes || orig < 0 || dest < 0) {
+            return false;
+        }
+
+        if (adjacencyList.get(orig).containsKey(dest)) {
+            return false;
+        }
+
+        adjacencyList.get(orig).put(dest, weight);
+        adjacencyList.get(dest).put(orig, weight);
+        return true;
+    }
+
+    /**
+     * Returns the set of all adjacent nodes (neighbors) for the given node.
+     * @param node the index of the node whose neighbors are to be retrieved
+     * @return a HashSet containing the indices of all neighboring nodes
+     */
+    public HashSet<Integer> getNeighbors(int node) {
+        return new HashSet<>(adjacencyList.get(node).keySet());
+    }
+
+    /**
+     * Returns the weight of the edge between the origin node (@orig) and the destination node (@dest).
+     * If no edge exists, returns null.
+     * @param orig the index of the origin node
+     * @param dest the index of the destination node
+     * @return the weight of the edge between @orig and @dest, or null if no edge exists
+     */
+    public Integer getEdgeWeight(int orig, int dest) {
+        return adjacencyList.get(orig).getOrDefault(dest, null);
+    }
+
+    /**
+     * Returns the number of nodes currently in the graph.
+     * @return the number of nodes in the graph
+     */
+    public int size() {
+        return adjacencyList.size();
+    }
+}
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/TreeMatching.java b/src/main/java/com/thealgorithms/dynamicprogramming/TreeMatching.java
new file mode 100644
index 00000000..9fd82cca
--- /dev/null
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/TreeMatching.java
@@ -0,0 +1,78 @@
+package com.thealgorithms.dynamicprogramming;
+
+import com.thealgorithms.datastructures.graphs.UndirectedAdjacencyListGraph;
+
+/**
+ * This class implements the algorithm for calculating the maximum weighted matching in a tree.
+ * The tree is represented as an undirected graph with weighted edges.
+ *
+ * Problem Description:
+ *  Given an undirected tree G = (V, E) with edge weights γ: E → N and a root r ∈ V,
+ *  the goal is to find a maximum weight matching M ⊆ E such that no two edges in M
+ *  share a common vertex. The sum of the weights of the edges in M, ∑ e∈M γ(e), should be maximized.
+ *  For more Information: <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)">Matching (graph theory)</a>
+ *
+ * @author  <a href="https://github.com/DenizAltunkapan">Deniz Altunkapan</a>
+ */
+public class TreeMatching {
+
+    private UndirectedAdjacencyListGraph graph;
+    private int[][] dp;
+
+    /**
+     * Constructor that initializes the graph and the DP table.
+     *
+     * @param graph The graph that represents the tree and is used for the matching algorithm.
+     */
+    public TreeMatching(UndirectedAdjacencyListGraph graph) {
+        this.graph = graph;
+        this.dp = new int[graph.size()][2];
+    }
+
+    /**
+     * Calculates the maximum weighted matching for the tree, starting from the given root node.
+     *
+     * @param root The index of the root node of the tree.
+     * @param parent The index of the parent node (used for recursion).
+     * @return The maximum weighted matching for the tree, starting from the root node.
+     *
+     */
+    public int getMaxMatching(int root, int parent) {
+        if (root < 0 || root >= graph.size()) {
+            throw new IllegalArgumentException("Invalid root: " + root);
+        }
+        maxMatching(root, parent);
+        return Math.max(dp[root][0], dp[root][1]);
+    }
+
+    /**
+     * Recursively computes the maximum weighted matching for a node, assuming that the node
+     * can either be included or excluded from the matching.
+     *
+     * @param node The index of the current node for which the matching is calculated.
+     * @param parent The index of the parent node (to avoid revisiting the parent node during recursion).
+     */
+    private void maxMatching(int node, int parent) {
+        dp[node][0] = 0;
+        dp[node][1] = 0;
+
+        int sumWithoutEdge = 0;
+        for (int adjNode : graph.getNeighbors(node)) {
+            if (adjNode == parent) {
+                continue;
+            }
+            maxMatching(adjNode, node);
+            sumWithoutEdge += Math.max(dp[adjNode][0], dp[adjNode][1]);
+        }
+
+        dp[node][0] = sumWithoutEdge;
+
+        for (int adjNode : graph.getNeighbors(node)) {
+            if (adjNode == parent) {
+                continue;
+            }
+            int weight = graph.getEdgeWeight(node, adjNode);
+            dp[node][1] = Math.max(dp[node][1], sumWithoutEdge - Math.max(dp[adjNode][0], dp[adjNode][1]) + dp[adjNode][0] + weight);
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/TreeMatchingTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/TreeMatchingTest.java
new file mode 100644
index 00000000..d5418770
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/TreeMatchingTest.java
@@ -0,0 +1,120 @@
+package com.thealgorithms.dynamicprogramming;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import com.thealgorithms.datastructures.graphs.UndirectedAdjacencyListGraph;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+class TreeMatchingTest {
+    UndirectedAdjacencyListGraph graph;
+
+    @BeforeEach
+    void setUp() {
+        graph = new UndirectedAdjacencyListGraph();
+        for (int i = 0; i < 14; i++) {
+            graph.addNode();
+        }
+    }
+
+    @Test
+    void testMaxMatchingForGeneralTree() {
+        graph.addEdge(0, 1, 20);
+        graph.addEdge(0, 2, 30);
+        graph.addEdge(1, 3, 40);
+        graph.addEdge(1, 4, 10);
+        graph.addEdge(2, 5, 20);
+        graph.addEdge(3, 6, 30);
+        graph.addEdge(3, 7, 30);
+        graph.addEdge(5, 8, 40);
+        graph.addEdge(5, 9, 10);
+
+        TreeMatching treeMatching = new TreeMatching(graph);
+        assertEquals(110, treeMatching.getMaxMatching(0, -1));
+    }
+
+    @Test
+    void testMaxMatchingForBalancedTree() {
+        graph.addEdge(0, 1, 20);
+        graph.addEdge(0, 2, 30);
+        graph.addEdge(0, 3, 40);
+        graph.addEdge(1, 4, 10);
+        graph.addEdge(1, 5, 20);
+        graph.addEdge(2, 6, 20);
+        graph.addEdge(3, 7, 30);
+        graph.addEdge(5, 8, 10);
+        graph.addEdge(5, 9, 20);
+        graph.addEdge(7, 10, 10);
+        graph.addEdge(7, 11, 10);
+        graph.addEdge(7, 12, 5);
+        TreeMatching treeMatching = new TreeMatching(graph);
+        assertEquals(100, treeMatching.getMaxMatching(0, -1));
+    }
+
+    @Test
+    void testMaxMatchingForTreeWithVariedEdgeWeights() {
+        graph.addEdge(0, 1, 20);
+        graph.addEdge(0, 2, 30);
+        graph.addEdge(0, 3, 40);
+        graph.addEdge(0, 4, 50);
+        graph.addEdge(1, 5, 20);
+        graph.addEdge(2, 6, 20);
+        graph.addEdge(3, 7, 30);
+        graph.addEdge(5, 8, 10);
+        graph.addEdge(5, 9, 20);
+        graph.addEdge(7, 10, 10);
+        graph.addEdge(4, 11, 50);
+        graph.addEdge(4, 12, 20);
+        TreeMatching treeMatching = new TreeMatching(graph);
+        assertEquals(140, treeMatching.getMaxMatching(0, -1));
+    }
+
+    @Test
+    void emptyTree() {
+        TreeMatching treeMatching = new TreeMatching(graph);
+        assertEquals(0, treeMatching.getMaxMatching(0, -1));
+    }
+
+    @Test
+    void testSingleNodeTree() {
+        UndirectedAdjacencyListGraph singleNodeGraph = new UndirectedAdjacencyListGraph();
+        singleNodeGraph.addNode();
+
+        TreeMatching treeMatching = new TreeMatching(singleNodeGraph);
+        assertEquals(0, treeMatching.getMaxMatching(0, -1));
+    }
+
+    @Test
+    void testLinearTree() {
+        graph.addEdge(0, 1, 10);
+        graph.addEdge(1, 2, 20);
+        graph.addEdge(2, 3, 30);
+        graph.addEdge(3, 4, 40);
+
+        TreeMatching treeMatching = new TreeMatching(graph);
+        assertEquals(60, treeMatching.getMaxMatching(0, -1));
+    }
+
+    @Test
+    void testStarShapedTree() {
+        graph.addEdge(0, 1, 15);
+        graph.addEdge(0, 2, 25);
+        graph.addEdge(0, 3, 35);
+        graph.addEdge(0, 4, 45);
+
+        TreeMatching treeMatching = new TreeMatching(graph);
+        assertEquals(45, treeMatching.getMaxMatching(0, -1));
+    }
+
+    @Test
+    void testUnbalancedTree() {
+        graph.addEdge(0, 1, 10);
+        graph.addEdge(0, 2, 20);
+        graph.addEdge(1, 3, 30);
+        graph.addEdge(2, 4, 40);
+        graph.addEdge(4, 5, 50);
+
+        TreeMatching treeMatching = new TreeMatching(graph);
+        assertEquals(100, treeMatching.getMaxMatching(0, -1));
+    }
+}