Graphs

A graph is a data structure that allows you to store two different kinds of objects: vertices and edges. Typically (but not always), we think of vertices as the objects that are actually being stored and edges define the connections between them. For example, one could imagine the graph of 'friend connections' of the Facebook world, where individual accounts are represented by vertices and two vertices are connected by an edge if the associated accounts are friends. Such a graph is called undirected since these edges have no inherent direction.

Another example could be the graph of instagram follows: in this case, since following an account does not necessarily mean they will follow you back, such a graph is considered 'directed' since the is an implied direction associated with an edge: perhaps an edge from some vertex u to v would denote that the account associated with vertex u follows the account associated with vertex v.

As a change of pace, in this project you won't have to build the Graph data structure yourself, and can instead download this file. In order for it to work, you'll also need this HashSet implementation. This HashSet works more or less like Java's HashSet, except that it implements the Java Deque interface, so it has convenient methods like addFirst, addLast, getFirst, getLast, etc. You'll find that this structure can be quite useful throughout this project, so feel free to use it.

All documentation for the Graph class can be found here. All documentation for the HashSet class can be found here.

Testing

As always, as you are coding up this project write tests for each class you create exercising the public methods implemented in this class. For the remaining projects (including this one), these tests should follow the structure of the tests given to you earlier this semester and in the lectures given by Naser.

Tasks

The overall goal of this project is to determine the fastest way to visit the capitol city of every state of the contiguous United States (so all states other than Alaska and Hawaii). We'll achieve this by:

  1. building a graph representation of all the cities
  2. attempting a brute force search of all possible paths, but observing that this simply takes too long
  3. using a minimum spanning tree to get an approximate solution.
This lab will start us out by practicing some graph algorithms.

  1. Setup

    Make a new folder for this week's project. Include the files downloaded above.

  2. Create a GraphAlgorithms class

    All methods in this class will be static: the role of this class is to make common useful algorithms to use in conjunction with the given Graph class.

  3. Implement Shortest Paths

    In the GraphAlgorithms class, create a method for determining the shortest distance between a start vertex and all other reachable vertices of the graph.

    public static <V, E> HashMap<Graph.Vertex<V, E>, Double> shortestPaths(Graph<V, E> g, Graph.Vertex<V, E> source): the HashMap m returned by this must guarantee that m.get(v) is the length of the shortest distance path from the vertex source to the vertex v. Any vertices in g that are unreachable from source should have infinite distance. The runtime of this method should be linear with respect to the number of vertices in g.

  4. Create a method for reading in data for graphs

    In the GraphAlgorithms class, create a method for reading a .csv file and making a graph out of it. In particular, you can expect the .csv file to follow the format of this file.

    public static Graph<String, Object> readData(String filename): this reads in the data of a weighted graph stored in the given file. You can assume that the file follows the format of the file linked above. You can choose whether to use the distance or the time for the weights of the edges.

  5. Create a method for finding all Hamiltonian Cycles

    Eventually, we'll want to find the minimal cycle that visits all the cities in the linked .csv file and finishes at the starting location. The first step in a brute-force approach to that is calculating all the possible Hamiltonian Cycles: that is, cycles that visit every vertex exactly one and finish where they start. There are many ways to do this, but I recommend recursion.

    public <V, E> Collection<List<Graph.Edge<V, E>>> allHamCycles(Graph<V, E> g, Vertex<V, E> start): this method returns a collection of lists of edges, where each list of edges is a path that visits every vertex in the given graph exactly once, except for the specified start vertex which is both the first and the last vertex to be visited. You'll notice that the return type is a Collection of Lists of Edges: for your program to know what this means, you'll need to import java.util.List and java.util.Collection. These are both just standard interfaces, which most datastructures we've talked about so far this semester implement. The takeaway is that it's up to you to decide how you want to organize your outputs here so that things are relatively optimized.

  6. Observe the futility of your allHamCycles method on the given capitols graph

    Try and run the allHamCycles method on the capitols data linked above. You should find that it has no hope of finishing anytime soon: this is because the runtime of this algorithm is at least O(n!), so it's quite impractical for graphs with more than even 10 vertices.

CHECK-IN

The due-date for this lab is Sunday 12/4.

Once you have completed the this lab, get started on the project.