Discussion 11: 6 Degrees of Song Collaborations

In lecture, we discussed the Breadth-First Search (BFS) and Depth-First Search (DFS) graph traversal algorithms. These procedures allow us to explore the structure of graphs in different ways and locate paths between vertices. Recall that BFS traverses the vertices by level away from some designated source vertex. In this discussion, you’ll use BFS to find the vertices a certain distance away from the source.

Learning Outcomes

  1. Identify substructures in graphs such as neighborhoods, paths, and cycles both visually and programmatically.
  2. Perform BFS and DFS traversals of a given graph by hand and in code.
  3. Visualize the state of a graph traversal at a given point of its execution, describing each vertex as either undiscovered, discovered, visited, and/or settled.
Exercise 1: k Degrees of Singing
You may be aware of the concept of "six degrees of separation", which posits that any two people on Earth are six or fewer acquaintance links apart. This same idea has been popularized in specialized settings as well. For example, one can connect Hollywood actors to their co-stars to form a graph, leading to the popular Six Degrees of Kevin Bacon game. One can connect research mathematicians to their co-authors, leading to the popular (in different circles) concept of Erdős numbers. In this discussion, we'll consider vocal artists' collaborations; two artists are connected if they sang together on a song. The graph is visualized at the top of the next page. For the sake of simplicity, we consider only a small subset of that true graph (which would contain millions of vertices and edges).

Vertices in this graph represent artists/singers. If an edge exists between two singers, they have sung together (collaborated) on a song. Note: This counts Billie Eilish singing on "Never Felt So Alone" by Labrinth, though it is uncredited.

In lecture, we discuss graphs with directed edges. However, this graph is undirected. We can think of each connection in this picture as a pair of directed edges, such as both (SZA, Khalid) and (Khalid, SZA).
(a)
Identify two cycles in this graph.
(b)
Who belongs to Billie Eilish's neighborhood in the graph? What do we know about these individuals?
(c)
Which vertices are two degrees of separation away from Billie Eilish on a shortest path?
Exercise 2: Applying BFS
You may realize that Breadth-first search (BFS), where we search by levels (or a certain breadth) away from the source vertex, may be well-suited to this task of finding "degrees of separation". For more information on BFS, refer to Lecture 22.

(a)
Beginning with Billie Eilish, simulate BFS by hand to find Taylor Swift. Keep track of the vertex that is visited in each iteration, the newly discovered vertices, and the queue contents at the end of that iteration. Assume that a vertex's neighbors are discovered in alphabetical order. Track your progress using the table below. The first two rows of the table below have been filled out for you. Once you discover Taylor Swift, report the degrees of separation you find.

Step Visiting Newly discovered artists Queue [front, ... , back]
0 --- Billie Eilish [Billie Eilish]
1 Billie Eilish Charli XCX, Justin Bieber, Khalid, Labrinth [Charli XCX, Justin Bieber, Khalid, Labrinth]
2
3
4
5
6
7
8
Exercise 3: depthKVertices()
Complete the definition of the following depthKVertices() method according to its specifications. Note that:
  • The code makes use of the Vertex and Edge ADTs from Lecture 21. Think about which methods from these interfaces may be useful for your implementation.
  • In this code, we can leverage the fact that the LinkedList class implements both the List and Queue interfaces to use the same object as both the BFS queue and the method return value. Using your answer to the previous exercise, can you identify when the state of the queue will be exactly our desired return value?
  • Java's Queue uses slightly different method names than we introduced in lecture. Their enqueue() method is called add(), and their dequeue() method is called remove().

DepthKVerticesDemo.java