Archive‎ > ‎2010‎ > ‎Assignments‎ > ‎

Homework #2

Introduction

The goals of this homework are to:
  • give you a feel for how to properly design object-oriented software,
  • help you get some confidence working with multiple classes, and
  • allow you to (re)familiarize yourself with the concepts of inheritance, containment, and specialization

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 on-campus 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:
  1. List all the methods you think such a graph implementation needs and describe their functionality. (4pts)
  2. Write a generic interface, in a file called IGraph.java, that will specify the contract such a graph implementation has to fulfill. (4pts)
  3. As you were taught in class, a class should not expose its internal workings, because it creates unnecessary coupling. What is the information your IGraph interface should not expose? Think about the fact that everything you provide as functionality, in terms of methods, can be used against your class. (4pts)
  4. Describe two possible internal representations for the graph and briefly explain how they work. (4pts)
  5. Choose an internal representation and explain your choice. (4pts)
  6. For each method in the IGraph interface, write pseudocode implementing the method. (10pts)
  7. Finally, implement the IGraph interface, in a file called Graph.java. Your graph implementation must be generic. Design for robustness and reuse! (10pts)

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 weighted-node 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 weighted-edge version, i.e. explore a collection of potential paths in a lowest-cost-first 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 two-dimensional 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 two-dimensional 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 well-known heuristics for 2D path finding:

  • The Euclidean Heuristic (3pts): the distance between two nodes, n1 and n2, on the plane is given by:

  • The Manhattan Heuristic (2pts): the distance between two nodes n1 and n2 on the plane is given by:

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:

  • Alice and Bob start at an initial random location.
  • Bob is moving to a random adjacent point on the map every 2 seconds.
  • Every 2 seconds, Bob's phone transmits its GPS position to Alice (just before moving). This allows Alice to look for a path leading to Bob.
  • Every second, Alice can move to an adjacent point on the map.
  • The scenario stops when Alice finds Bob.
Some additional points:
  • You will need to make use of Threads and synchronization primitives.
  • Aim for as much reuse of your previous code as possible.
  • Output to the console the various actions taken by Alice and Bob throughout the simulation.



Deliverables for Homework #2

To 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/sweng2010-candea).

  • You must place your answers in an SVNAccount/trunk/assignment2/answers.txt file.
  • You must provide your Java source files in the SVNAccount/trunk/assignment2 folder, including the sources of the test classes. Your code should successfully compile on the BC machines, by running "javac assignment2/epfl/sweng/graph/*.java". If your files do not compile, you will lose all of the points for the code writing exercises that are affected by the compilation errors.
  • You must write how much time (in hours) you spent solving each exercise in an SVNAccount/trunk/assignment2/timeSpent.txt file.

Frequently Asked Questions

Q: 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 extra-careful 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.

Therefore, not only *can* you deny incorrect use of your graph, but you should (or must!).

Furthermore, you should not see this as "losing genericity", but rather as protecting yourself against incorrect use (by someone else - or even by you) of your graph. As you were told in the lectures, you should never assume that people using your code will use it correctly.

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!

The short answer is: "No, you are not required to account for cases where a mutable object is modified after being added to your graph".

There are ways to protect against this, but to my knowledge there is no simple solution.

For this homework, we choose to take a similar approach to that taken by the designers of java.util.Set, where is it mentioned that "Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set."

However, please note that you are still required to enforce uniqueness of graph nodes under immutability.

***

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) {
    return null;
}