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.
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:
This extra credit does not involve programming.
Suppose that you have a directed graph represented as an adjacency matrix. There are n2 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 Ω(n2) 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 Ω(n2) 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.
Submit electronically via Canvas the following files:
NamedAdjacencyMapGraph.java
class,main
method given above, and