Skip to content

feat: add Traveling Salesman Problem implementation #6205

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 13 commits into from
Mar 31, 2025
Merged

feat: add Traveling Salesman Problem implementation #6205

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
13 commits
Select commit Hold shift + click to select a range
4c53d06
Implement solution for Constrained Shortest Path Problem (CSPP) with …
DenizAltunkapan Jan 27, 2025
100ba51
Fix issues to make the project build successfully and rename files
DenizAltunkapan Jan 27, 2025
e5b1527
Merge branch 'master' into master
DenizAltunkapan Jan 27, 2025
ce61a94
Merge remote-tracking branch 'upstream/master'
DenizAltunkapan Feb 28, 2025
fb3ba56
add dp solution for maximum weighted matching in a tree
DenizAltunkapan Feb 28, 2025
02d4cb0
Formatted code using clang-format to ensure consistent styling
DenizAltunkapan Feb 28, 2025
834850e
Fix method name to follow Java naming conventions (MaxMatching → maxM…
DenizAltunkapan Feb 28, 2025
b071a9e
add Traveling Salesman Problem implementation
DenizAltunkapan Mar 31, 2025
88e5f7b
Merge branch 'master' of https://github.com/DenizAltunkapan/Java
DenizAltunkapan Mar 31, 2025
7a5ce9c
resolve Checkstyle errors (constructor + imports)
DenizAltunkapan Mar 31, 2025
fad634f
clang-Format #6205
DenizAltunkapan Mar 31, 2025
22071c6
declare TravelingSalesman as final
DenizAltunkapan Mar 31, 2025
9995922
Merge branch 'master' into master
siriak Mar 31, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Formatted code using clang-format to ensure consistent styling
  • Loading branch information
@DenizAltunkapan
DenizAltunkapan committed Feb 28, 2025
commit 02d4cb0dc6f196ef484d9f7cd19db4304b24e3ae
12 changes: 5 additions & 7 deletions src/main/java/com/thealgorithms/dynamicprogramming/TreeMatching.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -37,12 +37,12 @@ public TreeMatching(UndirectedAdjacencyListGraph graph) {
* @return The maximum weighted matching for the tree, starting from the root node.
*
*/
public int getMaxMatching(int root, int parent){
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]);
return Math.max(dp[root][0], dp[root][1]);
}

/**
Expand All @@ -58,7 +58,7 @@ private void MaxMatching(int node, int parent) {

int sumWithoutEdge = 0;
for (int adjNode : graph.getNeighbors(node)) {
if (adjNode == parent){
if (adjNode == parent) {
continue;
}
MaxMatching(adjNode, node);
Expand All @@ -68,13 +68,11 @@ private void MaxMatching(int node, int parent) {
dp[node][0] = sumWithoutEdge;

for (int adjNode : graph.getNeighbors(node)) {
if (adjNode == parent){
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);
dp[node][1] = Math.max(dp[node][1], sumWithoutEdge - Math.max(dp[adjNode][0], dp[adjNode][1]) + dp[adjNode][0] + weight);
}
}

}
14 changes: 7 additions & 7 deletions src/test/java/com/thealgorithms/dynamicprogramming/TreeMatchingTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,9 +1,10 @@
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;
import com.thealgorithms.datastructures.graphs.UndirectedAdjacencyListGraph;
import static org.junit.jupiter.api.Assertions.assertEquals;

class TreeMatchingTest {
UndirectedAdjacencyListGraph graph;
Expand All @@ -29,7 +30,7 @@ void testMaxMatchingForGeneralTree() {
graph.addEdge(5, 9, 10);

TreeMatching treeMatching = new TreeMatching(graph);
assertEquals(110,treeMatching.getMaxMatching(0,-1));
assertEquals(110, treeMatching.getMaxMatching(0, -1));
}

@Test
Expand All @@ -47,7 +48,7 @@ void testMaxMatchingForBalancedTree() {
graph.addEdge(7, 11, 10);
graph.addEdge(7, 12, 5);
TreeMatching treeMatching = new TreeMatching(graph);
assertEquals(100,treeMatching.getMaxMatching(0,-1));
assertEquals(100, treeMatching.getMaxMatching(0, -1));
}

@Test
Expand All @@ -65,13 +66,13 @@ void testMaxMatchingForTreeWithVariedEdgeWeights() {
graph.addEdge(4, 11, 50);
graph.addEdge(4, 12, 20);
TreeMatching treeMatching = new TreeMatching(graph);
assertEquals(140,treeMatching.getMaxMatching(0,-1));
assertEquals(140, treeMatching.getMaxMatching(0, -1));
}

@Test
void emptyTree() {
TreeMatching treeMatching = new TreeMatching(graph);
assertEquals(0,treeMatching.getMaxMatching(0,-1));
assertEquals(0, treeMatching.getMaxMatching(0, -1));
}

@Test
Expand Down Expand Up @@ -116,5 +117,4 @@ void testUnbalancedTree() {
TreeMatching treeMatching = new TreeMatching(graph);
assertEquals(100, treeMatching.getMaxMatching(0, -1));
}

}
Loading