IntroductionThe goals of this homework are to:
Please keep track of how much time, in terms of number of hours, it takes you to solve each exercise, as we will ask you to provide us with this information. The total number of points for this homework is 125. Of these, 25 are bonus points that can be counted toward future milestones where you do less well. Please be mindful of the Collaboration Policy. If you have any questions regarding the assignment requirements, ask on the discussion group. If you have any doubts about whether it's appropriate to ask something, check with the course staff. You are allowed to use Web search to find answers to questions. The deadline for this homework is October 15, 2010, at 23:59. Any assignments (or parts thereof) handed in late will not be considered. Some popular features for the Campus Buddy application are related to transportation and oncampus navigation. As such, they will require the ability to search a map for possible paths to points of interest. In this homework, you will contribute toward building a first module for Campus Buddy by implementing parts of a graph search framework for finding shortest paths in graphs. The project skeleton can be downloaded here. Start by familiarizing yourself with the class structure. It is not necessary for you to try and understand every single line of code, instead try to get a good feel for the functionality of each class and how classes interact.
Exercise 1 (40 points)In this first exercise, you will design and implement an unweighted directed simple graph class. Your tasks will be:
Exercise 2 (20 points)Take a closer look at Node.java. This class implements a weighted graph node (i.e. the weight  or cost  is at the node), The cost is represented in a class named Cost.java. Explain what the valid() method in both classes does and why such a method is useful. (2pts) The cost() function in Node.java returns a Cost object instead of, say, a double. Explain why this is good practice. (2pts) Now, implement a similar valid() method for your graph and insert calls to valid() at the appropriate locations. (16pts)
Exercise 3 (10 points)In this exercise, we combine the graph implemented in exercise 1 with the weighted nodes introduced in exercise 2 in order to make a weighted simple directed graph on which to search for shortest paths. The cost of a path in a weightednode graph is the sum of the cost of the individual nodes that make up the path. The path finding algorithm implemented in PathFinder.java is able to accommodate various graph implementations and search strategies. This is done by providing the path finding algorithm with an object implementing the IGraphFacade interface (this is an example of the Facade design pattern) and with an object implementing the IGoal interface (this is an example of the Strategy design pattern  also called Policy design pattern or Specialization design pattern). Implementing a custom IGoal class allows one to modify the behavior of PathFinder so that it follows a particular search strategy. Your first task will be to create a class that implements the IGraphFacade interface, for the graph in exercise 1. (5pts) Your second task will be to provide an implementation for the IGoal interface that can be used to make the path finder behave as Dijkstra's Algorithm. Warning: we are considering a graph with weighted nodes (not weighted edges!), but the algorithm follows the same idea as the weightededge version, i.e. explore a collection of potential paths in a lowestcostfirst order. (5pts) You are encouraged to test your implementation.
Exercise 4 (15 points)In this exercise and the next, we move away from abstract mathematical graphs to concrete twodimensional plane graphs. In such a graph, nodes are placed on the plane with x and y coordinates and an edge between two nodes is a straight line. This time, however, the cost of traveling between two nodes is the Euclidean distance (i.e. the length of the straight line between the two). You will implement a path finding module, which allows one to find the shortest path between two points in a twodimensional graph. Since we are considering a new problem setting, you will need to adapt parts of our existing framework to account for the new reality. First, you will need to implement another Node class, called GeoNode, which takes into consideration x and y coordinates. (10pts) You will then need to implement a GeoNode cost evaluator (see ICostEvaluator.java) so that the NodePath implementation can correctly compute the cost of a GeoNode path. The cost of a GeoNode path is the sum of the distances between two adjacent nodes in that path. (5pts)
Exercise 5 (15 points)
While Dijkstra's Algorithm works very well for a variety of problems, it often requires exploration of a large portion of the graph, in order to find a solution. This can become a problem if the graph in question is very large. Fortunately, there exists an extension to Dijkstra's Algorithm, the A* algorithm, which, given a lower bound on the distance to the goal node (this lower bound is an estimate called a heuristic), offers better performance and is better suited for some problems. In this exercise, you will make use of A* to solve one such problem.In this exercise, you are asked to provide an implementation for the IGoal interface that will make PathFinder behave like the A* algorithm. This goal must be able to accommodate various heuristics. (10pts) Then, you will use this Goal class to implement two wellknown heuristics for 2D path finding:
Note that for A*, you will use these heuristics to compute the distance between a node and a goal node. You are encouraged to test your implementation. Note that even though you are not explicitly required in this exercise to think about your design and write pseudocode before actually implementing the functionality, it is strongly recommended!
Bonus exercise (25 points)
You will now get the chance to apply your new path finding algorithm to a real scenario. Alice got separated from her boyfriend, Bob, on campus. She's trying to find him. Unfortunately, Bob banged his head and is moving around the whole campus randomly. Implement, in a class called FindingBob.java, the above scenario on a 2D graph with at least 20 GeoNodes. Here are the detailed parameters:
Deliverables for Homework #2To hand in your assignments, you will use your SVN account. Below, SVNAccount stands for the actual path to your SVN account (e.g., https://svn.epfl.ch/svn/sweng2010candea).
Frequently Asked QuestionsQ: I'm not sure I understand question 1.3. I'm not sure I understand this question. Do we have to name the methods (from the interface we just created) we can "hide" ? Or do we have to talk about the data in general (not only methods) ? Could you explain this a little bit more ?A: The point of this question is to make you think twice before exposing the internal workings of your class through your interface. A quick example of such bad design would be the following: public class Person { // Should not be modified! private final Date birthday_; ... public Date birthday() { return birthday_; } } The birthday() method returns the same Date object used internally (maybe for other purposes). Now, consider what happens if a user of this class does something like that: Person p = new Person(...); Date birthday = p.birthday(); ... birthday.setYear(2233); // !! Obviously, this is just a (simple) example of the many things that could go wrong if one isn't extracareful with exposing internal representation. In this question, you are asked to think of specific examples of things that could go wrong (so that you may avoid these problems in your implementation). ***
Q: When we are dealing with abstract objects like graphs to do reusable classes, can we assume that the caller of our class knows what the constraints of this object are and that he won't try to use this class to solve his problem if he knows that his problem doesn't respect one of these constraints? Can we deny operations such as adding two identical vertices. A: The specification for your graph interface is that it corresponds to a simple directed unweighted graph (not a simple graph, not a graph, not a multigraph!). That interface represents a contract between users of that interface and implementing classes. To respond more specifically to your example: yes, you must protect yourself against someone trying to create two identical vertices in the same graph. Note that this is just one example of the things your graph implementation must not allow... ***
Q: What if someone adds an object to our class and mutates it afterwards? Is this a lack of robustness of our code? If yes, is there a good way to block this in the generic class? A: This is a very good question!
***
Q: What purpose has the public method Cost distanceFrom(GeoNode srcNode)? A: This method was meant as a hint for you to implement the compare method.
However, since it seems to be confusing many of you, we'll make
implementing it optional.
If you don't want to implement this method, please use the following
dummy implementation: public Cost distanceFrom(N src) {
