This is the code for deliverable A:

import java.io$.*$;

import java.util.$*$;

$//$ Class DelivA does the work for deliverable DelivA of the Prog$340$

public class DelivA $\{$

File inputFile;

File outputFile;

PrintWriter output;

Graph g;

public DelivA$($ File in$,$ Graph gr $)\{$

inputFile $=$ in;

g $=$ gr;

$//$ Get output file name.

String inputFileName $=$ inputFile.toString$()$;

String baseFileName $=$ inputFileName.substring$(0,$ inputFileName.length$()-4)$; $//$ Strip off $".$txt$"$

String outputFileName $=$ baseFileName.concat$("\_$out.txt$")$;

outputFile $=$ new File$($ outputFileName $)$;

if $($ outputFile.exists$())\{//$ For retests

outputFile.delete$()$;

$\}$

try $\{$

output $=$ new PrintWriter$($outputFile$)$;

$\}$

catch $($Exception x $)\{$

System.err.format$("$Exception: $\%$s$\%$n$",$ x$)$;

System.exit$(0)$;

$\}$

$/*$

$*$ Design of solution:

$*1.$ Sort the cities by value $($using Arrays.sort$().$ This sounds like a general thing to do$,$ so I'll do it in the Node class.

$*2.$ Go from city to city until done, then go back to the first city.

$*3.$ Print the distance.

$*/$

Collections.sort$($ g$.$getNodeList$(),$ new Comparator$()\{$

@Override

public int compare$($ Node n$1,$ Node n$2)\{$

return Integer.valueOf$($ n$1.$getVal$()).$compareTo$($ Integer.valueOf$($ n$2.$getVal$()))$;

$\}$

$\})$;

int totalDist $=0$;

System.out.print$($ "Path $")$; output.print$($ "Path $")$;

for $($ Node n : g$.$getNodeList$())\{$

System.out.print$($ n$.$getAbbrev$()+"")$; output.print$($ n$.$getAbbrev$()+"")$;

$\}$

System.out.print$($ g$.$getNodeList$().$get$(0).$getAbbrev$()+"")$; output.print$($ g$.$getNodeList$().$get$(0).$getAbbrev$()+"")$;

int s $=$ g$.$getNodeList$().$size$()$;

for $($ int i $=0$; i $$ s; i$++)\{$

Node t $=$ g$.$getNodeList$().$get$($ i $)$;

Node h;

if $($ i $==($s$-1))\{$

h $=$ g$.$getNodeList$().$get$(0)$;

$\}$

else $\{$

h $=$ g$.$getNodeList$().$get$($ i$+1)$;

$\}$

Edge e $=$ t$.$findEdgeTo$($ h $)$; $//$ Complete graph, we know it exists.

totalDist $+=$ e$.$getDist$()$;

$\}$

System.out.println$($ "has distance $"+$ totalDist $)$; output.println$($ "has distance $"+$ totalDist $)$;

$//$System$.$out.println$($ "DelivA: To be implemented"$)$;

$//$output$.$println$($ "DelivA: To be implemented"$)$;

output.flush$()$;

$\}$

$\}$

Based off of this, Start with your $($ideally working$)$ submission of Deliverable A$.$ Read a file of the name $$F$[]$b$.$txt$.$ This is a file of distances between cities in which the value of each city is a floating point number that lists either the latitude or longitude of each city.

$$

Using the algorithm one $($or both$)$ of the papers on bitonic tours that is in D$2$L $($BitonicTour Paper Reference One and$/$or BitonicTour Paper Reference Two$),$ find the shortest bitonic tour going from the highest value to the lowest value, then back to the highest value for each set of cities.$[1]$

A bitonic tour is a Traveling Salesperson Tour $($Deliverable A was a Traveling Salesperson problem where you start at a given city, visit every other city in order exactly once and go back home$).$ Deliverable B is a more complex Traveling Salesperson Tour in which you start with a city at one end $($say most northerly or westerly$),$ go in one direction south$/$east to the most southerly$/$easterly city $($maybe visiting cities along the way$),$ and return home visiting every unvisited city south$-$to$-$north$/$east$-$to$-$west on the way back.

$$

The output should look like the photo attached. Thank you!

Output:

The input will be a table of distances representing a graph, like the one below. The largest graph I will test with will have $49$ cities.

Yields output:

Shortest bitonic tour has distance $4015$

Tour is W M C S N F D W