Lab 6: Computing Reachable Cities

In class, we looked at graphs with cities as the core content of the nodes, and we wrote a hasRoute method to determine whether there exists a route from one city to another. For this assignment, we want a different twist on a similar problem: we’d like to gather a list of all the cities that one can get to from a given starting city. In other words, we want to add a method reachableFrom to graphs, as captured by the following (partial) interface:

  interface IGraph {
    ...
    // produce a list of all nodes reachable from given starting node
    LinkedList<Node> reachableFrom (Node from);
  }

For the graph example we’ve been using in lecture, the list of nodes reachable from the node for Providence would contain both Providence and Hartford. The list of nodes reachable from the node for Hartford would just be Hartford.

Concretely, solve the following problems, starting from the initial graph implementation from Tuesday’s lecture:

Add a reachableFrom method to the Graph class.
Include a good set of tests for reachableFrom. Ideally, your tests should not presume a specific order for nodes in the output of reachableFrom.
In a clearly-labeled comment, argue why your reachableFrom method will terminate. A good answer will state an invariant on the code and how that contributes to termination.
Your Graph class could (in theory) capture friend relationships in a social network just as well as it captures routes between cities. For a social network graph, however, the content at each node isn’t just a string, but a user profile. The following class defines a simple user profile:
  class Profile {
    String name;
    String college;
  }
1. Use generics to enable you to check for routes or compute reachable nodes in either social networks or city graphs using the same interface and classes.
2. Write test cases for reachableFrom using each of graphs over cities and social network graphs over profiles (think about a more meaningful name of the reachableFrom method in the context of social networks to help you understand this example.

1 What to turn in

Turn in all .java files for this assignment via Turnin.