CS 10: Winter 2016

Short Assignment 10
Due: Monday, February 15

Assignment

This assignment will help you learn about graphs, and will allow you to develop a useful class for Lab 5.

Lab 5 will ask you to write a program to play the Kevin Bacon game. As part of the solution you will construct an undirected graph with actors as vertices and edges between pairs of actors who appeared in a movie together. These edges are labeled by the movie name.

You will also construct a shortest-path tree, which can be represented as a directed graph. Edges go from children to their parents and Kevin Bacon is at the root of the tree. You then find an actor in the graph and follow a path to the root, listing actors (vertices are labeled with actor names) and movies (edges are labeled with movie names) until you get to the root. To solve this you will use the book's code, which is available in net.datastructures.zip. Unzip this folder and drag it to the "src" icon in your Eclipse project.

The graph class AdjacencyMapGraph provided by the book will be the basis for representing both the actor-movie graph (undirected) and the shortest-path tree (directed). However, it has a drawback: the only way to find a particular actor's vertex is to iterate through a linked list of vertices. When there are thousands of actors in the graph this is slow!

To solve this problem you will write the class NamedAdjacencyMapGraph.java. The NamedAdjacencyMapGraph class extends the AdjacencyMapGraph class, and it also maintains a map from vertex names (or whatever information you store with a vertex) to the Vertex objects. In addition to the methods of AdjacencyMapGraph, it provides the following:

Vertex<V> getVertex(V name) returns the Vertex object corresponding to the name in the parameter, or null if there is no vertex with that name.
boolean vertexInGraph(V name) returns a boolean indicating whether the graph contains a vertex with the name in the parameter.
Edge<E> insertEdge(V uName, V vName, E element) throws IllegalArgumentException inserts an edge whose vertices have the names uName and vName into the graph. Like the insertEdge method of AdjacencyMapGraph, it throws an IllegalArgumentException if there is already an edge (u, v) in the graph.
Edge<E> getEdge(V uName, V vName) throws IllegalArgumentException returns the edge whose endpoints are named by uName and vName, or null if the graph contains no such edge.

It must also supply a constructor, override insertVertex(V element) to put the vertex name and the corresponding vertex into the map, and override removeVertex(Vertex<V> v) to remove the vertex name and corresponding vertex from the map.

In an AdjacencyMapGraph it is valid to have multiple vertices with the same name. However, in a NamedAdjacencyMapGraph this would cause problems, because you would not know which vertex to associate with a given name. Therefore your version of insertVertex(V element) should check to make sure that the name is not already in the map, and throw an IllegalArgumentException if it is.

None of these seven methods should be more than a few lines of code, and most have single-line bodies. If yours are longer you are probably doing something wrong and should get help.

You should test your program on the following main method:

// A testing method public static void main(String [] args) { boolean isDirected = false; NamedAdjacencyMapGraph<String, String> baconGraph; do { baconGraph = new NamedAdjacencyMapGraph<String, String>(isDirected); System.out.println("\nisDirected = " + isDirected); baconGraph.insertVertex("Kevin Bacon"); baconGraph.insertVertex("Laura Linney"); baconGraph.insertVertex("Tom Hanks"); baconGraph.insertVertex("Liam Neeson"); baconGraph.insertEdge("Laura Linney","Kevin Bacon", "Mystic River"); baconGraph.insertEdge("Liam Neeson", "Laura Linney", "Kinsey"); baconGraph.insertEdge( "Tom Hanks", "Kevin Bacon", "Apollo 13"); System.out.println("\nvertexInGraph for Laura Linney = " + baconGraph.vertexInGraph("Laura Linney")); System.out.println("\nvertexInGraph for L. Linney = " + baconGraph.vertexInGraph("L. Linney")); System.out.println("\ngetEdge between Laura Linney and Tom Hanks = " + baconGraph.getEdge("Laura Linney", "Tom Hanks")); System.out.println("\ngetEdge between Laura Linney and Kevin Bacon = " + baconGraph.getEdge("Laura Linney", "Kevin Bacon").getElement()); Edge<String> e = baconGraph.getEdge("Kevin Bacon", "Laura Linney"); if(e == null) System.out.println("\nNo edge between Kevin Bacon and Laura Linney"); else System.out.println("\ngetEdge between between Kevin Bacon and Laura Linney = " + e.getElement()); System.out.println("\nInDegree of Laura Linney = " + baconGraph.inDegree(baconGraph.getVertex("Laura Linney"))); System.out.println("\nOutDegree of Laura Linney = " + baconGraph.outDegree(baconGraph.getVertex("Laura Linney"))); System.out.println("\nEdges into to Laura Linney:"); for(Edge<String> edge : baconGraph.incomingEdges(baconGraph.getVertex("Laura Linney"))) System.out.println(edge.getElement()); System.out.println("\nEdges out of to Laura Linney:"); for(Edge<String> edge : baconGraph.outgoingEdges(baconGraph.getVertex("Laura Linney"))) System.out.println(edge.getElement()); System.out.println("\nThe entire graph:"); for(Vertex<String> vertex : baconGraph.vertices()) { System.out.println("\nEdges into " + vertex.getElement() + ":"); for(Edge<String> edge : baconGraph.incomingEdges(vertex)) System.out.println(edge.getElement()); System.out.println("\nEdges out of " + vertex.getElement() + ":"); for(Edge<String> edge : baconGraph.outgoingEdges(vertex)) System.out.println(edge.getElement()); } baconGraph.removeVertex(baconGraph.getVertex("Kevin Bacon")); System.out.println("\nCalled removeVertex for Kevin Bacon"); System.out.println("getVertex for Kevin Bacon returns: " + baconGraph.getVertex("Kevin Bacon")); System.out.println("\nThe entire graph after Kevin Bacon removed:"); for(Vertex<String> vertex : baconGraph.vertices()) { System.out.println("\nEdges into " + vertex.getElement() + ":"); for(Edge<String> edge : baconGraph.incomingEdges(vertex)) System.out.println(edge.getElement()); System.out.println("\nEdges out of " + vertex.getElement() + ":"); for(Edge<String> edge : baconGraph.outgoingEdges(vertex)) System.out.println(edge.getElement()); } isDirected = !isDirected; } while(isDirected); try{ baconGraph.insertVertex("Laura Linney"); } catch(IllegalArgumentException ex) { System.out.println("\nCaught exception for duplicate vertex name: " + ex.getMessage()); } }

Extra Credit

This extra credit does not involve programming.

Suppose that you have a directed graph represented as an adjacency matrix. There are n² entries in the matrix. There is a theorem that says that, for any monotone property of a graph, determining whether a graph represented as an adjacency matrix has that property takes Ω(n²) time. (A monotone property is false on the empty graph, true on the complete graph, and for any graph for which the property is true, it remains true if you add more edges.) So most of the time algorithms on graphs represented by adjacency matricies take Ω(n²) time.

However, here is a non-monotone property that can be tested in Θ(n) time. Determine if a directed graph has a sink. A sink is a vertex that has no outgoing edges and has an incoming edge from every other vertex in the graph. Describe an algorithm for finding a sink or determining that the graph does not have a sink in Θ(n) time.

Canvas Submission

Submit electronically via Canvas the following files:

your NamedAdjacencyMapGraph.java class,
a screenshot or file containing your output obtained by running the main method given above, and
your solution to the extra-credit problem, if you do it.

Short Assignment 10Due: Monday, February 15

Assignment

Extra Credit

Canvas Submission

Short Assignment 10
Due: Monday, February 15