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.
- 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.
The path is just a list of vertices. If the walk reaches a vertex with no out-edge, it stops short. Else it takesList<V> randomWalk(Graph<V,E> g, V start, int steps)
steps
steps, so the list is of lengthsteps+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 methoditerator
to get a new iterator, and repeatedly invokingnext
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<V> verticesByInDegree(Graph<V,E> 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:
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).{ A->B, A->C, A->D, A->E, B->A, B->C, C->A, C->B, C->D, E->B, E->C }
Submission Instructions
Turn in your java files for the graph library and tests, and the output from your testing.