SA-10, due Nov 6

Assignment

This assignment will help you learn about graphs and the Decorator design pattern.

PS-5 asks you to write a program to play the Kevin Bacon game. As part of the solution you will 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.zip. Unzip this folder and drag it to the "src" icon in your Eclipse project.

Unfortunately, the graph class AdjacencyListGraph provided by the book has two drawbacks for representing such a tree: (1) it is undirected, and (2) the only way to find a particular actor's vertex is to iterate through a linked list of vertices.

The second problem is solved by the class AdjacencyListGraphMap, which replaces the linked list of vertices by a map from vertex identifiers to vertices. The first problem you will solve in this short assignment.

Write a directed graph class DirectedAdjListMap that extends AdjacencyListGraphMap. It should implement the two methods that the book requires for a directed graph (p. 626), plus some useful additional methods. In particular, you will implement the following methods:

/** * Is the given edge directed? * @param e the edge to test * @return true if e is directed */ public boolean isDirected(Edge<E> e){ /** * Insert a directed edge into this graph * @param v - the source vertex * @param w - the destination vertex * @param label - the edge label * @return the new edge */ public Edge<E> insertDirectedEdge(Vertex<V> v, Vertex<V> w, E label) { /** * Get all incident edges with v as destination * @param v the destination vertex * @return collection of incident edges with v as destination */ public Iterable<Edge<E>> incidentEdgesIn(Vertex<V> v) { /** * Get all incident edges with v as source * @param v the source vertex * @return collection of incident edges with v as source */ public Iterable<Edge<E>> incidentEdgesOut(Vertex<V> v) { /** * Get the in degree of a vertex * @param v the vertex * @return the in degree of v */ public int inDegree(Vertex<V> v) { /** * Get the out degree of a vertex * @param v the vertex * @return the out degree of v */ public int outDegree(Vertex<V> v) {

You should also implement overloaded versions of the last five methods that take a vertex identifier of type V instead of a vertex of type Vertex<V>. Each of these should have a one-line body that calls a version of a method that has one or more Vertex<V> parameters instead of a V parameters. Thus you will have a total of eleven methods in your class.

Your graph will actually be a mixed graph. Some edges will be labeled as directed. They only go from source to destination. They are created by a call to insertDirectedEdge. However, your class inherits a method insertEdge that inserts a undirected edge. Such an edge should be considered equivalent to having two directed edges, one in each direction. Therefore it is treated as both an incoming edge and an outgoing edge for each of its incident vertices, and it should contribute to both the in-degree and out-degree of an incident vertex.

Note that your new class will extend the AdjacencyListGraph, and thus cannot change how edges are represented within that class. How can we tell which edges are directed? We use the Decorator pattern and the fact that MyEdge implements the DecorablePosition inteface (via extending MyPosition). That means that there is a small map associated with each edge, and that map can be used to save additional properties for that edge. In particular you can create a property object EDGE_TYPE and a value object DIRECTED and call put(EDGE_TYPE, DIRECTED) on an edge that you wish to mark as directed. You can then use get(EDGE_TYPE) to determine if an edge is directed. (You could also have an object UNDIRECTED, but it requires less code to simply assume that an edge that is not marked DIRECTED is undirected.) See the DFS code on p. 618 for an example of how decorations can be used to save properties.

You should test your program on the following main method:

public static void main(String [] args) { DirectedAdjListMap<String, String> baconGraph = new DirectedAdjListMap<String, String>(); baconGraph.insertVertex("Kevin Bacon"); baconGraph.insertVertex("Laura Linney"); baconGraph.insertVertex("Tom Hanks"); baconGraph.insertVertex("Liam Neeson"); baconGraph.insertDirectedEdge("Laura Linney","Kevin Bacon", "Mystic River"); baconGraph.insertEdge("Liam Neeson", "Laura Linney", "Kinsey"); baconGraph.insertDirectedEdge( "Tom Hanks", "Kevin Bacon", "Apollo 13"); System.out.println("\nDegree of Laura Linney = " + baconGraph.degree("Laura Linney")); System.out.println("\nInDegree of Laura Linney = " + baconGraph.inDegree("Laura Linney")); System.out.println("\nOutDegree of Laura Linney = " + baconGraph.outDegree("Laura Linney")); System.out.println("\nEdges into to Laura Linney:"); for(Edge<String> edge : baconGraph.incidentEdgesIn("Laura Linney")) System.out.println(edge); System.out.println("\nEdges out of to Laura Linney:"); for(Edge<String> edge : baconGraph.incidentEdgesOut("Laura Linney")) System.out.println(edge); System.out.println("The entire graph:"); for(Vertex<String> vertex : baconGraph.vertices()) { System.out.println("\nEdges adjacent to " + vertex + ":"); for(Edge<String> edge : baconGraph.incidentEdges(vertex)) System.out.println(edge); System.out.println("\nEdges into " + vertex + ":"); for(Edge<String> edge : baconGraph.incidentEdgesIn(vertex)) System.out.println(edge); System.out.println("\nEdges out of " + vertex + ":"); for(Edge<String> edge : baconGraph.incidentEdgesOut(vertex)) System.out.println(edge); } System.out.println("\nRenaming Laura Linney to L. Linney"); baconGraph.replace("Laura Linney", "L. Linney"); System.out.println("\nGetting Laura Linney: " + baconGraph.getVertex("Laura Linney")); for(Vertex<String> vertex : baconGraph.vertices()) { System.out.println("\nEdges adjacent to " + vertex + ":"); for(Edge<String> edge : baconGraph.incidentEdges(vertex)) System.out.println(edge); } System.out.println("\nRemoving L. Linney"); baconGraph.removeVertex("L. Linney"); System.out.println("\nThe entire graph:"); for(Vertex<String> vertex : baconGraph.vertices()) { System.out.println("\nEdges adjacent to " + vertex + ":"); for(Edge<String> edge : baconGraph.incidentEdges(vertex)) System.out.println(edge); System.out.println("\nEdges into " + vertex + ":"); for(Edge<String> edge : baconGraph.incidentEdgesIn(vertex)) System.out.println(edge); System.out.println("\nEdges out of " + vertex + ":"); for(Edge<String> edge : baconGraph.incidentEdgesOut(vertex)) System.out.println(edge); } }

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 problem that can be solved 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.

Blackboard Submission

Submit electronically via Blackboard the zip file of a folder that contains: (1) your DirectedAdjListMap.java class, (2) a screenshot of your output for the test your code by running the main method of DirectedAdjListMap.java, and (3) your solution to the extra-credit problem, if you happened to do it.