Deliverable A program:

import java.io$.$File;

import java.io$.$FileNotFoundException;

import java.util.Scanner;

public class GraphCycle $\{$

public static void main$($String$[]$ args$)\{$

int$[][]$ distanceMatrix;

int numCities;

$//$ Step $1$: Read and Parse the File

try $\{$

File file $=$ new File$("/$Users$/$saidw$/$Desktop$/$F$1$a$.$txt$")$;

Scanner scanner $=$ new Scanner$($file$)$;

numCities $=$ scanner.nextInt$()$; $//$ Read number of cities

distanceMatrix $=$ new int$[$numCities$][$numCities$]$;

$//$ Fill the distance matrix

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

for $($int j $=0$; j $<$ numCities; j$++)\{$

distanceMatrix$[$i$][$j$]=$ scanner.nextInt$()$;

$\}$

$\}$

scanner.close$()$;

$\}$ catch $($FileNotFoundException e$)\{$

System.out.println$("$File not found."$)$;

return;

$\}$

$//$ Step $2$ and $3$: Calculate the Hamiltonian Cycle Path and Distance

int totalDistance $=0$;

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

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

System.out.print$(($i $+1)+"")$;

if $($i $<$ numCities $-1)\{$

totalDistance $+=$ distanceMatrix$[$i$][$i $+1]$;

$\}$ else $\{$

totalDistance $+=$ distanceMatrix$[$i$][0]$; $//$ Return to start

$\}$

$\}$

System.out.println$("$

Total Distance: $"+$ totalDistance$)$;

$\}$

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$\mathrm{.}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 $$prog$340$ handout describes the format of the input file for this and all program deliverables.

As will always be the case in this class, the program must be written in Java and must run on the University Windows computer systems. To ensure this I strongly recommend that you:

Use only Oracle Java SE constructs, and

Test it on the University systems before submission if you have any doubts about its ability to run on the University Windows.

Submit the Java source code to the open Deliverable B submission folder. Submit your code as an Eclipse package or submit all the $.$java$$ source files in a zipped archive, and in addition all $.$java source files as text file $($yes both ways$),$ plus screen shots proving your code runs. You need not include test files.

Algorithm:

The bitonic tour algorithm is described in the two bitonic tour papers uploaded under Program in D$2$L$.$ Use whichever algorithm you find easiest to understand $($they$$re essentially similar and will give identical results$).$

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.

~ val C D F M N S W

Chicago $41\mathrm{.}9$ ~ $1004967398473296863$

Denver $39\mathrm{.}71004$ ~ $79492411588501097$

FortWorth $32\mathrm{.}8967794$ ~ $9446636311297$

Minneapolis $45\mathrm{.}0398924944$ ~ $875557458$

Nashville $36\mathrm{.}24731158663875$ ~ $3091338$

SaintLouis $38\mathrm{.}7296850631557309$ ~ $1013$

Winnipeg $49\mathrm{.}98631097129745813381013$ ~

Yields output:

Shortest bitonic tour has distance $4015$

Tour is W M C S N F D W

$\}$