Arbitrario

Easily solve combinatoric optimization problems

Version: 1.5

A cross-platform application for solving the Travelling Salesman Problem (TSP) using multiple algorithm implementations. The TSP is a classic combinatorial optimization problem: given a set of cities and distances between them, find the shortest possible route that visits each city exactly once and returns to the starting city.

---

What's inside?

• 3 implementations of the Travelling Salesman Problem (@dag4202)
  • Optimal TSP - Brute force with permutations (exact solution)
  • Greedy TSP - Minimum spanning tree with union-find (approximation)
  • MST TSP - Prim's algorithm with preorder traversal (approximation)
• CLI mode
  • JCommander for command-line argument parsing
• GUI mode
  • JavaFX framework with MVC architecture
• Configuration
  • Properties file for max vertices, algorithm settings, and logging
• Cross-platform JAR - Single executable for Windows, macOS, and Linux

---

Project Structure

arbitrario/
├── src/
│   ├── main/java/nau/arbitrario/
│   │   ├── Main.java                    # Entry point
│   │   ├── Launcher.java                # CLI/GUI router
│   │   ├── Settings.java                # Configuration singleton
│   │   ├── Util.java                    # File I/O utilities
│   │   ├── cli/
│   │   │   ├── ArbitrarioCLI.java       # Interactive CLI
│   │   │   ├── CommandParser.java       # JCommander definitions
│   │   │   └── CorrectAlgorithm.java    # Algorithm validator
│   │   ├── gui/
│   │   │   ├── ArbitrarioGUI.java       # JavaFX application
│   │   │   ├── controller/
│   │   │   │   ├── MainController.java  # Main window logic
│   │   │   │   └── HelpController.java  # Help dialog logic
│   │   │   └── model/
│   │   │       └── MainModel.java       # GUI data model
│   │   └── travelling_salesman/
│   │       ├── Graph.java               # Graph representation
│   │       ├── Edge.java                # Edge data structure
│   │       ├── Vertex.java              # Vertex data structure
│   │       ├── OptimalTSP.java          # Brute force algorithm
│   │       ├── GreedyTSP.java           # Greedy approximation
│   │       └── MstTSP.java              # MST approximation
│   ├── main/resources/
│   │   ├── config.properties            # Application settings
│   │   └── fxml/                        # JavaFX layouts
│   └── test/java/nau/arbitrario/        # Unit tests
├── pom.xml                              # Maven configuration
├── LICENSE                              # MIT License
└── README.md

---

Requirements

• Java 8 or higher (JDK 1.8+)
• Maven 3.x (for building from source)
• JavaFX (included in JDK 8, separate module in JDK 11+)

Dependencies (managed by Maven)

Dependency	Version	Purpose
jcommander	1.58	Command-line argument parsing
junit	4.12	Unit testing
mockito-all	1.9.5	Test mocking
jsr305	3.0.0	Nullability annotations

---

Installation

Download Pre-built JAR

Download here: version 1.5 (current)

Build from Source

# Clone the repository
git clone https://github.com/your-repo/arbitrario.git
cd arbitrario

# Build with Maven
mvn clean package

# The executable JAR will be at:
# target/magma.one-jar.jar

---

Usage

Launch GUI Mode

java -jar magma.one-jar.jar --gui

Or simply (defaults to interactive CLI):

java -jar magma.one-jar.jar

CLI with Options

# Run Optimal TSP algorithm
java -jar magma.one-jar.jar -al 1

# Run Greedy TSP algorithm with file import
java -jar magma.one-jar.jar -al 2 -i input.txt

# Run MST TSP algorithm
java -jar magma.one-jar.jar -al 3

Command-line Options

Option	Description
--algorithm, -al <number>	Specify algorithm (1=Optimal, 2=Greedy, 3=MST)
--gui	Launch graphical interface
--import, -i <file>	Import graph data from file
--help, --usage	Display help message

Example CLI Session

$ java -jar magma.one-jar.jar -al 1

Enter number of vertices (max 13): 5

Generated graph with 5 vertices.

Running Optimal TSP...

