#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

struct Place $\{$

int index;

string name;

double x$,$ y;

$\}$;

struct Edge $\{$

int from, to;

double weight;

bool operator$>($const Edge& other$)$ const $\{$

return weight $>$ other.weight;

$\}$

$\}$;

double calculateDistance$($const Place& a$,$ const Place& b$)\{$

return sqrt$($pow$($a$.$x $-$ b$.$x$,2)+$ pow$($a$.$y $-$ b$.$y$,2))$;

$\}$

vector split$($const string &s$,$ char delimiter$)\{$

vector tokens;

string token;

istringstream tokenStream$($s$)$;

while $($getline$($tokenStream$,$ token, delimiter$))\{$

tokens.push$\_$back$($token$)$;

$\}$

return tokens;

$\}$

vector readPlacesFromFile$($const string& filename$)\{$

ifstream file$($filename$)$;

vector places;

string line;

int index $=0$;

while $($getline$($file$,$ line$))\{$

vector tokens $=$ split$($line$,\text{'},\text{'})$;

if $($tokens$.$size$()==3)\{$

Place place;

place.index $=$ index$++$;

place.name $=$ tokens$[0]$;

place.x $=$ stod$($tokens$[1])$;

place.y $=$ stod$($tokens$[2])$;

places.push$\_$back$($place$)$;

$\}$

$\}$

return places;

$\}$

void printPlaces$($const vector& places$)\{$

for $($const auto& place : places$)\{$

cout $$ "Index: $"$ place.index Name: $"$ place.name X: $"$ place.x Y: $"$ place.y $$ endl;

$\}$

$\}$

vector tspBruteForce$($const vector& places$)\{$

$//$ Your implementation goes here

$\}$

vector tspPrimApproximation$($const vector& places$)\{$

$//$ your implementation goes here

$\}$

int main$()\{$

string filename;

vector places;

ifstream file;

cout $$ "Enter the filename: $"$;

cin $>>$ filename;

file.open$($filename$)$;

if $(!$file$)\{$

cout $$ "File not found. Please try again." $$ endl;

return $1$;

$\}$

string line;

int index $=0$;

while $($getline$($file$,$ line$))\{$

vector tokens $=$ split$($line$,\text{'},\text{'})$;

if $($tokens$.$size$()==4)\{$

Place place;

place.index $=$ index$++$;

place.name $=$ tokens$[1]$;

place.x $=$ stod$($tokens$[2])$;

place.y $=$ stod$($tokens$[3])$;

places.push$\_$back$($place$)$;

$\}$

$\}$

file.close$()$;

printPlaces$($places$)$;

cin.ignore$($numeric$\_$limits::max$(),\text{'}$

$\text{'})$;

int startIndex;

cout $$ "Enter the index of the starting city: $"$;

cin $>>$ startIndex;

if $($startIndex $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ startIndex $>=$ places.size$())\{$

cout $$ "Invalid index for starting city." $$ endl;

return $1$;

$\}$

cin.ignore$($numeric$\_$limits::max$(),\text{'}$

$\text{'})$;

string indicesList;

cout $$ "Enter the indices of the cities you wish to visit, separated by commas $($do not include the starting city$)$: $"$;

getline$($cin$,$ indicesList$)$;

vector indicesToVisit $=$ split$($indicesList$,\text{'},\text{'})$;

unordered$\_$set selectedIndices;

vector selectedPlaces;

selectedIndices.insert$($startIndex$)$;

cout $$ "Starting City: $"$ places$[$startIndex$].$name $$ endl;

for $($const auto& indexStr : indicesToVisit$)\{$

int index $=$ stoi$($indexStr$)$;

if $($index $==$ startIndex$)\{$

cout $$ "Note: The starting city $($Index: $"$ startIndex was included in the visit list and will be ignored." $$ endl;

continue;

$\}$

if $($index $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ index $>=$ places.size$())\{$

cout $$ "Invalid index: $"$ index This city will be ignored." $$ endl;

continue;

$\}$

if $($selectedIndices$.$count$($index$)>0)\{$

cout $$ "Duplicate index: $"$ index This city will be ignored." $$ endl;

continue;

$\}$

selectedIndices.insert$($index$)$;

selectedPlaces.push$\_$back$($places$[$index$])$;

$\}$

cout $$ "Cities to Visit:" $$ endl;

for $($const auto& place : selectedPlaces$)\{$

cout $$ "Index: $"$ place.index Name: $"$ place.name X: $"$ place.x Y: $"$ place.y $$ endl;

$\}$

$//$Modify main below this point to print out the paths traveled for both TSP brute and approx

return $0$;

$\}$