SA-9

Exercises

Let's provide some more functionality for our Graph interface, in a library of graph analysis methods. These will be static methods in the GraphLib class (as in Math.random), and will be generic with respect to the type of vertices and edges in a graph. Here's a scaffold: GraphLib.java.

  1. A "random walk" repeatedly moves from the current node to a randomly selected neighbor. In the example graph listed below, when starting from A it might go to B and then back to A and then to C and then to B. Or it might go from A to E to B to C. Or it might go from A to D and get stuck. Implement a method that takes a graph, a start vertex, and desired number of steps and returns one such random walk. 
    List<V> randomWalk(Graph<V,E> g, V start, int steps)
    The path is just a list of vertices. If the walk reaches a vertex with no out-edge, it stops short. Else it takes steps steps, so the list is of length steps+1.

    Implementation note: the neighbors are stored in an Iterable, which means you can write a for-each loop over them. You can also manually iterate, by calling the method iterator to get a new iterator, and repeatedly invoking next on it to get the next item.

  2. Recall that the "in-degree" of a node is the number of incoming edges. Write a method to return a list of the vertices in a graph, sorted in decreasing order of in-degree (i.e., largest first). 
    List<V> verticesByInDegree(Graph<V,E> g)

    Implementation note: List.sort will do the work for you; pass it an appropriate comparator.

  3. Test these functions in a separate file (e.g., following RelationshipsTest from class), using a graph with the following directed edges: 
    { A->B, A->C, A->D, A->E, B->A, B->C, C->A, C->B, C->D, E->B, E->C }
    For this assignment, it doesn't matter what labels you put on the edges. Try multiple random walks of the same length from one vertex, and try varying the length and the starting vertex. You can also sort the vertices by out-degree to see who is most popular (but you can submit your code based on sorting on in-degree).

Submission Instructions

Turn in your java files for the graph library and tests, and the output from your testing.