Goals

This assignment aims to help you:

● Practice graphs

● Try greedy algorithms

In this assignment we begin our systematic study of algorithms and algorithm patterns.

Reading

● Graphs (K&T, chapter 3, S&W Chapter 4.1-4.2)

● Greedy algorithms (K&T chapter 4, S&W Chapter 4.4)

Advice

Before writing the code try to run a small example on paper.  Think what you would do if you were given the set of instructions or hints and had to do it without a computer. Then start programming. It is always advisable, but especially important in this programming assignment. This assignment is about 80% reading, 20% coding...

Questions

1.

2.  Graphs (Loosely based on the ”small world phenomenon” exercise from S&W, see here: http://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/bacon.html.

Briefly, the assignment asks you to read in a file containing information about films and actors, and find the Bacon number (or whoever is the center of the universe) of an actor given as a parameter. Your task is to write a class named DegreesOfSeparationBFS that builds a shortest paths graph from a center, say Kevin Bacon (or any other actor) based on a SymbolGraph read from a file. Then it can take an actor’s name and produces this actor’s Bacon number and the shortest path to Kevin Bacon

(or whoever the center is). The name format is “Last, First” . So for an input of:

"Kidman,  Nicole"

It has to calculate Nicole Kidman’s Bacon number (2) and the path in the graph:

Kidman,  Nicole  ->  My  Life  (1993  I)  with  de  Sosa,  Ruth  ->  Planes,  Trains  &  Automobiles  (1987) with  Bacon,  Kevin

You may use the DegreesOfSeparation class for ideas (see S&W code).

Make sure that you understand the SymbolGraph class very well before you start coding. An illustration appears in the Undirected Graphs class notes.

Notice that the original assignment asks you to calculate a histogram, but the part that writes the histogram is already implemented by S&W:                                                                                                https://algs4.cs.princeton.edu/41graph/BaconHistogram.java.html.

Therefore, it is not going to be tested as part of my test suite, but you should print out the histogram to your memo.txt file (see below).  The original assignment has you read the actor names from the standard input but this is not what you have to do here.

Specific Instructions:

● The DegreesOfSeparationBFS class has two class variables: a SymbolGraph and a BreadthFirstPaths, with the appropriate getters called getSymbolGraph() and getBreadthFirstPaths()  (Don’t        forget the getters!  I need them!).

● You should be able to instantiate it, so the constructor has to be public. The constructor gets three

Strings: a File name, a delimiter and a source. For example: DegreesOfSeparationBFS("movies.txt", "/"  ,"Bacon,  Kevin"). Notice the name format is Last, First. The constructor builds the symbol           graph and calculates the distance.

● In addition to the getters, the class should implement the following functions (at least.  You can add more as you see fit):

–  int  baconNumber(String  sink).  This function gets a String in the format ”Last, First” (for example ”Kidman, Nicole”) and calculates the actor’s beacon number.  In the case of Nicole Kidman it should return 2. If the actor is not in the database or there is no path from the center to it, it should return -1.

–  Stack<Integer>  graphPath(String  sink).  This function calculates the path itself.  Nor- mally I would advise you to do both in one function (the Bacon number and the path) but it makes my grading easier... Notice that the Stack<Integer> holds the indices of the vertices on the path. Look at the algs4 implementation of paths.

– I suggest you also add functions for printing the path for debugging purposes but I won’t test them.

● The command line parameters should be at least the following three: The input movie file name,    the separator and the ”center” (Kevin Bacon in the example but you should not hard code it.    The center can be any actor). Additional optional command line parameters will be actor names    whose Bacon number we want to test. So, for example, you should run your function as follows:      DegreesOfSeparationBFS movies.txt  "/"  "Bacon,  Kevin",  "Kidman,  Nicole",  "Nicholson, Jack"

3.  A* For Euclidean  Graphs:  This question is based on the Map Routing exercise from S&W, see here: http://www.cs.princeton.edu/courses/archive/spring04/cos226/assignments/map.html. A* is an extension of Dijkstra’s algorithm that, in addition to the graph distances, uses heuristics to guide the search. A heuristic in general is a technique that may speed up an algorithm based on some properties of the problem.

In the general Dijkstra’s algorithm, we select the node that has the minimum distance from the start and that is still in the priority queue.  We can define a function g(n) whose value for every node n is that distance, and thus say that Dijkstra’s algorithm minimizes that function at every stage of its run. This is just another (more mathematical) way to describe what Dijkstra’s algorithm does.  It selects, at every stage, the minimum yet-to-be-processed vertex through the use of priority queues.

In this problem we compute for each query the shortest path between a start node s and a goal t, not between s and everything, so the goal is well defined.  Dijkstra’s algorithm doesn’t take into account where the goal node is, so it may spend a lot of time on nodes that take you in the opposite direction. A* adds another function h(n) that estimates the cost required to extend the path all the way to the goal node and prioritizes nodes that take us closer. At every stage of the algorithm, the path we extend minimizes f (n) = g(n) + h(n).  Notice that if h(n) is 0, this is simply Dijkstra’s algorithm.  It can be shown that if the heuristic function never overestimates the actual cost to get to the goal, A* is guaranteed to return a shortest path from start to goal, and often much faster than Dijkstra’s.

The question requires you to use A* on maps, or graphs whose vertices are points in the plane and are connected by edges whose weights are Euclidean distances. Think of the vertices as cities and the edges

as roads connected to them. See an example in the description of the exercise. In this case, a heuristic that is guaranteed to give the shortest paths is to use h(n) = dist(n, t) where t is the goal. The reason why it works is that in a Euclidean graph (where the nodes represent geographical locations and the edges between the nodes represent distances), a straight line is the shortest possible distance between two points (it is not necessarily true in general graphs!).  Therefore, h(n) is the lowest bound on the remaining distance (graph distance) between n and t (it certainly can’t be less than that!).

So, to speed up the search, we store the vertices in the priority queue just like in Dijkstra’s algorithm, only that the priority for each vertex n is now:  wt(n) + dist(n, t) where wt(n) is the weight of the shortest path from s to n on the graph and dist(n, t) is the Euclidean distance between n and t. Notice that we initialize wt(s) = dist(s, t) and not 0. Given that, we can stop the search as soon as t is added to the queue. When we reach t we know that there is no shorter path in the graph.

Using the straight line distances as the heuristic is the same as re-weighting the graph such that for each edge (u, v) with weight w, the edge weight is now w + dist(v, t) · dist(u, t).  From here you can run Dijkstra’s algorithm as usual. Notice that due to the Euclidean distance property, the weights are still guaranteed to be positive and as we travel along any path from s to t, the Euclidean distances cancel out, and since dist(t, t) = 0, the search will eventually output the correct distance on the map for every path.

For the question itself, please implement ideas 1 and 2 in the instructions. That is – in each query only calculate the shortest paths until the destination is reached and reset the data structures so that only vertices and edges that participated in the search are reset, and use the A* heuristic described above

(don’t implement multiway heap etc. Just use a variant of Dijkstra’s algorithm in algs4). Specifically, implement the following:

● A class called EuclideanGraph.

You can use ideas from a file (older version of algs4) which you can import by typing: wget  -nd  ftp://ftp.cs.princeton.edu/pub/cs226/map/EuclideanGraph.java

This implementation is not fully compatible with algs4 so you will have to modify it.  Look at the code for various graph types in algs4.  Use Point2D for the coordinates.  It already has the Euclidean distance method.

● A class called AStar that implements the A* search as described above, on Euclidean graphs. You can start from Dijkstra’s implementation provided by algs4, but you will have to modify it, of course.  Remember these are undirected graphs.  This class has a main function which runs as follows:

java  -cp  .:../lib/algs4.jar  pa2.AStar  <file1>  <file  2>  <integer>

The first argument is a file containing the Euclidean graph description as mentioned above.  The second graph is a file containing pairs of source and end vertices within the graph.  The third argument is a flag that sets the heuristics.  If its value is 0, your program should implement the regular Dijkstra’s algorithm.  Otherwise it should implement A*.  Your class should run over all the pairs and calculate the shortest path for every pair.  An example of a large map file can be found as a handout – usa.txt.

So, for example, you can run your program as:

java  -cp  .:../lib/algs4.jar  pa2.AStar  usa.txt  usa-2paths.txt  1

You should process two paths – 56011  -  56066 and 0  -  5000 with  1,717 and  17,132 edges processed, respectively. Running:

java  -cp  .:../lib/algs4.jar  pa2.AStar  usa.txt  usa-2paths.txt  0

(That is, original Dijkstra’s) should give you the same distances and paths but with 21,423 and 83,109 edges processed, respectively.

Your main function should be able to time your run (for the questions below).  You can use the following trick. In your AStar main function, before you run your queries, do:

long  startTime  =  System.currentTimeMillis();

After you finish, do:

long  endTime  =  System.currentTimeMillis();

The difference between the two is the time it takes all the queries to run.