Result:
Path: 0 -> 3 -> 1 -> 4 -> 2 -> 0
Total distance: 247.83

Input File Format

HEADER INFO (ignored)
DATA
0 1 10.5
0 2 15.3
1 2 12.0
...
EOF

---

Algorithms

1. Optimal TSP (Brute Force)

Generates all permutations of vertices and computes the total distance for each possible tour. Guarantees the optimal solution.

• Time Complexity: O((N-1)! × N)
• Use Case: Small graphs (N ≤ 13)
• Guarantee: Exact optimal solution

Algorithm:
1. Generate initial permutation [1, 2, ..., N-1]
2. For each permutation:
   - Calculate total path distance through all vertices
   - Track minimum distance and corresponding path
3. Return best path found

2. Greedy TSP (Edge-based Approximation)

Sorts all edges by weight and builds a Hamiltonian path by greedily selecting the shortest edges while avoiding cycles and ensuring each vertex has at most 2 connections.

• Time Complexity: O(E log E) where E = N(N-1)/2
• Use Case: Medium graphs (N ≤ 100)
• Guarantee: Approximation (typically within 25% of optimal)

Algorithm:
1. Sort all edges by weight (ascending)
2. For each edge in sorted order:
   - If adding edge doesn't create cycle (union-find)
   - And neither vertex has 2 edges yet
   - Add edge to tour
3. Perform DFS to extract path

3. MST TSP (Prim's Algorithm)

Constructs a Minimum Spanning Tree using Prim's algorithm, then performs a preorder DFS traversal to create the tour.

• Time Complexity: O(N²) for dense graphs
• Use Case: Large graphs (N > 100)
• Guarantee: Within 2× optimal for metric TSP

Algorithm:
1. Build MST using Prim's algorithm with priority queue
2. Start from vertex 0
3. Perform preorder DFS traversal of MST
4. Return vertices in order visited

---

Class Documentation

Core Data Structures

Class	Description	Key Methods
Graph	Completely connected euclidean graph	getWeight(), DFS(), updateGraph(), getVertices()
Edge	Edge between two vertices	compareTo() for sorting by weight
Vertex	Vertex with parent tracking for MST	compareTo() for priority queue

TSP Algorithm Classes

Class	Algorithm	Key Methods
OptimalTSP	Brute force permutation	solveGraph(), nextPermutation(), computeDistance()
GreedyTSP	Edge-based greedy	solveGraph(), nested Quick (sort), UnionFind (cycle detection)
MstTSP	Prim's MST + DFS	solveGraph(), nested PriorityQueue (min-heap)

GUI Components

Class	Purpose	Key Methods
ArbitrarioGUI	JavaFX application launcher	start()
MainController	Main window MVC controller	handleSolveProblem(), handleSelectFileButton()
HelpController	Help dialog controller	showHelp()
MainModel	Observable data model	JavaFX properties for binding

CLI Components

Class	Purpose	Key Methods
ArbitrarioCLI	Interactive command-line	run(), getData(), getProblemDataFromConsole()
CommandParser	JCommander parameters	Fields: gui, algorithm, importFilePath
CorrectAlgorithm	Parameter validator	validate()

Utilities

Class	Purpose	Key Methods
Launcher	Routes to CLI or GUI	launch()
Settings	Configuration singleton	getInstance(), getMaxVertices()
Util	File I/O helpers	getProblemDataFromFilePath()

---

Configuration

Edit src/main/resources/config.properties:

# Maximum number of vertices (limited for Optimal TSP)
main.max_vertices = 13

# Available algorithms
main.algorithms = Optimal TSP, Greedy TSP, Mst TSP

# Validation range
validator.max_algorithm_number = 3

---

TODOs

• Extended test coverage (JUnit + TestFX)
• Add fourth algorithm implementation
• Platform-specific packages (installers)
• File export functionality
• Graph visualization

---

License

This project is licensed under the MIT License - see the LICENSE file for details.

---

Acknowledgments

• Algorithm implementations - @dag4202
• Icons - @NeonProject and Icons8