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

Identify substructures in graphs such as neighborhoods, paths, and cycles both visually and programmatically.
Perform BFS and DFS traversals of a given graph by hand and in code.
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.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool; it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going, so we can make adjustments in future classes. Your grade in discussion is based on your attendance, active participation, and completion of that day’s activity. More information about the grading and expectations can be found in the syllabus.

Since discussion activities are not graded for correctness, we do not restrict what resources you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from thinking critically to “puzzle” them out.

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. For the sake of simplicity, we have a small subset of that true graph (which would contain millions of vertices and edges).

Understanding the Graph

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).

Exercise 1:

(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? Hint: there are 6 possible answers

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.

Exercise 2: Find Taylor Swift

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 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().

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


/** Finds and returns a (possibly empty) list of all vertices distance 
 * exactly `k` away from the `source` using BFS. Requires that `source` 
 * is a valid, non-`null` vertex in a graph and `k >= 0`. */
public static <V extends Vertex<E>, E extends Edge<V>>  
              List<V> depthKVertices(V source, int k) {
  LinkedList<V> ret = new LinkedList<>(); // to be returned
  Set<V> discovered = new HashSet<>();
  Queue<V> frontier = ret;

  discovered.add(source);
  frontier.add(source);
  int currentLevel = 0;

  // TODO: implement this method based on the specification













  return ret;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


/** Finds and returns a (possibly empty) list of all vertices distance 
 * exactly `k` away from the `source` using BFS. Requires that `source` 
 * is a valid, non-`null` vertex in a graph and `k >= 0`. */
public static <V extends Vertex<E>, E extends Edge<V>>  
              List<V> depthKVertices(V source, int k) {
  LinkedList<V> ret = new LinkedList<>(); // to be returned
  Set<V> discovered = new HashSet<>();
  Queue<V> frontier = ret;

  discovered.add(source);
  frontier.add(source);
  int currentLevel = 0;

  // TODO: implement this method based on the specification













  return ret;
}

If you would like to confirm your implementation, type it up in DepthKVerticesDemo.java in the provided testing code. Its unit test confirms that the method works correctly for the graph visualized above.

Download Testing Code download

Submission

At the end of class, your group’s primary author should create a PDF with your written answers and upload this to the “Discussion 11” Gradescope assignment, tagging all other members of the group onto the submission.