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.

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 randomWalk$($Graph 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.

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 verticesByInDegree$($Graph g$)$

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

Test these functions in a separate file $($e$.$g$.,$ following RelationshipsTest from class$),$ using a graph with the following directed edges:

$\{$A rarr B$,$A rarr C$,$A rarr D$,$A rarr E$,$B rarr A$,$B rarr C$,$C rarr A$,$C rarr B$,$C rarr D$,$E rarr B$,$E rarr 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.

GraphLib.java

public class GraphLib $\{/***$ Takes a random walk from a vertex, up to a given number of steps $*$ So a $0-$step path only includes start, while a $1-$step path includes start and one of its out$-$neighbors, $*$ and a $2-$step path includes start, an out$-$neighbor, and one of the out$-$neighbor's out$-$neighbors $*$ Stops earlier if no step can be taken $($i$.$e$.,$ reach a vertex with no out$-$edge$)*$ @param g graph to walk on $*$ @param start initial vertex $($assumed to be in graph$)*$ @param steps max number of steps $*$ @return a list of vertices starting with start, each with an edge to the sequentially next in the list; $*$ null if start isn't in graph $*/$ public static List randomWalk$($Graph g$,$ V start, int steps$)\{//$ TODO: your code here $\}/***$ Orders vertices in decreasing order by their in$-$degree $*$ @param g graph $*$ @return list of vertices sorted by in$-$degree, decreasing $($i$.$e$.,$ largest at index $0)*/$ public static List verticesByInDegree$($Graph g$)\{//$ TODO: your code here $\}\}$