Discussion 11: 6 Degrees of Song Collaborations

Solutions

Exercise 1:

(a)

Identify two cycles in this graph.

There are many different answers, but the smallest include:

Taylor Swift \(\rightarrow\) Kendrick \(\rightarrow\) Future \(\rightarrow\) Taylor Swift

The Weeknd \(\rightarrow\) Kendrick \(\rightarrow\) Future \(\rightarrow\) The Weeknd

(b)

Who belongs to Billie Eilish’s neighborhood in the graph? What do we know about these individuals?

Charli XCX, Khalid, Labrinth, Justin Bieber. These are the four artists who sang with Billie Eilish on a song.

(c)

Which vertices are two degrees of separation away from Billie Eilish on a shortest path? Hint: there are 6 possible answers

Lorde, Troye Sivan, SZA, The Weeknd, Halsey, Ed Sheeran

Exercise 2: BFS-by-hand

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	Charli XCX	Lorde, Troye Sivan	[Justin Bieber, Khalid, Labrinth, Lorde, Troye Sivan]
3	Justin Bieber	Ed Sheeran, Halsey	[Khalid, Labrinth, Lorde, Troye Sivan, Ed Sheeran, Halsey]
4	Khalid	SZA	[Labrinth, Lorde, Troye Sivan, Ed Sheeran, Halsey, SZA]
5	Labrinth	The Weeknd	[Lorde, Troye Sivan, Ed Sheeran, Halsey, SZA, The Weeknd]
6	Lorde	(No new additions)	[Troye Sivan, Ed Sheeran, Halsey, SZA, The Weeknd]
7	Troye Sivan	(No new additions)	[Ed Sheeran, Halsey, SZA, The Weeknd]
8	Ed Sheeran	Taylor Swift	[Halsey, SZA, The Weeknd, Taylor Swift]

Taylor Swift is separated from Billie Eilish by 3 degrees via the shortest path: Billie Eilish \(\rightarrow\) Justin Bieber \(\rightarrow\) Ed Sheeran \(\rightarrow\) Taylor Swift

Exercise 3: depthKVertices()

Key insight: The queue contains the nodes at level k right before the first node of level k is visited.

 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
30


/** 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) {
  assert k >= 0;
  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;

  while (!frontier.isEmpty() && currentLevel < k) {
      int levelSize = frontier.size();  // visit only nodes at current level
      for (int i = 0; i < levelSize; i++) {
          V v = frontier.remove();
          for (E e : v.outgoingEdges()) { // iterate over neighbors
              V neighbor = e.head();
              if (!discovered.contains(neighbor)) { // discovered new vertex
                  discovered.add(neighbor);
                  frontier.add(neighbor);
              }
          }
      }
      currentLevel++; // ready to visit nodes in next level
  }
  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
30


/** 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) {
  assert k >= 0;
  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;

  while (!frontier.isEmpty() && currentLevel < k) {
      int levelSize = frontier.size();  // visit only nodes at current level
      for (int i = 0; i < levelSize; i++) {
          V v = frontier.remove();
          for (E e : v.outgoingEdges()) { // iterate over neighbors
              V neighbor = e.head();
              if (!discovered.contains(neighbor)) { // discovered new vertex
                  discovered.add(neighbor);
                  frontier.add(neighbor);
              }
          }
      }
      currentLevel++; // ready to visit nodes in next level
  }
  return ret;
}