The data we will use for this homework is the set of adjacencies between the states making up the contiguous United States, and DC (District of Columbia). For the purpose of this homework, we will refer to DC as a state as well. For example, the adjacency "AL FL" on the first line of the file indicates that AL and FL share a boundary.

We would like to find states to host three facilities. The objective is to minimize the number of state boundaries that anyone has to cross to reach one of the facilities.

More precisely, suppose that the states hosting the three facilities are Loc1, Loc2, and Loc3. For a states St, let dist(Loc1, Loc2, Loc3, St) denote the smallest number of state boundaries that someone in St will have to cross to get to either Loc1, Loc2, or Loc3. Thus if Loc1 = WA, Loc2 = NY, and Loc3 = FL, dist(Loc1, Loc2, Loc3, OR) equals 1, because of the adjacency "OR WA". Similarly, dist(Loc1, Loc2, Loc3, CA) equals 2, because from CA we can get to WA via the adjacencies "CA OR" and "OR WA". Whereas dist(Loc1, Loc2, Loc3, GA) equals 1 because of the adjacency "FL GA". And dist(Loc1, Loc2, Loc3, IA) is considerably higher.

The goal is to find states Loc1, Loc2, and Loc3 that minimize the maximum, over all states St, of dist(Loc1, Loc2, Loc3, St).

Here are some illustrative examples if the problem description was not clear enough. (Maps courtesy

In this homework, you should write a program that reads in the adjacencies between the states and prints (a) the three optimal locations OptLoc1, OptLoc2, and OptLoc3, and (b) the following number: the maximum, over all states St, of dist(OptLoc1, OptLoc2, OptLoc3, St).

You should make the program as general as possible. Thus, you should write a function or method that takes as input an arbitrary graph representing the adjacencies, and solves and returns the answer for that graph. (You could also make the number of facilities, in this case 3, an input parameter of this function. But this is optional.) A separate piece of code should read in the adjacencies from the above file, construct the appropriate graph representation, and call the said method.

You should submit (a) a brief description of your approach to solving the problem, (b) the source code, and (c) instructions for compiling and/or running it. Look for a dropbox named Homework2 in ICON. The submission deadline is 11:59 pm on Friday, September 19.