CompSci-61B Lab 9b
Graphs

A node in graphs (and digraphs) is called "vertex" and a link is called an "edge". In linked lists, nodes contain additional information besides an entry value -- they contain links to adjacent nodes. In graphs, vertices also contain additional information, but it is to support traveral. In linked lists, the links are stored inside the nodes, plus there are separate head, tail, and current links. In graphs, since there are so many link possibilities, the edges are stored in separate data structures.

Two popular ways to represent edges are (1) adjacency matrices (which we will exercises in this lab assignment) and (2) adjacency lists. Adjacency matrices are like 2D arrays with a row and column for each vertex, and a mark in the matrix to indicate a connection or a from-to relationship between 2 vertices. (For graphs, the matrix can be triangular, since there are no from-to relationships.) An adjacency list is an array of lists, one for each vertex, containing references to all of its adjacent vertices. (Applied to graphs, this method require duplication of links.)

In this lab assignment, we'll develop a graph class to solve a shortest route problem for a roadmap, the data for which is stored in a text file of city names and distances between adjacent cities. The class will not be generic. Not all Java solutions have to be written for generic use, and this one is written a specific use. We will use the java.util.Map interface and the java.util.HashMap class for the adjacency matrix. We'll also make extensive use of the java.util.Queue interface, the java.util.List interface, and the java.util.LinkedList class, and the java.util.Stack class, and java.util.PriorityQueue class.

This assignment is worth 40 points, and consists of 1 exercise. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab9b.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.

• The class should have these private inner classes:
  1. private class Edge, with two strings for the "from" and "to" city names, and an integer for the mileage between the cities. Edge objects will be stored in a hash table, so you will need to override equals(Object) and hashCode(). Equality is to be based on matching both city names, and does not involve the mileage. Share ideas with others about how to do the hash code.
  2. private class Vertex, with a city name as its key data member. To support traversal, also include these data members: (1) a boolean to track if the vertex was visited, (2) a link to a previous Vertex, and (3) an int to to store the mileage to this vertex from some origin through some route. Include a method to reset all traversal-related data members to their defaults (zeros, nulls, and falses). Override equals(Object) and base it on the matching city name only.
  3. private class VertexTemp, so support the cheapest route algorithm, with (1) a Vertex reference, (2) a link to a previous Vertex, and (3) an int to to store the mileage to this vertex from some origin through some route. Implement Comparable<VertexTemp>, and write compareTo(VertexTemp v) based on mileage only -- this is so that VertexTemp objects can be stored in a priority queue. (This is necessary because the same Vertex object may be used simultaneously in multiple VertexTemps.)
• The class should have these private data members:
  1. private List<Vertex> vertices, and create any array-based list or linked list for it. Use it to store the names of all the cities in the road map.
  2. private Map<Edge, Edge> adjacencyMatrix, and create a HashMap for it. This is the adjacency matrix. The first Edge is for comparing matching keys, and does not need to set the mileage. The second Edge is for complete objects with mileage. Use the matrix to look up whether an edge exists between any two cities, and if so, get the Edge object with the mileage.
• The class should extend and implement nothing. The methods should be as follows:
  1. public ShortestRoute(String filename), which should read cities and mileages from a text file of comma-separated-value format, with the two cities and the mileage between. Click here for a sample input file that you can use. Fill the list of cities and the adjacency matrix as you read the file. The map is bi-directional, so each pair of cities should produce two entries in the adjacency matrix, and the first time that a city name appears, a vertex should be added to the list of vertices. HINT: create a new Vertex object for each city name that you read, and use something like:if (!vertexes.contains(vertex)) vertexes.add(vertex); to add it to the list if it is not already there.
  2. public Queue<String> getBreadthFirstTraversal(String startCity), returning a queue of the city names in the traveral. Follow the algorighm in 30.12 of Carrano.
  3. public Queue<String> getDepthFirstTraversal(String startCity), returning a queue of the city names in the traveral. Once the breadth-first method is working, this one is a simple copy/paste/markup of it. Follow the algorighm in 30.13 of Carrano.
  4. public int getShortestRoute(String startCity, String endCity, Stack<String> outputPath), returning the least #of edges between 2 cities. A stack is to be created in main before a call to this method, and the method fills the stack. Pop values off the stack to get the route -- do not iterate! Follow the algorighm in 30.19 of Carrano.
  5. public int getCheapestRoute(String startCity, String endCity, Stack<String> outputPath), returning the least mileage between 2 cities. A stack is to be created in main before a call to this method, and the method fills the stack. Pop values off the stack to get the route -- do not iterate! Follow the algorighm in 30.24 of Carrano.
  Include no other public methods -- no iterators, not even a default constructor.

Test the methods -- not all will be used in the final version of the program. Make sure that the methods can be called more than once and in any order. Follow the algorithms of chapter 30 in Carrano, and build the methids in the order of their appearance in the list above, starting with the 1-parameter constructor.

MAIN
Here is the main for this application:

  public static void main(String[] argv) throws Exception
  {
    BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));   

    ShortestRoute s = new ShortestRoute("cities.txt");

    // print al city names
    System.out.print("\nEnter a city name to begin the listing of city names: ");
    String fromCity = cin.readLine();
    for (String city: s.getBreadthFirstTraversal("San Francisco"))
      System.out.print(city + ' ');
    System.out.println();

    while (true)
    {
      System.out.print("\nEnter the source city [blank to exit]: ");
      String fromCity = cin.readLine();
      if (fromCity.length() == 0) break;

      System.out.print("Enter the destination city [blank to exit]: ");
      String toCity = cin.readLine();
      if (toCity.length() == 0) break;

      Stack<String> r = new Stack(){};
      System.out.println("Total miles: " + s.getCheapestRoute(fromCity, toCity, r));  
      while (!r.empty()) System.out.println(" " + r.pop() + ' ');
  } }

Each of the 4 traversal methods are worth -5 points if omitted. If you omit getBreadthFirstTraversal or getCheapestRoute which are used in the supplied main method, modify main to use the method(s) that you do have.

CONVERTING CITY NAMES TO VERTEX OBJECT REFERENCES
This should help to get you started:

  public ... get...(String startName, ...)
  {
    Vertex startVertex = null;

    for (Vertex v: vertexes)
    {
      v.reset();
      if (v.name.equalsIgnoreCase(startName)) startVertex = v;
      ...
    }
    if (startVertex == null || ...) return ...

    // now use the vertex(es) in the algorithm instead of the string names
    ...

    Edge key = new Edge(); // for key comparing only
    key.firstName = frontVertex.name;
    for (Vertex neighbor: vertexes)
    {
      key.secondName = neighbor.name;
      Edge edge = adjacencyTable.get(key);
      if (edge == null) continue; // no matching key
      ...if you get to here, "neighbor" is a neighbor...

[ Home | Contact Prof. Burns ]