Assignment 4: Advanced Tour Algorithms & Route Optimization

This project extends the custom-built singly linked list from the previous assignment, transforming it into a powerful tool for complex data manipulation and algorithmic problem-solving. It introduces a suite of advanced methods for comparing, combining, and filtering tours, highlighted by the implementation of a route-optimization algorithm.

Core Functionality & Algorithms

This implementation adds several high-level capabilities to the Tour class:

• Shortest Tour Calculation (createShortestTour): Implements a greedy algorithm known as the Nearest Neighbor heuristic to find an efficient path for the Traveling Salesperson Problem (TSP). It starts at a specified waypoint and iteratively adds the closest unvisited point until all waypoints are in the new tour.

• Set-Based Operations:

  • createPopularTour: Performs a set intersection, returning a new tour containing only the waypoints common to two different tours.
  • createTourWithoutDuplicates: Creates a tour with unique waypoints by removing any duplicates from the original tour.
  • createUnion: Performs a set union by combining two tours, removing duplicates, and then running the shortest tour algorithm on the result.

• Structural Manipulation:

  • copy: Creates a safe, deep copy of a tour, ensuring the original tour remains unchanged.
  • createConcatenatedTour: Appends one tour to the end of another.
  • createTourWithOrder: Builds a new tour by arranging waypoints in a custom order specified by an array of indices.

Code Architecture

The project retains the robust three-class architecture:

• Waypoint.java: The immutable data object representing a 2D coordinate.
• TourElement.java: The recursive node of the list, where most of the traversal and manipulation logic resides.
• Tour.java: The high-level manager class that provides a clean public API and orchestrates the complex operations, delegating the work to the TourElement chain.

How to Run the Tests

This project's functionality is verified through a comprehensive JUnit test suite. The easiest way to run the tests is within an IDE.

1. Open the project in an IDE like IntelliJ IDEA or Eclipse.
2. Navigate to the test source folder.
3. Right-click on a specific test file (e.g., PubTourTest4.java) or the entire test directory and select "Run Tests". The IDE will compile the project and display the results, confirming that all algorithms and edge cases are handled correctly.